这是语法 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, $

这不是shift-reduce冲突，肯定不是LR(1)文法？或者它是否会减少，因为 $ 和 u 都在 C 的后续集合中？

Answer 1

确实存在shift-reduce冲突。这是通过选择 shift 产生的状态机。冲突处于状态 4。

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

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

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

存在这些表示语法有歧义。

证明一般语法有歧义是一个不可判定的问题：没有算法可以解决它。幸运的是，这个并不难解决。