En informática , los analizadores sintácticos LR son un tipo de analizador sintáctico ascendente que analiza lenguajes deterministas libres de contexto en tiempo lineal. [1] Existen varias variantes de analizadores sintácticos LR: analizadores sintácticos SLR , analizadores sintácticos LALR , analizadores sintácticos LR(1) canónicos , analizadores sintácticos LR(1) mínimos y analizadores sintácticos LR generalizados (analizadores GLR). Los analizadores sintácticos LR pueden ser generados por un generador de analizadores sintácticos a partir de una gramática formal que define la sintaxis del lenguaje que se va a analizar. Se utilizan ampliamente para el procesamiento de lenguajes informáticos .
Un analizador LR (de izquierda a derecha, derivación más a la derecha en reversa) lee el texto de entrada de izquierda a derecha sin retroceder (esto es cierto para la mayoría de los analizadores) y produce una derivación más a la derecha en reversa: realiza un análisis de abajo a arriba , no un análisis LL de arriba a abajo o un análisis ad hoc. El nombre "LR" a menudo va seguido de un calificador numérico, como en "LR(1)" o, a veces, "LR( k )". Para evitar dar marcha atrás o adivinar, se permite al analizador LR echar un vistazo a k símbolos de entrada de búsqueda anticipada antes de decidir cómo analizar los símbolos anteriores. Normalmente, k es 1 y no se menciona. El nombre "LR" a menudo va precedido de otros calificadores, como en "SLR" y "LALR". Knuth sugirió la notación "LR( k )" para una gramática para representar "traducible de izquierda a derecha con límite k ". [1]
Los analizadores LR son deterministas; producen un único 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 arbitrarios libres de contexto (por ejemplo, Cocke–Younger–Kasami , Earley , GLR ) tienen un rendimiento en el peor de los casos de tiempo O( n 3 ). Otros métodos que retroceden o producen múltiples análisis pueden incluso tardar un tiempo exponencial cuando adivinan mal. [2]
Las propiedades anteriores de L , R y k son compartidas por todos los analizadores sintácticos de reducción por desplazamiento , incluidos los analizadores sintácticos de precedencia . Pero por convención, el nombre LR representa la forma de análisis sintáctico inventada por Donald Knuth , y excluye los métodos de precedencia anteriores, menos potentes (por ejemplo, el analizador sintáctico de precedencia de operadores ). [1] Los analizadores sintácticos LR pueden manejar una gama más amplia de idiomas y gramáticas que los analizadores sintácticos de precedencia o el análisis sintáctico LL de arriba hacia abajo . [3] 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 sintáctico 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.
Un analizador LR escanea y analiza el texto de entrada en una pasada 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 esta pasada, 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 correcto del patrón de sintaxis que los combinará.
En el paso 6 de un análisis de ejemplo, 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 los 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".
Al igual que otros analizadores con función Shift-Reduce, un analizador LR funciona realizando una combinación de pasos Shift y pasos Reduce.
Si la entrada no tiene errores de sintaxis, el analizador continúa con estos pasos hasta que se haya consumido toda la entrada y todos los árboles de análisis se hayan reducido a un solo árbol que representa una entrada legal completa.
Los analizadores LR difieren de otros analizadores de desplazamiento-reducción en cómo deciden cuándo reducir y cómo elegir entre reglas con finales similares. Pero 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 carácter determinista. Para evitar adivinar, el analizador LR suele mirar hacia delante (hacia la derecha) en el siguiente símbolo escaneado, antes de decidir qué hacer con los símbolos escaneados anteriormente. El escáner léxico trabaja con uno o más símbolos por delante del analizador. Los símbolos de búsqueda anticipada son el "contexto de la derecha" para la decisión de análisis. [4]
Al igual que otros analizadores con reducción por desplazamiento, un analizador LR espera perezosamente hasta que ha escaneado y analizado todas las partes de algún constructo antes de decidir cuál es el constructo combinado. El analizador actúa entonces 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-3 tan pronto como se ve lookahead *, en lugar de esperar más tiempo 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 cosas que aparecen mucho más tarde a la derecha.
Las reducciones reorganizan los elementos analizados más recientemente, inmediatamente a la izquierda del símbolo de búsqueda anticipada. De modo que la lista de elementos ya analizados 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 y más a la izquierda. Cada paso de reducción actúa solo sobre los fragmentos de análisis más nuevos y más a la derecha. (Esta pila de análisis acumulativa es muy diferente a la pila de análisis predictiva que crece hacia la izquierda que utilizan los analizadores descendentes ).
El paso 6 aplica una regla gramatical con múltiples partes:
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 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 los Productos internos y Valor se envían a algún paso posterior del compilador o se combinan y guardan en el nuevo símbolo Productos. [5]
En los analizadores LR, las decisiones de cambio 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 pila superior. Si se hace de una manera poco inteligente, eso podría dar lugar 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, resumiendo toda la información de contexto izquierda relevante en un solo número llamado estado del analizador LR(0) . Para cada gramática y método de análisis 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 de anticipación actual y el texto restante sin escanear. La siguiente acción del analizador se determina por su número de estado LR(0) actual (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 los mismos que en otros analizadores sintácticos con desplazamiento-reducción que no sean LR. Las pilas de analizadores sintácticos LR agregan la información de estado en violeta, resumiendo las frases en negro a su izquierda en la pila y las posibilidades de sintaxis que se esperan a continuación. Los usuarios de un analizador sintáctico 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
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 desplazar 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
Los estados correspondientes a las frases apiladas son 0, 4 y 5. El estado actual, más a la derecha en la pila, es el estado 5. Cuando el estado 5 ve el int de anticipación , sabe que debe desplazar ese int 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 la búsqueda anticipada eof , sabe que debe aplicar la regla gramatical completada.
combinando las tres frases más a la derecha de la pila para Sumas, + y Productos en una sola cosa. El estado 3 en sí mismo no sabe cuál debería ser el siguiente 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 completada de una Suma, avanza al estado 1 (nuevamente). Esta consulta de estados anteriores es la razón por la que se mantienen en la pila, en lugar de mantener 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. La gramática no cubre 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 de todo el programa. Los analizadores LR utilizan una gramática independiente del 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:
Los símbolos terminales de la gramática son los símbolos de múltiples caracteres o "tokens" que un escáner léxico encuentra en el flujo de entrada . Aquí, 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 int o la ortografía de id , ni tampoco le importan 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 y tupido) del árbol de análisis.
Los términos en mayúsculas como Sumas son símbolos no terminales . Son nombres de conceptos o patrones en el lenguaje. Se definen en la gramática y nunca aparecen en el flujo de entrada. Siempre son nodos internos (por 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 hacer referencia a sí mismas, lo que se denomina recursivo . Esta gramática utiliza reglas recursivas para manejar operadores matemáticos repetidos. Las gramáticas para lenguajes completos utilizan reglas recursivas para manejar listas, expresiones entre paréntesis y declaraciones anidadas.
Cualquier lenguaje de programación puede describirse mediante varias gramáticas diferentes. Un analizador sintáctico LR(1) puede manejar muchas gramáticas comunes, pero no todas. 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 ser aumentada 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 lenguaje, lo que da como resultado un árbol de análisis único con un solo significado y una secuencia única de acciones de desplazamiento/reducción para ese ejemplo. El análisis LR no es una técnica útil para los lenguajes humanos con gramáticas ambiguas que dependen de la interacción de 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.
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 e idiomas. El conocimiento de la gramática y sus implicaciones sintácticas se codifican en tablas de datos inmutables llamadas tablas de análisis (o tablas de análisis ). Las entradas de una tabla muestran si se debe desplazar o reducir (y mediante 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 sintácticos como Bison . [6]
Dependiendo de cómo se generen los estados y la tabla de análisis, el analizador resultante se denomina analizador SLR (LR simple) , analizador LALR (LR de anticipación) o analizador LR canónico . Los analizadores LALR manejan más gramáticas que los analizadores SLR. Los analizadores LR canónicos manejan incluso más gramáticas, pero utilizan muchos más estados y tablas mucho más grandes. La gramática de ejemplo es SLR.
Las tablas de análisis LR son bidimensionales. Cada estado actual del analizador LR(0) tiene su propia fila. Cada posible símbolo siguiente tiene su propia columna. Algunas combinaciones de estado y símbolo siguiente no son posibles para flujos de entrada válidos. Estas celdas en blanco activan mensajes de error de sintaxis.
La mitad izquierda de la tabla de acciones tiene columnas para símbolos de terminal de búsqueda anticipada. Estas celdas determinan si la siguiente acción del analizador es desplazar (al estado n ) o reducir (según la regla gramatical r n ).
La mitad derecha 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 símbolos no terminales; el símbolo terminal de búsqueda anticipada no cambia.
La columna de la tabla "Reglas actuales" documenta el significado y las posibilidades sintácticas de cada estado, tal como las calcula el generador del analizador. No se incluye en las tablas reales que se utilizan 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 • se han analizado y se espera que las cosas a la derecha se analicen pronto. Un estado tiene varias de esas 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 desplazar el signo + de la regla gramatical.
La siguiente frase esperada es Productos. Productos comienza con los símbolos terminales int o id . Si el lookahead es cualquiera de estos, el analizador los desplaza hacia adentro y avanza al estado 8 o 9, respectivamente. Cuando se ha encontrado un Productos, el analizador avanza al estado 3 para acumular la lista completa de sumandos y encontrar el final de la regla r0. Un Productos también puede comenzar con un valor no terminal. Para cualquier otro lookahead 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 una de dos posibles reglas gramaticales:
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 anticipación es * , está en la regla 3, por lo que el analizador cambia 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 que no están en blanco ni contienen errores corresponden a la misma reducción r6. Algunos analizadores ahorran tiempo y espacio en la tabla al no comprobar el símbolo de búsqueda anticipada en estos casos simples. Los errores de sintaxis se detectan un poco más tarde, después de algunas reducciones inofensivas, pero antes de la siguiente acción de desplazamiento o decisión del analizador.
Las celdas de una tabla individual no deben contener múltiples acciones alternativas, de lo contrario el analizador no sería determinista y tendría que hacer conjeturas y volver atrás. Si la gramática no es LR(1), algunas celdas tendrá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 sea 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 búsqueda anticipada que contiene el primer símbolo escaneado del flujo de entrada. Luego, el analizador repite el siguiente paso del bucle hasta que termina o se queda atascado en un error de sintaxis:
El estado superior en la pila de análisis es un estado s y la búsqueda anticipada 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 búsqueda anticipada. Esa acción es Shift, Reduce, Accept o Error:
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 ese estado). Además, estos símbolos casi nunca son necesarios ya que el estado es todo lo que importa al tomar la decisión de análisis. [7]
La mayoría de los usuarios de generadores de analizadores sintácticos LR pueden omitir esta sección del artículo.
El estado 2 en la tabla de análisis de ejemplo es para la regla parcialmente analizada
Esto muestra cómo llegó el analizador a esta situación, al ver Sums y luego + mientras buscaba un Sums más grande. El marcador • ha avanzado más allá del comienzo de la regla. También muestra cómo el analizador espera completar eventualmente la regla, al encontrar a continuación un Products completo. Pero se necesitan más detalles sobre cómo analizar todas las partes de ese Products.
Las reglas parcialmente analizadas para un estado se denominan "elementos LR(0) básicos". El generador del analizador agrega reglas o elementos adicionales para todos los posibles pasos siguientes en la creación de los productos esperados:
El marcador • está al principio de cada una de estas reglas agregadas; el analizador aún no ha confirmado ni analizado ninguna parte de ellas. Estos elementos adicionales se denominan "cierre" de los elementos principales. Para cada símbolo no terminal que sigue inmediatamente a un • , el generador agrega las reglas que definen ese símbolo. Esto agrega 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 Products. Luego, se agrega Value por cierre. Los terminales seguidores son int e id .
Los elementos de núcleo y cierre juntos muestran todas las formas legales posibles de proceder desde el estado actual a estados futuros y frases completas. Si un símbolo de seguidor aparece en un solo elemento, conduce a un estado siguiente que contiene solo un elemento de núcleo con el marcador • avanzado. Por lo tanto, int conduce al siguiente estado 8 con núcleo
Si el mismo símbolo seguidor aparece en varios elementos, el analizador aún no puede determinar qué regla se aplica aquí. Por lo tanto, ese símbolo conduce a un siguiente estado que muestra todas las posibilidades restantes, nuevamente con el marcador • avanzado. Productos aparece tanto en r1 como en r3. Por lo tanto, Productos conduce al siguiente estado 3 con el núcleo
En otras palabras, eso significa que si el analizador ha visto un solo producto, es posible que haya terminado, o que aún tenga más elementos para multiplicar. Todos los elementos principales tienen el mismo símbolo antes del marcador • ; todas las transiciones a este estado siempre tienen el mismo símbolo.
Algunas transiciones se dirigirán a núcleos y estados que ya se han enumerado. Otras transiciones conducen a nuevos estados. El generador comienza con la regla de objetivo de la gramática. A partir de allí, continúa explorando estados y transiciones conocidos hasta que se hayan encontrado todos los estados necesarios.
Estos estados se denominan estados "LR(0)" porque utilizan un valor de anticipación de k = 0, es decir, no hay ningún valor de anticipación. La única comprobación de los símbolos de entrada se produce cuando se desplaza el símbolo hacia dentro. La comprobación de los valores de anticipación para las reducciones se realiza por separado mediante la tabla de análisis, no mediante los propios estados enumerados.
La tabla de análisis describe todos los estados LR(0) posibles y sus transiciones. Forman una máquina de estados finitos (FSM). Una FSM es un motor simple para analizar lenguajes simples no anidados, sin usar una pila. En esta aplicación LR, el "lenguaje de entrada" modificado de la FSM tiene símbolos terminales y no terminales, y cubre 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, 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 desplazamiento o de ir a 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) y encontrar la frase completa más a la izquierda que se debe reducir a continuación. ¡Y ese es, de hecho, su trabajo!
¿Cómo puede una simple FSM hacer esto cuando el lenguaje original sin analizar tiene anidamiento y recursión y definitivamente requiere un analizador con una pila? El truco es que todo lo que está a la izquierda de la parte superior de la pila ya se ha reducido por completo. Esto elimina todos los bucles y anidamiento de esas frases. La FSM puede ignorar todos los comienzos de frases más antiguos 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".
Los estados y las transiciones brindan toda la información necesaria para las acciones de desplazamiento y de ir a la tabla de análisis. El generador también debe calcular los conjuntos de búsqueda anticipada esperados para cada acción de reducción.
En los analizadores sintácticos SLR , estos conjuntos de anticipación se determinan directamente a partir de la gramática, sin considerar los estados y 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 sintáctico, cada reducción a S utiliza Follow(S) como su conjunto de anticipación LR(1). Estos conjuntos de anticipación también son utilizados por los generadores de analizadores sintácticos de arriba hacia abajo LL. Una gramática que no tiene conflictos de desplazamiento/reducción o reducción/reducción cuando utiliza conjuntos de seguimiento se denomina gramática SLR.
Los analizadores LALR tienen los mismos estados que los analizadores SLR, pero utilizan una forma más complicada y precisa de calcular los valores mínimos de reducción necesarios para cada estado individual. Según los detalles de la gramática, puede resultar que sea el mismo que el conjunto Follow calculado por los generadores de analizadores SLR, o puede resultar que sea un subconjunto de los valores de reducción SLR. Algunas gramáticas son adecuadas para los generadores de analizadores LALR, pero no para los generadores de analizadores SLR. Esto sucede cuando la gramática tiene conflictos de desplazamiento/reducción o reducción/reducción espurios utilizando conjuntos Follow, pero no conflictos cuando se utilizan los conjuntos exactos calculados por el generador LALR. La gramática se denomina entonces 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 innecesarios de búsqueda anticipada. Los analizadores LR canónicos utilizan 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 conflictos de reducción. Esto maneja algunas gramáticas más. Desafortunadamente, esto aumenta en gran medida 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 no tiene conflictos para un generador LR canónico pero que 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 lenguaje correcto. Cuando la entrada tiene un error de sintaxis, el analizador LALR puede realizar algunas reducciones adicionales (inofensivas) antes de detectar el error, en comparación con las que haría el analizador LR canónico. Y el analizador SLR puede hacer incluso 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 y verdaderos para ese estado en particular.
Los analizadores LR pueden generar mensajes de error bastante ú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 símbolo de búsqueda anticipada incorrecto inesperado. 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 sintácticos yacc y bison, el analizador sintáctico tiene un mecanismo ad hoc para abandonar la declaración actual, descartar algunas frases analizadas y tokens de anticipación que rodean el error y volver a sincronizar el análisis con algún delimitador confiable a nivel de declaració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 errores tipográficos u omisiones de un símbolo trivial. Algunos analizadores LR intentan detectar y reparar automáticamente estos casos comunes. El analizador enumera cada posible inserción, eliminación o sustitución 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 instantáneas de la pila de análisis y el flujo de entrada, normalmente innecesarios para el analizador). Se selecciona una mejor reparación. Esto genera 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 hacer de manera consistente en analizadores (como LR) que tienen tablas de análisis y una pila de datos explícita.
El generador de analizador LR decide qué debe suceder para cada combinación de estado del analizador y símbolo de anticipación. Estas decisiones se suelen convertir en tablas de datos de solo lectura que impulsan un bucle de analizador genérico que es independiente de la gramática y del estado. Pero también hay otras formas de convertir esas decisiones en un analizador activo.
Algunos generadores de analizadores sintácticos LR crean un código de programa personalizado independiente para cada estado, en lugar de una tabla de análisis sintáctico. Estos analizadores sintácticos pueden ejecutarse varias veces más rápido que el bucle de análisis sintáctico genérico en analizadores sintácticos controlados por tablas. Los analizadores sintácticos más rápidos utilizan código ensamblador generado.
En la variante del analizador ascendente 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 terminan varios niveles de llamadas a subrutinas, lo que resulta complicado en la mayoría de los lenguajes. Por lo tanto, los analizadores ascendentes recursivos son generalmente más lentos, menos obvios y más difíciles de modificar manualmente que los analizadores descendentes recursivos .
Otra variación reemplaza la tabla de análisis por reglas de coincidencia de patrones en lenguajes no procedimentales como Prolog .
Los analizadores sintácticos LR generalizados utilizan técnicas ascendentes de LR para encontrar todos los análisis sintácticos posibles del texto de entrada, no solo un análisis sintáctico correcto. Esto es esencial para gramáticas ambiguas como las que se utilizan en los lenguajes humanos. Los múltiples árboles de análisis sintáctico válidos se calculan simultáneamente, sin retroceso. GLR a veces es útil para lenguajes informáticos que no se describen fácilmente mediante una gramática LALR(1) libre de conflictos.
Los analizadores sintácticos de esquina izquierda de LC utilizan técnicas ascendentes de LR para reconocer el extremo izquierdo de las reglas gramaticales alternativas. Cuando las alternativas se han reducido a una única regla posible, el analizador cambia a técnicas descendentes LL(1) para analizar el resto de esa regla. Los analizadores sintácticos de LC tienen tablas de análisis más pequeñas que los analizadores sintácticos de LALR y mejores diagnósticos de errores. No existen generadores ampliamente utilizados para analizadores sintácticos de LC deterministas. Los analizadores sintácticos de LC de análisis múltiple son útiles con lenguajes humanos con gramáticas muy grandes.
Los analizadores sintácticos LR fueron inventados por Donald Knuth en 1965 como una generalización eficiente de los analizadores sintácticos de precedencia . Knuth demostró que los analizadores sintácticos LR eran los analizadores sintácticos más generales posibles y que aún serían eficientes en los peores casos. [ cita requerida ]
En otras palabras, si un lenguaje fuera lo suficientemente razonable como para permitir un analizador sintáctico eficiente de una sola pasada, 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). 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 para muchos lenguajes de programación están cerca de ser LR(1). [ cita requerida ]
Los analizadores LR canónicos descritos por Knuth tenían demasiados estados y tablas de análisis muy grandes que eran imprácticamente 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. [10] [11]
Para obtener detalles completos sobre la teoría LR y cómo los analizadores sintácticos LR se derivan de las gramáticas, consulte The Theory of Parsing, Translation, and Compiling, Volume 1 (Aho y Ullman). [7] [2]
Los analizadores sintácticos Earley aplican las técnicas y la notación de los analizadores sintácticos LR a la tarea de generar todos los análisis posibles para gramáticas ambiguas, como las de los 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 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] 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 . [ 14 ]
Este ejemplo de análisis LR utiliza la siguiente gramática pequeña con el símbolo de objetivo E:
Para analizar la siguiente entrada:
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 una terminal (incluida una terminal especial $ que indica el final del flujo de entrada) y contiene tres tipos de acciones:
La tabla goto está indexada por un estado del analizador y un no terminal y simplemente indica cuál será el siguiente estado del analizador si ha reconocido un determinado no terminal. Esta tabla es importante para averiguar el siguiente estado después de cada reducción. Después de una reducción, el siguiente estado se encuentra buscando la entrada de la tabla goto para la parte superior de la pila (es decir, el estado actual) y el LHS de la regla reducida (es decir, no terminal).
La siguiente tabla ilustra cada paso del proceso. Aquí, el estado se refiere al elemento que se encuentra en la parte superior de la pila (el elemento que se encuentra 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 secuencia.
El analizador comienza con la pila que contiene solo el estado inicial ('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 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 cambio al estado 2, y por lo tanto el estado 2 se inserta en la pila (de nuevo, toda la información de estado está en la pila, por lo que "cambiar al estado 2" es lo mismo que insertar 2 en la pila). La pila resultante es
donde la parte superior de la pila es 2. Para mayor claridad se muestra el símbolo (por ejemplo, '1', B) que provocó la transición al siguiente estado, aunque estrictamente hablando no es parte de la pila.
En el estado 2, la tabla de acciones indica que se debe reducir con la regla gramatical 5 (sin importar qué terminal ve 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 (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 el estado 0 y B, es decir, el estado 4. La pila resultante es:
Sin embargo, en el estado 4, la tabla de acciones dice que el analizador ahora debe reducir 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 el estado 0 y E, que es el estado 3. La pila resultante:
La siguiente terminal que ve el analizador es un '+' y, según la tabla de acciones, debería pasar al estado 6:
La pila resultante se puede interpretar como el historial de un autómata de estados finitos que acaba de leer una E no terminal seguida de un '+' 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 goto en la tabla de goto.
La siguiente terminal ahora es '1' y esto significa que el analizador realiza un cambio y pasa al estado 2:
Al igual que el '1' anterior, este se reduce a B dando la siguiente pila:
La pila corresponde a una lista de estados de un autómata finito que ha leído un E no terminal, seguido de un '+' y luego un B no terminal. En el estado 8, el analizador siempre realiza una reducción con la regla 2. Los 3 estados superiores de la pila corresponden a los 3 símbolos del lado derecho de la regla 2. Esta vez, sacamos 3 elementos de la pila (ya que el lado derecho de la regla tiene 3 símbolos) y buscamos el estado al que se debe ir para E y 0, con lo que volvemos a colocar el estado 3 en la pila.
Finalmente, el analizador lee un '$' (símbolo de fin de entrada) del flujo de entrada, lo que significa que, según la tabla de acciones (el estado actual es 3), el analizador acepta la cadena de entrada. Los números de reglas que se habrán escrito en el flujo de salida serán [5, 3, 5, 2], que es, de hecho, una derivación del extremo derecho de la cadena "1 + 1" en sentido inverso.
La construcción de estas tablas de análisis se basa en la noción de elementos LR(0) (aquí simplemente llamados elementos ) que son reglas gramaticales con un punto especial agregado en algún lugar del lado derecho. Por ejemplo, la regla E → E + B tiene los siguientes cuatro elementos correspondientes:
Las reglas de la forma A → ε tienen un solo 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 '+' seguido de otra cadena correspondiente a B.
Normalmente no es posible caracterizar el estado del analizador con un único elemento porque puede que no sepa de antemano qué regla va a 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 • * B se aplicarán después de que se haya leído una cadena correspondiente a E. Por lo tanto, es conveniente caracterizar el estado del analizador con un conjunto de elementos, en este caso el conjunto { E → E • + B, E → E • * B }.
Un elemento con un punto antes de un elemento no terminal, como E → E + • B, indica que el analizador espera analizar el elemento no terminal B a continuación. 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, entonces 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:
Por lo tanto, cualquier conjunto de elementos se puede ampliar añadiendo recursivamente todos los elementos apropiados hasta que se tengan en cuenta todos los elementos no terminales precedidos por puntos. La extensión mínima se denomina cierre de un conjunto de elementos y se escribe clos ( I ) donde I es un conjunto de elementos. Son estos conjuntos de elementos cerrados los que se toman como estados del analizador, aunque solo se incluirán en las tablas aquellos que sean realmente accesibles desde el estado inicial.
Antes de determinar las transiciones entre los diferentes estados, la gramática se amplía con una regla adicional
donde S es un nuevo símbolo de inicio y E el antiguo. El analizador utilizará esta regla para la reducción exactamente cuando haya aceptado toda la cadena de entrada.
Para este ejemplo, la misma gramática que la anterior se amplía de la siguiente manera:
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 añadida: S → • E eof:
El " + " en negrita que aparece 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 elementos originales sin un " + " se denominan núcleo del conjunto de elementos.
Partiendo del estado inicial (S0), se determinan todos los estados a los que se puede llegar desde este estado. Las posibles transiciones para un conjunto de elementos se pueden encontrar observando los símbolos (terminales y no terminales) que se encuentran 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 conduce cada símbolo, se sigue el siguiente procedimiento para cada uno de los símbolos:
Para la terminal '0' (es decir, donde x = '0') esto da como resultado:
y para la terminal '1' (es decir, donde x = '1') esto da como resultado:
y para el E no terminal (es decir, donde x = E) esto resulta en:
y para el no terminal B (es decir, donde x = B) esto resulta en:
El cierre no agrega nuevos elementos en todos los casos: en los nuevos conjuntos anteriores, por ejemplo, no hay elementos 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 las terminales '*' y '+'. Para el símbolo, la transición va a:
y para la transición va a:
Ahora comienza la tercera iteración.
Para el conjunto de elementos 5, se deben considerar 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:
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 es:
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 estados, se muestra a continuación.
La tabla de transición para el autómata ahora se ve así:
A partir de esta tabla y de los conjuntos de elementos encontrados, las tablas de acción y de destino se construyen de la siguiente manera:
El lector puede verificar que estos pasos producen la acción y el acceso a la tabla presentada anteriormente.
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 se produzca independientemente del siguiente símbolo en el flujo de entrada. Por eso se trata de tablas de análisis LR(0): no realizan ninguna búsqueda anticipada (es decir, buscan símbolos cero por adelantado) antes de decidir qué reducción realizar. Una gramática que necesita una búsqueda anticipada para desambiguar 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).
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 desplazamiento (un conflicto desplazamiento-reducción ) o con dos acciones de reducción diferentes (un conflicto reducción-reducción ). 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 desplazamiento-reducción es el problema de else pendiente .
Un pequeño ejemplo de una gramática no LR(0) con un conflicto de desplazamiento-reducción es:
Uno de los conjuntos de elementos encontrados es:
Hay un conflicto de desplazamiento-reducción en este conjunto de elementos: al construir la tabla de acciones según las reglas anteriores, la celda para [conjunto de elementos 1, terminal '1'] contiene s1 (desplazamiento al estado 1) y r2 (reducción con la regla gramatical 2).
Un pequeño ejemplo de una gramática no LR(0) con un conflicto de reducción-reducción es:
En este caso se obtiene el siguiente conjunto de elementos:
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 una para la regla 4.
Ambos ejemplos anteriores se pueden resolver dejando que el analizador utilice el conjunto siguiente (ver analizador LL ) de un A no terminal para decidir si va a utilizar una de las reglas de A para una reducción; solo utilizará la regla A → w para una reducción si el siguiente símbolo en el flujo de entrada está en el conjunto siguiente de A. Esta solución da como resultado los denominados analizadores LR simples .
