Lesson 51: LL(1) 预测分析表构造与语法解析
练习任务
难度：中
用位掩码不动点迭代计算 FIRST/FOLLOW 集，自动构建预测分析表，实现表驱动 LL(1) 语法解析器，解析表达式 id + id * id。你需要完成七个核心组件：
token_id()— 将词法字符串映射为终结符枚举值（"id"→0,"+"→1, ...）- 栈操作 —
push/pop/empty/stack_str四个栈操作函数 compute_first()— 位掩码不动点迭代计算所有非终结符的 FIRST 集compute_follow()— 位掩码不动点迭代计算所有非终结符的 FOLLOW 集build_table()— 由 FIRST/FOLLOW 集自动构建二维预测分析表table[NT][T]print_sets()— 按指定格格式打印 FIRST 和 FOLLOW 集- LL(1) 解析主循环 — 使用预测分析表驱动栈式解析
验证方式：make test 编译运行，通过 diff 比对 expected_output.txt。
=== LL(1) Table-Driven Parser ===
Grammar: E→TE' E'→+TE'|ε T→FT' T'→*FT'|ε F→id|(E)
Input: id + id * id
=== FIRST Sets ===
FIRST(E) = {id, (}
FIRST(E') = {+}
FIRST(T) = {id, (}
FIRST(T') = {*}
FIRST(F) = {id, (}
=== FOLLOW Sets ===
FOLLOW(E) = {), $}
FOLLOW(E') = {), $}
FOLLOW(T) = {+, ), $}
FOLLOW(T') = {+, ), $}
FOLLOW(F) = {+, *, ), $}
[00] $E id+id*id$ E → T E'
[01] $E'T id+id*id$ T → F T'
...
[17] ACCEPT提示：LL(1) 的核心洞察是——每一步根据栈顶的语法符号和当前输入符号，查表决定使用哪条产生式。表由 FIRST/FOLLOW 自动生成，解析循环是通用引擎。学会这一课，你就理解了 yacc/bison 等解析器生成工具的底层原理。
核心知识点
- LL(1) 架构 — Left-to-right scan, Leftmost derivation, 1 lookahead。栈 + 输入缓冲 + 预测分析表的三角协作
- 位掩码表示 — 用
int的 6 个 bit 分别表示 6 个终结符。HAS(mask, t)和ADD(mask, t)宏实现 O(1) 集合操作 - RHS 逆序编码 — 每个产生式的 RHS 符号按逆序存储（最右侧符号在索引 0），
rhs_at(p, i)实现正向索引映射。LIFO 压栈天然配合逆序 - FIRST 不动点迭代 — 反复扫描产生式、传播非 ε 终结符，直到没有新元素加入。可空符号（E', T'）不阻断传播
- FOLLOW 不动点迭代 — 两条规则：FOLLOW(B) ⊇ FIRST(β)-{ε}，若 β 可空则 FOLLOW(B) ⊇ FOLLOW(A)。开始符号的 FOLLOW 初始含
$ - 预测分析表构造 — 对每个产生式 A→α：FIRST(α) 中的终结符填入产生式编号；若 α 可推导出 ε，FOLLOW(A) 中的终结符也填入
- 表驱动解析循环 — while 栈非空：栈顶是终结符则匹配消耗，是非终结符则查表展开。解析逻辑与文法完全分离
代码框架
c
#include <stdio.h>
#include <string.h>
#define STACK_SZ 64
#define PROD_CNT 8
/* ─── 符号定义 ─── */
enum { T_ID, T_PLUS, T_STAR, T_LPAR, T_RPAR, T_EOF, T_COUNT = 6 };
enum { NT_E, NT_Ee, NT_T, NT_Te, NT_F, NT_COUNT = 5 };
enum { SYM_TERM, SYM_NONTERM };
typedef struct { int type; int id; } Sym;
const char *tname[T_COUNT] = {"id", "+", "*", "(", ")", "$"};
const char *nname[NT_COUNT] = {"E", "E'", "T", "T'", "F"};
const char *prod_label[PROD_CNT] = {
"E → T E'", "E' → + T E'", "E' → ε",
"T → F T'", "T' → ε", "T' → * F T'",
"F → id", "F → ( E )",
};
/* RHS 展开序列：终结符用枚举值 (0-5), 非终结符 = id+100, -1=结束
* 逆序存储：rhs[p][0] 是最右侧符号，rhs[p][last] 是最左侧符号 */
#define NT(x) ((x) + 100)
int rhs[PROD_CNT][4] = {
{NT(NT_Ee), NT(NT_T), -1}, /* 0: E → T E' */
{NT(NT_Ee), NT(NT_T), T_PLUS, -1}, /* 1: E' → + T E' */
{-1}, /* 2: E' → ε */
{NT(NT_Te), NT(NT_F), -1}, /* 3: T → F T' */
{-1}, /* 4: T' → ε */
{NT(NT_Te), NT(NT_F), T_STAR, -1}, /* 5: T' → * F T' */
{T_ID, -1}, /* 6: F → id */
{T_RPAR, NT(NT_E), T_LPAR, -1}, /* 7: F → ( E ) */
};
int prod_lhs[PROD_CNT] = {NT_E, NT_Ee, NT_Ee, NT_T, NT_Te, NT_Te, NT_F, NT_F};
/* ─── FIRST / FOLLOW / 预测分析表（由学生填充） ─── */
int first[NT_COUNT], follow[NT_COUNT], table[NT_COUNT][T_COUNT];
/* ─── 位掩码辅助宏 ─── */
#define HAS(bitmask, t) ((bitmask) & (1 << (t)))
#define ADD(bitmask, t) ((bitmask) |= (1 << (t)))
/* ─── 工具函数（已提供） ─── */
static int rhs_len(int p) { int len = 0; while (rhs[p][len] != -1) len++; return len; }
static int rhs_at(int p, int i) { return rhs[p][rhs_len(p) - 1 - i]; }
static int is_terminal(int sym_id) { return sym_id >= 0 && sym_id < T_COUNT; }
static void input_str(int *tokens, int pos, int n, char *buf) {
int p = 0;
for (int i = pos; i < n; i++) {
const char *s = tname[tokens[i]];
while (*s) buf[p++] = *s++;
}
buf[p] = '\0';
}
static void set_str(int mask, char *buf) {
int p = 0;
buf[p++] = '{';
int first_item = 1;
for (int t = 0; t < T_COUNT; t++) {
if (HAS(mask, t)) {
if (!first_item) { buf[p++] = ','; buf[p++] = ' '; }
first_item = 0;
const char *s = tname[t];
while (*s) buf[p++] = *s++;
}
}
buf[p++] = '}'; buf[p] = '\0';
}
/* ─── TODO 1: token_id ─┌─────────────────────────── */
static int token_id(const char *s) {
// 遍历 tname 数组，strcmp 比较后返回枚举值
}
/* ─── TODO 2: 栈操作 ─┌───────────────────────────── */
Sym stack[STACK_SZ];
int top_idx = -1;
static void push(int type, int id) { /* Sym s = {type, id}; stack[++top_idx] = s; */ }
static Sym pop(void) { /* return stack[top_idx--]; */ }
static int empty(void) { /* return top_idx < 0; */ }
static void stack_str(char *buf) { /* 遍历 stack, 按 type 拼接 tname/nname */ }
/* ─── TODO 3: compute_first ─────────────────────── */
static void compute_first(void) {
// 初始化 first[] = 0
// do-while(changed) 循环：遍历产生式，传播非 ε 终结符
// E' 和 T' 可空（不阻断传播），其他非终结符不可空
}
/* ─── TODO 4: compute_follow ────────────────────── */
static void compute_follow(void) {
// 初始] = follow[] = 0, ADD(follow[NT_E], T_EOF)
// do-while(changed): 规则1 FIRST(β), 规则2 FOLLOW(A) 传播
}
/* ─── TODO 5: build_table ───────────────────────── */
static void build_table(void) {
// 初始化 table[nt][t] = -1；对每个产生式 p: A→α
// 若 α=ε: 对 b∈FOLLOW(A), table[A][b]=p
// 否则: 对 a∈FIRST(α), table[A][a]=p；若 α⇒*ε 还填 FOLLOW(A)
}
/* ─── TODO 6: print_sets ────────────────────────── */
static void print_sets(void) {
// 用 set_str() 打印 FIRST 集，空一行，再打印 FOLLOW 集
}
/* ─── 主解析循环 ─── */
int main(void) {
char *input[] = {"id", "+", "id", "*", "id", "$", NULL};
int tokens[16], n = 0;
for (int i = 0; input[i]; i++) tokens[n++] = token_id(input[i]);
compute_first();
compute_follow();
build_table();
printf("=== LL(1) Table-Driven Parser ===\n");
printf("Grammar: E→TE' E'→+TE'|ε T→FT' T'→*FT'|ε F→id|(E)\n");
printf("Input: id + id * id\n\n");
print_sets();
push(SYM_TERM, T_EOF);
push(SYM_NONTERM, NT_E);
/* TODO 7: LL(1) 解析主循环 */
return 0;
}阅读骨架后，尝试自己填充所有 TODO 标记的部分。核心挑战：rhs_at 的索引映射逻辑是什么？compute_first 中 do-while(changed) 如何检测收敛？compute_follow 中 beta_all_nullable 标志位如何维护？build_table 中 ε 产生式为什么需要查 FOLLOW 集？解析主循环中栈顶是终结符和非终结符的处理有何不同？
深度讲解
1. LL(1) 解析器架构
LL(1) 是自顶向下语法分析的经典算法：
LL(1) = Left-to-right scan + Leftmost derivation + 1 lookahead token核心思想：每一步根据栈顶的语法符号和当前输入符号，查表决定使用哪条产生式。
┌──────────────────────────────────────────────────────────┐
│ LL(1) 解析器架构 │
├──────────────────────────────────────────────────────────┤
│ 输入缓冲区 栈（LIFO） │
│ ┌───┬───┬───┬───┬───┬───┐ ┌───────┐ │
│ │id │ + │id │ * │id │ $ │ │ E │ ← 栈顶 │
│ └───┴───┴───┴───┴───┴───┘ │ $ │ ← 栈底 │
│ ↑ └───────┘ │
│ 前瞻指针 (ip) │
│ 预测分析表 table[NT][T] │
│ ┌─────┬─────┬─────┬─────┐ │
│ │ id │ + │ * │ ... │ │
│ ┌────┼─────┼─────┼─────┼─────┤ │
│ │ E │ 0 │ - │ - │ ... │ │
│ │ E' │ - │ 1 │ - │ ... │ │
│ │ T │ 3 │ - │ - │ ... │ │
│ └────┴─────┴─────┴─────┴─────┘ │
└──────────────────────────────────────────────────────────┘解析循环伪代码：
while (栈非空):
X = 栈顶符号, a = 当前输入符号
if X 是终结符:
if X == a: pop X, ip++
else: ERROR
if X 是非终结符:
p = table[X][a]
if p == -1: ERROR
else: pop X, 按产生式 p 的 RHS 压栈（从右到左）2. 文法与 RHS 编码
文法定义（消除左递归后）
E → T E' (0) T → F T' (3)
E' → + T E' (1) T' → * F T' (5)
E' → ε (2) T' → ε (4)
F → ( E ) (7)
F → id (6)为什么需要 E' 和 T'？ 原始文法 E → E + T | T 含左递归，会导致递归下降解析器无限循环。引入 E' 和 T' 消除左递归后，文法满足 LL(1) 要求。
RHS 逆序编码
RHS 数组使用不同编码区分终结符和非终结符，且逆序存储：
值范围 含义 示例
0 ~ 5 终结符枚举值 T_ID(0), T_PLUS(1)
100 ~ 104 非终结符(NT+100) NT(NT_E)=100, NT(NT_T)=102
-1 结束标记
示例：E' → + T E' 的 RHS = {NT_E'+100, NT_T+100, T_PLUS, -1}
= {101, 102, 1, -1}
↑ ↑
最右侧符号(E') ← 最右侧符号(+)
压栈顺序（i=0 到 -1）:
i=0: 101 → push(E') ← 最右侧先压入（栈底）
i=1: 102 → push(T) ← 中间
i=2: 1 → push(+) ← 最左侧最后压入（栈顶）IMPORTANT
正向向读取 RHS 符号必须使用 rhs_at(p, i)：return rhs[p][len - 1 - i]。直接索引 rhs[p][i] 会得到错误的符号顺序。但压栈时直接遍历 rhs[pid] 即可，因为逆序正是 LIFO 所需。
可空性判断
| 非终结符 | 可空？ | 原因 |
|---|---|---|
| E | 否 | E→TE'，T 不可空 |
| E' | 是 | E'→ε 产生式 |
| T | 否 | T→FT'，F 不可空 |
| T' | 是 | T'→ε 产生式 |
| F | 否 | F→id 或 F→(E)，均以终结符开头 |
本练习中可空性固定，可硬编码：X_id != NT_Ee && X_id != NT_Te。
3. FIRST 集——不动点迭代
位掩码表示与算法
每个 FIRST 集用一个 int 位掩码表示，6 个终结符映射到 6 个 bit：
bit 0→id bit 1→+ bit 2→* bit 3→( bit 4→) bit 5→$
HAS(mask, t): (mask) & (1 << (t))
ADD(mask, t): (mask) |= (1 << (t))不动点迭代算法：
初始化：first[NT] = ∅
重复直到收敛：
for 每个产生式 A → X1 X2 ... Xn:
for i = 1 to n:
if Xi 是终结符 a: first[A] ∪= {a}; break
else: first[A] ∪= first[Xi]; if Xi 不可空: break迭代过程追踪
初始: first[E]=∅, first[E']=∅, first[T]=∅, first[T']=∅, first[F]=∅
第1轮: F→id → first[F]={id}; F→(E) → first[F]={id,(}
第2轮: T→FT' → first[T]={id,(}; E→TE' → first[E]={id,(}
第3轮: E'→+TE' → first[E']={+}; T'→*FT' → first[T']={*}
第4轮: 无变化 → 收敛 ✓代码实现要点
c
static void compute_first(void) {
for (int i = 0; i < NT_COUNT; i++) first[i] = 0;
int changed;
do {
changed = 0;
for (int p = 0; p < PROD_CNT; p++) {
int A = prod_lhs[p], len = rhs_len(p);
for (int i = 0; i < len; i++) {
int X = rhs_at(p, i);
if (is_terminal(X)) {
if (!HAS(first[A], X)) { ADD(first[A], X); changed = 1; }
break;
} else {
int X_id = X - 100;
for (int t = 0; t < T_COUNT; t++)
if (HAS(first[X_id], t) && !HAS(first[A], t))
{ ADD(first[A], t); changed = 1; }
if (X_id != NT_Ee && X_id != NT_Te) break;
}
}
}
} while (changed);
}CAUTION
终结符后必须 break——终结符不可空，不能继续处理后续符号。否则 FIRST 集会错误地包含不应有的终结符。
4. FOLLOW 集——传播与可空性
FOLLOW(A) = { a | S ⇒* ...Aa..., a 是终结符 }。对每个产生式 A → αBβ：
规则1: FOLLOW(B) ⊇ FIRST(β) - {ε}
规则2: 若 β ⇒* ε，FOLLOW(B) ⊇ FOLLOW(A)迭代过程（关键步骤）
初始: follow[E]={$}, 其他=∅
产生式 0 (E→TE'):
B=T, β=E': first[E']={+}(规则1), E'可空(规则2) → follow[T]={+,$}
B=E', β=∅(规则2) → follow[E']={$}
产生式 1 (E'→+TE'):
B=T, β=E': first[E']={+}, E'可空 → follow[T]∪={+}, follow[T]∪=follow[E']
B=E', β=∅ → 无变化
... 继续迭代：F→(E)中 B=E β=) → follow[E]∪={)}
第2轮: follow[E]={),$}, follow[E']获取{)} → follow[E']={),$}
第2轮: 产生式7 (F→(E)): 规则2→follow[E]∪=follow[F] 但有)=first[E])...
继续迭代... 最终收敛最终结果：
| 非终结符 | FIRST | FOLLOW |
|---|---|---|
| E | ||
| E' | ||
| T | ||
| T' | ||
| F |
CAUTION
FOLLOW 迭代中最容易出错：beta_all_nullable 只在 β 中所有符号都可空时才为真。有一个终结符或不可空非终结符就立即置 0 并 break。
c
static void compute_follow(void) {
for (int i = 0; i < NT_COUNT; i++) follow[i] = 0;
ADD(follow[NT_E], T_EOF);
int changed;
do {
changed = 0;
for (int p = 0; p < PROD_CNT; p++) {
int A = prod_lhs[p], len = rhs_len(p);
for (int i = 0; i < len; i++) {
int X = rhs_at(p, i);
if (is_terminal(X)) continue;
int B = X - 100, beta_all_nullable = 1;
for (int j = i + 1; j < len; j++) {
int Y = rhs_at(p, j);
if (is_terminal(Y)) {
if (!HAS(follow[B], Y)) { ADD(follow[B], Y); changed = 1; }
beta_all_nullable = 0; break;
} else {
int Y_id = Y - 100;
for (int t = 0; t < T_COUNT; t++)
if (HAS(first[Y_id], t) && !HAS(follow[B], t))
{ ADD(follow[B], t); changed = 1; }
if (Y_id != NT_Ee && Y_id != NT_Te)
{ beta_all_nullable = 0; break; }
}
}
if (beta_all_nullable)
for (int t = 0; t < T_COUNT; t++)
if (HAS(follow[A], t) && !HAS(follow[B], t))
{ ADD(follow[B], t); changed = 1; }
}
}
} while (changed);
}5. 预测分析表构造
对每个产生式 A → α：
规则1: a ∈ FIRST(α) → table[A][a] = p
规则2: 若 α ⇒* ε, b ∈ FOLLOW(A) → table[A][b] = p构造过程示例：
E→TE': FIRST(TE')={id,(} → table[E][id]=0, table[E][(]=0
E'→ε: FOLLOW(E')={),$} → table[E'][)]=2, table[E'][$]=2
E'→+TE': FIRST(+TE')={+} → table[E'][+]=1
T'→ε: FOLLOW(T')={+,),$} → table[T'][+]=4, table[T'][)]=4, table[T'][$]=4
T'→*FT': FIRST(*FT')={*} → table[T'][*]=5
F→id: FIRST(id)={id} → table[F][id]=6
F→(E): FIRST((E))={(} → table[F][(]=7完整预测分析表：
| id | + | * | ( | ) | $ | |
|---|---|---|---|---|---|---|
| E | 0 | — | — | 0 | — | — |
| E' | — | 1 | — | — | 2 | 2 |
| T | 3 | — | — | 3 | — | — |
| T' | — | 4 | 5 | — | 4 | 4 |
| F | 6 | — | — | 7 | — | — |
（数字 = 产生式编号，— = -1 表示语法错误）
c
static void build_table(void) {
for (int nt = 0; nt < NT_COUNT; nt++)
for (int t = 0; t < T_COUNT; t++) table[nt][t] = -1;
for (int p = 0; p < PROD_CNT; p++) {
int A = prod_lhs[p], len = rhs_len(p);
if (len == 0) {
for (int t = 0; t < T_COUNT; t++)
if (HAS(follow[A], t)) table[A][t] = p;
continue;
}
int nullable_prod = 1;
for (int i = 0; i < len; i++) {
int X = rhs_at(p, i);
if (is_terminal(X)) { table[A][X] = p; nullable_prod = 0; break; }
int X_id = X - 100;
for (int t = 0; t < T_COUNT; t++)
if (HAS(first[X_id], t)) table[A][t] = p;
if (X_id != NT_Ee && X_id != NT_Te) { nullable_prod = 0; break; }
}
if (nullable_prod)
for (int t = 0; t < T_COUNT; t++)
if (HAS(follow[A], t)) table[A][t] = p;
}
}WARNING
先初始化 table[][] = -1！未显式填充的表项可能是随机值，导致不可预测行为。
6. 解析主循环——完整追踪
输入 id + id * id $ 的完整解析过程：
Step 栈（栈底→栈顶） 输入 动作
──── ───────────────────── ───────────────── ────────────
[00] $E id+id*id$ E → T E'
[01] $E'T id+id*id$ T → F T'
[02] $E'T'F id+id*id$ F → id
[03] $E'T'id id+id*id$ match id
[04] $E'T' +id*id$ T' → ε
[05] $E' +id*id$ E' → + T E'
[06] $E'T+ +id*id$ match +
[07] $E'T id*id$ T → F T'
[08] $E'T'F id*id$ F → id
[09] $E'T'id id*id$ match id
[10] $E'T' *id$ T' → * F T'
[11] $E'T'F* *id$ match *
[12] $E'T'F id$ F → id
[13] $E'T'id id$ match id
[14] $E'T' $ T' → ε
[15] $E' $ E' → ε
[16] $ $ match $
[17] ACCEPT ✓Step 0：栈 $ E（栈顶 E），查 table[E][id]=0 → E→TE'。pop E，压入 T 和 E'（rhs 逆序遍历）。 Step 4：栈顶 T'、输入 +，查 table[T'][+]=4 → T'→ε。pop T'，不压入。 Step 16-17：栈只剩 $，输入只剩 $。match → pop → 栈空 → ACCEPT。
IMPORTANT
解析逻辑与文法完全分离——文法信息全部编码在 table 中。换一个 LL(1) 文法，只需重新计算表，解析循环不需修改。这就是 yacc/bison 的核心原理。
参考解答
完整解答：ll1_parser.c（仅 TODO 部分，工具函数保持不变）
c
/* TODO 1: token_id — 字符串映射到终结符枚举 */
static int token_id(const char *s) {
for (int i = 0; i < T_COUNT; i++)
if (strcmp(s, tname[i]) == 0) return i;
return -1;
}
/* TODO 2: 栈操作 */
Sym stack[STACK_SZ];
int top_idx = -1;
static void push(int type, int id) {
Sym s = {type, id};
stack[++top_idx] = s;
}
static Sym pop(void) { return stack[top_idx--]; }
static int empty(void) { return top_idx < 0; }
static void stack_str(char *buf) {
int p = 0;
for (int i = 0; i <= top_idx; i++) {
const char *s = (stack[i].type == SYM_TERM)
? tname[stack[i].id] : nname[stack[i].id];
while (*s) buf[p++] = *s++;
}
buf[p] = '\0';
}
/* TODO 3: compute_first — 不动点迭代 */
static void compute_first(void) {
for (int i = 0; i < NT_COUNT; i++) first[i] = 0;
int changed;
do {
changed = 0;
for (int p = 0; p < PROD_CNT; p++) {
int A = prod_lhs[p], len = rhs_len(p);
for (int i = 0; i < len; i++) {
int X = rhs_at(p, i);
if (is_terminal(X)) {
if (!HAS(first[A], X)) { ADD(first[A], X); changed = 1; }
break;
} else {
int X_id = X - 100;
for (int t = 0; t < T_COUNT; t++)
if (HAS(first[X_id], t) && !HAS(first[A], t))
{ ADD(first[A], t); changed = 1; }
if (X_id != NT_Ee && X_id != NT_Te) break;
}
}
}
} while (changed);
}
/* TODO 4: compute_follow — 不动点迭代 */
static void compute_follow(void) {
for (int i = 0; i < NT_COUNT; i++) follow[i] = 0;
ADD(follow[NT_E], T_EOF);
int changed;
do {
changed = 0;
for (int p = 0; p < PROD_CNT; p++) {
int A = prod_lhs[p], len = rhs_len(p);
for (int i = 0; i < len; i++) {
int X = rhs_at(p, i);
if (is_terminal(X)) continue;
int B = X - 100, beta_all_nullable = 1;
for (int j = i + 1; j < len; j++) {
int Y = rhs_at(p, j);
if (is_terminal(Y)) {
if (!HAS(follow[B], Y)) { ADD(follow[B], Y); changed = 1; }
beta_all_nullable = 0; break;
} else {
int Y_id = Y - 100;
for (int t = 0; t < T_COUNT; t++)
if (HAS(first[Y_id], t) && !HAS(follow[B], t))
{ ADD(follow[B], t); changed = 1; }
if (Y_id != NT_Ee && Y_id != NT_Te)
{ beta_all_nullable = 0; break; }
}
}
if (beta_all_nullable)
for (int t = 0; t < T_COUNT; t++)
if (HAS(follow[A], t) && !HAS(follow[B], t))
{ ADD(follow[B], t); changed = 1; }
}
}
} while (changed);
}
/* TODO 5: build_table — 预测分析表 */
static void build_table(void) {
for (int nt = 0; nt < NT_COUNT; nt++)
for (int t = 0; t < T_COUNT; t++) table[nt][t] = -1;
for (int p = 0; p < PROD_CNT; p++) {
int A = prod_lhs[p], len = rhs_len(p);
if (len == 0) {
for (int t = 0; t < T_COUNT; t++)
if (HAS(follow[A], t)) table[A][t] = p;
continue;
}
int nullable_prod = 1;
for (int i = 0; i < len; i++) {
int X = rhs_at(p, i);
if (is_terminal(X)) { table[A][X] = p; nullable_prod = 0; break; }
int X_id = X - 100;
for (int t = 0; t < T_COUNT; t++)
if (HAS(first[X_id], t)) table[A][t] = p;
if (X_id != NT_Ee && X_id != NT_Te) { nullable_prod = 0; break; }
}
if (nullable_prod)
for (int t = 0; t < T_COUNT; t++)
if (HAS(follow[A], t)) table[A][t] = p;
}
}
/* TODO 6: print_sets — 打印 FIRST/FOLLOW */
static void print_sets(void) {
char buf[64];
printf("=== FIRST Sets ===\n");
for (int nt = 0; nt < NT_COUNT; nt++) {
set_str(first[nt], buf);
printf("FIRST(%s) = %s\n", nname[nt], buf);
}
printf("\n=== FOLLOW Sets ===\n");
for (int nt = 0; nt < NT_COUNT; nt++) {
set_str(follow[nt], buf);
printf("FOLLOW(%s) = %s\n", nname[nt], buf);
}
printf("\n");
}
/* TODO 7: LL(1) 解析主循环（main() 体中） */
push(SYM_TERM, T_EOF);
push(SYM_NONTERM, NT_E);
int ip = 0, step = 0;
char s_buf[64], i_buf[64];
while (!empty()) {
Sym s_top = stack[top_idx];
int cur = tokens[ip];
stack_str(s_buf); input_str(tokens, ip, n, i_buf);
printf("[%02d] %-18s %-16s ", step, s_buf, i_buf);
if (s_top.type == SYM_TERM) {
if (s_top.id == cur) {
printf("match %s\n", tname[cur]);
pop(); ip++;
} else { printf("ERROR\n"); return 1; }
} else {
int pid = table[s_top.id][cur];
if (pid < 0) { printf("ERROR\n"); return 1; }
printf("%s\n", prod_label[pid]);
pop();
for (int i = 0; rhs[pid][i] != -1; i++) {
if (rhs[pid][i] >= 100) push(SYM_NONTERM, rhs[pid][i] - 100);
else push(SYM_TERM, rhs[pid][i]);
}
}
step++;
}
stack_str(s_buf); input_str(tokens, ip, n, i_buf);
printf("[%02d] %-18s %-16s ACCEPT\n", step, s_buf, i_buf);工具函数（rhs_len, rhs_at, is_terminal, input_str, set_str）和全局数据定义均保持不变。以上实现完整填入 7 个 TODO，输出与 expected_output.txt 完全一致。
对照检查：
compute_first中终结符后break了吗？compute_follow中beta_all_nullable在 β 全可空时正确传播了FOLLOW(A)吗？build_table先全填了 -1 吗？ε 产生式正确查了FOLLOW(A)吗？解析循环压栈时直接遍历rhs[pid]（不用rhs_at）了吗？
课堂讨论
为什么 LL(1) 叫 "LL(1)" 而不是 "LL(k)"？ 本题文法只需 1 个前瞻符号即可确定产生式。某些文法（如 if-then-else 悬空 else）需要 k>1。LL(k) 表的大小随 k 指数增长，实际中很少用 k>1。
如果文法不是 LL(1) 的会怎样？ 构建预测分析表时出现"冲突"——同一
table[A][a]被两个产生式填充。如E → id | id ( E )，table[E][id]冲突。解决：提取左因子或消除左递归。FIRST 迭代为什么一定能收敛？ 每个 FIRST 集是有限集合（最多 T_COUNT 个元素），每次迭代只增增不减（单调递增）。有限集上的单调递增序列必然在有限步内停止。FOLLOW 同理。
位掩码的局限性是什么？
int只有 32 位，最多 32 个终结符。对大型文法（C 语言 100+ 关键字）需用long long或 bitset 数组。但本练习的 6 个终结符完美适配。为什么不直接用递归下降？ 递归下降更直观，但文法改变需重写代码。表驱动解析器把文法数据化——FIRST/FOLLOW/table 是数据，解析循环是通用引擎。这是 yacc/bison/ANTLR 的基础。
能否扩展为表达式求值器？ 可以！在每个展开动作时执行语义动作：
F→id查符号表取值，展开完成时执行运算。这就是语法制导翻译（Syntax-Directed Translation）。
课后练习
扩展词法分析器。修改输入为从 stdin 读取（而非硬编码字符串数组），使解析器可处理任意输入。跳过空白字符。
添加语法错误恢复。当前遇到语法错误直接
return 1。实现恐慌模式（Panic Mode）恢复：跳过输入直到同步符号（如)或$），弹出栈直到可恢复。提示：恐慌模式伪代码
if (pid < 0) { printf("ERROR: unexpected %s, skipping...\n", tname[cur]); ip++; while (!empty() && table[stack[top_idx].id][tokens[ip]] < 0) pop(); continue; }实现文法验证。编写
int is_ll1(void)检查预测分析表是否有多重定义（同一表项被填入多个不同产生式）。发现冲突时打印位置和涉及的产生式。打印分析表。编写
print_table()以表格形式打印完整预测分析表。表头为终结符名称，每行一个非终结符，空位显示-。
参考资料
- 《编译原理》(Dragon Book, Aho/Lam/Sethi/Ullman) 第 4.4 节 — LL(1) 语法与预测分析
- 《Engineering a Compiler》(Cooper/Torczon) 第 3.3 节 — Top-Down Parsing
- Wikipedia: LL parser — https://en.wikipedia.org/wiki/LL_parser
- Crafting Interpreters (Robert Nystrom) 第 6 章 — Parsing Expressions
- CS 6120: Advanced Compilers (Cornell) — 不动点迭代在编译器中的应用
"The parser is the heart of any compiler." — Alfred V. Aho