compiler-construction - Is every LL(1) grammar also an LR(1)?

Question

Is every LL(1) grammar also an LR(1)?

Answer 1

是的，因为 LL 和 LR 都从左到右解析数据；并且由于 LL(1) 只向前看一个标记，它一定是 LR(1)。对于 LR(k) 也是如此，其中 k > 1，因为 LR(k) 文法可以转换为 LR(1) 文法。

LR 和 LL 语法之间的区别在于 LR 产生最右边的推导，而 LL 产生最左边的推导。所以这意味着 LR 解析器实际上可以解析比 LL 语法更大的集合，因为它是从叶子构建的。

假设我们的产品如下：

A -> "(" A ")" | "(" ")"

然后 LL(1) 将解析字符串(())：

(()) -> A
     -> "(" A ")"
     -> "(" "(" ")" ")"

其中 LR(1) 将解析如下：

Input  Stack          Action
(())   0       
())    0 '('
))     0 '(' '(' 
)      0 '(' '(' ')'  Reduce using A -> "(" ")"
)      0 '(' A
-      0 '(' A ')'    Reduce using A -> "(" A ")"
-      0  A           Accept

欲了解更多信息，请参阅：http ://en.wikipedia.org/wiki/LL_parsing