编译原理总复习2015

《编译原理总复习2015》由会员分享，可在线阅读，更多相关《编译原理总复习2015（34页珍藏版）》请在金锄头文库上搜索。

1、1 题型及分值,一、判断题 （15=5）二、填空题 （110=10）三、选择题（25=10）四、简答题 （本题共35分）:其中包括两个名词解释。五、计算题 （10+15+15=40）,编译原理,2 教材各章知识点概览,编译原理,1、 编译程序概论,（1）基本概念翻译程序，编译程序（2）编译过程的五个阶段，各阶段的任务及其依循的规则、描述工具分别是什么？除了这个5个阶段之外，还应该有哪两个重要内容？五个逻辑阶段：词法分析、语法分析、语义分析和中间代码产生、代码优化和目标代码生成。除了这五个阶段之外，编译程序的每个阶段都涉及到表格管理和错误处理这两个重要内容。,编译原理,1、 编译程序概论,（3）

2、编译错误的种类从编译程序的角度来看，源程序中的错误主要分为：语法错误 和 语义错误两类错误。（4）高级程序设计语言翻译的两种方式以及它们的区别高级程序设计语言的翻译主要有两种方式：编译方式 和 解释方式。区别：是否生成目标代码。,编译原理,2、 文法和语言,（1）基本概念文法、推导、最左推导、最右推导、句型、句子、语言、文法的二义性（2）对文法G，能够给出给定句型或句子的最左推导及最右推导序列，并画出其对应的语法分析树。（3）能够计算某文法的语言。（4）理解文法的二义性，能够说明一个文法是二义的。,编译原理,2、 文法和语言,（5）形式语言分类(chomsky,1956)0型 普通（短语）文法

3、 1型 上下文有关文法2型 上下文无关文法3型 线性（正规、正则）文法3型2型1型0型,编译原理,3、 词法分析与有限自动机,（1）基本概念状态等价、DFA的化简（2）词法分析器的任务及其输出形式任务：自左至右逐个字符地对源程序进行扫描，按语言的构词规则识别出一个个单词，把作为字符串的源程序改造为单词符号串的中间程序。输出形式：二元式 （ 单词种别， 单词符号的属性值）（3）单词符号的种类关键字、标识符、常数、运算符、界符,编译原理,3、 词法分析与有限自动机,（4）正规文法、正规式、有限自动机之间的相互等价性定理（5）正规式 NFA DFA 最小化DFA（注意：状态函数定义不完整之情形）（6

4、）状态转换图的构造(标识符、整数),编译原理,4、 自上而下语法分析方法,（1）语法分析的方法根据语法分析树建立方向的不同，将语法分析分成两类：自上而下语法分析方法和自下而上语法分析方法。（2）自上而下分析的基本思想穷举试探法（3）自上而下分析面临的两个最主要的问题左递归、回溯（4）自上而下分析的基本方法 LL（1）分析法、递归下降分析器,编译原理,4、 自上而下语法分析方法,（5）左递归（直接、间接）和回溯的消除直接左递归的消除间接左递归的消除排序代入及消除左递归化简,编译原理,4、 自上而下语法分析方法,（5）左递归（直接、间接）和回溯的消除回溯的消除：提左公因子,编译原理,4、 自上而下

5、语法分析方法,（6）LL(1)的含义LL(1)中的第一个L表示从左至右扫描输入串，第二个L表示最左推导，1表示分析时每一步只需向前查看一个符号。（7）LL(1)分析器的组成部分输入缓冲区、分析栈、分析表、总控程序（8）LL(1)分析的四种动作成功、匹配、推导、报错,编译原理,4、 自上而下语法分析方法,（9）LL(1)文法的判定条件文法不含左递归。文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若则 对文法中的每个非终结符A，若它存在某个候选首符集包含，则如果一个文法G满足以上条件，则称该文法G为LL(1)文法。,编译原理,4、 自上而下语法分析方法,（10）LL(1)分析方法假

6、设要用非终结符A进行匹配，面临的输入符号为a，关于A的所有产生式为则LL(1)分析算法如下：若 ，则指派 去执行匹配任务。若a不属于任何一个候选首符集，则若属于某个 且 ，则让A与自动匹配；否则，a的出现是一种语法错误。根据LL(1)文法的条件，每一步这样的工作都是确信无疑的。,编译原理,4、 自上而下语法分析方法,（11）FIRST集和FOLLOW集的构造（12）预测分析表的构造,编译原理,5、 自下而上语法分析方法,（1）基本概念短语、直接短语、句柄、素短语、最左素短语、算符文法、算符优先文法、LR（0）项目、活前缀、可归前缀（2）自下而上分析的基本思想及其核心基本思想：移进-归约核心问题

7、：可归约串的界定（3）自下而上分析的基本方法算符优先分析法：以最左素短语作为可归约串，非规范归约LR分析法：以句柄作为可归约串，规范归约,编译原理,5、 自下而上语法分析方法,（4）给定一个文法的句型，找出其短语、直接短语、句柄、素短语和最左素短语方法：首先画出句型的语法分析树，然后根据语法树寻找。每棵子树的叶子结点自左至右排列构成一个相对于子树根的短语。每棵简单子树（只有父子两代）的叶子结点自左至右排列构成一个直接短语。最左简单子树的叶子结点自左至右排列构成一个句柄。将所有短语中至少含一个终结符的短语，按长度从小到大排列，长度最短的认定为素短语，然后考察其余长度较大的，若不包含更小的素短语，

