LR parser

Mientras${\displaystyle \operatorname {LR} (k)}$Las gramáticas se utilizan principalmente para el análisis sintáctico , la siguiente definición de la${\displaystyle \operatorname {LR} (k)}$Las gramáticas, en cambio, utilizan la perspectiva dual: la de comenzar con el símbolo de inicio.${\displaystyle S}$y aplicando repetidamente las reglas de producción de una gramática para producir una secuencia de formas oracionales . Por oración , entendemos una forma oracional sin símbolos no terminales.

Una forma oracional derecha es cualquier forma oracional que se puede obtener comenzando con el símbolo de inicio.${\displaystyle S}$y aplicando repetidamente las reglas de producción solo a los no terminales más a la derecha. Todo el marco LR utiliza únicamente formas sentenciales derechas.

La definición de${\displaystyle \operatorname {LR} (k)}$Ahora es breve: Una gramática libre de contexto${\displaystyle G}$se llama${\displaystyle \operatorname {LR} (k)}$Si para cada par de derivaciones de formas oracionales derechas que coinciden con el siguiente patrón, podemos concluir que${\displaystyle {\color {blue}\alpha }={\color {green}\alpha '}}$y${\displaystyle {\color {red}B}={\color {green}B'}}$:$${\displaystyle {\begin{matrix}S&{\overset {*}{\underset {G}{\implies }}}&{\color {blue}\alpha }{\color {red}B}{\color {blue}c_{1}c_{2}\dotsb c_{k}}{\color {purple}\gamma }&{\underset {G}{\implies }}&{\color {blue}\alpha \beta c_{1}c_{2}\dotsb c_{k}}\color {purple}\gamma \\S&{\overset {*}{\underset {G}{\implies }}}&{\color {green}\alpha 'B'}{\color {blue}c_{1}c_{2}\dotsb c_{k}}\color {magenta}\gamma '&{\underset {G}{\implies }}&{\color {blue}\alpha \beta c_{1}c_{2}\dotsb c_{k}}\color {magenta}\gamma '\end{matrix}}}$$

Un analizador LR escanea y analiza el texto de entrada en una sola pasada hacia adelante. 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 esta pasada, el analizador ha acumulado una lista de subárboles o frases del texto de entrada que ya han sido analizadas. Estos subárboles aún no se han unido porque el analizador aún no ha llegado al extremo correcto del patrón de sintaxis que los combinará.

En el paso 6 de un ejemplo de análisis, solo se ha analizado "A * 2", de forma incompleta. Solo existe la esquina inferior izquierda sombreada del árbol de análisis. Ninguno de los nodos del árbol de análisis numerados del 7 en adelante existe todavía. 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 porción restante sin analizar del flujo de entrada es "+ 1".

Al igual que otros analizadores sintácticos de desplazamiento-reducción, un analizador LR funciona realizando una combinación de pasos de desplazamiento y pasos de reducción.

• Un paso de desplazamiento avanza un símbolo en el flujo de entrada. Ese símbolo desplazado se convierte en un nuevo árbol de análisis sintáctico de un solo nodo.
• Un paso de Reducción aplica una regla gramatical completa a algunos de los árboles de análisis sintáctico recientes, uniéndolos en un solo árbol con un nuevo símbolo raíz.

Si la entrada no contiene errores de sintaxis, el analizador continúa con estos pasos hasta que se haya procesado toda la entrada y todos los árboles de análisis se hayan reducido a un único árbol que represente una entrada válida completa.

Los analizadores LR se diferencian de otros analizadores de desplazamiento-reducción en cómo deciden cuándo reducir y cómo elegir entre reglas con terminaciones similares. Sin embargo, las decisiones finales y la secuencia de pasos de desplazamiento o reducción son las mismas.

Gran parte de la eficiencia del analizador LR se debe a su determinismo. Para evitar conjeturas, el analizador LR suele mirar hacia adelante (a la derecha) al siguiente símbolo escaneado, antes de decidir qué hacer con los símbolos escaneados previamente. El analizador léxico trabaja con uno o más símbolos por delante del analizador. Los símbolos de anticipación constituyen el "contexto de la derecha" para la decisión de análisis. ^{[ 4 ]}

