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

Question

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

Answer 1

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

LR和LL语法的不同之处在于LR产生最右边的派生，而as 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