编译原理期末总结

思维导图：

引论

编译程序的过程：

词法分析——>语法分析——>语义分析——>中间代码生成——>代码优化——>目标代码生成

其中中间代码生成和代码优化不是必要的。

文法和语言

描述文法的两种方式：生成方式、识别方式

什么是文法：

文法的等价：文法所生成语言的等价

句型和句子的区别：句型>句子,句子是终结符串，句型可以包含非终结符

推导：直接推导、星推导、加推导
最右推导：每次对最右边的非终结符进行替换（规范推导），最左推导：每次替换最左边的非终结符。

推导和规约：推导：产生式右边代替产生式左边，规约：产生式左边代替产生式右边

推导是自顶向下，右边代替左边；规约是自底向上，左边代替右边

文法的分类和对应的自动机：

0型文法：所有的文法都是0型文法
1型文法：产生式右边长度大于产生式的左边
2型文法：产生式左边只有一个非终结符
3型文法：产生式右边只有一个终结符或者一个终结符号和一个非终结符

1型文法为什么是上下文有关的（context-sensitive）：上下文：非终结符前后的终结符号，想要用产生式的右边代替左边的时候必须考虑非终结符的前后位置（上下文）

语法树：描述上下文无关文法的句型推导的直观表示，是句型分析的工具。

什么样的文法是二义的：某个文法对应两棵不同的语法树，注意文法的二义性和语言的二义性是不同的。很可能文法是二义的但是语言是相同的，文法的二义只是影响我们对语言的分析。判断一个文法是不是二义的是一个递归不可解的问题，但是我们可以给出一个文法不是二义文法的充分条件。

分析程序：完成句型分析的程序
概念：句子，句型，句柄，短语

短语：短语是句型的一部分，这一部分是由某个非终结符加推导（经过一次或者多次推导）出来的，在语法树中，短语是以非终结符为根，其叶子节点按顺序排列的结果（事实上我们并不关心是由哪个非终结符推导得到的，只关心短语本身）

直接短语：直接由某个非终结符号推导出的短语
句柄：最左直接短语（一个非常重要的概念）

给出语言写文法，给出文法写语言

句型分析要解决的问题：

• 自顶向下：多候选式时如何选择；
• 自底向上：选择要进行规约的子串（可规约串）

词法分析

词法分析程序的任务：从左至右逐个字符地对源程序扫描，产生单词序列，用于语法分析
讨论范畴：3型文法

正规文法，正规式，自动机都是3型文法的讨论范畴

1. 正规文法、正规式概念
2. 正规式、正规文法，自动机的的相互转换（以NFA为桥梁转换）：

• 正规式↔NFA
  
• 正规文法↔NFA
  

3. DFA和NFA的区别：DFA的变换函数f是一对一映射，NFA是一对多映射，也就是NFA一个状态遇到一个字母，下一个状态是不唯一的、不确定的。

4. NFA的确定化：
   思路：用状态集代替状态。
   ε-closure：某个状态经过若干条ε弧到达的状态集合。
   
   行表头是字母表里面的字母，列表头是状态集合。利用Ia规则更新状态，新的状态依据宽度优先搜索进入到列表头，不断递归，直到无新状态集产生。然后用状态代替状态集。

5. DFA的最小化：

• 消除无用状态：不可到达（任何输入串不能到达该状态：没有出现在产生式的右边）和不可终止（该状态没有通路到达终态：无限递归）
• 合并等价状态：

6. 证明正规文法/正规式等价：

写出对应的NFA——>确定化NFA——>最小化DFA——>画出最后的自动机，判断自动机是否等价

零碎知识点：

• 正规式的等价、正规集的等价、自动机的等价是等价的
• 状态转换图：初态双箭头表示，终态双括号表示
• 自动机到正规式的时候只要形成循环就是闭包
• 正规式到自动机的时候想要表示闭包不仅要形成循环，还有前后两条空
• 正规文法到自动机需要新增一个终态

问题：为什么程序设计语言的单词集合对应正规语言？

自顶向下的语法分析

写在前面的话，我更希望明白LL（1）的思路。
1

LL（1）文法原理

1. first集 ：首终结符集合
2. follow集：向后看一个符号，后面跟着的终结符集合
3. select集 ：
4. 判断是否为LL（1）文法：同一个非终结符的产生式右边的select集没有交集
5. LL（1）分析：步骤，分析栈，符号串
6. 消除左公因子、左递归

补充：自顶向下的语法分析包括递归子程序和LL（1）分析表，两种功能相同

自底向上的语法分析

补充：自底向上的语法分析包括优先分析和LR分析，两者功能相同

1. 移进、规约、待约、接受项目

2. 移进、规约、接受，出错动作

3. LR（0），SLR（1），LALR（1），LR（1）文法判断
   LR（0）文法：没有移进-规约，规约-规约冲突
   SLR（0） 面向follow集规约，没有移进-规约，规约-规约冲突
   LALR(1):LR(1)文法合并同心集之后没有新的冲突产生
   LR（1）文法：没有规约规约冲突

4. SLR（1）文法写分析表的时候小技巧：先写普通的action和动作，最后再补充的状态内既有移进又有规约的规约动作。

语义分析

1. 继承属性
2. 综合属性
3. 语义子程序
4. 逆波兰式，三元式，四元式