Al igual que otros analizadores sintácticos de desplazamiento-reducción, un analizador LR espera perezosamente hasta haber escaneado y analizado todas las partes de una construcción antes de determinar 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 Value y luego a Products en los pasos 1 a 3 tan pronto como se encuentra el asterisco (*), 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 escáner ya han visto, sin considerar elementos 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. Así, la lista de elementos ya analizados actúa como una pila . Esta pila crece hacia la derecha. La base o parte inferior de la pila se encuentra a la izquierda y contiene el fragmento de análisis más antiguo y situado más a la izquierda. Cada paso de reducción actúa únicamente sobre los fragmentos de análisis más recientes y situados más a la derecha. (Esta pila de análisis acumulativa es muy diferente de la pila de análisis predictiva que crece hacia la izquierda, utilizada por los analizadores descendentes ).

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, en este caso un Productos más grande. Si el analizador sintáctico construye á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 Productos internos y Valor se envían a una pasada posterior del compilador , o se combinan y se guardan en el nuevo símbolo Productos. ^{[ 5 ]}

En los analizadores LR, las decisiones de desplazamiento y reducción se basan potencialmente en toda la pila de todo lo que se ha analizado previamente, no solo en un único símbolo de la parte superior de la pila. Si se hace de forma poco eficiente, esto podría dar lugar a analizadores muy lentos que se vuelven cada vez más lentos a medida que aumenta la longitud de la entrada. Los analizadores LR lo hacen a velocidad constante, resumiendo toda la información relevante del contexto izquierdo en un único número llamado estado del analizador LR(0) . Para cada gramática y método de análisis LR, existe un número fijo (finito) de dichos estados. Además de almacenar 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, el texto de entrada completo se divide en una pila de frases previamente analizadas, un símbolo de anticipación actual y el texto restante sin analizar. La siguiente acción del analizador viene determinada por su número de estado LR(0) actual (el de más a la derecha en la pila) y el símbolo de anticipación. En los pasos siguientes, todos los detalles en negro son exactamente iguales que en otros analizadores sintácticos de desplazamiento-reducción que no son LR. Las pilas de los analizadores LR añaden la información de estado en púrpura, resumiendo las frases en negro a su izquierda en la pila y las posibles sintaxis que cabe esperar a continuación. Los usuarios de un analizador LR normalmente 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 análisis,
• El texto de anticipación "A" se escaneó como un símbolo de identificación y
• el texto restante sin escanear "* 2 + 1".

La pila de análisis comienza manteniendo solo el estado inicial 0. Cuando el estado 0 ve el ID de anticipación , sabe que debe mover ese ID a la pila, escanear el siguiente símbolo de entrada * y avanzar al estado 9.

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

• la sección analizada "A  *" con 2 frases apiladas Productos y * ,
• El texto de anticipación "2" se escaneó como un símbolo entero , y
• el texto restante sin escanear " + 1".

Los estados correspondientes a las frases apiladas son 0, 4 y 5. El estado actual, el más a la derecha de la pila, es el estado 5. Cuando el estado 5 ve el entero de anticipación , sabe que debe desplazar ese entero a la pila como su propia frase, y escanear el siguiente símbolo de entrada + , y avanzar 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 salto de línea anticipado (lookahead eof) , sabe que debe aplicar la regla gramatical completa.

Sumas → Sumas + Productos

Al combinar las tres frases más a la derecha de la pila para Sumas, + y Productos en una sola, el estado 3 desconoce cuál debería ser el siguiente. Este se determina 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 una Suma, avanza al estado 1 (de nuevo). Esta consulta de estados anteriores es la razón por la que se mantienen en la pila, en lugar de conservar solo el estado actual.

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. Esta gramática no abarca todas las reglas del lenguaje, como el tamaño de los números o el uso coherente de nombres y sus definiciones en el contexto del programa completo. Los analizadores LR utilizan una gramática libre de contexto que se ocupa únicamente de patrones locales de símbolos.

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

r0: Meta → Sumas eof

r1: Sumas → Sumas + Productos

r2: Sumas → 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» que encuentra un analizador léxico en el flujo de entrada . Estos incluyen + * e int para cualquier constante entera , id para cualquier nombre de identificador y eof para el final del archivo de entrada. A la gramática no le importan los valores de int ni la ortografía de id , ni tampoco los espacios en blanco o los saltos de línea. La gramática utiliza estos símbolos terminales, pero no los define. Siempre son nodos hoja (en la parte inferior del árbol de análisis sintáctico).

