5.2 LL(1) 文法与预测分析表

LL(1) 语法分析器（parser）从左到右读取输入，构造最左推导，并只用 1 个词法单元（token）的向前看（lookahead）选择产生式。它不是每份文法都必须获得的标签，而是一种严格的分析策略。它最大的优点是透明：文法、表、栈和当前词法单元就能完整解释语法分析器的每一次选择。

下面的表达式文法已改成右递归形式，适合自顶向下消费：

Expr     -> Term ExprTail
ExprTail -> + Term ExprTail | epsilon
Term     -> Factor TermTail
TermTail -> * Factor TermTail | epsilon
Factor   -> NUMBER | IDENT | ( Expr )

变换后的文法依然表示左结合的源语言表达式，只是解析树更适合预测（prediction）。构造 AST 时，语法分析器可以把 Tail 序列向左折叠，恢复源语言真正需要的结合性。

LL(1) 的选择条件

同一非终结符的两个候选右部必须能被一个向前看词法单元区分。定义：

SELECT(A -> alpha) = FIRST(alpha) - { epsilon }

若 epsilon 属于 FIRST(alpha)，还要把 FOLLOW(A) 加入 SELECT。一个文法是 LL(1)，当且仅当同一左部各候选产生式的 SELECT 集互不相交。

对 ExprTail：

FIRST(+ Term ExprTail) = { + }
FIRST(epsilon)         = { epsilon }
FOLLOW(ExprTail)       = { ), EOF }

SELECT(ExprTail -> + Term ExprTail) = { + }
SELECT(ExprTail -> epsilon)          = { ), EOF }

当前词法单元是 + 时选择第一条；是 ) 或 EOF 时选择空产生式，没有格子需要猜测。相反，下面的文法不是 LL(1)：

Stmt -> IDENT = Expr ; | IDENT ( Args ) ;

两条规则都从 IDENT 开始，一个词法单元无法选择。应左因子提取为 Stmt -> IDENT StmtRest，等看到 = 或 ( 后再决定。

构造并阅读预测分析表

预测表每行对应一个非终结符，每列对应一个终结符或 EOF。对每条 A -> alpha：

1. 对每个 a ∈ FIRST(alpha) - { epsilon }，把该产生式放进 M[A, a]。

2. 若 epsilon ∈ FIRST(alpha)，则对每个 b ∈ FOLLOW(A)，把该产生式放进 M[A, b]。

3. 若一个格子得到两条不同产生式，报告冲突（conflict），绝不悄悄保留其中一条。

表达式文法的关键行如下：

              NUMBER  IDENT  (   +   *   )   EOF
Expr          E->TE'  E->TE' E->TE'
ExprTail                         E'->+TE'  E'->eps E'->eps
Term          T->FT'  T->FT' T->FT'
TermTail                               T'->*FT' T'->eps T'->eps
Factor        F->num  F->id  F->(E)

空格子意味着当前词法单元不可能启动所需非终结符，它是语法分析错误，不是应该填默认值的位置。epsilon 产生式只能出现在 FOLLOW 许可的列中，这正是 FOLLOW 必不可少的原因。

表驱动的分析机器

机器维护一个栈，初始为 EOF Program，输入游标指向以 EOF 结尾的词法单元流。

• 栈顶是与向前看相同的终结符：弹栈并前进。

• 栈顶是与向前看不同的终结符：报错。

• 栈顶是非终结符 A：查询 M[A, lookahead]，将右部逆序压栈。

• 只有栈与输入同时到 EOF 才接受。

分析 NUMBER + NUMBER EOF 时，栈从 EOF Expr 变成 EOF ExprTail Term，再变成 EOF ExprTail TermTail Factor，后续依此类推。每次展开都是表查询，每次词法单元匹配都可见。缺点是裸表驱动语法分析器不会自然对应 AST 构造函数，所以工程中常用递归下降把同样的 LL(1) 选择直接写进代码。

冲突是文法设计的反馈

LL(1) 冲突精确说明语法分析器为什么不能只凭一个向前看作决定，并不必然代表语言本身错误。常见修复方式包括：

• 消除左递归。

• 对共享前缀做左因子提取。

• 为可选语法加入明确的分隔符。

• 把上下文相关的区别移动到语义阶段。

• 当语言确实需要时，换用更强的分析策略。

不要通过给产生式人为排序来“解决”冲突。那会让语法分析器行为依赖文件顺序，拒绝一个程序时也很难解释。应输出冲突格子、竞争产生式与各自 SELECT 集，把形式化失败转化为具体的语言设计讨论。

看一次 epsilon 决定

在输入 id ) 的 ExprTail 处，lookahead ) 不能启动 + Term ExprTail，却能跟在完成的 ExprTail 后，所以选择 epsilon。语法分析器只弹出 ExprTail，不消费 )；调用方仍要匹配分隔符。若 epsilon 分支吃掉 )，栈/输入契约就被破坏。

空表格子很有价值：它精确指出无法共存的非终结符与 lookahead。诊断应保留这对信息，而不只说“语法错误”。