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

《《编译原理总复习》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1题型及分值一、判断题（1′×5=5′）二、填空题（1′×10=10′）三、选择题（2′×5=10′）四、简答题（本题共35分）:其中包括两个名词解释。五、计算题（10′+15′+15′=40′）编译原理2教材各章知识点概览编译程序概论1文法和语言2词法分析与有限自动机3自上而下语法分析方法4自下而上语法分析方法5语法制导翻译和语义分析6符号表7代码优化8编译原理1、编译程序概论（1）基本概念翻译程序，编译程序（2）编译过程的五个阶段，各阶段的任务及其依循的规则、描述工具分别是什么？除了这个5个阶段之外，还应该有哪两个重要内容？五个逻辑阶段：词法分析、语法分析、语义分析和中间代码

2、产生、代码优化和目标代码生成。除了这五个阶段之外，编译程序的每个阶段都涉及到表格管理和错误处理这两个重要内容。编译原理1、编译程序概论（3）编译错误的种类从编译程序的角度来看，源程序中的错误主要分为：语法错误和语义错误两类错误。（4）高级程序设计语言翻译的两种方式以及它们的区别高级程序设计语言的翻译主要有两种方式：编译方式和解释方式。区别：是否生成目标代码。编译原理2、文法和语言（1）基本概念文法、推导、最左推导、最右推导、句型、句子、语言、文法的二义性（2）对文法G，能够给出给定句型或句子的最左推导及最右推导序列，并画出其对应的语法分析树。（3）能够计算某文法的语言。（4）理解

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

4、、有限自动机之间的相互等价性定理（5）正规式→NFA→DFA→最小化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）基本概念短语、直接短语、句柄、素短语、最左素短语、算符文法、算符优先文法、L

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