Analizador LR

En informática, los analizadores LR son un tipo de analizador ascendente que analiza lenguajes deterministas independientes del contexto en tiempo lineal. Hay varias variantes de analizadores LR: analizadores SLR, analizadores LALR, analizadores Canonical LR(1), analizadores Minimal LR(1) y analizadores GLR. Los analizadores LR pueden ser generados por un generador de analizadores a partir de una gramática formal que define la sintaxis del lenguaje a analizar. Son ampliamente utilizados para el procesamiento de lenguajes informáticos.

Un analizador LR (Lderivación de izquierda a derecha, Derechamás a la derecha al revés) lee el texto de entrada de izquierda a derecha sin respaldo hacia arriba (esto es cierto para la mayoría de los analizadores), y produce una derivación hacia la derecha a la inversa: hace un análisis de abajo hacia arriba, no un análisis de LL de arriba hacia abajo o un análisis ad-hoc. El nombre LR suele ir seguido de un calificador numérico, como en LR(1) o, a veces, LR(k). Para evitar retroceder o adivinar, el analizador LR puede echar un vistazo a los símbolos de entrada de anticipación k antes de decidir cómo analizar los símbolos anteriores. Normalmente, k es 1 y no se menciona. El nombre LR suele estar precedido por otros calificadores, como en SLR y LALR. Knuth sugirió que la notación LR(k) para una gramática representara "traducible de izquierda a derecha con k enlazado. "

Los analizadores LR son deterministas; producen un solo análisis correcto sin conjeturas ni retrocesos, en tiempo lineal. Esto es ideal para lenguajes informáticos, pero los analizadores LR no son adecuados para lenguajes humanos que necesitan métodos más flexibles pero inevitablemente más lentos. Algunos métodos que pueden analizar lenguajes libres de contexto arbitrarios (p. ej., Cocke–Younger–Kasami, Earley, GLR) tienen el peor rendimiento de O(n< sup>3) tiempo. Otros métodos que retroceden o producen múltiples análisis pueden incluso tomar un tiempo exponencial cuando adivinan mal.

Las propiedades anteriores de L, R y k en realidad son compartidas por todos los analizadores shift-reduce, incluidos los analizadores de precedencia. Pero por convención, el nombre LR representa la forma de análisis inventada por Donald Knuth y excluye los métodos de precedencia anteriores y menos potentes (por ejemplo, el analizador de precedencia de operadores). Los analizadores LR pueden manejar una gama más amplia de idiomas y gramáticas que los analizadores de precedencia o el análisis LL de arriba hacia abajo. Esto se debe a que el analizador LR espera hasta que ha visto una instancia completa de algún patrón gramatical antes de comprometerse con lo que ha encontrado. Un analizador LL tiene que decidir o adivinar lo que está viendo mucho antes, cuando solo ha visto el símbolo de entrada más a la izquierda de ese patrón.

Resumen

Árbol de análisis de abajo hacia arriba, por ejemplo A*2 + 1

Árbol de parse arriba construido en pasos numerados

Un analizador LR escanea y analiza el texto de entrada en un paso hacia adelante sobre el texto. El analizador construye el árbol de análisis de forma incremental, de abajo hacia arriba y de izquierda a derecha, sin adivinar ni retroceder. En cada punto de este pase, el analizador ha acumulado una lista de subárboles o frases del texto de entrada que ya se han analizado. Esos subárboles aún no están unidos porque el analizador aún no ha llegado al extremo derecho del patrón de sintaxis que los combinará.

En el paso 6 de un análisis de ejemplo, solo "A*2" ha sido analizado, incompletamente. Solo existe la esquina inferior izquierda sombreada del árbol de análisis. Todavía no existe ninguno de los nodos del árbol de análisis con el número 7 o superior. Los nodos 3, 4 y 6 son las raíces de subárboles aislados para la variable A, el operador * y el número 2, respectivamente. Estos tres nodos raíz se mantienen temporalmente en una pila de análisis. La parte restante sin analizar del flujo de entrada es "+ 1".

Desplazar y reducir acciones

Al igual que con otros analizadores shift-reduce, un analizador LR funciona mediante una combinación de pasos de cambio y pasos de reducción.

• A Cambio paso avanza en el flujo de entrada por un símbolo. Ese símbolo cambiado se convierte en un nuevo árbol de pares de un solo nodo.
• A Reducir paso aplica una regla de gramática completa a algunos de los árboles pares recientes, uniéndose a ellos como un árbol con un nuevo símbolo raíz.

Si la entrada no tiene errores de sintaxis, el analizador continúa con estos pasos hasta que se ha consumido toda la entrada y todos los árboles de análisis se han reducido a un solo árbol que representa una entrada legal completa.

Los analizadores LR se diferencian de otros analizadores shift-reduce en cómo deciden cuándo reducir y cómo elegir entre reglas con finales similares. Pero las decisiones finales y la secuencia de los pasos de cambio o reducción son las mismas.

Gran parte de la eficiencia del analizador LR se debe a que es determinista. Para evitar adivinar, el analizador LR a menudo mira hacia adelante (hacia la derecha) en el siguiente símbolo escaneado, antes de decidir qué hacer con los símbolos escaneados previamente. El escáner léxico trabaja uno o más símbolos por delante del analizador. Los símbolos de anticipación son el 'contexto de la derecha' para la decisión de análisis.

Pila de análisis de abajo hacia arriba

Parser de arriba abajo en el paso 6

Al igual que otros analizadores shift-reduce, un analizador LR espera perezosamente hasta que ha escaneado y analizado todas las partes de alguna construcción antes de confirmar cuál es la construcción combinada. El analizador actúa inmediatamente sobre la combinación en lugar de esperar más. En el ejemplo del árbol de análisis, la frase A se reduce a Valor y luego a Productos en los pasos 1 a 3 tan pronto como se ve la anticipación *, en lugar de esperar más tarde para organizar esas partes del árbol de análisis. Las decisiones sobre cómo manejar A se basan únicamente en lo que el analizador y el analizador ya han visto, sin tener en cuenta las cosas que aparecen mucho más adelante a la derecha.