Los términos en mayúsculas como Sums son símbolos no terminales . Estos son nombres para conceptos o patrones en el lenguaje. Se definen en la gramática y nunca aparecen directamente en el flujo de entrada. Siempre son nodos internos (por encima del nodo inferior) del árbol de análisis sintáctico. Solo aparecen como resultado de que el analizador sintáctico 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 recursividad . Esta gramática utiliza reglas recursivas para manejar operadores matemáticos repetidos. Las gramáticas de lenguajes completos utilizan reglas recursivas para manejar listas, expresiones entre paréntesis y sentencias anidadas.

Cualquier lenguaje de programación puede describirse mediante varias gramáticas diferentes. Un analizador LR(1) puede manejar muchas, pero no todas, las gramáticas comunes. Generalmente, es posible modificar manualmente una gramática para que se ajuste a las limitaciones del análisis LR(1) y de la herramienta generadora.

La gramática de un analizador LR debe ser inequívoca o ampliarse con reglas de precedencia para desempatar. Esto significa que solo hay una forma correcta de aplicar la gramática a un ejemplo válido del lenguaje, lo que resulta en 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 LR no es una técnica útil para 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 pueden calcular simultáneamente todos los árboles de análisis posibles en una sola pasada.

Most LR parsers are table driven. The parser's program code is a simple generic loop that is the same for all grammars and languages. The knowledge of the grammar and its syntactic implications are encoded into unchanging data tables called parse tables (or parsing tables). Entries in a table show whether to shift or reduce (and by which grammar rule), for every legal combination of parser state and lookahead symbol. The parse tables also tell how to compute the next state, given just a current state and a next symbol.

The parse tables are much larger than the grammar. LR tables are hard to accurately compute by hand for big grammars. So they are mechanically derived from the grammar by some parser generator tool like Bison.^[6]

Depending on how the states and parsing table are generated, the resulting parser is called either a SLR (simple LR) parser, LALR (look-ahead LR) parser, or canonical LR parser. LALR parsers handle more grammars than SLR parsers. Canonical LR parsers handle even more grammars, but use many more states and much larger tables. The example grammar is SLR.

LR parse tables are two-dimensional. Each current LR(0) parser state has its own row. Each possible next symbol has its own column. Some combinations of state and next symbol are not possible for valid input streams. These blank cells trigger syntax error messages.

The Action left half of the table has columns for lookahead terminal symbols. These cells determine whether the next parser action is shift (to state n), or reduce (by grammar rule r_n).

The Goto right half of the table has columns for nonterminal symbols. These cells show which state to advance to, after some reduction's Left Hand Side has created an expected new instance of that symbol. This is like a shift action but for nonterminals; the lookahead terminal symbol is unchanged.

The table column "Current Rules" documents the meaning and syntax possibilities for each state, as worked out by the parser generator. It is not included in the actual tables used at parsing time. The • (pink dot) marker shows where the parser is now, within some partially recognized grammar rules. The things to the left of • have been parsed, and the things to the right are expected soon. A state has several such current rules if the parser has not yet narrowed possibilities down to a single rule.

En el estado 2 anterior, el analizador sintáctico acaba de encontrar y desplazar el + de la regla gramatical

r1: Sumas → Sumas + • Productos

La siguiente frase esperada es Products. Products comienza con los símbolos terminales int o id . Si la anticipación es alguno de estos, el analizador los inserta y avanza al estado 8 o 9, respectivamente. Cuando se encuentra un Products, el analizador avanza al estado 3 para acumular la lista completa de sumandos y encontrar el final de la regla r0. Un Products también puede comenzar con el valor no terminal Value. Para cualquier otra anticipación o valor no terminal, el analizador anuncia un error de sintaxis.

En el estado 3, el analizador sintáctico acaba de encontrar una frase de productos, que podría provenir de dos posibles reglas gramaticales:

r1: Sumas → Sumas + 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 debe verificar el símbolo de anticipación para saber qué hacer. Si la anticipación es * , está en la regla 3, por lo que el analizador cambia en el * y avanza al estado 5. Si la anticipación es eof , está al final de la regla 1 y la regla 0, por lo que el analizador ha terminado.

En el estado 9 anterior, todas las celdas no vacías y sin errores corresponden a la misma reducción r6. Algunos analizadores ahorran tiempo y espacio en la tabla al no comprobar el símbolo de anticipación en estos casos sencillos. Los errores de sintaxis se detectan entonces algo más tarde, tras algunas reducciones inofensivas, pero aún antes de la siguiente acción de desplazamiento o decisión del analizador.