8、则也为素短语。位于句型中最左边的素短语即为最左素短语。,5、 自下而上语法分析方法,（5）算符文法与算符优先文法算符文法：任意产生式右部不含两个连续的非终结符，（.QR.）算符优先文法：算符文法中任意两个终结符之间至多只含“”、“”、“=”三种关系之一。算符优先文法一定是算符文法。算符优先关系是有序的，但不满足对称性和传递性，即对于文法G的终结符a、b和c：如果aa；如果存在a=b和b=c，不一定有b=a或a=c；如果存在ab和bc，也不能得出ac。,5、 自下而上语法分析方法,（6）FIRSTVT集与LASTVT集的计算FIRSTVT规则一：若有产生式Pa或 PQa，则aFIRSTVT(P)

9、；规则二：若aFIRSTVT(Q)且有产生式 PQ，则aFIRSTVT(P) ；规则三：反复使用以上两条规则，直到FIRSTVT(P)不再增大为止。LASTVT规则一：若有产生式Pa或 PaQ，则aLASTVT(P)；规则二：若aLASTVT(Q)且有产生式 PQ，则aLASTVT(P) ；规则三：反复使用以上两条规则，直到LASTVT(P)不再增大为止。,5、 自下而上语法分析方法,（7）算符优先关系表的构造规则一：对形如Pab或PaQb的产生式，有a=b；规则二：对形如PaR的产生式，若有bFIRSTVT(R)，则ab；规则四：对于语句括号#，有#=#，且若aFIRSTVT(S)和bLAS

10、TVT(S)，则有#。,5、 自下而上语法分析方法,（8）优先表与优先函数之间的关系对应一个优先关系表的优先函数f和g不唯一，只要存在一对，就存在无穷多对。也有许多优先关系表不存在 对应的优先函数。（9）算符优先分析算法最左素短语的寻找依据：,5、 自下而上语法分析方法,（9）算符优先分析算法算符优先分析的特点：算符优先分析一般并不等价于规范归约无法使用单非产生式(如：TF)进行归约。算符优先分析比规范归约过程要快，跳过了所有的单非产生式。可能将本来不是句子的输入串误认为是句子。（10）LR分析器的基本思想及其组成部分基本思想：记住历史、展望未来、定夺现在组成部分：输入缓冲区、分析栈（状态、符

11、号）、分析表（动作、转换）、总控程序,5、 自下而上语法分析方法,（11）四类LR分析表LR分析表是LR分析器的核心，主要有以下几种分析表：LR(0)表、 SLR(1)表（即简单LR表）、LR(1)表（即规范LR表）、LALR表（即向前LR表）。其中，L代表自左至右扫描输入串，R代表构建最右推导的逆过程，1代表分析时每一步至多向前查看一个符号，S代表简单的。（12）LR分析器的四种动作移进、归约、接受、报错（13）LR分析器的两种冲突移进归约 冲突 和 归约归约 冲突,5、 自下而上语法分析方法,（14）四类不同的项目,5、 自下而上语法分析方法,（15）四类LR分析表的构造拓广文法构造LR(

12、0)（LR(0)和SLR分析表）或LR(1)（LR(1)和LALR分析表）项目集规范簇构造相应分析表（16）LR文法的特点LR文法肯定是无二义的，一个二义文法决不会是LR文法。LR分析法比预测分析法更加一般化。LR(0)文法一定是SLR文法，SLR文法和LALR文法一定是LR(1)文法。,6、 语法制导翻译和语义分析,（1）基本概念 S属性文法 、L属性文法（2）属性分类综合属性：用于“自下而上”地传递信息。继承属性：用于“自上而下”地传递信息。终结符号只有综合属性，由词法分析器提供。非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。（3）语义规则的表示,

13、6、 语法制导翻译和语义分析,（4）常见的中间代码的几种形式后缀式（逆波兰表示式）图表示法抽象语法树DAG图三地址代码四元式三元式间接三元式,6、 语法制导翻译和语义分析,（5）后缀式（逆波兰式）的表示把运算量（操作数）写在前面，把运算符写在后面（后缀）的一种表达式表示方法。其归纳定义如下：如果E是一个变量或常数，则E的后缀式是E自身。如果E是E1 op E2 形式的表达式，op是二元操作符，则E的后缀式为E1E2op，其中E1，E2分别是E1和E2的后缀式。若E是（E1）形式的表达式，则E的后缀式就是E1的后缀式。,6、 语法制导翻译和语义分析,（6）将以下语句翻译为四元式序列表达式（算术及

14、布尔）赋值语句数组IF语句WHILE语句（7）参数传递的几种方式传地址、 传值、传名、得结果,7、 符号表,（1）符号表的重要性合理地组织符号表并选择好的查表、填表方法是提高编译程序工作效率的有效办法。（2）符号表的基本组成、基本操作组成：一张符号表的每一项入口包含：名字栏和信息栏 操作：查表、填表、访表、更新、删除（3）符号表的组织方式按照处理对象的特点，符号表的组织方式一般可分为直接方式和间接方式。也按标识符的种属分别建立不同的符号表。,7、 符号表,（4）符号表的构造和处理方法符号表主要有三种构造和处理方式：线性表、二叉树、杂凑（哈希）。（5）内情向量的基本表项在编译过程中，碰到数组的说明时，通常将数组的有关信息记录在一个内情向量表中，这些信息包括：维数、首地址、各维界差、各维上界、各维下届、数组元素类型、地址不变量。（6）编程语言中常用的两条作用域规则使用前说明和块结构的最近嵌套作用域规则。,8、 代码优化,（1）基本概念优化、基本块、局部优化（2）代码优化遵循的原则 等价原则、有效原则、合算原则（3）优化分类根据编译阶段的不同划分为：与机器无关的中间代码优化和依赖于机器的目标代码优化。根据优化对象所涉及的程序范围划分为：局部优化、循环优化和全局优化。,