LL(1) 文法实战：3步构建预测分析表，解决王原生习题4.1歧义
LL(1) 文法实战：3步构建预测分析表，解决王原生习题4.1歧义
编译原理中，语法分析是理解程序结构的关键环节。而LL(1)文法作为自顶向下分析的重要工具，其预测分析表的构建往往是学习难点。本文将以王原生《编译原理》第三版第四章习题1为例，演示如何通过标准化流程解决文法歧义问题。
1. 问题描述与文法改写
原始文法G[S]如下：
S → a | ∧ | (T) T → T,S | S该文法存在两个典型问题：
- 左递归：T → T,S 会导致无限循环
- 公共左因子：S的三个产生式首符号不同，但T的两个产生式首符号重叠
1.1 消除左递归
采用标准左递归消除公式：
原规则：A → Aα | β 改写为：A → βA' A' → αA' | ε应用在T的产生式：
T → S T' T' → ,S T' | ε1.2 提取左因子
观察改写后的文法，已无公共左因子问题。最终改写结果为：
(1) S → a | ∧ | (T) (2) T → S T' (3) T' → ,S T' | ε2. FIRST集与FOLLOW集计算
2.1 FIRST集计算规则
| 非终结符 | 计算规则 | 结果 |
|---|---|---|
| S | a, ∧, ( 的FIRST | {a, ∧, (} |
| T | FIRST(S) | {a, ∧, (} |
| T' | , 的FIRST ∪ ε | {",", ε} |
2.2 FOLLOW集计算步骤
- 初始化：FOLLOW(S) = {#, ","}
- 传播规则：
- S出现在T → S T'，因此FOLLOW(S) ∪= FIRST(T') - {ε} ∪ FOLLOW(T)
- T' → ,S T' 导致FOLLOW(S) ∪= FIRST(T') - {ε}
最终结果：
FOLLOW(S) = {#, ",", )} FOLLOW(T) = {)} FOLLOW(T') = FOLLOW(T) = {)}3. 预测分析表构建与验证
3.1 LL(1)分析表构造算法
def build_predict_table(): for 产生式 A → α: for 每个终结符 a ∈ FIRST(α): 将 A → α 加入 M[A,a] if ε ∈ FIRST(α): for 每个终结符 b ∈ FOLLOW(A): 将 A → α 加入 M[A,b]3.2 完整预测分析表
| 非终结符 | a | ∧ | ( | ) | , | # |
|---|---|---|---|---|---|---|
| S | S→a | S→∧ | S→(T) | |||
| T | T→ST' | T→ST' | T→ST' | |||
| T' | T'→ε | T'→,ST' |
3.3 输入串(a,a)#分析过程
使用栈和输入缓冲区进行模拟：
| 步骤 | 栈 | 输入 | 动作 |
|---|---|---|---|
| 1 | #S | (a,a)# | S→(T) |
| 2 | #)T( | (a,a)# | 匹配 ( |
| 3 | #)T | a,a)# | T→ST' |
| 4 | #)T'S | a,a)# | S→a |
| 5 | #)T'a | a,a)# | 匹配 a |
| 6 | #)T' | ,a)# | T'→,ST' |
| 7 | #)T'S, | ,a)# | 匹配 , |
| 8 | #)T'S | a)# | S→a |
| 9 | #)T'a | a)# | 匹配 a |
| 10 | #)T' | )# | T'→ε |
| 11 | #) | )# | 匹配 ) |
| 12 | # | # | 接受 |
通过12步推导，最终判定(a,a)#是该文法的合法句子。这个标准化流程可推广到其他LL(1)文法分析场景，特别是处理嵌套结构和列表表达式时特别有效。