compiler-construction - 每个LL(1)语法也是LR(1)吗？

Question

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

Answer 1

是的，因为LL和LR都从左到右解析数据；并且因为LL(1)仅向前看一个 token ，所以它必须一定是LR(1)。对于LR(k)(k> 1)也是如此，因为可以将LR(k)语法转换为LR(1)语法。

LR和LL语法之间的差异在于LR产生最右导数，而LL产生最左导数。因此，这意味着与LR语法相比，LR语法分析器实际上可以从叶子中解析出更大的集合。

可以说我们的作品如下:

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