¿Es cada LL (1) gramática también una LR (1)?

Question

¿Son todas las LL (1) gramática también LR (1)?

Answer 1

Sí, dado que tanto LL como LR analizan los datos de izquierda a derecha; y dado que LL (1) anticipa solo una ficha, necesariamente debe ser una LR (1). Esto también es cierto para LR (k), donde k> 1, ya que una gramática LR (k) se puede transformar en una gramática LR (1).

La diferencia entre las gramáticas LR y LL se debe a que LR produce la derivación más a la derecha, mientras que LL produce la derivación más a la izquierda. Entonces, esto significa que un analizador LR puede, de hecho, analizar un conjunto mayor que una gramática LL a medida que se acumula desde las hojas.

digamos que tenemos producciones de la siguiente manera:

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

Entonces LL (1) va a analizar la cadena (()):

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

Donde como la LR (1) analizará la siguiente manera:

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

Para más información ver: http://en.wikipedia.org/wiki/LL_parsing