Las reducciones reorganizan los elementos analizados más recientemente, inmediatamente a la izquierda del símbolo de anticipación. Entonces, la lista de cosas ya analizadas actúa como una pila. Esta pila de análisis crece hacia la derecha. La base o parte inferior de la pila está a la izquierda y contiene el fragmento de análisis más antiguo que se encuentra más a la izquierda. Cada paso de reducción actúa solo en los fragmentos de análisis más nuevos y más a la derecha. (Esta pila de análisis acumulativo es muy diferente a la pila de análisis predictivo que crece hacia la izquierda y que utilizan los analizadores de arriba hacia abajo).

Pasos de análisis de abajo hacia arriba, por ejemplo, A*2 + 1

El paso 6 aplica una regla gramatical con varias partes:

Productos → Productos * Valor

Esto coincide con la parte superior de la pila que contiene las frases analizadas "... Productos * Valor". El paso de reducción reemplaza esta instancia del lado derecho de la regla, "Productos * Valor" por el símbolo del lado izquierdo de la regla, aquí un Productos más grande. Si el analizador genera árboles de análisis completos, los tres árboles para Productos internos, * y Valor se combinan mediante una nueva raíz de árbol para Productos. De lo contrario, los detalles semánticos de los productos internos y el valor se envían a algún paso posterior del compilador, o se combinan y guardan en el nuevo símbolo de productos.

Pasos de análisis de LR, por ejemplo, A*2 + 1

En los analizadores LR, las decisiones de cambio y reducción se basan potencialmente en la pila completa de todo lo que se ha analizado previamente, no solo en un único símbolo de pila superior. Si se hace de una manera poco inteligente, eso podría conducir a analizadores muy lentos que se vuelven cada vez más lentos para entradas más largas. Los analizadores LR hacen esto con velocidad constante, al resumir toda la información relevante del contexto izquierdo en un solo número llamado LR(0) estado del analizador. Para cada método de análisis de gramática y LR, hay un número fijo (finito) de dichos estados. Además de contener los símbolos ya analizados, la pila de análisis también recuerda los números de estado alcanzados por todo hasta esos puntos.

En cada paso del análisis, todo el texto de entrada se divide en una pila de frases analizadas previamente, un símbolo actual de anticipación y el texto restante sin analizar. La siguiente acción del analizador está determinada por su número de estado LR(0) actual (en el extremo derecho de la pila) y el símbolo de anticipación. En los pasos a continuación, todos los detalles negros son exactamente iguales que en otros analizadores de reducción de desplazamiento que no son LR. Las pilas de analizadores LR agregan la información de estado en púrpura, resumiendo las frases negras a su izquierda en la pila y qué posibilidades de sintaxis esperar a continuación. Los usuarios de un analizador LR generalmente pueden ignorar la información de estado. Estos estados se explican en una sección posterior.

En el paso inicial 0, el flujo de entrada "A*2 + 1" se divide en

• una sección vacía en la pila de pares,
• texto "A" escaneado como un id símbolo, y
• el texto no escaneado restante "*2 + 1".

La pila de análisis comienza manteniendo solo el estado inicial 0. Cuando el estado 0 ve el id anticipado, sabe cambiar ese id a la pila y escanear el siguiente ingrese el símbolo * y avance al estado 9.

En el paso 4, el flujo de entrada total "A*2 + 1" actualmente se divide en

• la sección "A *" con 2 frases apiladas Productos y *,
• texto "2" escaneado como un int símbolo, y
• el texto no escaneado restante " + 1".

Los estados correspondientes a las frases apiladas son 0, 4 y 5. El estado actual más a la derecha de la pila es el estado 5. Cuando el estado 5 ve el int anticipado, sabe cambiarlo int en la pila como su propia frase, y escanea el siguiente símbolo de entrada +, y avanza al estado 8.

En el paso 12, se ha consumido todo el flujo de entrada, pero solo se ha organizado parcialmente. El estado actual es 3. Cuando el estado 3 ve el avance eof, sabe aplicar la regla gramatical completa

Sums → Sums + Productos

combinando las tres frases más a la derecha de la pila para Sums, + y Products en una sola cosa. El estado 3 en sí mismo no sabe cuál debería ser el próximo estado. Esto se encuentra volviendo al estado 0, justo a la izquierda de la frase que se está reduciendo. Cuando el estado 0 ve esta nueva instancia completa de Sums, avanza al estado 1 (nuevamente). Esta consulta de estados más antiguos es la razón por la que se mantienen en la pila, en lugar de mantener solo el estado actual.

Gramática para el ejemplo A*2 + 1

Los analizadores LR se construyen a partir de una gramática que define formalmente la sintaxis del lenguaje de entrada como un conjunto de patrones. La gramática no cubre todas las reglas del idioma, como el tamaño de los números o el uso consistente de nombres y sus definiciones en el contexto de todo el programa. Los analizadores LR utilizan una gramática libre de contexto que se ocupa solo de patrones locales de símbolos.

La gramática de ejemplo utilizada aquí es un pequeño subconjunto del lenguaje Java o C:

r0: Objetivo → Sums eof

r1: Sums → Sums + Productos

r2: Sums → Productos

r3: Productos → Productos * Valor

r4: Productos → Valor

r5: Valor → int

r6: Valor → id

Los símbolos terminales de la gramática son los símbolos de varios caracteres o 'tokens' encontrado en el flujo de entrada por un escáner léxico. Aquí estos incluyen + * y int para cualquier constante entera, y id para cualquier nombre de identificador, y eof para el final del archivo de entrada. A la gramática no le importa cuáles son los valores de int o la ortografía de id, ni los espacios en blanco o los saltos de línea. La gramática usa estos símbolos terminales pero no los define. Siempre son nodos de hoja (en el extremo inferior tupido) del árbol de análisis.

Los términos en mayúscula como Sums son símbolos no terminales. Estos son nombres para conceptos o patrones en el idioma. Se definen en la gramática y nunca aparecen en el flujo de entrada. Siempre son nodos internos (encima de la parte inferior) del árbol de análisis. Solo ocurren como resultado de que el analizador aplique alguna regla gramatical. Algunos no terminales se definen con dos o más reglas; Estos son patrones alternativos. Las reglas pueden referirse a sí mismas, lo que se denomina recursivo. Esta gramática usa reglas recursivas para manejar operadores matemáticos repetidos. Las gramáticas para lenguajes completos usan reglas recursivas para manejar listas, expresiones entre paréntesis y declaraciones anidadas.