Las celdas de la tabla no deben contener múltiples acciones alternativas; de lo contrario, el analizador sería no determinista, con conjeturas y retrocesos. Si la gramática no es LR(1), algunas celdas presentarán conflictos de desplazamiento/reducción entre una posible acción de desplazamiento 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 (cuando es posible) comprobando símbolos de anticipación adicionales más allá del primero.

El analizador LR comienza con una pila de análisis casi vacía que contiene solo el estado inicial 0, y con la anticipación que almacena el primer símbolo escaneado del flujo de entrada. A continuación, el analizador repite el siguiente paso del bucle hasta que finaliza o se atasca en un error de sintaxis:

El estado superior en la pila de análisis es un estado s , y la anticipación actual es un símbolo terminal t . Busque la siguiente acción del analizador en la fila s y la columna t de la tabla de acciones de anticipación. Esa acción es Desplazar, Reducir, Aceptar o Error:

• Desplazamiento n :

Mueva el terminal t coincidente a la pila de análisis y escanee el siguiente símbolo de entrada en el búfer de anticipación.

Inserta el siguiente estado n en la pila de análisis como el nuevo estado actual.

• Reducir r _m : Aplicar regla gramatical r _m : Lhs → S ₁ S ₂ ... S _L

Elimine los símbolos L superiores coincidentes (y los árboles de análisis y los números de estado asociados) de la pila de análisis.

Esto expone un estado previo p que esperaba una instancia del símbolo LHS.

Unir los árboles de análisis L para formar un único árbol de análisis con el nuevo símbolo raíz Lhs.

Busque el siguiente estado n en la fila p y la columna Lhs de la tabla LHS Goto.

Coloca el símbolo y el árbol de Lhs en la pila de análisis.

Inserta el siguiente estado n en la pila de análisis como el nuevo estado actual.

La anticipación y el flujo de entrada permanecen sin cambios.

• Aceptar: La aserción anticipada t es el marcador de fin de archivo . Fin del análisis. Si la pila de estado contiene solo el estado inicial, se informa de éxito. De lo contrario, se informa de un error de sintaxis.
• Error: Se ha producido un error de sintaxis. El analizador sintáctico finaliza o intenta recuperarse.

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 a ese 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. ^{[ 7 ]}

El estado 2 en la tabla de análisis de ejemplo corresponde a la regla parcialmente analizada.

r1: Sumas → Sumas + • Productos

Esto muestra cómo el analizador llegó hasta aquí, al ver Sumas y luego + mientras buscaba una Suma mayor. El marcador • ha avanzado más allá del inicio de la regla. También muestra cómo el analizador espera completar la regla, al encontrar a continuación un Producto completo. Pero se necesitan más detalles sobre cómo analizar todas las partes de ese Producto.

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

r3: Productos → • Productos * Valor

r4: Productos → • Valor

r5: Valor → • int

r6: Valor → • id

El marcador • está al principio de cada una de estas reglas añadidas; el analizador aún no ha confirmado ni analizado ninguna parte de ellas. Estos elementos adicionales se denominan el "cierre" de los elementos centrales. Para cada símbolo no terminal que sigue inmediatamente a un • , el generador añade las reglas que definen ese símbolo. Esto añade más marcadores • y posiblemente diferentes símbolos seguidores. Este proceso de cierre continúa hasta que se hayan expandido todos los símbolos seguidores. Los no terminales seguidores para el estado 2 comienzan con Productos. A continuación, se añade Valor mediante cierre. Los terminales seguidores son int e id .

Los elementos del núcleo y del cierre, en conjunto, muestran todas las posibles formas legales de proceder desde el estado actual a estados futuros y frases completas. Si un símbolo seguidor aparece en un solo elemento, conduce a un estado siguiente que contiene solo un elemento del núcleo con el marcador • avanzado. Por lo tanto , int conduce al estado siguiente 8 con núcleo

r5: Valor → int •

Si el mismo símbolo seguidor aparece en varios elementos, el analizador aún no puede determinar qué regla se aplica. Por lo tanto, ese símbolo conduce a un estado siguiente que muestra todas las posibilidades restantes, nuevamente con el marcador • avanzado. Products aparece tanto en r1 como en r3. Por lo tanto, Products conduce al estado siguiente 3 con core.

r1: Sumas → Sumas + Productos •

r3: Productos → Productos • * Valor

