Ist jede LL (1) Grammatik auch ein LR (1)?

Question

Ist jede LL (1) Grammatik auch ein LR (1)?

Answer 1

Ja, da beide LL und LR die Daten von links nach rechts zu analysieren; und da LL (1) sieht vor nur ein Token muss unbedingt ein LR (1) sein. Dies gilt auch für die LR (k), wobei k> 1, da eine LR (k) Grammatik in eine LR (1) Grammatik umgewandelt werden.

Die Differenz zwischen LR und LL-Grammatiken kommt, daß in die äußerste rechte LR Ableitung erzeugt, wobei als LL die ganz linke Ableitung erzeugt. Dies bedeutet also, dass ein LR-Parser in der Tat Parst einen größeren Satz als eine LL Grammatik kann, wie es aus den Blättern aufbaut.

Lassen Sie uns sagen wir Produktionen wie folgt:

A -> "(" A ")" | "(" ")"

Dann LL (1) wird die Zeichenfolge (()) analysieren:

(()) -> A
     -> "(" A ")"
     -> "(" "(" ")" ")"

Wo, wie die LR (1) wird analysiert, wie folgt:

Input  Stack          Action
(())   0       
())    0 '('
))     0 '(' '(' 
)      0 '(' '(' ')'  Reduce using A -> "(" ")"
)      0 '(' A
-      0 '(' A ')'    Reduce using A -> "(" A ")"
-      0  A           Accept

Für weitere Informationen siehe: http://en.wikipedia.org/wiki/LL_parsing