Cualquier lenguaje informático dado puede ser descrito por varias gramáticas diferentes. Un analizador LR(1) puede manejar muchas pero no todas las gramáticas comunes. Por lo general, es posible modificar manualmente una gramática para que se ajuste a las limitaciones del análisis sintáctico LR(1) y la herramienta generadora.

La gramática de un analizador LR debe ser inequívoca en sí misma o debe complementarse con reglas de precedencia de desempate. Esto significa que solo hay una forma correcta de aplicar la gramática a un ejemplo legal dado del idioma, lo que da como resultado un árbol de análisis único con un solo significado y una secuencia única de acciones de cambio/reducción para ese ejemplo. El análisis sintáctico LR no es una técnica útil para los lenguajes humanos con gramáticas ambiguas que dependen de la interacción de las palabras. Los lenguajes humanos se manejan mejor con analizadores como el analizador LR generalizado, el analizador Earley o el algoritmo CYK que puede calcular simultáneamente todos los árboles de análisis posibles en una sola pasada.

Tabla de análisis para la gramática de ejemplo

La mayoría de los analizadores LR se basan en tablas. El código del programa del analizador es un bucle genérico simple que es el mismo para todas las gramáticas y lenguajes. El conocimiento de la gramática y sus implicaciones sintácticas están codificados en tablas de datos inmutables llamadas tablas de análisis (o tablas de análisis sintáctico). Las entradas en una tabla muestran si cambiar o reducir (y según qué regla gramatical), para cada combinación legal de estado del analizador y símbolo de anticipación. Las tablas de análisis también indican cómo calcular el siguiente estado, dado solo un estado actual y un siguiente símbolo.

Las tablas de análisis son mucho más grandes que la gramática. Las tablas LR son difíciles de calcular con precisión a mano para gramáticas grandes. Por lo tanto, se derivan mecánicamente de la gramática mediante alguna herramienta generadora de analizadores como Bison.

Dependiendo de cómo se generan los estados y la tabla de análisis, el analizador resultante se denomina analizador SLR (LR simple), analizador LALR (LR anticipado) o analizador LR canónico. Los analizadores LALR manejan más gramáticas que los analizadores SLR. Los analizadores LR canónicos manejan aún más gramáticas, pero usan muchos más estados y tablas mucho más grandes. La gramática de ejemplo es SLR.

Las tablas de análisis de LR son bidimensionales. Cada estado actual del analizador LR(0) tiene su propia fila. Cada siguiente símbolo posible tiene su propia columna. Algunas combinaciones de estado y siguiente símbolo no son posibles para flujos de entrada válidos. Estas celdas en blanco activan mensajes de error de sintaxis.

La mitad izquierda Acción de la tabla tiene columnas para los símbolos de terminales anticipados. Estas celdas determinan si la siguiente acción del analizador es cambiar (para indicar n) o reducir (por la regla gramatical r_n).

La mitad derecha Ir a de la tabla tiene columnas para símbolos no terminales. Estas celdas muestran a qué estado avanzar, después de que el Lado izquierdo de alguna reducción haya creado una nueva instancia esperada de ese símbolo. Esto es como una acción de cambio pero para no terminales; el símbolo de terminal anticipado no cambia.

La columna de la tabla "Reglas actuales" documenta las posibilidades de significado y sintaxis para cada estado, tal como lo resuelve el generador del analizador. No está incluido en las tablas reales utilizadas en el momento del análisis. El marcador • (punto rosa) muestra dónde se encuentra ahora el analizador, dentro de algunas reglas gramaticales parcialmente reconocidas. Las cosas a la izquierda de • han sido analizadas, y las cosas a la derecha se esperan pronto. Un estado tiene varias de estas reglas actuales si el analizador aún no ha reducido las posibilidades a una sola regla.

En el estado 2 anterior, el analizador acaba de encontrar y cambiar el + de la regla gramatical

r1: Sums → Sums + • Productos

La siguiente frase esperada es Productos. Los productos comienzan con los símbolos de terminal int o id. Si la búsqueda anticipada es cualquiera de esos, el analizador los cambia y avanza al estado 8 o 9, respectivamente. Cuando se ha encontrado un producto, el analizador avanza al estado 3 para acumular la lista completa de sumandos y encontrar el final de la regla r0. Un producto también puede comenzar con un valor no terminal. Para cualquier otra búsqueda anticipada o no terminal, el analizador anuncia un error de sintaxis.

En el estado 3, el analizador acaba de encontrar una frase de Productos, que podría ser de dos posibles reglas gramaticales:

r1: Sums → Sums + Productos •

r3: Productos → Productos • * Valor

La elección entre r1 y r3 no se puede decidir simplemente mirando hacia atrás en las frases anteriores. El analizador tiene que comprobar el símbolo de anticipación para saber qué hacer. Si la búsqueda anticipada es *, está en la regla 3, por lo que el analizador cambia en el * y avanza al estado 5. Si la búsqueda anticipada es eof, está al final de la regla 1 y la regla 0, por lo que el analizador está listo.

En el estado 9 anterior, todas las celdas que no están en blanco y que no contienen errores son para la misma reducción r6. Algunos analizadores ahorran tiempo y espacio en la tabla al no verificar el símbolo de anticipación en estos casos simples. Los errores de sintaxis se detectan algo más tarde, después de algunas reducciones inofensivas, pero aún antes de la siguiente acción de cambio o decisión del analizador.

Las celdas individuales de la tabla no deben contener múltiples acciones alternativas, de lo contrario, el analizador sería no determinista con conjeturas y retroceso. Si la gramática no es LR(1), algunas celdas tendrán conflictos de cambio/reducción entre una posible acción de cambio y una acción de reducción, o conflictos de reducción/reducción entre múltiples reglas gramaticales. Los analizadores LR(k) resuelven estos conflictos (siempre que sea posible) comprobando símbolos de anticipación adicionales además del primero.

Bucle analizador LR

El analizador LR comienza con una pila de análisis casi vacía que contiene solo el estado de inicio 0, y con la búsqueda anticipada que contiene el primer símbolo escaneado del flujo de entrada. Luego, el analizador repite el siguiente paso de bucle hasta que finaliza o se atasca en un error de sintaxis:

El estado superior en la pila de análisis es algún estado s, y la búsqueda actual es algún símbolo de terminal t. Busque la siguiente acción del analizador en la fila s y la columna t de la tabla de acciones anticipadas. Esa acción es Shift, Reduce, Done o Error:

• Cambio n:

Cambio de la terminal concordada t en la pila de parse y escanear el siguiente símbolo de entrada en el amortiguador.

Empuja el próximo estado n en la pila de pares como el nuevo estado actual.

• Reducir r_m: Aplicar la regla de gramática r_m: Lhs → S₁ S₂... S_L

Retire los símbolos L más iguales (y parse árboles y números de estado asociados) de la pila de parse.

Esto expone un estado anterior p que esperaba una instancia del símbolo Lhs.

Únete a los árboles de parse L juntos como un árbol de pares con nuevo símbolo de raíz Lhs.

Buscar el próximo estado n de la fila p y columna Lhs de la mesa LHS Goto.

Empuja el símbolo y el árbol para Lhs en la pila de parse.

Empuja el próximo estado n en la pila de pares como el nuevo estado actual.

La cabeza de mira y el flujo de entrada permanecen sin cambios.

• Hecho: t es eof marcador. Fin de parsing. Si la pila del estado contiene sólo el éxito del informe del estado inicial. De lo contrario, reporte un error de sintaxis.
• Error: reporte un error de sintaxis. El parser termina, o intenta alguna recuperación.

La pila del analizador LR generalmente almacena solo los estados del autómata LR(0), ya que los símbolos gramaticales pueden derivarse de ellos (en el autómata, todas las transiciones de entrada a algún estado están marcadas con el mismo símbolo, que es el símbolo asociado con este estado). Además, estos símbolos casi nunca son necesarios ya que el estado es lo único que importa al tomar la decisión de análisis.

Análisis del generador LR

La mayoría de los usuarios de generadores de analizadores LR pueden omitir esta sección del artículo.

Estados LR

El estado 2 en la tabla de análisis de ejemplo es para la regla parcialmente analizada

r1: Sums → Sums + • Productos

Esto muestra cómo llegó aquí el analizador, al ver Sums y luego + mientras buscaba Sums más grandes. El marcador • ha avanzado más allá del comienzo de la regla. También muestra cómo el analizador espera completar finalmente la regla, al encontrar a continuación un Productos completo. Pero se necesitan más detalles sobre cómo analizar todas las partes de esos Productos.

Las reglas analizadas parcialmente para un estado se denominan sus "elementos LR(0) centrales". El generador del analizador agrega reglas o elementos adicionales para todos los próximos pasos posibles en la creación de los productos esperados:

r3: Productos → • Productos * Valor

r4: Productos → • Valor

r5: Valor → • int

r6: Valor → • id

El marcador • se encuentra al principio de cada una de estas reglas añadidas; el analizador aún no ha confirmado ni analizado ninguna parte de ellos. Estos elementos adicionales se denominan "cierre" de los elementos básicos. Para cada símbolo no terminal que sigue inmediatamente a •, el generador agrega las reglas que definen ese símbolo. Esto agrega más marcadores • y posiblemente diferentes símbolos de seguidores. Este proceso de cierre continúa hasta que se hayan expandido todos los símbolos de seguidor. Los no terminales del seguidor para el estado 2 comienzan con Productos. El valor se agrega luego por el cierre. Los terminales seguidores son int y id.

El núcleo y los elementos de cierre juntos muestran todas las formas legales posibles de pasar del estado actual a estados futuros y frases completas. Si aparece un símbolo de seguidor en un solo elemento, conduce al siguiente estado que contiene solo un elemento principal con el marcador • avanzado. Entonces int lleva al siguiente estado 8 con core

r5: Valor → int •

Si aparece el mismo símbolo de seguidor en varios elementos, el analizador aún no puede saber qué regla se aplica aquí. Entonces ese símbolo conduce al siguiente estado que muestra todas las posibilidades restantes, nuevamente con el marcador • avanzado. Los productos aparecen tanto en r1 como en r3. Así que Productos conduce al siguiente estado 3 con núcleo

r1: Sums → Sums + Productos •

r3: Productos → Productos • * Valor

En palabras, eso significa que si el analizador ha visto un solo producto, es posible que esté listo o que aún tenga más elementos para multiplicar. Todos los elementos principales tienen el mismo símbolo que precede al marcador •; todas las transiciones a este estado son siempre con ese mismo símbolo.

Algunas transiciones serán a núcleos y estados que ya se han enumerado. Otras transiciones conducen a nuevos estados. El generador comienza con la regla del objetivo de la gramática. A partir de ahí, sigue explorando estados y transiciones conocidos hasta que se hayan encontrado todos los estados necesarios.

Estos estados se denominan "LR(0)" estados porque utilizan una anticipación de k=0, es decir, sin anticipación. La única verificación de los símbolos de entrada ocurre cuando el símbolo se desplaza hacia adentro. La verificación de las reducciones anticipadas se realiza por separado por la tabla de análisis, no por los estados enumerados en sí.

Máquina de estados finitos

La tabla de análisis describe todos los estados LR(0) posibles y sus transiciones. Forman una máquina de estados finitos (FSM). Un FSM es un motor simple para analizar lenguajes simples no anidados, sin usar una pila. En esta aplicación LR, el "idioma de entrada" modificado del FSM tiene símbolos terminales y no terminales, y cubre cualquier instantánea de pila analizada parcialmente del análisis LR completo.

Recuerde el paso 5 del Ejemplo de pasos de análisis:

La pila de análisis muestra una serie de transiciones de estado, desde el estado inicial 0, al estado 4 y luego al 5 y al estado actual 8. Los símbolos en la pila de análisis son los símbolos de cambio o ir a para esas transiciones. Otra forma de ver esto es que la máquina de estados finitos puede escanear el flujo "Productos * int + 1" (sin usar otra pila más) y encuentre la frase completa más a la izquierda que debe reducirse a continuación. ¡Y ese es de hecho su trabajo!

