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

Question

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

Answer 1

はい、LLとLRの両方がデータを左から右に解析するためです。そして、LL（1）は1つのトークンだけを見ているので、必然的にLR（1）でなければなりません。これは、LR（k）文法をLR（1）文法に変換できるため、LR（k）にも当てはまります。

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