En otras palabras, esto significa que si el analizador sintáctico ha visto un solo producto, es posible que haya terminado, o que aún tenga que multiplicar más elementos. Todos los elementos principales tienen el mismo símbolo antes del marcador • ; todas las transiciones a este estado siempre se realizan con ese mismo símbolo.

Algunas transiciones conducen a núcleos y estados ya enumerados. Otras transiciones llevan a nuevos estados. El generador comienza con la regla objetivo de la gramática. A partir de ahí, continúa explorando estados y transiciones conocidos hasta encontrar todos los estados necesarios.

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

La tabla de análisis describe todos los estados posibles de LR(0) y sus transiciones. Estos forman una máquina de estados finitos (FSM). Una FSM es un motor sencillo para analizar lenguajes simples no anidados, sin usar una pila. En esta aplicación LR, el "lenguaje de entrada" modificado de la FSM contiene símbolos terminales y no terminales, y abarca cualquier instantánea de pila parcialmente analizada 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, pasando por el estado 4 y luego por el 5, hasta llegar al estado actual 8. Los símbolos en la pila de análisis son los símbolos de desplazamiento o de salto para esas transiciones. Otra forma de verlo es que la máquina de estados finitos puede escanear la secuencia "Productos  * int + 1" (sin usar otra pila) y encontrar la frase completa más a la izquierda que debe reducirse a continuación. ¡Y esa es precisamente su función!   

¿Cómo puede una simple máquina de estados finitos (FSM) lograr esto cuando el lenguaje original sin analizar contiene anidamiento y recursión, y requiere sin duda un analizador con pila? El truco reside en 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 el anidamiento de esas frases. La FSM puede ignorar todos los inicios de frases anteriores y rastrear solo las frases más recientes que podrían completarse a continuación. El término técnico para esto en la teoría de regresión logística es "prefijo viable".

Los estados y las transiciones proporcionan toda la información necesaria para las acciones de desplazamiento y de ir a la tabla de análisis. El generador también necesita calcular los conjuntos de anticipación 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 considerar los estados y transiciones individuales. Para cada no terminal S, 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 utiliza Follow(S) como su conjunto de anticipación LR(1). Dichos conjuntos de seguimiento también son utilizados por los generadores para analizadores LL descendentes. Una gramática que no presenta conflictos de desplazamiento/reducción o reducción/reducción al utilizar conjuntos de seguimiento se denomina gramática SLR.

Los analizadores LALR tienen los mismos estados que los analizadores SLR, pero utilizan un método más complejo y preciso para calcular las anticipaciones de reducción mínimas necesarias para cada estado. Dependiendo de los detalles de la gramática, esto puede coincidir con el conjunto Follow calculado por los generadores de analizadores SLR, o bien ser un subconjunto de las anticipaciones SLR. Algunas gramáticas son compatibles con los generadores de analizadores LALR, pero no con los generadores de analizadores SLR. Esto ocurre cuando la gramática presenta conflictos espurios de desplazamiento/reducción o reducción/reducción al usar conjuntos Follow, pero no al usar los conjuntos exactos calculados por el generador LALR. En ese caso, la gramática se denomina 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 LR canónicos usan estados duplicados (o "divididos") para recordar mejor el contexto izquierdo y derecho del uso de un no terminal. Cada ocurrencia de un símbolo S en la gramática puede tratarse de forma independiente con su propio conjunto de anticipación, para ayudar a resolver 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 puede hacerse de forma manual y selectiva con cualquier analizador SLR o LALR, creando dos o más copias con nombre de algunos no terminales. Una gramática que no tiene 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ónico realizan exactamente las mismas decisiones de cambio y reducción cuando la entrada está en el idioma correcto. Cuando la entrada contiene un error de sintaxis, el analizador LALR puede realizar algunas reducciones adicionales (inocuas) antes de detectar el error, en comparación con el analizador LR canónico. Y el analizador SLR puede realizar aún más. Esto sucede porque los analizadores SLR y LALR utilizan una aproximación de superconjunto generosa a los símbolos de anticipación mínimos reales para ese estado particular.

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

En los generadores de analizadores sintácticos yacc y bison, el analizador cuenta con un mecanismo ad hoc para abandonar la instrucción actual, descartar algunas frases analizadas y tokens de anticipación que rodean el error, y resincronizar el análisis en algún delimitador confiable a nivel de instrucción , como punto y coma o llaves. Esto suele funcionar bien para permitir que el analizador y el compilador revisen el resto del programa.

