すべてのLL(1)文法もLR(1)ですか?
-
09-10-2019 - |
質問
すべてのLL(1)文法もLR(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
所属していません StackOverflow