每个 LL(1) 文法也是 LR(1) 文法吗？

Question

每个 LL(1) 文法也是 LR(1) 文法吗？

Answer 1

是的，因为LL和LR都是从左到右解析数据；由于 LL(1) 只向前看一个标记，因此它必然是 LR(1)。对于LR(k)也是如此，其中k＞1。 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