¿Cómo puede un simple FSM hacer esto cuando el lenguaje original sin analizar tiene anidamiento y recursividad y definitivamente requiere un analizador con una pila? El truco es que todo lo que se encuentra a la izquierda de la parte superior de la pila ya se ha reducido por completo. Esto elimina todos los bucles y anidamientos de esas frases. El FSM puede ignorar todos los comienzos más antiguos de las frases y rastrear solo las frases más nuevas que podrían completarse a continuación. El nombre oscuro para esto en la teoría LR es "prefijo viable".

Conjuntos anticipados

Los estados y las transiciones brindan toda la información necesaria para las acciones de cambio y las acciones de ir a la tabla de análisis. El generador también necesita calcular los conjuntos anticipados esperados para cada acción de reducción.

En los analizadores SLR, estos conjuntos de anticipación se determinan directamente a partir de la gramática, sin tener en cuenta los estados y las transiciones individuales. Para cada S no terminal, el generador SLR calcula Follows(S), el conjunto de todos los símbolos terminales que pueden seguir inmediatamente a alguna ocurrencia de S. En la tabla de análisis, cada reducción a S usa Follow(S) como su LR(1) conjunto de anticipación. Dichos conjuntos de seguimiento también son utilizados por generadores para analizadores de arriba hacia abajo LL. Una gramática que no tiene conflictos de cambio/reducción o reducción/reducción cuando se utilizan conjuntos de seguimiento se denomina gramática SLR.

LALR tienen los mismos estados que los analizadores SLR, pero usan una forma más complicada y precisa de calcular las anticipaciones de reducción mínimas necesarias para cada estado individual. Dependiendo de los detalles de la gramática, esto puede resultar ser el mismo que el conjunto Seguir calculado por los generadores de analizadores SLR, o puede resultar ser un subconjunto de las búsquedas anticipadas SLR. Algunas gramáticas están bien para los generadores de analizadores LALR pero no para los generadores de analizadores SLR. Esto sucede cuando la gramática tiene conflictos falsos de cambio/reducción o reducción/reducción al usar los conjuntos de seguimiento, pero no al usar los conjuntos exactos calculados por el generador LALR. La gramática entonces se llama LALR(1) pero no SLR.

Un analizador SLR o LALR evita tener estados duplicados. Pero esta minimización no es necesaria y, a veces, puede crear conflictos de anticipación innecesarios. Los analizadores Canonical LR usan estados duplicados (o "divididos") para recordar mejor el contexto izquierdo y derecho del uso de un no terminal. Cada aparición de un símbolo S en la gramática se puede tratar de forma independiente con su propio conjunto de búsqueda anticipada, para ayudar a resolver los conflictos de reducción. Esto maneja algunas gramáticas más. Desafortunadamente, esto aumenta enormemente el tamaño de las tablas de análisis si se hace para todas las partes de la gramática. Esta división de estados también se puede hacer de forma manual y selectiva con cualquier analizador SLR o LALR, haciendo dos o más copias con nombre de algunos no terminales. Una gramática que está libre de conflictos para un generador LR canónico pero tiene conflictos en un generador LALR se llama LR(1) pero no LALR(1), y no SLR.

Los analizadores SLR, LALR y LR canónicos realizan exactamente el mismo cambio y reducen las decisiones cuando el flujo de entrada es el idioma correcto. Cuando la entrada tiene un error de sintaxis, el analizador LALR puede hacer algunas reducciones adicionales (inofensivas) antes de detectar el error que lo haría el analizador LR canónico. Y el analizador SLR puede hacer aún más. Esto sucede porque los analizadores SLR y LALR utilizan una generosa aproximación de superconjunto a los símbolos de anticipación mínimos verdaderos para ese estado en particular.

Recuperación de errores de sintaxis

Los analizadores LR pueden generar mensajes de error algo útiles para el primer error de sintaxis en un programa, simplemente enumerando todos los símbolos de terminal que podrían haber aparecido a continuación en lugar del inesperado símbolo de búsqueda incorrecta. Pero esto no ayuda al analizador a determinar cómo analizar el resto del programa de entrada para buscar más errores independientes. Si el analizador se recupera mal del primer error, es muy probable que analice mal todo lo demás y produzca una cascada de mensajes de error falsos inútiles.

En los generadores de analizadores yacc y bison, el analizador tiene un mecanismo ad hoc para abandonar la declaración actual, descartar algunas frases analizadas y tokens de búsqueda anticipada que rodean el error, y resincronizar el análisis en algún delimitador confiable a nivel de declaración como punto y coma o llaves. Esto a menudo funciona bien para permitir que el analizador y el compilador revisen el resto del programa.

Muchos errores de codificación sintáctica son simples errores tipográficos u omisiones de un símbolo trivial. Algunos analizadores de LR intentan detectar y reparar automáticamente estos casos comunes. El analizador enumera todas las posibles inserciones, eliminaciones o sustituciones de un solo símbolo en el punto de error. El compilador realiza un análisis de prueba con cada cambio para ver si funcionó bien. (Esto requiere retroceder a las instantáneas de la pila de análisis y el flujo de entrada, que normalmente el analizador no necesita). Se elige la mejor reparación. Esto da un mensaje de error muy útil y resincroniza bien el análisis. Sin embargo, la reparación no es lo suficientemente confiable como para modificar permanentemente el archivo de entrada. La reparación de errores de sintaxis es más fácil de realizar de manera consistente en analizadores (como LR) que tienen tablas de análisis y una pila de datos explícita.

Variantes de analizadores LR

El generador del analizador LR decide lo que debe suceder para cada combinación de estado del analizador y símbolo de anticipación. Estas decisiones generalmente se convierten en tablas de datos de solo lectura que impulsan un ciclo de analizador genérico que es independiente de la gramática y el estado. Pero también hay otras formas de convertir esas decisiones en un analizador activo.

Algunos generadores de analizadores LR crean un código de programa personalizado e independiente para cada estado, en lugar de una tabla de análisis. Estos analizadores pueden ejecutarse varias veces más rápido que el ciclo del analizador genérico en los analizadores controlados por tablas. Los analizadores más rápidos usan código ensamblador generado.

En la variación del analizador de ascenso recursivo, la estructura de pila de análisis explícito también se reemplaza por la pila implícita utilizada por las llamadas a subrutinas. Las reducciones finalizan varios niveles de llamadas a subrutinas, lo cual es complicado en la mayoría de los idiomas. Por lo tanto, los analizadores sintácticos recursivos de ascenso son generalmente más lentos, menos obvios y más difíciles de modificar a mano que los analizadores recursivos de descenso.