Muchos errores de codificación sintáctica son simples erratas u omisiones de símbolos triviales. Algunos analizadores LR intentan detectar y corregir 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 comprobar si funcionó correctamente. (Esto requiere retroceder a instantáneas de la pila de análisis y del flujo de entrada, algo que normalmente el analizador no necesita). Se selecciona la mejor reparación. Esto proporciona un mensaje de error muy útil y resincroniza correctamente el análisis. Sin embargo, la reparación no es lo suficientemente fiable como para modificar permanentemente el archivo de entrada. La corrección de errores sintácticos es más sencilla y consistente en analizadores (como LR) que disponen de tablas de análisis y una pila de datos explícita.

El generador del analizador LR decide qué sucederá con cada combinación de estado del analizador y símbolo de anticipación. Estas decisiones suelen convertirse en tablas de datos de solo lectura que impulsan un bucle de analizador genérico, independiente de la gramática y del estado. Sin embargo, existen otras maneras de convertir esas decisiones en un analizador activo.

Algunos generadores de analizadores LR crean código de programa personalizado para cada estado, en lugar de una tabla de análisis. Estos analizadores pueden ser varias veces más rápidos que el bucle de análisis genérico de los analizadores basados ​​en tablas. Los analizadores más rápidos utilizan código ensamblador generado.

En la variante de analizador sintáctico ascendente recursivo , la estructura explícita de la pila de análisis 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 resulta engorroso en la mayoría de los lenguajes. Por lo tanto, los analizadores sintácticos ascendentes recursivos suelen ser más lentos, menos intuitivos y más difíciles de modificar manualmente que los analizadores sintácticos descendentes recursivos .

Otra variante sustituye la tabla de análisis sintáctico por reglas de coincidencia de patrones en lenguajes no procedimentales como Prolog .

Los analizadores sintácticos LR generalizados utilizan técnicas LR ascendentes para encontrar todos los análisis posibles de un texto de entrada, no solo uno correcto. Esto es esencial para gramáticas ambiguas como las que se usan en los lenguajes humanos. Los múltiples árboles de análisis válidos se calculan simultáneamente, sin retroceso. GLR resulta útil en ocasiones para lenguajes de programación que no se describen fácilmente mediante una gramática LALR(1) libre de conflictos.

Los analizadores sintácticos LC de esquina izquierda utilizan técnicas LR de abajo hacia arriba para reconocer el extremo izquierdo de las 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 lenguas humanas con gramáticas muy extensas.

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 general más versátiles posibles que, aun en el peor de los casos, seguirían siendo eficientes.

"Las gramáticas LR( k ) se pueden analizar de manera eficiente con un tiempo de ejecución esencialmente proporcional a la longitud de la cadena." ^{[ 8 ]}

Para cada k ≥ 1 , "un lenguaje puede ser generado por una gramática LR( k ) si y solo si es determinista [y libre de contexto], si y solo si puede ser generado por una gramática LR(1)". ^{[ 9 ]}

En otras palabras, si un lenguaje era lo suficientemente razonable como para permitir un analizador sintáctico eficiente de una sola pasada, podía describirse mediante una gramática LR( k ). Y esa gramática siempre podía transformarse mecánicamente en una gramática LR(1) equivalente (pero más extensa). Por lo tanto, un método de análisis sintáctico LR(1) era, en teoría, lo suficientemente potente como para manejar cualquier lenguaje razonable. En la práctica, las gramáticas naturales de muchos lenguajes de programación se aproximan a ser LR(1).

Los analizadores LR canónicos descritos por Knuth tenían demasiados estados y tablas de análisis muy grandes, lo que resultaba impracticable 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. ^{[ 10 ] [ 11 ]}

Para obtener información detallada sobre la teoría LR y cómo se derivan los analizadores LR de las gramáticas, consulte The Theory of Parsing, Translation, and Compiling, Volume 1 (Aho y Ullman). ^{[ 7 ] [ 2 ]}

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

Si bien las gramáticas LR( k ) tienen igual poder generativo para todo k ≥ 1, el caso de las gramáticas LR(0) es ligeramente diferente. Se dice que un lenguaje L tiene la propiedad de prefijo si ninguna palabra en L es un prefijo propio de otra palabra en L. ^{[ 12} ] 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. ^{[ 13 ]} En 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. [ ^{14 ]}

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 se escribe como "s n " e indica que el siguiente estado es n
• reduce , que se escribe como "r m " e indica que se debe realizar una reducción con la regla gramatical m.
• accept , que se escribe 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, e indica cuál será el siguiente estado del analizador si ha reconocido un no terminal determinado. Esta tabla es importante para determinar el siguiente estado después de cada reducción. Tras una reducción, el siguiente estado se encuentra consultando la entrada de la tabla goto correspondiente a la parte superior de la pila (es decir, el estado actual) y al lado izquierdo (es decir, el no terminal) de la regla reducida.

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

