如何拯救有问题的LR(0)文法)
从“冲突”到“解决”：一个真实案例看懂SLR(1)如何拯救有问题的LR(0)文法
当你第一次构建LR(0)分析表时，可能会遇到一个令人困惑的现象：某些状态会同时要求"移进"和"归约"，或者出现多个可能的归约选项。这种冲突就像站在十字路口，不知道该往哪个方向走。本文将通过一个具体的表达式文法案例，带你亲历从LR(0)冲突到SLR(1)解决的完整过程，让你真正理解为什么我们需要SLR(1)这个"升级版"工具。
1. 案例准备：一个有问题的表达式文法
让我们考虑这个简单的表达式文法：
(1) E → E + T (2) E → T (3) T → a (4) T → ( E )这个文法看起来足够简单，但它却隐藏着LR(0)分析器无法处理的陷阱。为了构建分析表，我们首先需要拓广文法：
(0) S → E (1) E → E + T (2) E → T (3) T → a (4) T → ( E )提示：拓广文法通过添加一个新的开始符号S→E，确保整个分析过程有明确的接受状态。
2. LR(0)分析表的构建与冲突出现
按照LR(0)的构建流程，我们需要先构造项目集规范族。以下是关键状态的分析：
I0状态（初始状态）：
- S → •E
- E → •E + T
- E → •T
- T → •a
- T → •( E )
I1状态（经过E转移）：
- S → E•
- E → E• + T
这里已经能看到问题：I1状态同时包含一个归约项目(S→E•)和一个移进项目(E→E• + T)。在LR(0)分析中，这会导致移进-归约冲突——当看到输入符号"+"时，分析器不知道该移进还是归约。
类似地，I3状态也存在同样的问题：
- T → (•E)
- E → •E + T
- E → •T
- T → •a
- T → •( E )
3. SLR(1)的救援方案：引入FOLLOW集
SLR(1)通过引入FOLLOW集来解决这类冲突。FOLLOW集告诉我们：在某个非终结符后面可能出现的终结符有哪些。
让我们计算关键非终结符的FOLLOW集：
- FOLLOW(S) = {#}
- FOLLOW(E) = {+, ), #}
- FOLLOW(T) = {+, ), #}
现在，我们重新审视I1状态的冲突：
- 归约项目S→E•：只有在下一个输入符号∈FOLLOW(S)={#}时才归约
- 移进项目E→E• + T：只有在下一个输入符号是"+"时才移进
因为"#"和"+"没有交集，所以冲突被成功解决。分析表可以明确：
- 在I1状态，遇到"+"时移进
- 遇到"#"时归约
- 其他情况报错
4. 完整SLR(1)分析表的构建
让我们看看完整的SLR(1)分析表如何处理这个文法：
| 状态 | a | ( | ) | + | # | E | T |
|---|---|---|---|---|---|---|---|
| 0 | s5 | s3 | 1 | 2 | |||
| 1 | s6 | acc | |||||
| 2 | r2 | r2 | r2 | ||||
| 3 | s5 | s3 | 4 | 2 | |||
| 4 | s7 | s6 | |||||
| 5 | r3 | r3 | r3 | ||||
| 6 | s5 | s3 | 8 | ||||
| 7 | r4 | r4 | r4 | ||||
| 8 | r1 | r1 | r1 |
关键点解析：
- s表示移进并转移到指定状态
- r表示按指定产生式归约
- acc表示接受
- 空白表示错误
5. 为什么SLR(1)比LR(0)更强大
通过这个案例，我们可以总结SLR(1)的优势：
- 冲突解决能力：SLR(1)可以处理LR(0)无法解决的移进-归约和归约-归约冲突
- 前瞻信息利用：通过FOLLOW集提供1个符号的前瞻信息
- 文法覆盖范围：能处理更多实际编程语言中的文法结构
注意：SLR(1)不是万能的。当FOLLOW集有重叠时，冲突可能仍然存在，这时需要考虑更强大的LR(1)或LALR(1)分析器。
在实际编译器设计中，表达式解析、控制结构分析等场景经常会遇到这类冲突。理解SLR(1)的工作原理，能帮助你更好地设计和调试自己的文法规则。
