如何用含ε的SLR(1)文法解析输入串()()？
2026-6-24
用SLR(1)解析文法
S → (S)S | ε与输入串()() 文法与待解析目标
- 文法：
S → (S)S | ε - 待解析输入串：
()()
问题解决步骤
1. 构造LR(0)项目集规范族
先定义增广文法S' → S，再生成项目集：
- I0：
S'→·S、S→·(S)S、S→·ε - I1：
S'→S·（接受状态） - I2：
S→(·S)S、S→·(S)S、S→·ε（I0中移进(得到） - I3：
S→(S·)S（I2中移进S得到） - I4：
S→(S)·S、S→·(S)S、S→·ε（I3中移进)得到） - I5：
S→(S)S·（I4中移进S得到） - I6：同I2（I2/I4中移进
(得到） - I7：同I3（I6中移进S得到）
- I8：同I4（I7中移进
)得到） - I9：同I5（I8中移进S得到）
2. 计算FOLLOW集
根据文法推导：
- 由增广文法
S'→S，得$属于FOLLOW(S) - 由
S→(S)S，得)属于FOLLOW(S)，且FOLLOW(S)传递到该产生式末尾的S，最终FOLLOW(S) = {),$}
3. 构建SLR(1)分析表
| 状态 | ( | ) | $ | S |
|---|---|---|---|---|
| 0 | s2 | 归约（S→ε） | 归约（S→ε） | g1 |
| 1 | - | - | acc | - |
| 2 | s6 | 归约（S→ε） | - | g3 |
| 3 | - | s4 | - | - |
| 4 | s6 | 归约（S→ε） | 归约（S→ε） | g5 |
| 5 | - | 归约（S→(S)S） | 归约（S→(S)S） | - |
| 6 | s6 | 归约（S→ε） | - | g7 |
| 7 | - | s8 | - | - |
| 8 | s6 | 归约（S→ε） | 归约（S→ε） | g9 |
| 9 | - | 归约（S→(S)S） | 归约（S→(S)S） | - |
注：sX表示移进并进入状态X；gX表示归约后转到状态X；acc表示接受；归约项对应产生式。
4. 模拟解析输入串()()（补结束符$）
初始栈：[0]，输入串：()()$
- 栈顶0，输入
(：执行s2，栈变为[0,2]，输入串变为)()$ - 栈顶2，输入
)：FOLLOW(S)包含)，归约S→ε，栈变为[0,2,3]，输入串仍为)()$ - 栈顶3，输入
)：执行s4，栈变为[0,2,3,4]，输入串变为()$ - 栈顶4，输入
(：执行s6，栈变为[0,2,3,4,6]，输入串变为) $ - 栈顶6，输入
)：归约S→ε，栈变为[0,2,3,4,6,7]，输入串仍为) $ - 栈顶7，输入
)：执行s8，栈变为[0,2,3,4,6,7,8]，输入串变为$ - 栈顶8，输入
$：FOLLOW(S)包含$，归约S→ε，栈变为[0,2,3,4,6,7,8,9]，输入串仍为$ - 栈顶9，输入
$：归约S→(S)S，弹出栈顶4个状态，栈变为[0,2,3,4]，执行g5后栈变为[0,2,3,4,5]，输入串$ - 栈顶5，输入
$：归约S→(S)S，弹出栈顶4个状态，栈变为[0]，执行g1后栈变为[0,1]，输入串$ - 栈顶1，输入
$：执行acc，解析完成。
内容的提问来源于stack exchange，提问作者Abhishek upadhyay
相关产品推荐
相关产品推荐
