有人问我 LL(3) 是否是 LR(2) 的子集,反之亦然。
我成功地证明了 LL(3) 不是 LR(2) 的子集:
在 LL(3) 中,我们可以在读取开头的 3 个字符后识别规则。
在 LR(2) 中,我们可以在读取 2 个字符后识别规则。
因此,假设规则为空(upsilon),那么 LL(3) 会给我们比 LR(2) 更多的信息。因此,LL(3) 不包含在 LR(2) 中。
我如何证明另一种方式?
这https://cs.stackexchange.com/a/48声明这些语言集都不是其他语言的子集。
Upd:实际上它声明 LL(3) 是 LR(2) 的子集,抱歉。
根据我的编译器构建课程的幻灯片。
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) 不支持左递归语法。虽然它仍然不是一个证据