编译原理冲刺 · 第 07 课 ⏱ 冲刺模式 · ≤1周

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

把 FIRST/FOLLOW 变成一张表,再用栈"自动"分析。对应教材第 4 章 4.3、4.5。
🎯 本课唯一目标
判断 LL(1) 文法、会构造预测分析表 M、会用分析栈模拟分析一个句子。
为什么学它? 这是第 4 章的"终点大题",常考一整套:消左递归 → 求 FIRST/FOLLOW → 填表 → 模拟分析。前两课的功夫,这一课变现。

一、LL(1) 是什么

L(从左到右扫描输入)、L(最左推导)、1(每次向前看 1 个符号就能决定用哪条产生式)。

判定 LL(1):对每个非终结符 A 的所有候选 A→α₁|…|αₙ,要求各 SELECT(A→αᵢ) 两两不相交(等价:FIRST 们互不相交;若某 αᵢ 可推 ε,则其余 FIRST 与 FOLLOW(A) 也不相交)。

二、构造预测分析表 M[A, 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] 空白:出错

四、老师示范一题

例题 对文法 E→TE′, E′→+TE′|ε, T→FT′, T′→*FT′|ε, F→(E)|i,构造预测分析表并分析 i+i*i
用 L06 求好的 FIRST/FOLLOW 填表(行=非终结符,列=终结符,空格=出错):
i+*()#
EE→TE′ E→TE′
E′ E′→+TE′ E′→εE′→ε
TT→FT′ T→FT′
T′ T′→εT′→*FT′ T′→εT′→ε
FF→i F→(E)
每个格子都唯一、无冲突 ⟹ 该文法是 LL(1) 文法
分析 i+i*i#(栈顶在右侧):
分析栈剩余输入动作
1# Ei+i*i#E→TE′
2# E′ Ti+i*i#T→FT′
3# E′ T′ Fi+i*i#F→i
4# E′ T′ ii+i*i#匹配 i
5# E′ T′+i*i#T′→ε
6# E′+i*i#E′→+TE′
7# E′ T ++i*i#匹配 +
8# E′ Ti*i#T→FT′
9# E′ T′ Fi*i#F→i
10# E′ T′ ii*i#匹配 i
11# E′ T′*i#T′→*FT′
12# E′ T′ F **i#匹配 *
13# E′ T′ Fi#F→i
14# E′ T′ ii#匹配 i
15# E′ T′#T′→ε
16# E′#E′→ε
17##✔ 接受
💡 关键动作(第 1 步):栈顶 E、输入 i,查 M[E,i]=E→TE′;弹 E、逆序压入 → 栈变 # E′ T(T 在顶,先处理)。

五、你来做

1. LL(1) 中的 "1" 指的是?
2. 预测分析表 M[A,a] 为空白,表示?
3. 分析栈顶为非终结符 X、当前输入 a 时,应?
4. 表驱动预测分析"成功(接受)"的条件是?
5. 判定 LL(1) 文法的核心条件是?
得分:0 / 5
填表:FIRST 进列;含 ε 再按 FOLLOW 进列
分析:终结符就匹配、非终结符就查表逆序压栈、双 # 接受
📺 主源推荐 哈工大《编译原理》语法分析(LL(1)/预测分析)讲 — 中国大学MOOC[1]
🙋 分析栈"逆序压栈"最容易压错方向——拿一个句子(比如 (i+i)*i)自己走一遍栈,发我核对。
  1. [1] LL(1) 判定、预测分析表构造、表驱动分析(4.3、4.5):陈火旺《程序设计语言编译原理》;分析表与分析过程为经典标准结果,交叉印证 龙书讲义