川大编译原理复习要点

1、1. 编译的各个阶段扫描程序(scanner)在这个阶段编译器实际阅读源程序（通常以字符流的形式表示）。扫描程序执行词法分析（Lexical analysis）：它将字符序列收集到称作记号(t o k e n）的有意义单元中，记号同自然语言，如英语中的字词相似。语法分析程序(parser)语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析（syntax analysis），这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树（ parse tree）或语法树（syntax tree）。语义分析程序（semantic a

2、nalyzer）分析程序的静态语义，包括包括声明和类型检查。源代码优化程序（source code optimizer），代码生成器（code generator），目标代码优化程序（target code optimizer）。2. 编译器的前端（front end），后端（back end），遍（passes）扫描程序、分析程序和语义分析程序是前端，代码生成器是后端。编译器发现，在生成代码之前多次处理整个源程序很方便。这些重复就是遍（p a s s）3. 编译器，汇编器和解释器之间的区别 解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于：它立即执行源程序而不是生成在翻译完成

3、之后才执行的目标代码。汇编程序是用于特定计算机上的汇编语言的翻译程序。有时，编译器会生成汇编语言以作为其目标语言，然后再由一个汇编程序将它翻译成目标代码。4. 扫描，分析（语法，词法）的任务扫描的任务是将源程序读作字符文件并将其分为若干个记号 扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处理的逻辑单元。由扫描程序生成的逻辑单元称作记号（ t o k e n）分析的任务是确定程序的语法，或称作结构分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的分析树或语法树5. 上下文无关文法，最左推导，BNF，EBNF，乔姆斯基文

4、法层次 上下文无关文法说明程序设计语言的语法结构，利用了与正则表达式中极为类似的命名惯例和运算。二者的主要区别在于上下文无关文法的规则是递归的（recursive） 最左推导（ leftmost derivation）是指它的每一步中最左的非终结符都要被替换的推导最右推导（ rightmost derivation）则是指它的每一步中最右的非终结符都要被替换的推导。最左推导和与其相关的分析树的内部节点的前序编号相对应；而最右推导则和后序编号相对应最右推导的一个例子：文法规则：exp exp op exp | (e x p) | n u m b e rop + | - | * 相关题目：3.3

5、EBNF中注意重复和可选的表示方法，语法图 6. 句子，句型，文法所定义的语言，分析树，抽象语法树7. 自顶向下，自底向上语法分析 自顶向下（t o p - d o w n）的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶。分为两类：回溯分析程序（ backtracking parser）和预测分析程序（ predictive parser） 自底向上的分析程序有两种可能的动作(除“接受”之外)：1) 将终结符从输入的开头移进到栈的顶部。2) 假设有B N F选择Aa，将栈顶部的串a归约为非终结符A

6、。8. 为什么要解决公因子，左递归当有公因子存在时，不能立即区分出文法规则右边的选择当有左递归时，将导致一个无限循环。9. 写正则表达式，构造NFA，DFA，最小化（按照算法做）构造NFA（使用Thompson结构）:1) 基本正则表达式 基本正则表达式格式a或，其中a表示字母表中单个字符的匹配，表示空串的匹配。与正则表达式a等同的N FA（即在其语言中准确接受）的是：与等同的N FA是：2) 并置 我们希望构造一个与正则表达式r s等同的N FA，其中r 和s 都是正则表达式。可将与rs 对应的N FA构造如下： 3) 在各选项中选择 我们希望在与前面相同的假设下构造一个与r | s 相对应

7、的N FA。如下进行： 4) 重复 我们需要构造与r *相对应的机器，现假设已有一台与r 相对应的机器。那么就如下进行：构造NFA的一个例子：例：根据Thompson 结构将正则表达式a b | a 翻译为N FA。首先为正则表达式a 和b 分别构造机器： 接着再为并置a b 构造机器： 现在再为a 构造另一个机器复件，并利用它们组成a b | a 完整的N FA，如下图：将NFA转换成DFA（最小子集法）：- 闭包（ - c l o s u r e）是可由转换从某状态或某些状态达到的所有状态集合，它总是包含状态本身 子集构造：参见Chapter_two(2).ppt相关题目：2.1，2.12