El analizador comienza con la pila que contiene únicamente 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 (desplazamiento, reducción, aceptación o error), la tabla de acciones se indexa con el estado actual (el "estado actual" es simplemente lo que está en la parte superior de la pila), que en este caso es 0, y el símbolo de entrada actual, que es '1'. La tabla de acciones especifica un desplazamiento al estado 2, por lo que el estado 2 se inserta en la pila (de nuevo, toda la información de estado está en la pila, por lo que "desplazarse al estado 2" es lo mismo que insertar 2 en la pila). La pila resultante es

[ 0 '1' 2 ]

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

En el estado 2, la tabla de acciones indica que se debe reducir con la regla gramatical 5 (independientemente del terminal que el analizador vea 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 (ya que el lado derecho de la regla tiene un símbolo) y coloca en la pila el estado de la celda en la tabla goto para los estados 0 y B, es decir, el estado 4. La pila resultante es:

[ 0 B 4 ]

Sin embargo, en el estado 4, la tabla de acciones indica que el analizador debe reducir ahora con la regla 3. Por lo tanto, escribe 3 en el flujo de salida, extrae un estado de la pila y encuentra el nuevo estado en la tabla goto para los estados 0 y E, que es el estado 3. La pila resultante:

[ 0 E 3 ]

El siguiente terminal que ve el analizador es un '+' y, según la tabla de acciones, debería pasar al estado 6:

[ 0 E 3 '+' 6 ]

La pila resultante puede interpretarse como el historial de una máquina de estados finitos que acaba de leer un carácter no terminal E seguido de un carácter terminal '+'. La tabla de transiciones de este autómata se define mediante las acciones de desplazamiento en la tabla de acciones y las acciones de ir a en la tabla de ir a.

El siguiente 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 '1' anterior, este se reduce a B, lo que da como resultado la siguiente pila:

[ 0 E 3 '+' 6 B 8 ]

The stack corresponds with a list of states of a finite automaton that has read a nonterminal E, followed by a '+' and then a nonterminal B. In state 8 the parser always performs a reduce with rule 2. The top 3 states on the stack correspond with the 3 symbols in the right-hand side of rule 2. This time we pop 3 elements off of the stack (since the right-hand side of the rule has 3 symbols) and look up the goto state for E and 0, thus pushing state 3 back onto the stack

[0 E 3]

Finally, the parser reads a '$' (end of input symbol) from the input stream, which means that according to the action table (the current state is 3) the parser accepts the input string. The rule numbers that will then have been written to the output stream will be [5, 3, 5, 2] which is indeed a rightmost derivation of the string "1 + 1" in reverse.

The construction of these parsing tables is based on the notion of LR(0) items (simply called items here) which are grammar rules with a special dot added somewhere in the right-hand side. For example, the rule (2) E → E + B has the following four corresponding items:

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Rules of the form A → ε have only a single item A → •. The item E → E • + B, for example, indicates that the parser has recognized a string corresponding with E on the input stream and now expects to read a '+' followed by another string corresponding with B.

It is usually not possible to characterize the state of the parser with a single item because it may not know in advance which rule it is going to use for reduction. For example, if there is also a rule E → E * B then the items E → E • + B and E → E • * B will both apply after a string corresponding with E has been read. Therefore, it is convenient to characterize the state of the parser by a set of items, in this case the set { E → E • + B, E → E • * B }.

Un elemento con un punto antes de un no terminal, como E → E + • B, indica que el analizador espera analizar el no terminal B a continuación. Para garantizar que el conjunto de elementos contenga todas las reglas posibles que el analizador pueda estar procesando, debe incluir todos los elementos que describen cómo se analizará B. Esto significa que si existen 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 elemento B → • w' también debería estar en el conjunto de elementos.

Así, cualquier conjunto de elementos puede extenderse añadiendo recursivamente todos los elementos apropiados hasta que se hayan considerado 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 elementos. Estos conjuntos de elementos cerrados se toman como estados del analizador, aunque solo se incluirán en las tablas aquellos que sean realmente alcanzables desde el estado inicial.

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

(0) S → E eof

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

Para este ejemplo, la misma gramática que la anterior se amplía de la siguiente manera:

(0) S → E eof

(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.

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 agregada: S → • E eof:

Conjunto de elementos 0

S → • E eof

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

El signo " + " en negrita delante de un elemento indica los elementos que se añadieron para el cierre (no confundir con el operador matemático "+", que es un terminal). Los elementos originales sin el signo " + " se denominan núcleo del conjunto de elementos.

Partiendo del estado inicial (S0), todos los estados que se pueden alcanzar desde este estado ya están determinados. Las posibles transiciones para un conjunto de elementos se pueden encontrar observando los símbolos (terminales y no terminales) que aparecen después de los puntos; en el caso del conjunto de elementos 0, esos símbolos son los terminales '0' y '1' y los no terminales E y B. Para encontrar el conjunto de elementos al que pertenece cada símbolo${\textstyle x\in \{0,1,E,B\}}$Esto lleva a que se siga el siguiente procedimiento para cada uno de los símbolos:

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

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

Conjunto de artículos 1

B → 0 •

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

Conjunto de artículos 2

B → 1 •

y para el no terminal E (es decir, donde x = E) esto resulta en:

Conjunto de artículos 3

S → E • fin de

E → E • * B

E → E • + B

y para el no terminal B (es decir, donde x = B) esto resulta en:

Conjunto de artículos 4

E → B •

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

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

Conjunto de artículos 5

E → E * • B

+ B → • 0

+ B → • 1

y para ${\textstyle x={\texttt {+}}}$La transición va a:

Conjunto de artículos 6

E → E + • B

+ B → • 0

+ B → • 1

Ahora comienza la tercera iteración.

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

Conjunto de artículos 7

E → E * B •

Para el conjunto de elementos 6, se deben considerar los terminales '0' y '1' y 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:

Conjunto de artículos 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 añaden más conjuntos de elementos nuevos; así, el procedimiento de generación de elementos se completa. El autómata finito, con los conjuntos de elementos como estados, se muestra a continuación.

La tabla de transiciones para el autómata ahora se ve así:

A partir de esta tabla y los conjuntos de elementos encontrados, la tabla de acciones y la tabla de destino se construyen de la siguiente manera:

1. Las columnas correspondientes a los no terminales se copian a la tabla goto.
2. Las columnas correspondientes a los terminales se copian a la tabla de acciones como acciones de cambio.
3. Se agrega una columna adicional para '$' (fin de entrada) a la tabla de acciones. Se agrega una acción acc a la columna '$' para cada conjunto de elementos que contiene un elemento de la forma S → w • eof.
4. Si un conjunto de elementos i contiene un elemento de la forma A → w • y A → w es la regla m con m > 0, entonces la fila para el estado i en la tabla de acciones se llena completamente con la acción de reducción r m .

El lector puede comprobar que estos pasos producen la acción y la tabla de destino presentadas anteriormente.

El autómata está construido de tal manera que se garantiza su determinismo. Sin embargo, al añadir acciones de reducción a la tabla de acciones, puede ocurrir que una misma celda se llene con una acción de reducción y una acción de desplazamiento (un conflicto desplazamiento-reducción ) o con dos acciones de reducción diferentes (un conflicto reducción-reducción ). No obstante, se puede demostrar que, en estos casos, la gramática no es una gramática LR(0). Un ejemplo clásico del mundo real de un conflicto desplazamiento-reducción es el problema del else colgante .

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

(1) E → 1 E

(2) E → 1

Uno de los conjuntos de objetos encontrados es:

Conjunto de artículos 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Existe un conflicto de cambio-reducción en este conjunto de elementos: al construir la tabla de acciones de acuerdo con las reglas anteriores, la celda para [conjunto de elementos 1, terminal '1'] contiene s1 (cambio al estado 1) y r2 (reducción con regla gramatical 2).

Un pequeño ejemplo de una gramática no 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:

Conjunto de artículos 1

A → 1 •

B → 1 •

Existe 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.

Ambos ejemplos anteriores se pueden resolver permitiendo que el analizador use el conjunto de seguimiento (ver analizador LL ) de un no terminal A para decidir si va a usar una de las reglas de A 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 conjunto de seguimiento de A. Esta solución da como resultado los llamados analizadores LR simples .