Otra variación reemplaza la tabla de análisis por reglas de coincidencia de patrones en lenguajes no procedimentales como Prolog.

GLR Los analizadores LR generalizados usan técnicas ascendentes de LR para encontrar todos los análisis posibles del texto de entrada, no solo un análisis correcto. Esto es esencial para la gramática ambigua, como la que se usa para los lenguajes humanos. Los múltiples árboles de análisis válidos se calculan simultáneamente, sin retroceder. GLR a veces es útil para lenguajes informáticos que no se describen fácilmente mediante una gramática LALR(1) libre de conflictos.

LC Los analizadores de esquina izquierda utilizan técnicas de abajo hacia arriba LR para reconocer el extremo izquierdo de reglas gramaticales alternativas. Cuando las alternativas se han reducido a una sola regla posible, el analizador cambia a técnicas LL(1) de arriba hacia abajo para analizar el resto de esa regla. Los analizadores LC tienen tablas de análisis más pequeñas que los analizadores LALR y mejores diagnósticos de errores. No existen generadores ampliamente utilizados para analizadores LC deterministas. Los analizadores LC de análisis múltiple son útiles con lenguajes humanos con gramáticas muy grandes.

Teoría

Los analizadores LR fueron inventados por Donald Knuth en 1965 como una generalización eficiente de los analizadores de precedencia. Knuth demostró que los analizadores LR eran los analizadores de propósito más general posibles que aún serían eficientes en los peores casos.

"LR"k) gramática puede ser analizada eficientemente con un tiempo de ejecución esencialmente proporcional a la longitud de la cadena."

Por todos k≥1, "un idioma puede ser generado por un LR(k) gramática si y sólo si es determinista [y sin contexto], si y sólo si puede ser generado por una gramática LR(1)."

En otras palabras, si un lenguaje fuera lo suficientemente razonable como para permitir un analizador eficiente de un solo paso, podría describirse mediante una gramática LR(k). Y esa gramática siempre podría transformarse mecánicamente en una gramática LR(1) equivalente (pero más grande). Entonces, un método de análisis LR(1) era, en teoría, lo suficientemente poderoso para manejar cualquier lenguaje razonable. En la práctica, las gramáticas naturales de muchos lenguajes de programación están cerca de ser LR(1).

Los analizadores LR canónicos descritos por Knuth tenían demasiados estados y tablas de análisis muy grandes que eran demasiado grandes para la memoria limitada de las computadoras de esa época. El análisis LR se volvió práctico cuando Frank DeRemer inventó los analizadores SLR y LALR con muchos menos estados.

Para obtener detalles completos sobre la teoría LR y cómo los analizadores LR se derivan de las gramáticas, consulte The Theory of Parsing, Translation, and Compiling, Volume 1 (Aho y Ullman).

Los analizadores de Early aplican las técnicas y la notación • de los analizadores de LR a la tarea de generar todos los análisis posibles para gramáticas ambiguas como para lenguajes humanos

Mientras que las gramáticas LR(k) tienen el mismo poder generativo para todos los k≥1, el caso de las gramáticas LR(0) es ligeramente diferente. Se dice que un idioma L tiene la propiedad prefijo si ninguna palabra en L es un prefijo propio de otra palabra en L. Un lenguaje L tiene una gramática LR(0) si y solo si L es un lenguaje determinista libre de contexto con la propiedad de prefijo. Como consecuencia, un lenguaje L es determinista libre de contexto si y solo si L$ tiene una gramática LR(0), donde "$" no es un símbolo del alfabeto de L.

Ejemplo adicional 1+1

Parte inferior de 1+1

Este ejemplo de análisis LR utiliza la siguiente gramática pequeña con el símbolo de objetivo E:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

para analizar la siguiente entrada:

1 + 1

Tablas de acciones e ir a

Las dos tablas de análisis LR(0) para esta gramática tienen el siguiente aspecto:

La tabla de acciones está indexada por un estado del analizador y un terminal (incluido un terminal especial $ que indica el final del flujo de entrada) y contiene tres tipos de acciones:

• cambio, que está escrito como 'sn' e indica que el próximo estado es n
• reducción, que está escrito comom' e indica que una reducción con regla de gramática m debe realizarse
• aceptar, que está escrito como 'acc' e indica que el analizador acepta la cadena en el flujo de entrada.

La tabla goto está indexada por un estado del analizador y un no terminal y simplemente indica cuál será el próximo estado del analizador si ha reconocido un determinado no terminal. Esta tabla es importante para conocer el siguiente estado después de cada reducción. Después de una reducción, el siguiente estado se encuentra buscando la entrada goto table para la parte superior de la pila (es decir, el estado actual) y el LHS de la regla reducida (es decir, no terminal).

Pasos de análisis

La siguiente tabla ilustra cada paso del proceso. Aquí, el estado se refiere al elemento en la parte superior de la pila (el elemento más a la derecha), y la siguiente acción se determina consultando la tabla de acciones anterior. Se agrega un $ a la cadena de entrada para indicar el final de la transmisión.

Tutorial

El analizador comienza con la pila que contiene solo el estado inicial ('0'):

[0]

El primer símbolo de la cadena de entrada que ve el analizador es '1'. Para encontrar la siguiente acción (cambiar, reducir, aceptar o error), la tabla de acciones se indexa con el estado actual (el "estado actual" es lo que está en la parte superior de la pila), que en este case es 0, y el símbolo de entrada actual, que es '1'. La tabla de acciones especifica un cambio al estado 2, por lo que el estado 2 se coloca en la pila (nuevamente, toda la información del estado está en la pila, por lo que "cambiar al estado 2" es lo mismo que colocar 2 en la pila). La pila resultante es

[0 '1 ' 2]

donde la parte superior de la pila es 2. A modo de explicación, se muestra el símbolo (por ejemplo, '1', B) que causó la transición al siguiente estado, aunque estrictamente hablando no es así. parte de la pila.

