每个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产生最右边的推导,其中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