如何判断一个文法是否为LALR(1)?

发布网友发布时间：2024-10-02 08:44

共1个回答

热心网友时间：2024-11-30 14:43

【答案】：G1仅产生串da、bdc、dc和和bda。
读入缀活前缀d后到达的的LR(1)项目集簇为：
状态i：{A→d.,a;B→d.,c}
缀读入活前缀bd后到达的LR(1)项目集簇为：
状态j：{A→d.,c;B→d.,a}
显然，在构造的LR(1)项目集簇中不存在移进-归约或归约-归约冲突。因此，该文法为LR(1)态的。而上述状态i和和j为同心集，合并后为{A→d.,a/c;B→d.,a/c}，则出现了新是的归约-归约冲突，而这个冲突在合并前是没有的。因此，该文法不是LALR(1)的。
是很明显，该文法也不是SLR(1)的，因为在读入活前缀d后到达的LR(0)项目集簇(状态)为{A→d.;B→d.}而，包含了两个归约项目，而follow(A)∩follow(B)={a,c}
是≠Φ，因此，存在归约-归约冲突，故而该文法不是SLR(1)