自顶向下基本思想#

面向目标，寻找输入串的最左推导：从开始符（根）出发，按最左推导顺序，试图根据当前输入单词选择产生式，逐步构造分析树。

FIRST(α)——首符号集#

FIRST(α) = { a | α ⇒* aβ, a∈V_T }，若 α⇒*ε 则 ε∈FIRST(α)。

计算规则：

1. X∈V_T：FIRST(X)={X}。
2. X→a…（a∈V_T）：a∈FIRST(X)。
3. X→ε：ε∈FIRST(X)。
4. X→Y₁Y₂…Yₙ：
   • 把 FIRST(Y₁)−{ε} 加入 FIRST(X)；
   • 若 Y₁⇒*ε，再加 FIRST(Y₂)−{ε}；依次类推；
   • 若 Y₁…Yₙ 全部能⇒ε，则把 ε 也加入 FIRST(X)。
5. 反复迭代直到所有 FIRST 集不再变化。

FOLLOW(A)——后继符号集#

FOLLOW(A) = { a | S ⇒* …Aa…, a∈V_T }；若 S⇒*…A，则 #∈FOLLOW(A)。

计算规则（对所有出现在右部的非终结符反复迭代）：

1. #∈FOLLOW(S)（S 为开始符，# 为结束符）。
2. A→αBβ 且 β 不能⇒ε：FOLLOW(B) ⊇ FIRST(β)。
3. A→αB：FOLLOW(B) ⊇ FOLLOW(A)。
4. A→αBβ 且 β⇒*ε：FOLLOW(B) ⊇ (FIRST(β)−{ε}) ∪ FOLLOW(A)。

注意：FOLLOW 集中永远不含 ε（要么是终结符，要么是 #）。

SELECT(A→α)——选择集#

• α 不能⇒ε：SELECT(A→α) = FIRST(α)。
• α ⇒*ε：SELECT(A→α) = (FIRST(α)−{ε}) ∪ FOLLOW(A)。

含义#

• 第一个 L：从左到右扫描输入串。
• 第二个 L：生成最左推导。
• 1：向前看 1 个符号即可确定用哪个产生式。

判定充要条件#

对每个非终结符 A 的任意两个不同候选式 A→α | β： SELECT(A→α) ∩ SELECT(A→β) = ∅（且 α、β 不能同时⇒ε）。

判别步骤#

1. 列出各非终结符能否⇒ε。
2. 计算 FIRST、FOLLOW 集。
3. 计算各规则 SELECT 集。
4. 检查同一左部各规则的 SELECT 集是否两两不相交——全不相交则为 LL(1) 文法。

🧮 判定例（表达式文法 G[E] 是 LL(1)）#

1
E→TE'    E'→+TE'|ε    T→FT'    T'→*FT'|ε    F→(E)|i

• SELECT(E’→+TE’)={+}，SELECT(E’→ε)={#,)}，交集=∅ ✓
• SELECT(T’→FT’)={}，SELECT(T’→ε)={+,#,)}，交集=∅ ✓
• SELECT(F→(E))={(}，SELECT(F→i)={i}，交集=∅ ✓
• 故 G[E] 是 LL(1) 文法。

1. 消除左递归#

直接左递归 A→Aα|β：

1
A → βA'
2
A' → αA'|ε

一般式 A→Aα₁|…|Aαₙ|β₁|…|βₘ ⟹

1
A → β₁A'|…|βₘA'
2
A' → α₁A'|…|αₙA'|ε

间接左递归：先按非终结符排序，用代入法把间接左递归化成直接左递归，再消除，最后删除多余产生式。

例：S→Qc|c, Q→Rb|b, R→Sa|a，按 S,Q,R 排序，代入得 R→Rbca|bca|ca|a，消直接左递归得 R→bcaM|caM|aM, M→bcaM|ε。

2. 提取左公共因子#

A→αβ|αγ ⟹

1
A → αA'
2
A' → β|γ

一般式 A→αβ₁|…|αβₙ|γ₁|…|γₘ ⟹

1
A → αA'|γ₁|…|γₘ
2
A' → β₁|…|βₙ

提取后可能出现不可达的多余产生式，必须删除。

预测分析器三部分#

1. 预测分析表（矩阵） M[A,a]
2. 先进后出栈（分析栈，存语法符号）
3. 预测分析程序（总控）

构造预测分析表 M[A,a]#

对产生式 A→α，凡 a∈SELECT(A→α)，就把 →α 填入 M[A,a]。所有空格填 error。

表达式文法 G[E] 的预测分析表：

预测分析算法#

1
初始化：#、S 进栈（# 在底，S 在顶）
2
do {
3
  X = 栈顶符号；a = 当前输入符号；
4
  if (X∈V_T ∪ {#}) {
5
     if (X==a) { 若 X≠#，弹栈并前移输入指针; }
6
     else error();
7
  } else {                    // X 是非终结符
8
     if (M[X,a]==Y₁Y₂…Yₖ) { 弹出 X; 把 Yₖ…Y₂Y₁ 逆序压栈; }
9
     else error();
10
  }
11
} while (X≠#)

🧮 分析 i+i*i# 过程（片段）#