8、，2.1610. 写最左推导，最右推导，画分析树和抽象语法树相关题目：3.311. 写出给定程序的语法树，抽象语法树相关题目：3.312. 说明文法有二义性可生成带有两个不同分析树的串的文法称作二义性文法（ambiguousgrammar）相关题目：3.213. 写出给定程序的递归下降分析程序（可能用伪代码，C程序），构造语法树注意事项：在处理产生式A时，可以忽略，或者使用A的Follow集合。不要试图去匹配（不然要被拉去登记的）相关题目：4.2，4.3，4.414. 给定文法：消除左递归，提取公因子，求First Set，Follow Set，说明是否是LL(1)文法，构造LL(1)分析表，

9、给出一个输入分析的动作消左递归：简单直接左递归在这种情况下，左递归只出现在格式AAa | b，为了消除左递归，将这个文法规则重写为两个规则：一个是首先生成b，另一个是生成a的重复，它不用左递归却用右递归：A bA¢和A ¢aA¢ | 其它形式参见书本提取左因子：当两个或更多文法规则选择共享一个通用前缀串时，需要提取左因子。如Aab | a g，将左边的a分解出来，并将该规则重写为两个规则A aA¢和A¢ b | gFirst 集合：令X为一个文法符号（一个终结符或非终结符）或，则集合First (X) 由终结符组成，此外可能还有，它的定义如下：

10、1. 若X是终结符或，则First (X) = X。2. 若X是非终结符，则对于每个产生式XX1 X2 . . . Xn ，First (X)都包含了F i r s t(X1 ) - 。若对于某个i < n，所有的集合First (X1 ), . . . , First (Xi ) 都包括了，则First (X) 也包括了First (Xi + 1) - 。若所有集合First (X1 ), . . . , First (Xn)包括了，则First (X)也包括。 现在为任意串a = X1 X2 . . . Xn（终结符和非终结符的串）定义First (a)，如下所示：First (a)

11、包括First (X1 ) - 。对于每个i = 2, . . . , n，如果对于所有的k = 1, . . . ,i -1，First (Xk ) 包括了，则First (a)就包括了First (Xi ) - 。最后，如果对于所有的i =1, . . . , n，First (Xi ) 包括了，则First (a)也包括了。 Follow 集合：给出一个非终结符A，那么集合F o l l o w (A)则是由终结符组成，此外可能还有$。集合F o l l o w (A)的定义如下：1. 若A是开始符号，则$就在F o l l o w (A)中。2. 若存在产生式BaAg，则First (

12、 g) - 在F o l l o w (A)中。3. 若存在产生式BaAg，且在F i r s t (g)中，则F o l l o w (A)包括Follow (B)。 LL(1)文法：如果文法G相关的L L ( 1 )分析表的每个项目中至多只有一个产生式，则该文法就是L L ( 1 )文法(LL(1) grammar)。 LL(1) 分析表MN, T 的构造：为每个非终结符A和产生式Aa 重复以下两个步骤：1) 对于First (a)中的每个记号a，都将Aa添加到项目M A, a中。2) 若在First (a)中，则对于Follow (A) 的每个元素a（记号或是$），都将Aa 添加到MA, a中。相关题目：4.7，4.8，4.1015. 给定文法：求LR(0)的DFA，构造LR(0)和SLR(1)的分析表，说明是否是LR(0)或SLR(1)文法（描述冲突），给定一个输入，写出LR(0),SLR(1)的分析步骤相关题目：5.1，5.316. 算法（写伪代码）3种DFA代码，LL(1)算法，LR(0)算法，SLR(1)算法，消左递归，提公因子，构造Fi