CLR(1)分析中ε产生式处理方法及给定文法CLR(1)判定求助

CLR(1)（即LR(1)）分析中，ε产生式（如A→ε）的处理核心是正确构造LR(1)项目和处理归约动作，具体要点如下：

• 项目表示：ε产生式对应的LR(1)项目写为[A→·, a]（等价于[A→·ε, a]），其中a是向前看符号。当项目变为[A→ε·, a]（点移至ε之后，与[A→·, a]等价）时，该项目为归约项目。
• 闭包构造：若项目集包含[X→α·Aβ, a]（A是含ε产生式的非终结符），则需添加[A→·, b]到闭包中，b取FIRST(βa)的所有符号（若β可推导出ε，还需包含a）。
• 归约动作：当分析器处于包含[A→ε·, a]的状态，且当前输入符号为a时，执行归约：无需弹出栈中符号（因ε是空推导），将A压入栈，再跳转到当前状态通过A的Goto转移得到的新状态。
• 冲突检查：需警惕ε产生式引发的移进-归约或归约-归约冲突——若同一项目集中，某个输入符号同时对应移进和归约动作，或多个归约动作，则文法不是CLR(1)文法。

首先明确拓广后的文法：

0. S' → S
1. S → A
2. A → AB
3. A → ε
4. B → aB
5. B → b

步骤1：计算FIRST和FOLLOW集 #

• FIRST集：
  FIRST(S') = FIRST(S) = FIRST(A) = {ε, a, b}，FIRST(B) = {a, b}
• FOLLOW集：
  FOLLOW(S') = {$}，FOLLOW(S) = {$}，FOLLOW(A) = {$, a, b}，FOLLOW(B) = {$, a, b}

步骤2：构造LR(1)项目集规范族（核心部分） #

• I0（初始项目集）：包含[S'→·S, $]、[S→·A, $]、[A→·AB, $]、[A→·ε, $]、[A→·AB, a]、[A→·ε, a]、[A→·AB, b]、[A→·ε, b]。仅存在归约动作（输入$/a/b时归约A→ε），无冲突。
• I1：[S'→S·, $]（接受项目，无冲突）。
• I2：包含[S→A·, $]（输入$时归约S→A）、[A→A·B, $/a/b]、[B→·aB, $/a/b]、[B→·b, $/a/b]。输入$时归约，输入a/b时移进，无冲突。
• I3：[A→AB·, $/a/b]（输入$/a/b时归约A→AB，无冲突）。
• I4：包含[B→a·B, $/a/b]、[B→·aB, $/a/b]、[B→·b, $/a/b]（输入a/b时移进，无冲突）。
• I5：[B→b·, $/a/b]（输入$/a/b时归约B→b，无冲突）。
• I6：[B→aB·, $/a/b]（输入$/a/b时归约B→aB，无冲突）。

结论 #

所有项目集均无移进-归约冲突或归约-归约冲突，因此该文法是CLR(1)文法。

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