Un analizador LR canónico (también llamado analizador LR(1) ) es un tipo de algoritmo de análisis ascendente que se utiliza en informática para analizar y procesar lenguajes de programación . Se basa en la técnica de análisis LR , que significa "derivación de izquierda a derecha, más a la derecha en reversa".
Formalmente, un analizador LR canónico es un analizador LR(k) para k=1 , es decir, con una única terminal de búsqueda anticipada . El atributo especial de este analizador es que cualquier gramática LR(k) con k>1 se puede transformar en una gramática LR(1). [1] Sin embargo, se requieren sustituciones hacia atrás para reducir k y, a medida que aumentan las sustituciones hacia atrás, la gramática puede volverse rápidamente grande, repetitiva y difícil de entender. LR(k) puede manejar todos los lenguajes deterministas libres de contexto . [1] En el pasado, este analizador LR(k) se ha evitado debido a sus enormes requisitos de memoria en favor de alternativas menos potentes como el analizador LALR y el analizador LL(1) . Sin embargo, recientemente, varios generadores de analizadores ofrecen un "analizador LR(1) mínimo" cuyos requisitos de espacio son cercanos a los de los analizadores LALR [ cita requerida ] .
Como la mayoría de los analizadores, el analizador LR(1) es generado automáticamente por compiladores como GNU Bison , MSTA, Menhir, [2] HYACC, [3] y LRSTAR. [4]
En 1965, Donald Knuth inventó el analizador sintáctico LR(k) ( l eft to right, R ightmost derivation parser), un tipo de analizador sintáctico de desplazamiento-reducción , como una generalización de los analizadores sintácticos de precedencia existentes . Este analizador sintáctico tiene el potencial de reconocer todos los lenguajes deterministas libres de contexto y puede producir derivaciones tanto izquierdas como derechas de las declaraciones encontradas en el archivo de entrada. Knuth demostró que alcanza su máximo poder de reconocimiento de lenguaje para k=1 y proporcionó un método para transformar gramáticas LR(k), k > 1 en gramáticas LR(1). [1]
Los analizadores sintácticos LR(1) canónicos tienen la desventaja práctica de tener enormes requisitos de memoria para su representación interna en la tabla de analizadores sintácticos. En 1969, Frank DeRemer sugirió dos versiones simplificadas del analizador sintáctico LR llamadas LALR y SLR . Estos analizadores sintácticos requieren mucha menos memoria que los analizadores sintácticos LR(1) canónicos, pero tienen un poder de reconocimiento de lenguaje ligeramente menor. [5] Los analizadores sintácticos LALR(1) han sido las implementaciones más comunes del analizador sintáctico LR.
Sin embargo, en 1977 David Pager [6] introdujo un nuevo tipo de analizador LR(1), al que algunas personas llaman "analizador LR(1) mínimo", y demostró que se pueden crear analizadores LR(1) cuyos requisitos de memoria rivalizan con los de los analizadores LALR(1). Recientemente [ ¿cuándo? ] , algunos generadores de analizadores ofrecen analizadores LR(1) mínimos, que no solo resuelven el problema de los requisitos de memoria, sino también el problema de los conflictos misteriosos inherente a los generadores de analizadores LALR(1). [ cita requerida ] Además, los analizadores LR(1) mínimos pueden utilizar acciones de desplazamiento-reducción, lo que los hace más rápidos que los analizadores LR(1) canónicos.
El analizador sintáctico LR(1) es un autómata determinista y, como tal, su funcionamiento se basa en tablas de transición de estados estáticas . Estas codifican la gramática del lenguaje que reconoce y suelen denominarse "tablas de análisis sintáctico".
Las tablas de análisis del analizador LR(1) están parametrizadas con una terminal de búsqueda anticipada. Las tablas de análisis simples, como las que utiliza el analizador LR(0), representan reglas gramaticales de la forma
lo que significa que si tenemos la entrada A seguida de B , entonces reduciremos el par a A1 sin importar lo que siga. Después de parametrizar dicha regla con una búsqueda anticipada, tenemos:
lo que significa que la reducción ahora se realizará solo si la terminal de búsqueda anticipada es una . Esto permite lenguajes más ricos donde una regla simple puede tener diferentes significados dependiendo del contexto de búsqueda anticipada. Por ejemplo, en una gramática LR(1), todas las siguientes reglas realizan una reducción diferente a pesar de estar basadas en la misma secuencia de estados.
Lo mismo no sería cierto si no se tuviera en cuenta una terminal de búsqueda anticipada. Los errores de análisis se pueden identificar sin que el analizador tenga que leer toda la entrada declarando algunas reglas como errores. Por ejemplo,
puede declararse un error, lo que hace que el analizador se detenga. Esto significa que la información de búsqueda anticipada también se puede utilizar para detectar errores, como en el siguiente ejemplo:
En este caso, AB se reducirá a A1 cuando el lookahead sea a, b o c y se informará un error cuando el lookahead sea d.
La búsqueda anticipada también puede ser útil para decidir cuándo reducir una regla. La búsqueda anticipada puede ayudar a evitar la reducción de una regla específica si la búsqueda anticipada no es válida, lo que probablemente significaría que el estado actual debería combinarse con el siguiente en lugar del estado anterior. Eso significa que en el siguiente ejemplo
La secuencia se puede reducir a
en lugar de
Si la búsqueda anticipada después de que el analizador pasara al estado B no era aceptable, es decir, no existía ninguna regla de transición. Las reducciones se pueden producir directamente desde una terminal como en
lo que permite que aparezcan múltiples secuencias.
Los analizadores sintácticos LR(1) tienen el requisito de que cada regla se exprese de una manera LR(1) completa, es decir, una secuencia de dos estados con una anticipación específica. Esto hace que las reglas simples como
requiere una gran cantidad de reglas artificiales que enumeran esencialmente las combinaciones de todos los estados posibles y terminales de anticipación que pueden seguir. Un problema similar aparece para la implementación de reglas que no son de anticipación, como
donde deben enumerarse todos los posibles lookaheads. Esa es la razón por la que los analizadores LR(1) no pueden implementarse prácticamente sin optimizaciones de memoria significativas. [6]
Las tablas de análisis LR(1) se construyen de la misma manera que las tablas de análisis LR(0), con la modificación de que cada elemento contiene un terminal de anticipación . Esto significa que, a diferencia de los analizadores LR(0), se puede ejecutar una acción diferente si el elemento a procesar es seguido por un terminal diferente.
Partiendo de las reglas de producción de un lenguaje, primero se deben determinar los conjuntos de elementos para ese lenguaje. En palabras sencillas, un conjunto de elementos es la lista de reglas de producción de las que podría formar parte el símbolo que se está procesando actualmente. Un conjunto de elementos tiene una correspondencia uno a uno con un estado del analizador, mientras que los elementos dentro del conjunto, junto con el siguiente símbolo, se utilizan para decidir qué transiciones de estado y qué acción del analizador se van a aplicar. Cada elemento contiene un marcador para indicar en qué punto aparece el símbolo que se está procesando actualmente en la regla que representa el elemento. En el caso de los analizadores LR(1), cada elemento es específico de un terminal de búsqueda anticipada, por lo que el terminal de búsqueda anticipada también se ha indicado dentro de cada elemento.
Por ejemplo, supongamos un lenguaje que consta de los símbolos terminales 'n', '+', '(', ')', los no terminales 'E', 'T', la regla de inicio 'S' y las siguientes reglas de producción:
Los conjuntos de elementos se generarán de forma análoga al procedimiento para los analizadores LR(0). El conjunto de elementos 0, que representa el estado inicial, se creará a partir de la regla de inicio:
El punto '•' indica el marcador de la posición de análisis actual dentro de esta regla. La terminal de búsqueda anticipada esperada para aplicar esta regla se indica después de la coma. El signo '$' se utiliza para indicar que se espera el 'fin de la entrada', como es el caso de la regla de inicio.
Sin embargo, este no es el conjunto de elementos 0 completo. Cada conjunto de elementos debe estar "cerrado", lo que significa que todas las reglas de producción para cada elemento no terminal que sigue a un "•" deben incluirse recursivamente en el conjunto de elementos hasta que se hayan procesado todos esos elementos no terminales. El conjunto de elementos resultante se denomina cierre del conjunto de elementos con el que comenzamos.
Para LR(1), por cada regla de producción se debe incluir un elemento para cada posible terminal de búsqueda anticipada que siga a la regla. Para lenguajes más complejos, esto suele dar como resultado conjuntos de elementos muy grandes, lo que explica los grandes requisitos de memoria de los analizadores sintácticos LR(1).
En nuestro ejemplo, el símbolo inicial requiere el no terminal 'E', que a su vez requiere 'T', por lo que todas las reglas de producción aparecerán en el conjunto de elementos 0. En primer lugar, ignoramos el problema de encontrar los valores de anticipación y solo observamos el caso de un LR(0), cuyos elementos no contienen terminales de anticipación. Por lo tanto, el conjunto de elementos 0 (sin valores de anticipación) se verá así:
Para determinar terminales de anticipación, se utilizan los conjuntos denominados FIRST y FOLLOW. FIRST(A) es el conjunto de terminales que pueden aparecer como el primer elemento de cualquier cadena de reglas que coincidan con el no terminal A. FOLLOW(I) de un elemento I [A → α • B β, x] es el conjunto de terminales que pueden aparecer inmediatamente después del no terminal B, donde α, β son cadenas de símbolos arbitrarias y x es un terminal de anticipación arbitrario. FOLLOW(k,B) de un conjunto de elementos k y un no terminal B es la unión de los siguientes conjuntos de todos los elementos en k donde '•' va seguido de B. Los conjuntos FIRST se pueden determinar directamente a partir de los cierres de todos los no terminales del lenguaje, mientras que los conjuntos FOLLOW se determinan a partir de los elementos en uso de los conjuntos FIRST.
En nuestro ejemplo, como se puede verificar en la lista completa de conjuntos de elementos a continuación, los primeros conjuntos son:
Dentro del conjunto de elementos 0 se pueden encontrar los siguientes conjuntos:
A partir de esto, se puede crear el conjunto de elementos 0 completo para un analizador LR(1), creando para cada elemento del conjunto de elementos LR(0) una copia para cada terminal en el conjunto siguiente del no terminal LHS. Cada elemento del conjunto siguiente puede ser un terminal de búsqueda anticipada válido:
El resto de los conjuntos de elementos se pueden crear mediante el siguiente algoritmo
En el ejemplo obtenemos 5 conjuntos más del conjunto de elementos 0, el conjunto de elementos 1 para el no terminal E, el conjunto de elementos 2 para el no terminal T, el conjunto de elementos 3 para el terminal n, el conjunto de elementos 4 para el terminal '+' y el conjunto de elementos 5 para '('.
Conjunto de artículos 1 (E):
Conjunto de artículos 2 (T):
Conjunto de elementos 3 (n):
Conjunto de elementos 4 ('+'):
Conjunto de elementos 5 ('('):
A partir de los conjuntos de elementos 2, 4 y 5 se generarán varios conjuntos de elementos más. La lista completa es bastante larga y, por lo tanto, no se mencionará aquí. El tratamiento LR(k) detallado de esta gramática se puede encontrar, por ejemplo, en [1].
El avance de un elemento LR(1) se utiliza directamente solo cuando se consideran acciones de reducción (es decir, cuando el marcador • está en el extremo derecho).
El núcleo de un elemento LR(1) [S → a A • B e, c] es el elemento LR(0) S → a A • B e. Diferentes elementos LR(1) pueden compartir el mismo núcleo.
Por ejemplo, en el conjunto de elementos 2
El analizador debe realizar la reducción [E → T] si el siguiente símbolo es '$', pero debe realizar un desplazamiento si el siguiente símbolo es '+'. Tenga en cuenta que un analizador LR(0) no podría tomar esta decisión, ya que solo considera el núcleo de los elementos y, por lo tanto, informaría un conflicto de desplazamiento/reducción.
Un estado que contiene [A → α • X β, a] se moverá a un estado que contiene [A → α X • β, a] con etiqueta X.
Cada estado tiene transiciones según Goto.
Si [A → α • b β, a] está en el estado I k e I k se mueve al estado Im con etiqueta b, entonces agregamos la acción
Si [A→α •, a] está en el estado I k , entonces agregamos la acción