LL(1) 预测分析 | Codeboy's Blog

形式陈述

LL(1) 预测分析从左向右读取 token，按最左推导展开上下文无关文法，并且只用一个尚未消费的 token 选择下一条产生式。“1”限制的是选择时看的未来输入数量，不是只保存一个历史状态。

先计算Nullable、FIRST 与 FOLLOW。沿用 FIRST 不含 $\varepsilon$ 的约定，对每条 $A\to\alpha$ 定义

\operatorname{SELECT}(A\to\alpha) =\operatorname{FIRST}(\alpha) \cup \begin{cases} \operatorname{FOLLOW}(A),&\alpha\Rightarrow^*\varepsilon,\\ \varnothing,&\text{否则}. \end{cases}

若 $a$ 属于这个集合，就把产生式放入表格 $M[A,a]$ 。同一格有两条不同产生式表示冲突；空格表示当前非终结符与输入不能合法接续。对已删除不可达规则的文法，所有表格至多一条规则，就是这里采用的 LL(1) 条件。

分析器的栈保存尚待匹配的符号。本页把栈顶写在左边，初始为 $S\$$ ，输入末尾也加 $\$$ ：

栈顶是非终结符 $A$ ：查询当前输入 $a$ 的表格，用其右部替换 $A$ ；右部左端仍在栈顶
栈顶是终结符：必须与当前 token 相同，然后同时弹栈、前进输入
栈顶与输入都到 $\$$ ：接受；遇到空表格或终结符不匹配则拒绝

选了空产生式时只弹掉非终结符，不能消费一个“空 token”。若底层数组把栈顶放在右端，就要反序压入右部，才能仍先处理左端。

直觉

解析栈是一份尚未完成的语法树前沿。展开非终结符会把一个待办项目换成几个更小项目；匹配终结符才真正跨过输入。已经消费的前缀与栈中的未完成部分合在一起，始终是从开始符号能推出的句型。

假设已经消费 $u$ ，忽略结束标记后的栈为 $\gamma$ 。核心不变量是 $S\Rightarrow^*u\gamma$ ，且算法始终展开 $\gamma$ 最左的非终结符。接受时 $\gamma$ 为空，所以 $S\Rightarrow^*u$ ，给出可靠性。无冲突的 SELECT 集再保证：若剩余输入确能由当前栈生成，合法推导所用的首条规则必在当前表格中，因此算法不会选错。

例子与边界

一张完整的小表

考虑只含加法和括号的表达式：

E\to TX,\qquad X\to+TX\mid\varepsilon, \qquad T\to\mathrm{id}\mid(E).

$X$ 表示一个项之后尚可继续的加法尾部。FIRST( $E$ )=FIRST( $T$ )= $\{\mathrm{id},(\}$ ，FIRST( $X$ )= $\{+\}$ ，且只有 $X$ 可空。FOLLOW( $E$ )=FOLLOW( $X$ )= $\{),\$\}$ ，FOLLOW( $T$ )= $\{+,),\$\}$ 。

所有表项如下，“—”是拒绝：

栈顶	id	(	+	)	$\$$
$E$	$E\to TX$	$E\to TX$	—	—	—
$X$	—	—	$X\to+TX$	$X\to\varepsilon$	$X\to\varepsilon$
$T$	$T\to\mathrm{id}$	$T\to(E)$	—	—	—

对 id+(id)，完整执行过程为：

栈，左端为顶	剩余输入	动作
$E\$$	id+(id) $\$$	展开 $E\to TX$
$TX\$$	id+(id) $\$$	展开 $T\to\mathrm{id}$
id $X\$$	id+(id) $\$$	匹配 id
$X\$$	+(id) $\$$	展开 $X\to+TX$
$+TX\$$	+(id) $\$$	匹配 +
$TX\$$	(id) $\$$	展开 $T\to(E)$
$(E)X\$$	(id) $\$$	匹配 (
$E)X\$$	id) $\$$	展开 $E\to TX$
$TX)X\$$	id) $\$$	展开 $T\to\mathrm{id}$
id $X)X\$$	id) $\$$	匹配 id
$X)X\$$	) $\$$	用空规则弹掉内层 $X$
$)X\$$	) $\$$	匹配 )
$X\$$	$\$$	用空规则弹掉外层 $X$
$\$$	$\$$	接受

