问题
二义性、左递归问题和回溯问题
正则文法有二义性、可判定
存在某句型 v.t. 不同推导规则 → 两棵语法树，句柄不同
上下文无关(CFG)的二义性不可判定
自顶向下
带回溯的自顶向下分析方法
从根节点遍历文法树，匹配一个句子
极慢
消除左递归
- 提因子：右式中公共部分可以提出来，压缩文件长度
- 递归部分 → { Vt+ }
- 转为右递归：
- S → (左递归下的起始符号)S’
- S’ → 左递归的可重复部分S’ | ε
- 文法可能有间接子递归，通过将规则一条条带下去找到直接子递归
消除回溯
定义：对于文法U::= α1 | … | αn
无回溯的条件是对任意i≠j, First(αi) ∩ First(αj) = φ
消除方法
- 反复提取左因子：若两个αi的First集相同，则提出来放在U的右式的最左边
- U::= (<publicFirst> αi’ | αj’) | (…)
递归下降分析法（递归子程序法）
先把文法左递归消除掉
对每个非终结符，生成其对应的分析程序
算法流程是对一个输入串，从左往右依次读，终结符就直接判断，非终结符调用分析程序判断
含有ε的情况
follow(A): 所有句型中，紧挨A后面的终结符集合
S为识别符号
FOLLOW(A) = {a | Z ⇒* …Aa…}, a∈Vt
识别算法：
文法无回溯的充分必要条件
对于A的任意两条规则A ::= α | β
- FIRST(α) ∩ FIRST(β) = Φ
- 若β ⇒* ε，则还需满足FIRST(α) ∩ FOLLOW(A) = Φ
LL(1)分析法
适用于满足无二义无回溯无左递归的语法
维护一个符号表（二维矩阵）和符号栈
符号表
是一个Vt × Vn的二维矩阵
填表规则
- A → αi
- A ⇒ αi 且 ( a ∈ FIRST(αi) 或 (αi ⇒* ε 且 a ∈ FOLLOW(A) )
在分析非终结符A时，若匹配到的输入串的第一个字符为a，则将A替换成αi
符号栈
匹配的时候用
先push(#) 和 (识别符号)，指针ptr指向匹配串的最左侧
迭代分析过程：
对栈顶元素E
if E ∈ Vt
pop()
ptr右移一位
else if E ∈ Vn
*ptr → a，查T(E, a)
if A → αi
pop()
将αi从右往左依次push（目的是保证Leftmost）
else
error
else if E = #
if ptr = 匹配串终结符
end
else
error