compiler-construction - すべてのLL（1）文法もLR（1）ですか？

Question

すべてのLL（1）文法もLR（1）ですか？

Answer 1

はい、LLとLRの両方がデータを左から右に解析するためです。LL（1）は1つのトークンのみを先読みするため、必ずLR（1）である必要があります。これはLR（k）にも当てはまります。LR（k）文法はLR（1）文法に変換できるため、k>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を参照してください。