Es cada LL (1) gramática también es un LR (1)?

Question

Es cada LL (1) gramática también es un LR (1)?

Answer 1

Sí, ya que ambos LL y LR analizan los datos de izquierda a derecha; y desde LL (1) mira hacia adelante solamente una ficha que debe ser necesariamente un LR (1). Esto también es cierto para LR (k), donde k> 1, ya que una gramática LR (k) se puede transformar en un (1) gramática LR.

La diferencia entre LR y LL gramáticas viene en que LR produce la derivación por la derecha, donde como LL produce la derivación por la izquierda. Así que esto significa que un analizador sintáctico LR puede, de hecho, análisis sintáctico de un conjunto mayor que una gramática LL, ya que se acumula de las hojas.

digamos que tenemos producciones de la siguiente manera:

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

A continuación, LL (1) analizará la (()) cadena:

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

Donde como el LR (1) va a analizar como sigue:

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

Para obtener más información, véase: http://en.wikipedia.org/wiki/LL_parsing