《编译原理总复习》PPT课件.ppt

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

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

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

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

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

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

7、符文法、算符优先文法、LR（0）项目、活前缀、可归前缀 （2）自下而上分析的基本思想及其核心 基本思想：移进-归约 核心问题：可归约串的界定 （3）自下而上分析的基本方法 算符优先分析法：以最左素短语作为可归约串，非规范归约 LR分析法：以句柄作为可归约串，规范归约,编译原理,5、 自下而上语法分析方法,（4）给定一个文法的句型，找出其短语、直接短语、句柄、素短语和最左素短语 方法：首先画出句型的语法分析树，然后根据语法树寻找。 每棵子树的叶子结点自左至右排列构成一个相对于子树根的短语。 每棵简单子树（只有父子两代）的叶子结点自左至右排列构成一个直接短语。 最左简单子树的叶子结点自左至右排列构

8、成一个句柄。 将所有短语中至少含一个终结符的短语，按长度从小到大排列，长度最短的认定为素短语，然后考察其余长度较大的，若不包含更小的素短语，则也为素短语。位于句型中最左边的素短语即为最左素短语。,5、 自下而上语法分析方法,（5）算符文法与算符优先文法 算符文法：任意产生式右部不含两个连续的非终结符，（.QR.） 算符优先文法：算符文法中任意两个终结符之间至多只含“”、“a； 如果存在a=b和b=c，不一定有b=a或a=c； 如果存在ab和bc，也不能得出ac。,5、 自下而上语法分析方法,（6）FIRSTVT集与LASTVT集的计算 FIRSTVT 规则一：若有产生式Pa或 PQa，则aFI

9、RSTVT(P)； 规则二：若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； 规则四：对于语句括号#，有#=#，且

10、若aFIRSTVT(S)和bLASTVT(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、 自

12、下而上语法分析方法,（15）四类LR分析表的构造 拓广文法 构造LR(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）属性分类 综合属性：用于“自下而上”地传递信息。 继承属性：用于“自上而下”地传递信息。 终结符号只有综合属性，由词法分析器提供。 非终结符既可有综合属

13、性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。 （3）语义规则的表示,6、 语法制导翻译和语义分析,（4）常见的中间代码的几种形式 后缀式（逆波兰表示式） 图表示法 抽象语法树 DAG图 三地址代码 四元式 三元式 间接三元式,6、 语法制导翻译和语义分析,（5）后缀式（逆波兰式）的表示 把运算量（操作数）写在前面，把运算符写在后面（后缀）的一种表达式表示方法。其归纳定义如下： 如果E是一个变量或常数，则E的后缀式是E自身。 如果E是E1 op E2 形式的表达式，op是二元操作符，则E的后缀式为E1E2op，其中E1，E2分别是E1和E2的后缀式。 若E是（E1）形式的

14、表达式，则E的后缀式就是E1的后缀式。,6、 语法制导翻译和语义分析,（6）将以下语句翻译为四元式序列 表达式（算术及布尔） 赋值语句 数组 IF语句 WHILE语句 （7）参数传递的几种方式 传地址、 传值、传名、得结果,7、 符号表,（1）符号表的重要性 合理地组织符号表并选择好的查表、填表方法是提高编译程序工作效率的有效办法。 （2）符号表的基本组成、基本操作 组成：一张符号表的每一项入口包含：名字栏和信息栏 操作：查表、填表、访表、更新、删除 （3）符号表的组织方式 按照处理对象的特点，符号表的组织方式一般可分为直接方式和间接方式。也按标识符的种属分别建立不同的符号表。,7、 符号表,

15、（4）符号表的构造和处理方法 符号表主要有三种构造和处理方式：线性表、二叉树、杂凑（哈希）。 （5）内情向量的基本表项 在编译过程中，碰到数组的说明时，通常将数组的有关信息记录在一个内情向量表中，这些信息包括：维数、首地址、各维界差、各维上界、各维下届、数组元素类型、地址不变量。 （6）编程语言中常用的两条作用域规则 使用前说明和块结构的最近嵌套作用域规则。,8、 代码优化,（1）基本概念 优化、基本块、局部优化 （2）代码优化遵循的原则 等价原则、有效原则、合算原则 （3）优化分类 根据编译阶段的不同划分为：与机器无关的中间代码优化和依赖于机器的目标代码优化。 根据优化对象所涉及的程序范围划分为：局部优化、循环优化和全局优化。,8、 代码优化,（4）常见的优化的几种方法 删除公共子表达式、复写传播、删除无用代码、合并已知