一、开始
从根部开始构建语法树
二、两大问题
1、消除左递归
（1）问题：无限递归
根源是无限递归让编译器陷入死循环
（2）分类
a、直接左递归
A —> A+B | B
B —> int | (A)
修改为
A —> BA’
A’—> +BA’|ε
b、非直接左递归
S —> Aa | b
A —> Sd | ε
v先变换成直接左递归
S —> Aa | b
A —> Aad | bd | ε (这里注意改的是A，而不是S）
v再消除左递归
S —> Aa | b
A —> bdA’| A’
A’ —> adA’| ε
复杂一点的例子
2、提取左因子
（1）问题：一步推导存在多个产生式选择（推导不唯一）
根源是编译器不想回溯，即需要确定的知道下一步要干什么
（2）解决方法
A —>ab1 | ab2
修改为
A —> a A’
A’—> b1 | b2
复杂一点的例子
三、LL(1)文法
1、说明
a、通过对文法加限制来保证没有回溯
b、必须要先消除左递归，提取左因子，不然很容易发现得到的文法不是LL(1)的
c、第一个L是从左向右读入数据，第二个L是最左推导，采用1的前看符号
2、FIRST集合
（1）计算方法
a、X—>a... 将终结符a加入集合中
b、X—>ε 将ε加入集合中
c、X—>Y... 剔除FIRST(Y)中的ε后加入集合中
d、X—>Y1Y2...Yk（注意都是非终结符）
如果前k-1的FIRST中都有ε，就把所有FIRST(Y)剔除ε加入集合
如果前k 的FIRST中都有ε，就把所有FIRST(Y)加入集合（包括ε）
3、FOLLOW集合
（1）计算方法
a、开始符号S 将$加入集合
b、A—>αBβ 将FIRST(β)/ε加入B的集合中
c、A—>αB 将FOLLOW(A)加入FOLLOW(B)中
d、A—>αBβ，且ε属于FIRST(β)，将FOLLOW(A)加入FOLLOW(B)中
尤其注意这里的α，β都是文法的符号串
4、LL(1)文法要求
（1）A—> α | β，则要求FIRST(α) ∩ FIRST(β) = Φ
（2）若ε属于FIRST(β)，则要求FIRST(α) ∩ FOLLOW(A) = Φ
5、LL(1)文法的特征
没有左递归
没有左因子
不是二义的
6、递归下降的分析法
从文法的起始符号开始
为每一个非终结符写一个函数
这些函数可能是递归的
每个函数的设计规则
1、匹配FIRST集合：如果是非终结符匹配到的，转到该非终结符，如果是终结符匹配到的，成功匹配要删减输入串
2、如果FIRST有ε，则按照FOLLOW集合匹配
3、错误处理：对于FIRST没有ε的，匹配FOLLOW集合内容的，输出SYN错误，越过该函数
空白项的删除一个输入流符号
7、非递归下降的分析法
借助栈和预测分析表
预测分析表
行：非终结符
列：终结符（包括$）
表项：推导式右部（按照FIRST集合加）
如果ε在FIRST集合中，把A->α加入每个FOLLOW(A)中
空白项：错误
错误处理
同步错误（FOLLOW记录的）：弹栈
空白错误：移除首部输入流记号
举例
8、错误处理
（1）同步：词法分析器和记号流良匹配的状态
在出现不匹配错误时，可以放弃一些记号，直到达到同步状态，然后弹出非终结符，所以以下是出现错误情况下的选择走法
同步集合的选择
1、FOLLOW集合记录
2、高层的开始符号加入到底层的同步集合中（如；避免遗漏错过一大段程序）
3、也可以放置FIRST(A)，但是注意这是在出错之后才去选择的
4、推导式有空串，将该产生式作为优先考虑的推导式（会延迟错误的发现，但不会遗漏，可以减少错误恢复的非终结符）
遇到同步记号，则将非终结符弹栈
（2）空白：紧急恢复：抛弃一个输入记号
（3）栈顶的终结符和指针指向的终结符不匹配：终结符弹栈
注意除了空白是抛弃输入符号，其他都是弹栈操作
预测分析器动作
栈 输入 动作
$E id*id+id$
$E_T id*id+id$ 输出E->TE_
.......................
四元组
一组终结符，一组非终结符，开始符号，一组产生式