1

有人问我 LL(3) 是否是 LR(2) 的子集,反之亦然。

我成功地证明了 LL(3) 不是 LR(2) 的子集:

在 LL(3) 中,我们可以在读取开头的 3 个字符后识别规则。

在 LR(2) 中,我们可以在读取 2 个字符后识别规则。

因此,假设规则为空(upsilon),那么 LL(3) 会给我们比 LR(2) 更多的信息。因此,LL(3) 不包含在 LR(2) 中。

我如何证明另一种方式?

4

2 回答 2

1

https://cs.stackexchange.com/a/48声明这些语言集都不是其他语言的子集。

Upd:实际上它声明 LL(3) 是 LR(2) 的子集,抱歉。

于 2013-04-27T15:59:33.117 回答
0

根据我的编译器构建课程的幻灯片。

LR(k) = LR(1) 是任何 LL(k) 的超集

因此,LR(2) 或 LR(1) 是 LL(3) 或任何 LL(k) 的超集

从链接中查看图片。 语言图。LR(k), LL(k)

我无法证明,但很明显 LR(k) | k >= 1,比 LL(k) | 更强大 任何 k,因为 LL(k) 不支持左递归语法。虽然它仍然不是一个证据

于 2018-07-14T17:33:36.913 回答