En el estado 2, la tabla de acciones dice que se reduzca con la regla gramatical 5 (sin importar qué terminal vea el analizador en el flujo de entrada), lo que significa que el analizador acaba de reconocer el lado derecho de la regla 5. En este caso, el analizador escribe 5 en el flujo de salida, extrae un estado de la pila (dado que el lado derecho de la regla tiene un símbolo) y empuja en la pila el estado de la celda en la tabla Goto para el estado 0 y B, es decir, estado 4. La pila resultante es:

[0 B 4]

Sin embargo, en el estado 4, la tabla de acciones dice que el analizador ahora debe reducir con la regla 3. Entonces escribe 3 en el flujo de salida, extrae un estado de la pila y encuentra el nuevo estado en la tabla Goto para el estado 0 y E, que es el estado 3. La pila resultante:

[0 E 3]

El siguiente terminal que ve el analizador es un '+' y de acuerdo con la tabla de acción, entonces debería pasar al estado 6:

[0 E 3 '+ ' 6]

La pila resultante se puede interpretar como la historia de un autómata de estado finito que acaba de leer una E no terminal seguida de una terminal '+'. La tabla de transición de este autómata está definida por las acciones de desplazamiento en la tabla de acciones y las acciones de ir a en la tabla de ir a.

La próxima terminal ahora es '1' y esto significa que el analizador realiza un cambio y pasa al estado 2:

[0 E 3 '+ ' 6 '1 ' 2]

Al igual que el anterior '1' este se reduce a B dando la siguiente pila:

[0 E 3 '+ ' 6 B 8]

La pila se corresponde con una lista de estados de un autómata finito que ha leído una E no terminal, seguida de un '+' y luego un no terminal B. En el estado 8, el analizador siempre realiza una reducción con la regla 2. Los 3 estados superiores en la pila se corresponden con los 3 símbolos en el lado derecho de la regla 2. Esta vez sacamos 3 elementos del stack (ya que el lado derecho de la regla tiene 3 símbolos) y busque el estado goto para E y 0, empujando así el estado 3 de vuelta a la pila

[0 E 3]

Finalmente, el analizador lee un '$' (fin del símbolo de entrada) del flujo de entrada, lo que significa que, de acuerdo con la tabla de acciones (el estado actual es 3), el analizador acepta la cadena de entrada. Los números de regla que se habrán escrito en el flujo de salida serán [5, 3, 5, 2], que de hecho es una derivación más a la derecha de la cadena "1 + 1" en reversa.

Construcción de tablas de análisis LR(0)

Objetos

La construcción de estas tablas de análisis se basa en la noción de elementos LR(0) (simplemente llamados elementos aquí) que son reglas gramaticales con un punto especial agregado en alguna parte en el lado derecho. Por ejemplo, la regla E → E + B tiene los siguientes cuatro elementos correspondientes:

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Las reglas de la forma A → ε tienen un único elemento A → • . El elemento E → E • + B, por ejemplo, indica que el analizador ha reconocido una cadena correspondiente a E en el flujo de entrada y ahora espera leer un '+' seguida de otra cadena correspondiente a B.

Conjuntos de elementos

Por lo general, no es posible caracterizar el estado del analizador con un solo elemento porque es posible que no sepa de antemano qué regla utilizará para la reducción. Por ejemplo, si también hay una regla E → E * B, entonces los elementos E → E • + B y E → E < big>• * B se aplicará después de leer una cadena correspondiente a E. Por lo tanto, es conveniente caracterizar el estado del analizador por un conjunto de elementos, en este caso el conjunto { E → E • + B, E → E • * B }.

Extensión del conjunto de elementos por expansión de no terminales

Un elemento con un punto antes de un no terminal, como E → E + • B, indica que el analizador espera analizar el no terminal B siguiente. Para garantizar que el conjunto de elementos contenga todas las reglas posibles que el analizador puede estar analizando, debe incluir todos los elementos que describen cómo se analizará B. Esto significa que si hay reglas como B → 1 y B → 0, el conjunto de elementos también debe incluir los elementos B → • 1 y B → • 0. En general, esto se puede formular de la siguiente manera:

Si hay un elemento de la forma A → v • Bw en un conjunto de elementos y en la gramática hay una regla de la forma B → w ' entonces el artículo B → • w ' también debe estar en el conjunto del tema.

Cierre de conjuntos de artículos

Por lo tanto, cualquier conjunto de elementos se puede ampliar agregando recursivamente todos los elementos apropiados hasta que se tengan en cuenta todos los no terminales precedidos por puntos. La extensión mínima se denomina cierre de un conjunto de elementos y se escribe como clos(I) donde I es un conjunto de artículos Son estos conjuntos de elementos cerrados los que se toman como los estados del analizador, aunque solo se incluirán en las tablas aquellos que son realmente accesibles desde el estado inicial.

Gramática aumentada

Antes de que se determinen las transiciones entre los diferentes estados, la gramática se aumenta con una regla adicional

(0) S → E

donde S es un nuevo símbolo de inicio y E el antiguo símbolo de inicio. El analizador utilizará esta regla para la reducción exactamente cuando haya aceptado la cadena de entrada completa.

Para este ejemplo, la misma gramática anterior se amplía así:

(0) S → E

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Es para esta gramática aumentada que se determinarán los conjuntos de elementos y las transiciones entre ellos.

Construcción de mesas

Encontrar los conjuntos de elementos accesibles y las transiciones entre ellos

El primer paso para construir las tablas consiste en determinar las transiciones entre los conjuntos de elementos cerrados. Estas transiciones se determinarán como si estuviéramos considerando un autómata finito que puede leer tanto terminales como no terminales. El estado inicial de este autómata es siempre el cierre del primer elemento de la regla añadida: S → • E:

Tema 0

S → • E

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

El "+" en negrita; delante de un elemento indica los elementos que se agregaron para el cierre (no debe confundirse con el operador matemático '+' que es una terminal). Los artículos originales sin "+" se denominan el núcleo del conjunto de elementos.

