Est chaque LL (1) grammaire également un LR (1)?

Question

est chaque LL (1) grammaire également un LR (1)?

Answer 1

Oui, puisque les deux LL et LR analysent les données de gauche à droite; et depuis LL (1) regarde vers l'avenir qu'un seul jeton, il doit nécessairement être un LR (1). Ceci est également vrai pour LR (k), où k> 1, étant donné un LR (k) la grammaire peut être transformé en une grammaire LR (1).

La différence entre LR et LL grammaires vient dans cette LR produit la dérivation extrême droite, où LL produit la dérivation gauche. Cela signifie donc qu'un analyseur LR peut en effet analyser un ensemble plus grand qu'une grammaire LL comme il se forme des feuilles.

Disons que nous avons des productions comme suit:

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

Alors LL (1) va analyser la chaîne (()):

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

Où que le LR (1) analysera comme suit:

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

Pour plus d'informations, voir: http://en.wikipedia.org/wiki/LL_parsing