概述
- 从左(L) 向右读入程序，最左(L)推导，采用一个(1)前看符号
- LL(1)就是向前只搜索1个符号，即与FIRST集匹配，如果FIRST为空则考虑FOLLOW集
算法基本思想：表驱动的分析算法
LL(1)分析算法
tokens[]; // all tokens
i=0;
stack = [S] // S是开始符号
while (stack != [])
if (stack[top] is a terminal t)
if (t==tokens[i++])
pop();
else error(…);
else if (stack[top] is a nonterminal T)
pop()
push(table[T, tokens[i]])LL(1)分析表的构造
- 前提：$NULLABLE$集、$FOLLOW$集
- 表头：行首是终结符，列首是非终结符，在非终结符 与 FIRST_S集合对应的终结符的交汇处标记上编号。
- 填写规则：$k: N -> β_1...β_n \ \ \ \{x_1, x_2, ..., x_n\}$，就在表的$(N, x_i),i = 1,2,...,n$上标记k。
案例1：
0: S -> N V N # {s, t, g, w}
1: N -> s # {s}
2: | t # {t}
3: | g # {g}
4: | w # {w}
5: V -> e # {e}
6: | d # {d}例如：对于0: s -> N V N对应的FIRST_S集合是{s, t, g, w}就在(S,s)、(S,t)、(S,g)、(S,w)上标记0，5: V-> e对应的FIRST_S集合是{e}，(V, e)标5，6: V -> d对应的FIRST_S集合是{d}，(V, d)标6。
| NT | s | t | g | w | e | d |
|---|---|---|---|---|---|---|
| S | 0 | 0 | 0 | 0 | ||
| N | 1 | 2 | 3 | 4 | ||
| V | 5 | 6 |
栈顶 待预测的串sdt
$ N V N ●sdt$
$ N V dt$
$ N t$
$ $
案例2：
0: Z -> d # {d}
1: | X Y Z # {a, c, d}
2: Y -> c # {c}
3: | # {a, c, d}
4: X -> Y # {c, a, d}
5: | a # {a}| NT | a | c | d |
|---|---|---|---|
| Z | 1 | 1 | 0, 1 |
| Y | 3 | 2, 3 | 3 |
| X | 4, 5 | 4 | 4 |
LL(1)分析表中的冲突
案例3：
稍微修改下文法，加入第5行。
0: S -> N V N # {s, t, g, w}
1: N -> s # {s}
2: | t # {t}
3: | g # {g}
4: | w # {w}
5: | w V # {w}
6: V -> e # {e}
7: | d # {d}LL(1)分析表 如下：
| NT | s | t | g | w | e | d |
|---|---|---|---|---|---|---|
| S | 0 | 0 | 0 | 0 | ||
| N | 1 | 2 | 3 | 4, 5 | ||
| V | 5 | 6 |
冲突检测： 对N的任意两条产生式规则N->β和N->γ，要求FIRST_S(β) ∩ FIRST_S(γ) ={}。
通过LL(1)分析表可以很明显的看出 案例2和案例3存在冲突，并且可以很容易看出，是哪两行、对哪一个非终结符存在冲突。
LL(1)分析表冲突处理
一、存在左递归 —— 消除左递归
左递归的分类：
- 直接左递归：P → Pa
- 间接左递归：P → Aa， A → …… → Pb
1. 直接左递归的消除
- 对于 P → Pa | b 形式(b可为空)，可以知道，推导结束的时候一定有一个b在最开始位置（如ba），后面是无数多个a，所以可以归纳得出如下的消除方法
P → bP';
P' → aP' | ε;- 更一般化的形如P → PX|Y（其中X和Y看作一个整体，比如：P → Pabc|ab|b，X就是abc，Y就是ab|b），可以归纳成如下形式：
X → abc
Y → ab|b
P → YP'; ：P → abP' | b P'
P' → XP' | ε; ： P' → abcP' | ε2. 间接左递归的消除
- 对于P → Aa | x1， A → …… → Pb | x2的形式
消除规则
- ① 若消除过程中出现了直接左递归，就按照直接左递归的方法，来消除
- ② 若产生式右部最左的符号是非终结符，且这个非终结符序号大于等于左部非终结符，则暂不处理（后面会处理到）
- ③ 若序号小于左部的非终结符，则用之前求到的式子的右部来替换
步骤伪代码
- 1.把文法G的所有非终结符按任意顺序排列，并编号
- 2.按顺序对非终结符进行遍历
- 3.将当前处理的非终结符中的序号小于等于它的非终结符按规则③进行替换（序号大于的按规则②处理）
- 4.消除i序号的非终结符的直接左递归（如果存在的话）
- 5.删除其中不可达的非终结符（从开始符开始，无法再推出的非终结符）
注意：
- 第一步对非终结符进行排序的序列不同，最后结果的产生式有可能不同，但它们是等价的
- 开始符号不能改变
- 该算法，能同时消除直接、间接左递归
3. 案例：
存在如下文法，消除左递归
- S → Qc | c
- Q → Rb | b
- R → Sa | a
解：
- 把文法G的所有非终结符按任意顺序排列，并编号： 1 R、2 Q、3 S
- 按上面的排列顺序，对这些非终结符进行遍历：
- 将当前处理的非终结符中的序号小于它的非终结符按规则 ③ 进行替换（序号大于等于的按规则 ② 处理）
R:
R的右部中的非终结符有S;
S的下标大于R，可以暂时不处理;
所以此时R改写为：R → Sa | a
----------------------------------------------
Q:
Q的右部中的非终结符有R;
R的下标小于Q，将R的右部替换进来;
所以此时Q改写为：Q → Sab | ab | b;
S的下标大于Q，可以暂时不处理;
所以此时Q改写为：Q → Sab | ab | b;
-----------------------------------------
S:
S的右部中的非终结符有Q;
Q的下标小于S，将Q的右部替换进来;
所以此时S改写为：S → Sabc |abc | bc | c
S的下标等于S，可以暂时不处理;
所以此时S改写为：S → Sabc |abc | bc | c- 消除直接左递归（如果存在的话）
S → Sabc |abc | bc | c
∴ X = abc，Y = abc | bc | c
∴ 消除直接左递归的结果是:
S → abcS' | bcS' | cS'
S' → abcS' | ε- 删除其中不可达的非终结符，这里就是Q、R了
S → abcS' | bcS' | cS'
S' → abcS' | ε二、存在左公因子 —— 提取左公因子
文法
0: X -> a Y
1: | a Z
2: Y -> b
3: Z -> c
//修改后:
0: X -> a X’
1: X’-> Y
2: | Z
3: Y -> b
4: Z -> c缺点
能分析的文法类型受限、往往需要文法的改写（冲突处理）。解决：→ LR分析算法
- - - 结束 - - -