¿Alguien puede darme un ejemplo simple de análisis LL en comparación con análisis LR?
225
En un nivel alto, la diferencia entre el análisis LL y el análisis LR es que los analizadores LL comienzan en el símbolo de inicio e intentan aplicar producciones para llegar a la cadena de destino, mientras que los analizadores LR comienzan en la cadena de destino e intentan volver al inicio símbolo.
Un análisis LL es una derivación de izquierda a derecha, más a la izquierda. Es decir, consideramos los símbolos de entrada de izquierda a derecha e intentamos construir una derivación más a la izquierda. Esto se hace comenzando en el símbolo de inicio y expandiendo repetidamente el extremo izquierdo no terminal hasta llegar a la cadena objetivo. Un análisis LR es una derivación de izquierda a derecha, lo que significa que escaneamos de izquierda a derecha e intentamos construir una derivación de la derecha. El analizador selecciona continuamente una subcadena de la entrada e intenta revertirla a un no terminal.
Durante un análisis LL, el analizador elige continuamente entre dos acciones:
Como ejemplo, dada esta gramática:
intLuego, dada la cadena int + int + int, un analizador LL (2) (que usa dos tokens de búsqueda anticipada) analizaría la cadena de la siguiente manera:
Production Input Action
---------------------------------------------------------
S int + int + int Predict S -> E
E int + int + int Predict E -> T + E
T + E int + int + int Predict T -> int
int + E int + int + int Match int
+ E + int + int Match +
E int + int Predict E -> T + E
T + E int + int Predict T -> int
int + E int + int Match int
+ E + int Match +
E int Predict E -> T
T int Predict T -> int
int int Match int
Accept
Observe que en cada paso miramos el símbolo más a la izquierda en nuestra producción. Si es un terminal, lo igualamos, y si no es un terminal, predecimos cuál será al elegir una de las reglas.
En un analizador LR, hay dos acciones:
Como ejemplo, un analizador LR (1) (con un token de búsqueda anticipada) podría analizar la misma cadena de la siguiente manera:
Workspace Input Action
---------------------------------------------------------
int + int + int Shift
int + int + int Reduce T -> int
T + int + int Shift
T + int + int Shift
T + int + int Reduce T -> int
T + T + int Shift
T + T + int Shift
T + T + int Reduce T -> int
T + T + T Reduce E -> T
T + T + E Reduce E -> T + E
T + E Reduce E -> T + E
E Reduce S -> E
S Accept
Se sabe que los dos algoritmos de análisis que mencionó (LL y LR) tienen características diferentes. Los analizadores LL tienden a ser más fáciles de escribir a mano, pero son menos potentes que los analizadores LR y aceptan un conjunto de gramáticas mucho más pequeño que los analizadores LR. Los analizadores LR vienen en muchos sabores (LR (0), SLR (1), LALR (1), LR (1), IELR (1), GLR (0), etc.) y son mucho más potentes. También tienden a ser mucho más complejos y casi siempre son generados por herramientas como yacco bison. Los analizadores LL también vienen en muchos sabores (incluido LL (*), que es utilizado por la ANTLRherramienta), aunque en la práctica LL (1) es el más utilizado.
Como un complemento descarado, si desea obtener más información sobre el análisis de LL y LR, acabo de terminar de impartir un curso de compiladores y tengo algunos folletos y diapositivas sobre análisis en el sitio web del curso. Me agradaría dar más detalles sobre cualquiera de ellos si cree que sería útil.
Josh Haberman en su artículo LL y LR Parsing Demystified afirma que el análisis LL corresponde directamente con la notación polaca , mientras que LR corresponde a la notación polaca inversa . La diferencia entre PN y RPN es el orden de atravesar el árbol binario de la ecuación:
Según Haberman, esto ilustra la principal diferencia entre los analizadores LL y LR:
Para obtener una explicación detallada, ejemplos y conclusiones, consulte el artículo de Haberman .
fuente
El LL usa de arriba hacia abajo, mientras que el LR usa el enfoque de abajo hacia arriba.
Si analiza un lenguaje de programación:
fuente
El análisis de LL es perjudicial, en comparación con LR. Aquí hay una gramática que es una pesadilla para un generador de analizador LL:
Un FunctionDef se ve exactamente como un FunctionDecl hasta que ';' o '{' se encuentra.
Un analizador LL no puede manejar dos reglas al mismo tiempo, por lo que debe elegir FunctionDef o FunctionDecl. Pero para saber cuál es el correcto tiene que buscar un ';' o '{'. En el momento del análisis gramatical, la búsqueda anticipada (k) parece ser infinita. En el momento del análisis es finito, pero podría ser grande.
Un analizador LR no tiene que mirar hacia adelante, ya que puede manejar dos reglas al mismo tiempo. Por lo tanto, los generadores de analizadores LALR (1) pueden manejar esta gramática con facilidad.
Dado el código de entrada:
Un analizador LR puede analizar el
sin importarle qué regla se reconoce hasta que encuentra un ';' o un '{'.
Un analizador LL se cuelga en el 'int' porque necesita saber qué regla se reconoce. Por lo tanto, debe buscar un ';' o '{'.
La otra pesadilla para los analizadores LL es la recursividad en una gramática. La recursividad izquierda es algo normal en las gramáticas, no hay problema para un generador de analizador LR, pero LL no puede manejarlo.
Así que tienes que escribir tus gramáticas de una manera no natural con LL.
fuente
Ejemplo de derivación más a la izquierda: una gramática G que no tiene contexto tiene las producciones
z → xXY (Regla: 1) X → Ybx (Regla: 2) Y → bY (Regla: 3) Y → c (Regla: 4)
Calcule la cadena w = 'xcbxbc' con la derivación más a la izquierda.
z ⇒ xXY (Regla: 1) ⇒ xYbxY (Regla: 2) ⇒ xcbxY (Regla: 4) ⇒ xcbxbY (Regla: 3) ⇒ xcbxbc (Regla: 4)
Derecha Más derivación Ejemplo: K → aKK (Regla: 1) A → b (Regla: 2)
Calcule la cadena w = 'aababbb' con la derivación más correcta.
K ⇒ aKK (Regla: 1) ⇒ aKb (Regla: 2) ⇒ aaKKb (Regla: 1) ⇒ aaKaKKb (Regla: 1) ⇒ aaKaKbb (Regla: 2) ⇒ aaKabbb (Regla: 2) ⇒ aababbb (Regla: 2)
fuente