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.