En informática , los analizadores LR son un tipo de analizador ascendente que analiza lenguajes deterministas libres de contexto en tiempo lineal. [1] Hay varias variantes de analizadores LR: analizadores SLR , analizadores LALR , analizadores LR(1) canónicos , analizadores LR(1) mínimos y analizadores LR generalizados (analizadores GLR). Los analizadores LR pueden ser generados por un generador de analizadores a partir de una gramática formal que define la sintaxis del lenguaje que se va a analizar. Son ampliamente utilizados para el procesamiento de lenguajes informáticos .
Un analizador LR (de izquierda a derecha, derivación más a la derecha a la inversa) 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 a la inversa: realiza un análisis de abajo hacia arriba . no es un análisis LL de arriba hacia abajo o un análisis ad-hoc. El nombre "LR" suele ir seguido de un calificador numérico, como en "LR(1)" o, a veces, "LR( k )". Para evitar retroceder o adivinar, el analizador LR puede echar un vistazo hacia adelante a k símbolos de entrada anticipados antes de decidir cómo analizar los símbolos anteriores. Normalmente k es 1 y no se menciona. El nombre "LR" suele ir precedido de otros calificativos, como en "SLR" y "LALR". Knuth sugirió que la notación "LR( k )" para una gramática significara "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 en realidad son compartidas por todos los analizadores de reducción de desplazamiento , incluidos los analizadores de precedencia . Pero por convención, el nombre LR representa la forma de análisis inventada por Donald Knuth y excluye los métodos de precedencia anteriores y menos potentes (por ejemplo, el analizador de precedencia de operadores ). [1] Los analizadores LR pueden manejar una gama más amplia de idiomas y gramáticas que los analizadores de precedencia o el análisis LL de arriba hacia abajo . [3] Esto se debe a que el analizador LR espera hasta haber visto una instancia completa de algún patrón gramatical antes de comprometerse con lo que ha encontrado. Un analizador LL tiene que decidir o adivinar lo que está viendo mucho antes, cuando solo ha visto el símbolo de entrada más a la izquierda de ese patrón.
Un analizador LR escanea y analiza el texto de entrada en una pasada sobre el texto. El analizador construye el árbol de análisis de forma incremental, de abajo hacia arriba y de izquierda a derecha, sin adivinar ni retroceder. En cada punto de este paso, el analizador ha acumulado una lista de subárboles o frases del texto de entrada que ya han sido analizados. Esos subárboles aún no están unidos porque el analizador aún no ha llegado al extremo derecho del patrón de sintaxis que los combinará.
En el paso 6 de un análisis de ejemplo, sólo se analizó "A*2", de forma incompleta. Sólo existe la esquina inferior izquierda sombreada del árbol de análisis. Ninguno de los nodos del árbol de análisis numerados 7 y superiores 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 parte restante sin analizar del flujo de entrada es "+ 1".
Al igual que con otros analizadores de reducción de desplazamiento, un analizador LR funciona haciendo una combinación de pasos de desplazamiento y pasos de reducción.
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 se diferencian de otros analizadores de reducción de desplazamiento en cómo deciden cuándo reducir y cómo elegir entre reglas con finales similares. Pero las decisiones finales y la secuencia de cambios o reducción de pasos son las mismas.
Gran parte de la eficiencia del analizador LR se debe a que es determinista. Para evitar adivinar, el analizador LR a menudo mira hacia adelante (hacia la derecha) en el siguiente símbolo escaneado, antes de decidir qué hacer con los símbolos escaneados previamente. El escáner léxico trabaja uno o más símbolos antes que el analizador. Los símbolos de anticipación son el "contexto derecho" para la decisión de análisis. [4]
Al igual que otros analizadores de reducción de desplazamiento, un analizador LR espera perezosamente hasta haber escaneado y analizado todas las partes de alguna construcción antes de comprometerse con cuál es la construcción combinada. Luego, el analizador actúa inmediatamente sobre la combinación en lugar de esperar más. En el ejemplo del árbol de análisis, la frase A se reduce a Valor y luego a Productos en los pasos 1 a 3 tan pronto como se ve la anticipación *, en lugar de esperar más tarde para organizar esas partes del árbol de análisis. Las decisiones sobre cómo manejar A se basan únicamente en lo que el analizador y el escáner ya han visto, sin considerar las cosas que aparecen mucho más adelante a la derecha.
Las reducciones reorganizan los elementos analizados más recientemente, inmediatamente a la izquierda del símbolo de anticipación. Entonces, la lista de cosas ya analizadas actúa como una pila . Esta pila de análisis crece hacia la derecha. La base o parte inferior de la pila está a la izquierda y contiene el fragmento de análisis más antiguo y más a la izquierda. Cada paso de reducción actúa sólo en los fragmentos de análisis más recientes y situados más a la derecha. (Esta pila de análisis acumulativo es muy diferente a la pila de análisis predictiva que crece hacia la izquierda utilizada por los analizadores de arriba hacia abajo ).
El paso 6 aplica una regla gramatical con varias 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í Productos más grandes. Si el analizador crea á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 y Valor internos se envían a algún paso posterior del compilador, o se combinan y guardan en el nuevo símbolo de 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 pila superior. Si se hace de una manera poco inteligente, eso podría llevar 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 relevante del contexto izquierdo en un solo número llamado estado del analizador LR(0) . Para cada método de análisis de gramática y LR, existe 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 analizar. La siguiente acción del analizador está determinada por su número de estado actual LR(0) (el extremo derecho de 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 de reducción de desplazamiento que no son LR. Las pilas de analizadores LR agregan la información de estado en violeta, resumiendo las frases negras a su izquierda en la pila y las posibilidades de sintaxis que se pueden 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
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 cambiar ese id a la pila, escanea el siguiente símbolo de entrada * y avanza 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 situado más a la derecha en la pila es el estado 5. Cuando el estado 5 ve el int anticipado , sabe que debe cambiar ese int a la pila como su propia frase, y escanee el siguiente símbolo de entrada + y avance al estado 8.
En el paso 12, todo el flujo de entrada se ha consumido pero sólo parcialmente organizado. El estado actual es 3. Cuando el estado 3 ve el eof anticipado , sabe que debe aplicar la regla gramatical completa.
combinando las tres frases de la derecha de la pila para Sumas, + y Productos en una sola cosa. El estado 3 en sí no sabe cuál debería ser el próximo estado. Esto se encuentra volviendo al estado 0, justo a la izquierda de la frase que se está reduciendo. Cuando el estado 0 ve esta nueva instancia completa de Sums, avanza al estado 1 (nuevamente). Esta consulta de estados más antiguos es la razón por la que se mantienen en la pila, en lugar de mantener solo el estado actual.
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 consistente de nombres y sus definiciones en el contexto de todo el programa. Los analizadores LR utilizan una gramática libre de contexto que se ocupa ú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 varios caracteres o "tokens" que se encuentran en el flujo de entrada mediante un escáner léxico . Aquí estos incluyen + * e int para cualquier constante entera, e 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 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 de hojas (en el extremo inferior tupido) del árbol de análisis.
Los términos en mayúscula como Sums son símbolos no terminales . Estos son nombres de conceptos o patrones en el idioma. Están definidos en la gramática y nunca aparecen en el flujo de entrada. Siempre son nodos internos (encima de la parte inferior) del árbol de análisis. Solo ocurren como resultado de que el analizador aplica 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 de lenguajes completos utilizan reglas recursivas para manejar listas, expresiones entre paréntesis y declaraciones anidadas.
Cualquier lenguaje informático determinado 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 la herramienta generadora.
La gramática de un analizador LR debe ser inequívoca en sí misma o debe complementarse con reglas de precedencia de desempate. Esto significa que solo hay una forma correcta de aplicar la gramática a un ejemplo legal determinado del lenguaje, lo que da como resultado un árbol de análisis único con un solo significado y una secuencia única de acciones de cambio/reducción para ese ejemplo. El análisis LR no es una técnica útil para 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 funcionan con 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 cambiar 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 el estado actual y el 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 manualmente con precisión para gramáticas grandes. Por lo tanto, se derivan mecánicamente de la gramática mediante alguna herramienta generadora de analizadores como Bison . [6]
Dependiendo de cómo se generan los estados y la tabla de análisis, el analizador resultante se denomina analizador SLR (LR simple) , analizador LALR (LR anticipado) o analizador LR canónico . Los analizadores LALR manejan más gramáticas que los analizadores SLR. Los analizadores canónicos LR manejan aún más gramáticas, pero usan muchos más estados y tablas mucho más grandes. La gramática de ejemplo es SLR.
Las tablas de análisis LR son bidimensionales. Cada estado actual del analizador LR(0) tiene su propia fila. Cada posible siguiente símbolo 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 generan mensajes de error de sintaxis.
La mitad izquierda de Acción de la tabla tiene columnas para símbolos de terminal de anticipación. 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 Ir a la 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 no terminales; el símbolo del terminal de anticipación no cambia.
La columna de la tabla "Reglas actuales" documenta el significado y las posibilidades de sintaxis para cada estado, según lo resuelto por el generador del analizador. No está incluido en las tablas reales utilizadas en el momento del análisis. El marcador • (punto rosa) muestra dónde se encuentra ahora el analizador, dentro de algunas reglas gramaticales parcialmente reconocidas. Las cosas a la izquierda de • han sido analizadas y las cosas a la derecha se esperan pronto. Un estado tiene varias reglas actuales de este tipo 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 + de la regla gramatical.
La siguiente frase esperada es Productos. Los productos comienzan con los símbolos de terminal int o id . Si la anticipación es cualquiera de esas opciones, el analizador las desplaza y avanza al estado 8 o 9, respectivamente. Cuando se ha encontrado un Producto, el analizador avanza al estado 3 para acumular la lista completa de sumandos y encontrar el final de la regla r0. Los Productos A también pueden comenzar con un Valor no terminal. Para cualquier otra búsqueda anticipada o no terminal, el analizador anuncia un error de sintaxis.
En el estado 3, el analizador acaba de encontrar una frase de Productos, que podría provenir de dos posibles reglas gramaticales:
La elección entre r1 y r3 no se puede decidir simplemente mirando hacia atrás en frases anteriores. El analizador debe 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 se desplaza en * 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 y que no contienen errores son para la misma reducción r6. Algunos analizadores ahorran tiempo y espacio en la tabla al no verificar el símbolo de anticipación en estos casos simples. Los errores de sintaxis se detectan un poco más tarde, después de algunas reducciones inofensivas, pero aún antes de la siguiente acción de cambio o decisión del analizador.
Las celdas individuales de la tabla no deben contener múltiples acciones alternativas; de lo contrario, el analizador no sería determinista, con conjeturas y retrocesos. Si la gramática no es LR(1), algunas celdas tendrán conflictos de cambio/reducción entre una posible acción de cambio y una acción de reducción, o conflictos de reducción/reducción entre múltiples reglas gramaticales. Los analizadores LR(k) resuelven estos conflictos (cuando sea posible) comprobando símbolos de anticipación adicionales además 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 contiene el primer símbolo escaneado del flujo de entrada. Luego, 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 algún estado s , y la búsqueda anticipada actual es algún símbolo terminal t . Busque la siguiente acción del analizador en la fila sy la columna t de la tabla Lookahead Action. Esa acción es Desplazar, Reducir, Aceptar 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 este estado) . Además, estos símbolos casi nunca son necesarios ya que el estado es lo único que importa al tomar la decisión de análisis. [7]
La mayoría de los usuarios de generadores de analizadores 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 hasta aquí, al ver Sumas y luego + mientras busca Sumas más grandes. El marcador • ha avanzado más allá del inicio de la regla. También muestra cómo el analizador espera completar eventualmente la regla, para luego encontrar Productos completos. Pero se necesitan más detalles sobre cómo analizar todas las partes de esos Productos.
Las reglas parcialmente analizadas para un estado se denominan "elementos principales LR(0)". El generador de analizador agrega reglas o elementos adicionales para todos los siguientes pasos posibles 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 ellos. Estos elementos adicionales se denominan "cierre" de los elementos principales. Para cada símbolo no terminal que sigue inmediatamente a • , el generador agrega las reglas que definen ese símbolo. Esto agrega más marcadores y posiblemente diferentes símbolos de seguidor. Este proceso de cierre continúa hasta que se hayan expandido todos los símbolos de seguidores. Los no terminales seguidores para el estado 2 comienzan con Productos. Luego se agrega valor mediante el cierre. Los terminales seguidores son int e id .
Los elementos del núcleo y de cierre juntos muestran todas las formas legales posibles de pasar del estado actual a estados futuros y frases completas. Si un símbolo de seguidor aparece solo en un elemento, conduce al siguiente estado que contiene solo un elemento principal con el marcador • avanzado. Entonces int conduce al siguiente estado 8 con núcleo
Si el mismo símbolo de seguidor aparece en varios elementos, el analizador aún no puede determinar qué regla se aplica aquí. Entonces ese símbolo conduce al siguiente estado que muestra todas las posibilidades restantes, nuevamente con el marcador • avanzado. Los productos aparecen tanto en r1 como en r3. Entonces Productos lleva al siguiente estado 3 con núcleo
En palabras, eso significa que si el analizador ha visto un solo Producto, es posible que lo haya hecho o que aún tenga más cosas para multiplicar. Todos los elementos básicos tienen el mismo símbolo antes del • marcador; todas las transiciones a este estado son siempre con el mismo símbolo.
Algunas transiciones serán a núcleos y estados que ya han sido enumerados. Otras transiciones conducen a nuevos estados. El generador comienza con la regla objetivo de la gramática. A partir de ahí, sigue 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, sin anticipación. La única verificación de los símbolos de entrada ocurre cuando el símbolo se desplaza hacia adentro. La verificación de las reducciones se realiza por separado mediante la tabla de análisis, no por los estados enumerados en sí.
La tabla de análisis describe todos los estados posibles de LR(0) y sus transiciones. Forman una máquina de estados finitos (FSM). Un FSM es un motor simple para analizar lenguajes simples no anidados, sin utilizar una pila. En esta aplicación LR, el "lenguaje de entrada" modificado del FSM tiene símbolos tanto terminales como 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 ir a para esas transiciones. Otra forma de ver esto es que la máquina de estados finitos puede escanear el flujo "Productos * int + 1" (sin usar otra pila más) y encontrar la frase completa más a la izquierda que debe reducirse a continuación. ¡Y ese es efectivamente su trabajo!
¿Cómo puede un simple FSM hacer esto cuando el lenguaje original no analizado tiene anidamiento y recursividad 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 anidamientos de esas frases. El FSM puede ignorar todos los comienzos de frases más antiguos y realizar un seguimiento solo de las frases más nuevas que podrían completarse a continuación. El oscuro nombre de esto en la teoría LR es "prefijo viable".
Los estados y las transiciones brindan toda la información necesaria para las acciones de cambio y las acciones de ir a de 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 S no terminal, el generador SLR calcula Follows(S), el conjunto de todos los símbolos terminales que pueden seguir inmediatamente a alguna aparición de S. En la tabla de análisis, cada reducción a S usa Follow(S) como su LR(1). ) conjunto de anticipación. Estos conjuntos de seguimiento también los utilizan los generadores para analizadores de arriba hacia abajo de LL. Una gramática que no tiene conflictos de desplazamiento/reducción o reducción/reducción cuando se utilizan 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 las reducciones mínimas necesarias para cada estado individual. Dependiendo de los detalles de la gramática, esto puede resultar ser el mismo que el conjunto de seguimiento calculado por los generadores de analizadores SLR, o puede resultar ser un subconjunto de las búsquedas anticipadas de SLR. Algunas gramáticas están bien para los generadores de analizadores LALR pero no para los generadores de analizadores SLR. Esto sucede cuando la gramática tiene conflictos de cambio/reducción o reducción/reducción falsos usando conjuntos de seguimiento, pero no hay conflictos cuando se usan los conjuntos exactos calculados por el generador LALR. La gramática se llama entonces LALR(1) pero no SLR.
Un analizador SLR o LALR evita tener estados duplicados. Pero esta minimización no es necesaria y, en ocasiones, puede crear conflictos de anticipación innecesarios. Los analizadores canónicos de LR 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 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 se puede realizar de forma manual y selectiva con cualquier analizador SLR o LALR, haciendo dos o más copias con nombre de algunos no terminales. Una gramática que está libre de conflictos para un generador LR canónico pero 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 que las que haría el analizador LR canónico. Y el analizador SLR puede hacer aún más. Esto sucede porque los analizadores SLR y LALR utilizan una generosa aproximación de superconjunto a los símbolos de anticipación mínimos y verdaderos para ese estado en particular.
Los analizadores LR pueden generar mensajes de error algo útiles para el primer error de sintaxis en un programa, simplemente enumerando todos los símbolos de terminal que podrían haber aparecido a continuación en lugar del inesperado símbolo de anticipación incorrecta. Pero esto no ayuda al analizador a descubrir cómo analizar el resto del programa de entrada para buscar más errores independientes. Si el analizador no se recupera correctamente del primer error, es muy probable que analice mal todo lo demás y produzca una cascada de mensajes de error falsos e inútiles.
En los generadores de analizadores yacc y bison, el analizador tiene un mecanismo ad hoc para abandonar la declaración actual, descartar algunas frases analizadas y tokens de anticipación que rodean el error y resincronizar el análisis en algún delimitador confiable a nivel de declaración, como punto y coma o llaves. Esto 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 una prueba de análisis con cada cambio para ver si funcionó bien. (Esto requiere retroceder hasta instantáneas de la pila de análisis y el flujo de entrada, lo que normalmente el analizador no necesita). Se elige la 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 realizar de manera consistente en analizadores (como LR) que tienen tablas de análisis y una pila de datos explícita.
El generador del analizador LR decide qué debería suceder para cada combinación de estado del analizador y símbolo de anticipación. Estas decisiones generalmente se convierten en tablas de datos de solo lectura que impulsan un bucle de analizador genérico que es independiente de la gramática y el estado. Pero también hay otras formas de convertir esas decisiones en un analizador activo.
Algunos generadores de analizadores LR crean códigos de programa personalizados separados para cada estado, en lugar de una tabla de análisis. Estos analizadores pueden ejecutarse varias veces más rápido que el bucle de analizador genérico en los analizadores controlados por tablas. Los analizadores más rápidos utilizan código ensamblador generado.
En la variación del analizador de ascenso recursivo , la estructura de la pila de análisis explícita 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 complicado en la mayoría de los idiomas. Por lo tanto, los analizadores de ascenso recursivos son generalmente más lentos, menos obvios y más difíciles de modificar manualmente que los analizadores de descenso recursivos .
Otra variación reemplaza la tabla de análisis por reglas de coincidencia de patrones en lenguajes no procesales como Prolog .
Los analizadores LR generalizados de GLR utilizan técnicas ascendentes de LR para encontrar todos los análisis posibles de texto de entrada, no solo un análisis correcto. Esto es esencial para gramáticas ambiguas como las que se utilizan en los lenguajes humanos. Los múltiples árboles de análisis válidos se calculan simultáneamente, sin retroceder. A veces, GLR es útil para lenguajes informáticos que no se describen fácilmente mediante una gramática LALR(1) libre de conflictos.
Los analizadores de la esquina izquierda de LC utilizan técnicas ascendentes de LR para reconocer el extremo izquierdo de reglas gramaticales alternativas. Cuando las alternativas se han reducido a una única regla posible, el analizador cambia a técnicas LL(1) de arriba hacia abajo para analizar el resto de esa regla. Los analizadores LC tienen tablas de análisis más pequeñas que los analizadores LALR y mejores diagnósticos de errores. No existen generadores ampliamente utilizados para analizadores LC deterministas. Los analizadores LC de análisis múltiple son útiles con lenguajes humanos con gramáticas muy 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 más generales posibles y seguirían siendo eficientes en los peores casos. [ cita necesaria ]
En otras palabras, si un lenguaje fuera lo suficientemente razonable como para permitir un analizador eficiente de un solo paso, podría describirse mediante una gramática LR( k ). Y esa gramática siempre podría transformarse mecánicamente en una gramática LR(1) equivalente (pero más grande). Por tanto, un método de análisis 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 están cerca de ser LR(1). [ cita necesaria ]
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 de LR y cómo los analizadores de LR se derivan de las gramáticas, consulte La teoría del análisis, la traducción y la compilación, Volumen 1 (Aho y Ullman). [7] [2]
Los analizadores Earley aplican las técnicas y • 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.
Mientras que las gramáticas LR( k ) tienen el mismo poder generativo para todo k ≥1, el caso de las gramáticas LR(0) es ligeramente diferente. Se dice que un idioma 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 sólo 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 pequeña gramática 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 un terminal (incluido un terminal especial $ que indica el final del flujo de entrada) y contiene tres tipos de acciones:
La tabla goto está indexada por el 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 conocer 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 en la parte superior de la pila (el elemento más a la derecha) y la siguiente acción se determina consultando la tabla de acciones anterior. Se agrega un $ a la cadena de entrada para indicar el final de la secuencia.
El analizador comienza con la pila que contiene sólo 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 (desplazar, 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, por lo que el estado 2 se inserta en la pila (nuevamente, toda la información del estado está en la pila, por lo que "cambiar al estado 2" es lo mismo que empujar 2 a la pila). La pila resultante es
donde la parte superior de la pila es 2. Para explicar el símbolo (por ejemplo, '1', B) se muestra que causó la transición al siguiente estado, aunque estrictamente hablando no es parte de la pila.
En el estado 2, la tabla de acciones dice reducir con la regla gramatical 5 (independientemente de qué terminal vea el analizador en el flujo de entrada), lo que significa que el analizador acaba de reconocer el lado derecho de la regla 5. En este caso, el 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 empuja en la pila el estado de la celda en la tabla Goto para los estados 0 y B, es decir. , estado 4. La pila resultante es:
Sin embargo, en el estado 4, la tabla de acciones dice que el analizador ahora debería reducir con la regla 3. Entonces escribe 3 en el flujo de salida, extrae un estado de la pila y encuentra el nuevo estado en la tabla Goto para los estados 0 y E. que es el estado 3. La pila resultante:
El 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 la historia de un autómata de estado finito que acaba de leer un E no terminal seguido 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 ir a la tabla de ir.
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 se corresponde con 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 en la La pila se corresponde con los 3 símbolos en el 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 de paso para E y 0. , empujando así el estado 3 nuevamente a 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 regla que luego se habrán escrito en el flujo de salida serán [5, 3, 5, 2], que de hecho es una derivación más a la derecha de la cadena "1 + 1" a la inversa.
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.
Generalmente no es posible caracterizar el estado del analizador con un solo elemento porque es posible 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 mediante un conjunto de elementos, en este caso el conjunto { 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 en medio del análisis, debe incluir todos los elementos que describan cómo se analizará B. Esto significa que si existen 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 agregando recursivamente todos los elementos apropiados hasta que se tengan en cuenta todos los no terminales precedidos por puntos. La extensión mínima se denomina cierre de un conjunto de elementos y se escribe como clos ( I ) donde I es un conjunto de elementos. Son estos conjuntos de elementos cerrados los que se toman como estados del analizador, aunque solo se incluirán en las tablas aquellos a los que realmente se puede acceder desde el estado inicial.
Antes de determinar las transiciones entre los diferentes estados, la gramática se aumenta con una regla adicional.
donde S es un nuevo símbolo de inicio y E el antiguo símbolo de inicio. El analizador utilizará esta regla de reducción exactamente cuando haya aceptado toda la cadena de entrada.
Para este ejemplo, la misma gramática anterior se amplía así:
Es por esta gramática aumentada que se determinarán los conjuntos de elementos y las transiciones entre ellos.
El primer paso en la construcción de 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:
El " + " en negrita delante de un elemento indica los elementos que se agregaron para el cierre (no debe confundirse con el operador matemático '+' que es una terminal). Los elementos originales sin " + " se denominan núcleo del conjunto de elementos.
Empezando por el estado inicial (S0), ahora 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 el terminal '0' (es decir, donde x = '0'), esto da como resultado:
y para el terminal '1' (es decir, donde x = '1') esto da como resultado:
y para el no terminal E (es decir, donde x = E) esto da como resultado:
y para el no terminal B (es decir, donde x = B) esto da como resultado:
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 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 ya encontrados 1 y 2, respectivamente. Para el no terminal B, la transición va a:
Para el conjunto de elementos 6, se deben considerar el terminal '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, el la transición va a:
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 tiene el siguiente aspecto:
A partir de esta tabla y los conjuntos de elementos encontrados, la tabla de acciones y de ir a se construyen de la siguiente manera:
El lector puede verificar que estos pasos producen la acción e ir a la tabla presentada anteriormente.
Sólo 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. Esta es la razón por la que estas son tablas de análisis LR(0): no hacen ninguna anticipación (es decir, miran hacia adelante los símbolos cero) antes de decidir qué reducción realizar. Una gramática que necesita una anticipación para eliminar la ambigüedad de las reducciones requeriría una fila de la tabla de análisis que contenga diferentes acciones de reducción en diferentes columnas, y el procedimiento anterior no es capaz de crear dichas filas.
Las mejoras al 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 será determinista. Sin embargo, cuando se agregan acciones de reducción a la tabla de acciones, puede suceder que la misma celda se llene con una acción de reducción y una acción de cambio (un conflicto cambio-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 de reducción de turnos es el problema de lo demás .
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 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 (cambiar al estado 1) y r2 (reducir con gramática). regla 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 ítems:
Hay un conflicto de reducción-reducción en este conjunto de elementos porque en las celdas de la tabla de acciones para este conjunto de elementos habrá una acción de reducción para la regla 3 y otra para la regla 4.
Los dos ejemplos anteriores se pueden resolver dejando que el analizador utilice el siguiente conjunto (consulte el analizador LL ) de un A no terminal para decidir si va a utilizar 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 siguiente conjunto de A . Esta solución da como resultado los llamados analizadores LR simples .
