¿Cuál es la diferencia entre el análisis de LL y LR?

Question

¿Alguien me puede dar un ejemplo simple de análisis de LL versus análisis de LR?

Answer 1

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 y tratan de aplicar producciones para llegar a la cadena objetivo, mientras que los analizadores LR comienzan en la cadena objetivo e intentan llegar de vuelta en el símbolo de inicio.

Un análisis de 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 situada más a la izquierda. Esto se hace comenzando por el símbolo de inicio y expandiendo repetidamente el extremo no terminal más a la izquierda hasta que lleguemos a la cadena objetivo. Un análisis LR es una derivación de izquierda a derecha, más a la derecha, lo que significa que escaneamos de izquierda a derecha e intentamos construir una derivación a la derecha. El analizador selecciona continuamente una subcadena de la entrada e intenta invertirla de nuevo a un no terminal.

Durante un análisis sintáctico LL, el analizador elige continuamente entre dos acciones:

1. Predecir: Basado en el extremo izquierdo no terminal y un número de fichas de búsqueda hacia delante, elija el que la producción se debe aplicar a estar más cerca de la cadena de entrada.
2. Coincidir: coincide con el símbolo del terminal adivinado más a la izquierda con el símbolo de entrada no consumido más a la izquierda.

Como un ejemplo, dado esta gramática:

• S → E
• E → T + E
• E → T
• T → int

Entonces Dado que int + int + int cadena, un LL (2) analizador (que utiliza dos símbolos de búsqueda hacia delante) sería analizar 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 

en cuenta que en cada paso nos fijamos en el símbolo más a la izquierda en nuestra producción. Si se trata de un terminal, lo emparejamos, y si no es un terminal, predecimos lo que será al elegir una de las reglas.

En un analizador sintáctico LR, hay dos acciones:

1. Shift: Añadir el siguiente token de entrada a una memoria intermedia para su consideración.
2. Reducir: Reduzca una colección de terminales y no terminales en este búfer de regreso a algunos no terminales invirtiendo una producción.

A modo de ejemplo, un LR (1) analizador (con una ficha de búsqueda hacia delante) podría analizar esa misma cadena como sigue:

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 

Los dos algoritmos de análisis sintáctico que usted ha mencionado (LL y LR) son sabe que tiene diferentes características.Los analizadores de LL tienden a ser más fáciles de escribir a mano, pero son menos poderosos que los analizadores de LR y aceptan un conjunto de gramáticas mucho más pequeño que los analizadores de 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 se generan con herramientas como yacc o bison. Los analizadores LL también vienen en muchos sabores (incluyendo LL (*), que es usado por la herramienta ANTLR), aunque en la práctica LL (1) es el más utilizado.

Como un enchufe desvergonzado, si desea obtener más información sobre el análisis de LL y LR, acabo de terminar de enseñar un curso de compiladores y tengo some handouts and lecture slides on parsing en el sitio web del curso. Estaría encantado de elaborar sobre cualquiera de ellos si crees que sería útil.

Answer 2

Josh Haberman en su artículo LL and LR Parsing Demystified afirma que el análisis LL se corresponde directamente con Polish Notation, mientras que LR corresponde a Reverse Polish Notation. La diferencia entre PN y RPN es el orden de atravesar el árbol binario de la ecuación:

+ 1 * 2 3 // Polish (prefix) expression; pre-order traversal. 
1 2 3 * + // Reverse Polish (postfix) expression; post-order traversal. 

Según Haberman, esto ilustra la diferencia principal entre LL y LR analizadores:

La principal diferencia entre cómo operan los analizadores LL y LR es que un analizador LL emite un recorrido de preordenamiento del árbol de análisis sintáctico y un analizador LR genera un recorrido posterior al pedido.

Para obtener una explicación detallada, ejemplos y conclusiones, consulte Haberman's article.