《2011年成人高考专升本数学模拟试题.doc》由会员分享，可在线阅读，更多相关《2011年成人高考专升本数学模拟试题.doc（8页珍藏版）》请在金锄头文库上搜索。
1、2012-03-21 21:29 30人阅读 评论(0) 收藏 举报 编译原理要点第一章 编译引论1、编译程序：将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序2、源语言：用来编写源程序的语言（汇编，高级程序设计语言）3、源程序：用源语言写的程序4、目标语言：目标程序描述的语言5、目标程序：源程序经过编译后生成的程序6、宿主语言：编译程序的实现语言7、宿主机：编译程序的运行环境8、分类：解释程序【接受某语言的源程序将其直接翻译成目标代码且执行】；编译程序【接受某语言的源程序将其直接翻译成等价的目标代码，然后执行且允许重复执行】；汇编程序【接受汇编源程序将其直接翻译成等价的极其语言
2、的目标程序，然后执行且允许重复执行】9、编译执行：由编译程序生成一个与源程序等价的目标程序，完全取代源程序【笔译】10、解释执行：不生成目标程序，仅是对源程序逐句解释逐句执行【口译】11、编译程序逻辑结构：词法分析-语法分析-语义分析和中间代码生成-代码优化-目标代码生成（表格管理，出错处理）12、遍：对源程序或源程序的中间形式从头到尾扫描一遍，并做有关的分析加工，生成新的源程序的中间形式或生成目标程序13、编译程序构造要素：源语言，目标语言，编译方法、技术与工具第二章 形式语言自动机理论基础1、语言要素：语法（语言的描述规则），语义（语言的含义）2、元语言：描述另一个语言的语言3、字母表：元
3、素的非空有穷集合，表中的元素称为符号，字母表也称为符号集4、符号串：由字母表中的符号组成的任何有穷序列，符号串长度指符号串x中有m个符号，长度为m5、x是一个符号串，把从x的尾部删去0个或若干个符号之后剩余的部分称为x前缀【后缀相反，不是自身称为真前缀或真后缀】6、从一个符号串中删去它的一个前缀或一个后缀之后的剩余部分称为子串7、文法是一个四元组G=(Vn,Vt,S,P) Vn非空有限的非终结符号集，Vt非空有限终结符号集，S公理，P有限产生式集8、符号串的正闭包A+=A1UA2U.UAn；A的自反闭包为A*=A+UE9、语言：给定一部文法G，从G的开始符号S出发，反复使用产生式对非终结符进行
4、替换，最后得到的终结符号串的全体10、直接推导，直接推导序列，最左推导（总是对句型中最左边的非终结符进行替换），最右推导，句型（包含非终结符），句子（只含终结符），规范推导（最右推导），规范推导得到规范句型，规范推导逆序为规范归约；给定一个句子或句型其最左最右推导惟一11、递归文法：其中包括自身；直接递归（直接到自身），间接递归（经过中间到自身），左（右）递归12、语言：推导的句子a属于终结符，S能推导出a；如果L(G1)=L(G2)，则G1，G2文法等价；BNF表示法，扩充的BNF表示法13、语法树是句子结构的图形表示，代表了句子的推导结果，有利于理解句子语法结构层次；一棵语法树包括了一个句
5、型的所有可能的推导过程14、二义文法：对一部文法，如果至少存在一个句子，有两棵不同语法树，称该句子是二义性的，包含二义性的句子的文法称为二义文法。15、0型文法：对文法G中的规则不加任何限制，由图灵机来识别16、1型文法：对产生式限制 aAb-aBb，上下文有关，由线性有界自动机来识别17、2型文法：A-a A属于非终结符，a属于终结符和非终结符自反闭包，上下文无关文法，由非确定的下推自动机来识别18、3型文法：A-aB,或A-a a是终结符，A，B属于非终结符，称文法G为3型文法，3型文法可由确定的有限状态自动机来识别【从0型到3型，产生式越来越严，描述功能越来越弱】19、确定的有限自动机(
6、DFA)：M=(S,E,f,S0,Z)。其中S是状态的有限集合，E是输入字符的有限集合，每个元素是一个输入字符，f状态转换函数，S0是M的惟一初态，Z是M的终态集20、DFA等价表示： DFA形式定义-状态转换图-状态矩阵21、非确定的有限自动机M(NFA M)是一个五元组M=(S,E,f,S0,Z) S0指M的非空初始状态，f状态转换函数，但这里后继状态不唯一；对任何一个NFA M，都存在一个DFA M使L(M)=L(M)22、等价：设DFA M的两个不同状态q1,q2，如果对任意输入字符串w，从q1,q2状态出发，总是同时到达接收状态或拒绝状态之中，称q1,q2等价，如果两个状态不等价，称
7、q1,q2是可区别的23、如果从DFA M的初始状态开始，任何输入序列都不能到达的那些状态称为无关状态；如果DFA M没有无关状态，且没有彼此等价的状态，称DFA M是归约的24、DFA化简实现思想：通过删除无关状态，合并等价状态的归约过程，直到得到归约机，实现方法划分法（核心是寻找且合并等价状态）25、由正规式表示的集合称为正规集，正规式不是集合26、字母表上确定的有限自动机M所接受的语言L(M)是E上的一个正规集，对于每一个正规式，存在一个非确定有限自动机M，使得L(M)=L(r)第三章 词法分析1、作用：扫描的同时根据语言的词法规则识别出具有独立意义的单词，并产生与源程序等价的属性字流。
8、完成词法分析任务的程序称为词法分析程序或词法分析器；编译程序的第一个阶段且是必要阶段，核心任务是扫描识别单词且对识别出的单词给出定性定长的处理2、单词：语言中具有独立意义的最小语法单位；要素【独立的意义，最小的语法单位】3、单词类：关键字，标识符，常量，运算符，界限符4、输入缓冲区：成对且对半互补的输入缓冲区模式，一个缓冲区分为两个半区5、预处理程序：减少内存空间占用，减轻扫描器实质性处理负担；主要任务【滤掉程序中非单词成分，滤掉注释，宏替换，文件包含的嵌入，条件编译的嵌入】6、二级目录表：主表-数据项=状态+分表地址或子程序入口；分表-数据项=当前输入字符+转换状态7、扫描器自动生成器-LE
9、X/FLEX第四章 语法分析1、功能：按照源语言的文法，从源程序串识别出相应的语法范畴，同时进行语法检查；构造：源程序串，源语言的文法G，识别出的语法范畴的表示2、自上而下语法分析是从G的开始符号S出发，通过反复使用产生式大队句型中的非终结符进行替换，逐步推导出源程序串，是一种产生的方法，面向目标的方法。3、自下而上语法分析从输入串开始不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替之，逐步归约到S，是一种辨认的方法，基于目标的方法4、短语：S=aAb,A=p，p是句型apb相对于A的短语，直接短语就是A直接推导出p，直接短语一定是短语5、句柄：一个句型的最左直接短语称为句
10、柄，句柄一定是直接短语且具有最左性6、直接左递归的消除，间接左递归的消除【把间接左递归文法改写成直接左递归文法，用消除直接左递归的方法改写文法】，消除回溯7、LL(1)分析器的逻辑结构：总控程序，分析栈【存放分析过程中的文法符号】，分析表；扫描模式自左向右，分析模式最左推导，在分析中最多向前看1个输入字符8、First(A)的含义指每个候选式的终结首符集；Follow(A)的含义指在文法G的一切句型中能够紧跟着A之后的一切终结符或#9、一部文法G，若它的LL(1)分析表M不含多重定义入口，则称它是一个LL(1)文法，由LL(1)文法产生的语言称为LL(1)语言10、任何LL(1)文法是无二义性
11、的；若一文法中的非终结符含有左递归，则它必然是非LL(1)文法；非LL(1)语言是存在的；存在一种算法，能判定任一文法是否为LL(1)文法；存在一种算法，能判定任意两个LL(1)是否产生相同的语言；不存在这样的算法，它能判定上下文无关语言能否由LL(1)文法产生第五章 语法分析1、基本思想：对给定的G按照一定原则求出G的文法符号间的继承关系，按照优先关系确定句柄实施规约2、算符优先分析：定义算符之间的优先关系，借助关系寻找句柄进行规约；算符文法设有一文法G，如果G中没有U-.VW. V,W,U属于非终结符；算符文法的任何句型都不会含有两个相邻的非终结符3、设G是一个算符文法，p是句型apb关于
12、A的短语，且p至少含有一个终结符号，并且除自身外不再含有任何更小的带终结符符号的短语，则p是句型apb关于A的素短语，最左边的素短语为最左素短语4、算符优先分析器：总控程序，分析栈，优先函数表5、LR分析技术是编译系统中语法分析器实现最常用、最有效的一种方法【理论上比较完善，适用性强，便于自动生成】6、LR分析：一类对源程序串进行自左向右扫描并进行规范归约的语法分析方法，L扫描模式自左向右，R分析模式最右推导逆序，K再多向前看K个字符7、LR分析器组成：总控程序，分析栈，LR分析表【分析动作表，状态转换表】8、一个句型的任意首部，称为该句型的一个前缀；规范句型的一个前缀，称为该句型的一个活前缀
13、9、LR(0)项目：在文法G的每个产生式的右部的任何位置添加一个圆点，所构成的每个产生式；分类【归约项目，接受项目，移进项目，待约项目】10、识别文法G活前缀的DFA项目集的全体称为文法G的LR(0)项目集规范族11、LR(0)文法：一个文法G的识别活前缀的DFA的每一个项目不存在既含移进项目又含归约项目或含有多个归约项目，则每个项目集的项目相容12、如果每个入口不含多重定义，称为G的SLR(1)分析表，具有SLR(1)分析表的文法G称为SLR(1)文法，使用SLR(1)分析表的语法分析器称为SLR(1)分析器13、按照LR(1)的项目集规范族构造的文法G的KR(1)分析表，如果每个入口不含多
14、重定义，称它为LR(1)分析表，具有LR(1)分析表的文法称为LR(1)文法，使用LR(1)分析表的语法分析器称作LR(1)分析器14、同心项目集：对文法LR(1)项目集规范族，存在两个项目集I0，I1，其中I0，I1项目集中的LR(0)项目相同，仅搜索符不同，I0，I1为G的同心项目集15、按照LALR(1)的项目集规范族构造的文法G的LALR(1)分析表，如果每个入口不含多重定义，则称它为G的LALR(1)分析表。具有LALR(1)分析表的文法G称为LALR(1)文法。使用LALR(1)分析表的语法分析器称作LALR(1)分析器16、任何一个二义文法都不是一个LR文法17、编译中错误种类：
15、词法错误，语法错误，语义错误，违反环境限制的错误18、错误恢复策略：紧急恢复方式，短语级恢复，出错产生式，全局纠正19、YACC：是一个LALR(1)分析器自动生成器，包括YACC语言和YACC编译器第六章 语义分析1、任务：按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码，中间代码是介于源语言和目标代码之间的一种代码；引入目的：方便生成目标代码，便于优化和移植2、文法符号形式定义 A=(G,V,F) G一般为二型文法，V属性点的有穷集，F关于属性的断言或谓词的有穷集3、继承属性【由父节点或兄弟结点的属性定义】，综合属性【通过子节点的属性计算得到】4、中间语言：N元式，逆波兰式，图5、符号表：存放源程序中有关标识符的属性信息的数据结构，结构【名字域，属性信息域】，作用：收集标识符属性信息，语义检查依据，代码生成时地址分配依据6、语句标号处理：先定义后引用，先引用后定义，对于多遍扫描的编译器视为先定义后引用处理，对于一遍扫描的编译器采用拉链-返填技术，先保存再填值7、动态数组处理：内情向量表在程序运行时建立，编译时仅分配占内情向量表存储空间，确定后再将这些信息登录内情向量表第七章 代码优化1、功能：在不改变程序运行效果的前提下，对被编译的程序进行等价变换，使之能生成更加
