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

lenguaje ll1

Question

¿Alguien puede darme 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 sintáctico de LL y el análisis LR es que los analizadores LL comienzan en el símbolo inicial y tratan de aplicar producciones para llegar a la cadena objetivo, mientras que los analizadores LR comienzan en la cadena objetivo e intentan regresar al inicio símbolo.

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 de LL, el analizador elige continuamente entre dos acciones:

1. Predecir : basado en el extremo no terminal más a la izquierda y un número de tokens de anticipación, elija qué producción se debe aplicar para acercarse a la cadena de entrada.
2. Coincidencia : coincide con el símbolo de la terminal adivinada más a la izquierda con el símbolo de entrada no consumido más a la izquierda.

Como ejemplo, dada esta gramática:

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

Luego, dada la cadena int + int + int , un analizador LL (2) (que usa dos tokens de búsqueda anticipada) 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

Tenga en cuenta que en cada paso miramos 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 LR, hay dos acciones:

1. Shift : agrega el siguiente token de entrada a un buffer para su consideración.
2. Reducir : reduce una colección de terminales y no terminales en este búfer a algunos no terminales al invertir una producción.

Como ejemplo, un analizador LR (1) (con un token de búsqueda anticipada) podría analizar esa 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 mencionaste (LL y LR) tienen 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 sintáctico de LL y LR, acabo de terminar de enseñar un curso de compiladores y tengo algunos folletos y diapositivas de conferencias sobre el análisis 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 y LR Parsing Demystified afirma que el análisis LL se 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:

+ 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 principal diferencia entre los analizadores LL y LR:

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 la explicación en profundidad, ejemplos y conclusiones, consulte el artículo de Haberman.