这是文法LR(1)吗？

Question

对于这个语法是否含糊不清有点困惑。

C' -> C
C -> d C u C
C -> d C
C -> ε

我试着为这个建立DFA，但我在其中一个州得到了这个：

C -> d C DOT u C, $
C -> d C DOT, $

这不是一个转移-减少冲突，所以它肯定意味着语法不是LR(1)？或者它是否减少了，因为$和u都在下面的C集合中？

Answer 1

它确实有一个转变-减少冲突。这是通过选择shift生成的状态机。冲突处于第四状态。

​

我应该指出，你的问题有点离题。语法可以是明确的，但仍然不能LR(1)。

但这一次恰好是模棱两可的。考虑一下字符串ddudu。两个最左边的导子是

C'->C->dCuC->ddCuCuC->dduCuC->ddudCuC->dduduC->ddudu
C'->C->dCuC->ddCuC->dduC->ddudCuC->dduduC->ddudu

这些语法的存在表明语法是模糊的。

证明一个普通的语法模棱两可是一个不可判定的问题:它不可能有算法。幸运的是，这个问题不难解决。