输入 id+) 在匹配 + 后，栈顶是 $T$ 而当前 token 是 )； $M[T,)]$ 为空，故拒绝。不能为了让解析继续而随意把 $T$ 当作空串，因为它并不可空。

左因子提取解决的是决策时机

文法 $S\to aA\mid aB$ 的两条规则都以 $a$ 开头，所以 LL(1) 表在 $[S,a]$ 冲突。改为 $S\to aC,C\to A\mid B$ ，把决定推迟到消费 $a$ 之后；这次能否区分，要检查 $\operatorname{SELECT}(C\to A)$ 与 $\operatorname{SELECT}(C\to B)$ 是否不交；可空备选还会把 FOLLOW( $C$ ) 纳入自己的 SELECT 集。只有两者都不可空时，FIRST( $A$ ) 与 FIRST( $B$ ) 不交才直接给出所需条件。若 SELECT 集仍有交集，提取公共前缀本身不会创造不存在的信息。

左递归 $E\to E+T\mid T$ 若直接变成递归下降函数，会在消费输入前再次调用自身。可改写成上面的尾部形式，但语义动作应另行保证期望的结合性：用尾列表从左向右折叠可以构成左结合 AST；仅因文法改成右递归，就直接构造右结合运算树，会改变减法等运算的意思。

一个文法不是 LL(1)，不表示它有歧义，更不表示该语言没有其他 LL(1) 文法。冲突报告说明这张表无法唯一决定，不是语言歧义的通用判定器。

推论与应用

固定文法、预先建好表后，成功解析时每一步对应解析树上的展开或一个终结符匹配。对没有无效空推导环的 LL(1) 文法，树的大小随输入长度线性增长，因此解析时间为 $O(n)$ ，栈空间最坏为 $O(n)$ ；若把文法也视为输入，构表和每条长右部的压栈成本应另计。

本单元的主要路线先学这张表如何预测，再去看LR(0)怎样等到右部已经出现才归约。Earley保留多种待选推导，PEG则直接给备选规则一个优先次序；它们对“出现多个选择”的处理含义不同。

单元任务：给解析器一份可验收的交付

使用本页文法，完成四项工作：算出三个集合和全部非空表项；解析 id+(id+id) 并构造 AST；找出 id+) 的拒绝点；说明若把 $X\to\varepsilon$ 填进 $M[X,\mathrm{id}]$ 会发生什么。

解答的集合与表就是本页所列结果。合法输入外层展开为 $T\,X$ ，左 $T$ 产生第一个 id， $X$ 产生 + T X；右 $T$ 走括号规则，内层 $E$ 再形成一次加法。按前述左折叠构造得到 Add(Id, Add(Id, Id))；内层括号决定第二个 Add 必须作为右子树。两个尾部 $X$ 分别在 ) 与 $\$$ 前消失，任何一步都没有消费空串。

非法输入的拒绝点是已经读过 id+、当前 $[T,)]$ 的空格。把空规则误填进 $[X,\mathrm{id}]$ ，会使分析器在合法语言之外提前结束当前表达式；在完整独立解析中，之后还会因多余 id 与 $\$$ 不匹配而拒绝，但在嵌入式解析或错误恢复中可能错误切分输入。因此“最终仍报错”不能作为错误表项无害的理由。

验收时逐条核对：表项有 SELECT 依据；终结符匹配与展开分开；AST 保留括号决定的分组；错误位置来自第一条失效动作。进阶任务是在规范 LR(1)页解释一个 SLR 冲突，并在LALR页检查压缩状态是否保留这些区别。

参考资料

Stanford CS143, Lecture 7: Top-Down Parsing，slides 2–14、31–32：预测栈与构表；本页使用独立的加法/括号例子
Aho, Lam, Sethi, Ullman, Compilers, 2nd ed., 2007，§4.4：LL(1) 表、左递归消除与左因子提取

形式陈述 ​

一张完整的小表 ​

左因子提取解决的是决策时机 ​

单元任务：给解析器一份可验收的交付 ​

反向链接

形式陈述

一张完整的小表

左因子提取解决的是决策时机

单元任务：给解析器一份可验收的交付