Comenzando en el estado inicial (S0), todos los estados que pueden ser alcanzados desde este estado ahora están determinados. Las posibles transiciones para un conjunto de elementos se pueden encontrar mirando los símbolos (terminales y noterminales) encontrados siguiendo los puntos; en el caso de conjunto de elementos 0 esos símbolos son los terminales '0' y '1' y los noterminales E y B. Para encontrar el elemento establece que cada símbolo ${textstyle xin {0,1,E,B}$conduce a, se sigue el siguiente procedimiento para cada uno de los símbolos:

1. Toma el subconjunto, S, de todos los elementos en el juego actual donde hay un punto delante del símbolo de interés, x.
2. Para cada artículo en S, mover el punto a la derecha de x.
3. Cierre el conjunto resultante de artículos.

Para el terminal '0' (es decir, donde x = '0') esto da como resultado:

Tema 1

B → 0 •

y para el terminal '1' (es decir, donde x = '1') esto da como resultado:

Tema 2

B → 1 •

y para el no terminal E (es decir, donde x = E) esto da como resultado:

Tema 3

S → E • eof

E → E • * B

E → E • + B

y para el no terminal B (es decir, donde x = B) esto da como resultado:

Tema 4

E → B •

El cierre no agrega elementos nuevos en todos los casos; en los nuevos conjuntos anteriores, por ejemplo, no hay elementos no terminales después del punto.

El procedimiento anterior se continúa hasta que no se encuentren más conjuntos nuevos de elementos. Para los juegos 1, 2, y 4 no habrá transiciones ya que el punto no está delante de ningún símbolo. Para el set 3 sin embargo, tenemos puntos delante de terminales '*' y '+'. Para el símbolo ${textstyle x={textttt {}}$ la transición va a:

Tema 5

E → E * • B

+ B → • 0

+ B → • 1

y para ${textstyle x={textttt {}}$ la transición va a:

Tema 6

E → E + • B

+ B → • 0

+ B → • 1

Ahora, comienza la tercera iteración.

Para el conjunto de elementos 5, los terminales '0' y '1' y se debe considerar el no terminal B, pero los conjuntos de elementos cerrados resultantes son iguales a los conjuntos de elementos 1 y 2 ya encontrados, respectivamente. Para el no terminal B, la transición va a:

Tema 7

E → E * B •

Para el conjunto de elementos 6, el terminal '0' y '1' y se debe considerar el no terminal B, pero como antes, los conjuntos de elementos resultantes para los terminales son iguales a los conjuntos de elementos 1 y 2 ya encontrados. Para el no terminal B, la transición va a:

Tema 8

E → E + B •

Estos conjuntos de elementos finales 7 y 8 no tienen símbolos más allá de sus puntos, por lo que no se agregan más conjuntos de elementos nuevos, por lo que el procedimiento de generación de elementos está completo. El autómata finito, con conjuntos de elementos como sus estados, se muestra a continuación.

La tabla de transición para el autómata ahora tiene el siguiente aspecto:

Construcción de las tablas action y goto

A partir de esta tabla y los conjuntos de elementos encontrados, la acción y la tabla Goto se construyen de la siguiente manera:

1. Las columnas para los no-terminales se copian a la tabla de Goto.
2. Las columnas para los terminales se copian a la tabla de acción como acciones de cambio.
3. Una columna adicional para '$' (fin de entrada) se añade a la tabla de acción. An acc acción se añade a la columna '$' para cada conjunto de elementos que contiene un elemento del formulario S → w • Eof.
4. Si se establece un elemento i contiene un artículo de la forma A → w • y A → w es la regla m con m ■ 0 entonces la fila para el estado i en la mesa de acción se llena completamente con la acción de reducción rm.

El lector puede verificar que esto da como resultado la acción y la tabla de ir a que se presentaron anteriormente.

Una nota sobre el análisis de LR(0) frente a SLR y LALR

Solo el paso 4 del procedimiento anterior produce acciones de reducción, por lo que todas las acciones de reducción deben ocupar una fila completa de la tabla, lo que hace que la reducción ocurra independientemente del siguiente símbolo en el flujo de entrada. Esta es la razón por la que se trata de tablas de análisis LR(0): no realizan ninguna búsqueda anticipada (es decir, anticipan cero símbolos) antes de decidir qué reducción realizar. Una gramática que necesita anticipación para eliminar la ambigüedad de las reducciones requeriría una fila de la tabla de análisis que contenga diferentes acciones de reducción en diferentes columnas, y el procedimiento anterior no es capaz de crear dichas filas.

Los refinamientos del procedimiento de construcción de tablas LR(0) (como SLR y LALR) son capaces de construir acciones de reducción que no ocupan filas enteras. Por lo tanto, son capaces de analizar más gramáticas que los analizadores LR(0).

Conflictos en las tablas construidas

El autómata está construido de tal manera que se garantiza que sea determinista. Sin embargo, cuando se agregan acciones de reducción a la tabla de acciones, puede suceder que la misma celda se llene con una acción de reducción y una acción de cambio (un conflicto de cambio-reducción) o con dos acciones de reducción diferentes (un reducir-reducir el conflicto). Sin embargo, se puede demostrar que cuando esto sucede, la gramática no es una gramática LR(0). Un ejemplo clásico del mundo real de un conflicto de cambio-reducción es el problema pendiente de otra cosa.

Un pequeño ejemplo de una gramática que no es LR(0) con un conflicto shift-reduce es:

(1) E → 1 E

2) E → 1

Uno de los conjuntos de elementos encontrados es:

Tema 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Hay un conflicto de desplazamiento-reducción en este conjunto de elementos: al construir la tabla de acción de acuerdo con las reglas anteriores, la celda para [conjunto de elementos 1, terminal '1'] contiene s1< /b> (cambiar al estado 1) y r2 (reducir con la regla gramatical 2).

Un pequeño ejemplo de una gramática que no es LR(0) con un conflicto de reducción-reducción es:

(1) E → A 1

2) E → B 2

(3) A → 1

(4) B → 1

En este caso se obtiene el siguiente conjunto de elementos:

Tema 1

A → 1 •

B → 1 •

Hay un conflicto de reducción-reducción en este conjunto de elementos porque en las celdas de la tabla de acciones para este conjunto de elementos habrá una acción de reducción para la regla 3 y otra para la regla 4.

Los dos ejemplos anteriores se pueden resolver dejando que el analizador use el conjunto de seguimiento (ver analizador LL) de un A no terminal para decidir si va a usar uno de As reglas para una reducción; solo usará la regla A → w para una reducción si el siguiente símbolo en el flujo de entrada está en el siguiente conjunto de A. Esta solución da como resultado los llamados analizadores LR simples.