L(从左到右扫描输入)、L(最左推导)、1(每次向前看 1 个符号就能决定用哪条产生式)。
判定 LL(1):对每个非终结符 A 的所有候选 A→α₁|…|αₙ,要求各 SELECT(A→αᵢ) 两两不相交(等价:FIRST 们互不相交;若某 αᵢ 可推 ε,则其余 FIRST 与 FOLLOW(A) 也不相交)。
对每条产生式 A→α:
① 对每个 a∈FIRST(α):令 M[A,a] = A→α。
② 若 ε∈FIRST(α):对每个 b∈FOLLOW(A):令 M[A,b] = A→α。
③ 其余格子空白 = 出错。若有格子被填了两条产生式(冲突)→ 不是 LL(1)。
一个分析栈(栈底放 #,再放开始符 S),输入串末尾加 #。设栈顶 X、当前输入 a:
① X = a = # ⟹ 分析成功(接受)
② X = a(终结符) ⟹ 匹配:弹栈,读入下一个输入符
③ X 是终结符但 ≠ a ⟹ 出错
④ X 是非终结符 ⟹ 查 M[X,a]:
若 M[X,a]=X→Y₁…Yk:弹出 X,把 Y₁…Yk 逆序压栈(Y₁ 在栈顶;ε 则不压)
若 M[X,a] 空白:出错
i+i*i。| i | + | * | ( | ) | # | |
|---|---|---|---|---|---|---|
| E | E→TE′ | E→TE′ | ||||
| E′ | E′→+TE′ | E′→ε | E′→ε | |||
| T | T→FT′ | T→FT′ | ||||
| T′ | T′→ε | T′→*FT′ | T′→ε | T′→ε | ||
| F | F→i | F→(E) |
i+i*i#(栈顶在右侧):
| 步 | 分析栈 | 剩余输入 | 动作 |
|---|---|---|---|
| 1 | # E | i+i*i# | E→TE′ |
| 2 | # E′ T | i+i*i# | T→FT′ |
| 3 | # E′ T′ F | i+i*i# | F→i |
| 4 | # E′ T′ i | i+i*i# | 匹配 i |
| 5 | # E′ T′ | +i*i# | T′→ε |
| 6 | # E′ | +i*i# | E′→+TE′ |
| 7 | # E′ T + | +i*i# | 匹配 + |
| 8 | # E′ T | i*i# | T→FT′ |
| 9 | # E′ T′ F | i*i# | F→i |
| 10 | # E′ T′ i | i*i# | 匹配 i |
| 11 | # E′ T′ | *i# | T′→*FT′ |
| 12 | # E′ T′ F * | *i# | 匹配 * |
| 13 | # E′ T′ F | i# | F→i |
| 14 | # E′ T′ i | i# | 匹配 i |
| 15 | # E′ T′ | # | T′→ε |
| 16 | # E′ | # | E′→ε |
| 17 | # | # | ✔ 接受 |
# E′ T(T 在顶,先处理)。(i+i)*i)自己走一遍栈,发我核对。