编译原理目录
1、词法分析
2、语法分析（重点）
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化
概述
语法分析器的任务：记号流 => 语法分析器 => 抽象语法树。
语法分析器实现方法：
- 手工方式：递归下降分析器
- 使用语法分析器的自动生成器：LL(1)，LR(1)
两种方式在实际的编译器中都有广泛的应用：
- 自动的方式更适合快速对系统进行原型
- 手动的方式能够构建比较复杂的语法，适合对代码优化的场景。
上下文无关文法（CFG）及其他基本概念
三大集
- $NULLABLE$集：能推出 $N\rightarrow ε$ 的非终结符$N$的集合。
- $FIRST$集/$FIRST\_S$：非终结符$N$的开头的终结符的集合。
$FOLLOW$集：可以跟在非终结符$N$后面的终结符的集合。
- 注意是跟在$N$后面，而并非$N$本身。
- 判断方法：只看右部表达式$N$的后面。
自顶向下分析方法
自顶向下：非终结符 → 终结符，由非终结符推出若干个终结符，是一个移进的过程
自底向上：终结符 → 非终结符，由终结符推回开始符号or报错，是一个归约的过程
算法需要用到回溯，回溯效率比较低，而就这部分而言（就所有部分），编译器必须高效。因此，实际上我们需要线性时间的算法，避免回溯，引出递归下降分析算法和LL(1)分析算法。即用前看符号避免回溯。
0x01 递归下降分析（预测分析法）
利用函数之间的递归调用模拟语法树自上而下的构造过程
0x02 LL(1)分析算法
自底向上分析方法
自顶向下：非终结符 → 终结符，由非终结符推出若干个终结符，是一个移进的过程
自底向上：终结符 → 非终结符，由终结符推回开始符号or报错，是一个归约的过程
LR分析算法
0x03 LR(0)分析算法（移进-归约算法）
0x04 SLR算法
0x05 LR(1)分析算法
文法
LL(1)文法
G的任意两个具有相同左部的产生式$A → α$、$A → β$ 满足下列条件：
- 如果α、β均不能推导出ε，则 FIRST(α) ∩ FIRST(β) = ∅。
- 如果α 和 β 至多有一个能推导出 ε，假定 β 能推导出 ε，则 FIRST(α) ∩ FOLLOW(A) = ∅。
则称为LL(1)文法。LL(1)文法既不是二义性的，也不含左递归。
LR(0)文法
文法对应的自动机中不存在 移进-归约冲突 和 归约-归约冲突 。换言之，LR(0)文法分析不能解决这两种冲突。
SLR文法
文法对应的自动机中不存在 归约-归约冲突 ，有可能存在 移进-归约冲突。换言之，SLR文法分析过程可以用follow集解决移进-归约冲突，但是不一定能解决归约-归约冲突。
移进-归约冲突：就是在同一个项集族中同时出现了可以移进的产生式和可以归约的产生式。
归约-归约冲突同理。
其他问题
LR算法对文法二义性问题的处理
二义性文法无法使用LR分析算法分析，不过有几类二义性文法很容易理解，因此在LR分析器的生成工具中，可以对它们特殊处理，比如：优先级、结合性、悬空else等
LR分析算法包含关系
