发布时间 : 星期二 文章四川大学编译原理期末试卷4套+复习资料更新完毕开始阅读
.
1. 编译的各个阶段 扫描程序(scanner)
在这个阶段编译器实际阅读源程序（通常以字符流的形式表示）。扫描程序执行词法分析（Lexical analysis）：它将字符序列收集到称作记号(t o k e n）的有意义单元中，记号同自然语言，如英语中的字词相似。 语法分析程序(parser)
语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析（syntax analysis），这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树（ parse tree）或语法树（syntax tree）。 语义分析程序（semantic analyzer）
分析程序的静态语义，包括包括声明和类型检查。 源代码优化程序（source code optimizer），代码生成器（code generator），目标代码优化程序（target code optimizer） 2. 编译器的前端（front end），后端（back end），遍（passes） 扫描程序、分析程序和语义分析程序是前端，代码生成器是后端。
编译器发现，在生成代码之前多次处理整个源程序很方便。这些重复就是遍（p a s s） 3. 编译器，汇编器和解释器之间的区别
解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于：它立即执行源 程序而不是生成在翻译完成之后才执行的目标代码。 汇编程序是用于特定计算机上的汇编语言的翻译程序。有时，编译器会生成汇编语言以作为其目标语言，然后再由一个汇编程序将它翻译成目标代码。 4. 扫描，分析（语法，词法）的任务
扫描的任务是将源程序读作字符文件并将其分为若干个记号
扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处理的逻辑单 元。
由扫描程序生成的逻辑单元称作记号（ t o k e n） 分析的任务是确定程序的语法，或称作结构
分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的分析树或语法树
5. 上下文无关文法，最左推导，BNF，EBNF，乔姆斯基文法层次 上下文无关文法说明程序设计语言的语法结构，利用了与正则表达式中极为类似的命名惯例和运算。
二者的主要区别在于上下文无关文法的规则是递归的（recursive）
最左推导（ leftmost derivation）是指它的每一步中最左的非终结符都要被替换的推导 最右推导（ rightmost derivation）则是指它的每一步中最右的非终结符都要被替换的推导。最左推导和与其相关的分析树的内部节点的前序编号相对应；而最右推导则和后序编号相对应
最左推导的一个例子：书p73 相关题目：3.3
EBNF中注意重复和可选的表示方法，语法图
6. 句子，句型，文法所定义的语言，分析树，抽象语法树 7. 自顶向下，自底向上语法分析
自顶向下（t o p - d o w n）的分析算法通过在最左推导中描述出各个步骤来分析记号串输
.
.
入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶。 分为两类：回溯分析程序（ backtracking parser）和预测分析程序（ predictive parser） 自底向上的分析程序有两种可能的动作(除“接受”之外)： 1) 将终结符从输入的开头移进到栈的顶部。
2) 假设有B N F选择A→a，将栈顶部的串a归约为非终结符A。 8. 为什么要解决公因子，左递归
当有公因子存在时，不能立即区分出文法规则右边的选择 当有左递归时，将导致一个无限循环。
9. 写正则表达式，构造NFA，DFA，最小化（按照算法做） 构造NFA（使用Thompson结构）: 书P45-47 将NFA转换成DFA（最小子集法）：
ε- 闭包（ε - c l o s u r e）是可由ε转换从某状态或某些状态达到的所有状态集合，它总是包含状态本身
子集构造：参见Chapter_two(2).ppt 相关题目：2.1，2.12，2.16 10. 写最左推导，最右推导，画分析树和抽象语法树 相关题目：3.3
11. 写出给定程序的语法树，抽象语法树 相关题目：3.3
12. 说明文法有二义性
可生成带有两个不同分析树的串的文法称作二义性文法（ambiguousgrammar） 相关题目：3.2
13. 写出给定程序的递归下降分析程序（可能用伪代码，C程序），构造语法树
注意事项：在处理产生式A→ε时，可以忽略，或者使用A的Follow集合。不要试图去匹配ε（不然要被拉去登记的） 相关题目：4.2，4.3，4.4
14. 给定文法：消除左递归，提取公因子，求First Set，Follow Set，说明是否是LL(1)文法，构造LL(1)分析表，给出一个输入分析的动作 相关题目：4.7，4.8，4.10
15. 给定文法：求LR(0)的DFA，构造LR(0)和SLR(1)的分析表，说明是否是LR(0)或SLR(1)文法（描述冲突），
给定一个输入，写出LR(0),SLR(1)的分析步骤 相关题目：5.1，5.3
16. 算法（写伪代码）
3种DFA代码，LL(1)算法，LR(0)算法，SLR(1)算法，消左递归，提公因子，构造First，Follow集合 DFA代码（英文书P63，中文P42） LL（1）算法（英文书P155，中文P115） LR（0）算法（英文书P207，中文P158） SLR(1) 算法（英文书P210，中文P160） 左递归（英文书P159，中文P119） 公因子（英文书P164，中文P122）
构造First Set（英文书P168，中文P126）
.
.
构造Follow Set（英文书P173，中文P130） 参见书本单纯的课本内容，并不能满足学生的需要，通过补充，达到内容的完善 教育之通病是教用脑的人不用手，不教用手的人用脑，所以一无所能。教育革命的对策是手脑联盟，结果是手与脑的力量都可以大到不可思议。
.