SLR、LALR文法是否属于LR(1)文法及证明方法咨询

首先直接给两个问题的明确答案：

1. 所有SLR文法、LALR文法，都必然属于LR(1)文法，不存在例外。
2. 只要你能用SLR或者LALR方法构造出无冲突的分析表，就完全可以证明该文法是LR(1)文法，不需要额外构造完整的LR(1)项集。

包含关系的底层逻辑 #

LR文法族的严格包含关系是 LR(0) ⊂ SLR ⊂ LALR ⊂ LR(1)，这个关系是三类分析表的构造规则直接决定的：

• SLR文法的判定基于LR(0)项集族，仅在归约判断时用产生式左部非终结符的全局FOLLOW集做冲突过滤。这种过滤是非常保守的：它把所有可能在某个位置跟在该非终结符后的终结符都算作合法归约的向前看符号，没有结合当前项集的上下文做精准筛选。如果这种宽松判定下都没有移进-归约、归约-归约冲突，那么用LR(1)规则（为每个项携带当前上下文真正合法的后继符号作为向前看）构造分析表时，必然也不会出现冲突。
• LALR文法的判定基于合并核心相同的LR(1)项集：也就是把所有LR(0)部分一致、仅向前看集合不同的项集合并成一个。合并操作只会额外引入原本LR(1)表中不存在的归约-归约冲突，不会消除原有冲突。也就是说，如果合并后的LALR分析表没有冲突，那么未合并的原生LR(1)分析表肯定也没有冲突，对应的文法自然属于LR(1)文法。

验证方法的注意事项 #

你提到的「无向前看符号的SLR方法」是个常见误解：真正完全不依赖向前看符号的是LR(0)分析方法，SLR已经用全局FOLLOW集作为归约的向前看判断依据，只是不需要像LR(1)那样为每个项单独计算上下文相关的向前看符号，所以实现复杂度低很多。
用SLR/LALR方法做LR(1)的充分性验证时，只要注意一点就行：

这个验证是单向的：SLR/LALR无冲突可以证明文法是LR(1)，但SLR/LALR构造时出现冲突，不能证明文法不是LR(1)。

因为SLR的FOLLOW集过滤太宽松、LALR的项集合并可能引入假冲突，不少LR(1)文法在构造SLR/LALR表时会出现冲突，但构造完整LR(1)表时是无冲突的。如果你的目标只是证明某个文法属于LR(1)，只要跑出无冲突的SLR/LALR表就足够下结论，不用做更复杂的LR(1)项集构造；但如果SLR/LALR跑出了冲突，你又需要确认它是不是LR(1)文法，那就必须构造完整LR(1)表做最终判定。

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