关于文法S→(S)S | S→ε的LR(0)与SLR(1)判定咨询

目标文法 #

产生式定义：

• S → ( S ) S
• S → ε

LR(0)判定 #

LR(0)文法要求所有DFA状态中不存在任何移进-归约或归约-归约冲突。
你提到的DFA状态里，包含S → .（ε产生式对应的项目）的状态同时存在针对(的移进项，这直接构成移进-归约冲突。因此该文法不属于LR(0)。

SLR(1)判定 #

SLR(1)通过归约项目的FOLLOW集消解冲突，步骤如下：

1. 计算FOLLOW(S)：
   • 初始包含输入结束符$
   • 从产生式S → ( S ) S可知，S的后续符号包括)
   • 最终FOLLOW(S) = { ')', '$' }
2. 冲突消解验证：
   冲突状态中，移进符号为(，而归约项目S → .的FOLLOW集是)和$。由于(不在FOLLOW(S)中，可通过SLR(1)规则区分动作：
   • 输入符号为(时执行移进
   • 输入符号为)或$时执行归约
     冲突完全消除，因此该文法属于SLR(1)。

内容的提问来源于stack exchange，提问作者Asad Masood