parsing - 这是语法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 生成的状态机。冲突处于状态 4。

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

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

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

这些的存在说明语法是模棱两可的。

证明一般语法不明确是一个不可判定的问题：不可能有算法来解决它。令人高兴的是，这并不难解决。