Un analizador LR canónico (también llamado analizador LR(1) ) es un tipo de algoritmo de análisis ascendente utilizado 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 inversa de izquierda a derecha, más a la derecha".
Formalmente, un analizador LR canónico es un analizador LR(k) para k=1 , es decir, con un único terminal de anticipación . 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 se ha evitado este analizador LR(k) debido a sus enormes requisitos de memoria en favor de alternativas menos potentes como el analizador LALR y LL(1) . Sin embargo, recientemente, varios generadores de analizadores ofrecen un "analizador LR (1) mínimo" cuyos requisitos de espacio son cercanos a los analizadores LALR [ cita necesaria ] .
Como la mayoría de los analizadores, el analizador LR(1) es generado automáticamente por compiladores-compiladores como GNU Bison , MSTA, Menhir, [2] HYACC, [3] y LRSTAR. [4]
En 1965, Donald Knuth inventó el analizador LR(k) ( de izquierda a derecha, analizador de derivación más derecho ), un tipo de analizador de desplazamiento-reducción , como una generalización de los analizadores de precedencia existentes . Este analizador tiene el potencial de reconocer todos los lenguajes deterministas libres de contexto y puede producir derivaciones izquierda y derecha de 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 canónicos LR(1) tienen la desventaja práctica de tener enormes requisitos de memoria para su representación interna en la tabla del analizador. En 1969, Frank DeRemer sugirió dos versiones simplificadas del analizador LR llamadas LALR y SLR . Estos analizadores requieren mucha menos memoria que los analizadores Canonical LR(1), pero tienen un poder de reconocimiento de lenguaje ligeramente menor. [5] Los analizadores LALR(1) han sido las implementaciones más comunes del LR Parser.
Sin embargo, en 1977 David Pager [6] introdujo un nuevo tipo de analizador LR(1), que algunas personas llaman "analizador LR(1) mínimo", quien demostró que se pueden crear analizadores LR(1) cuyos requisitos de memoria rivalicen con los de analizadores LALR(1). Recientemente [ ¿ cuándo? ] , algunos generadores de analizadores ofrecen analizadores Minimal LR(1), que no sólo resuelven el problema de los requisitos de memoria, sino también el problema de conflicto misterioso inherente a los generadores de analizadores LALR(1). [ cita necesaria ] Además, los analizadores Minimal LR (1) pueden usar acciones de reducción de desplazamiento, lo que los hace más rápidos que los analizadores Canonical LR (1).
El analizador LR(1) es un autómata determinista y como tal su funcionamiento se basa en tablas de transición de estados estáticas . Éstos codifican la gramática del idioma que reconoce y normalmente se denominan "tablas de análisis".
Las tablas de análisis del analizador LR(1) están parametrizadas con un terminal de anticipación. Las tablas de análisis simples, como las utilizadas por el analizador LR(0), representan reglas gramaticales de la forma
lo que significa que si tenemos la entrada A seguida de B , reduciremos el par a A1 independientemente de lo que siga. Después de parametrizar dicha regla con una anticipación tenemos:
lo que significa que la reducción ahora se realizará solo si el terminal de anticipación es un . Esto permite lenguajes más ricos donde una regla simple puede tener diferentes significados según el contexto de anticipación. Por ejemplo, en una gramática LR(1), todas las reglas siguientes realizan una reducción diferente a pesar de estar basadas en la misma secuencia de estados.
No ocurriría lo mismo si no se tuviera en cuenta un terminal de anticipación. 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, provocando que el analizador se detenga. Esto significa que la información de anticipación también se puede utilizar para detectar errores, como en el siguiente ejemplo:
En este caso, AB se reducirá a A1 cuando la anticipación sea a, boc y se informará un error cuando la anticipación sea d.
La anticipación también puede resultar útil para decidir cuándo reducir una regla. La anticipación puede ayudar a evitar la reducción de una regla específica si la anticipación 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 en el siguiente ejemplo
La secuencia se puede reducir a
en lugar de
si la anticipación después de que el analizador pasó al estado B no era aceptable, es decir, no existía ninguna regla de transición. Las reducciones se pueden producir directamente desde un terminal como en
lo que permite que aparezcan múltiples secuencias.
Los analizadores LR(1) tienen el requisito de que cada regla se exprese de manera LR(1) completa, es decir, una secuencia de dos estados con una anticipación específica. Eso hace reglas simples como
requiriendo una gran cantidad de reglas artificiales que esencialmente enumeran las combinaciones de todos los estados posibles y terminales de anticipación que pueden seguir. Un problema similar aparece al implementar reglas sin anticipación, como
donde se deben enumerar todas las posibles anticipaciones. Ésta es la razón por la que los analizadores LR(1) no se pueden implementar en la práctica sin optimizaciones significativas de la memoria. [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 una 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 va seguido de una terminal diferente.
Partiendo de las reglas de producción de un idioma, primero se deben determinar los conjuntos de elementos para ese idioma. En palabras sencillas, un conjunto de elementos es la lista de reglas de producción de las que el símbolo actualmente procesado podría formar parte. 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 acciones del analizador se aplicarán. Cada elemento contiene un marcador, para indicar en qué punto aparece el símbolo actualmente procesado en la regla que representa el elemento. Para los analizadores LR(1), cada elemento es específico de un terminal de anticipación, por lo que el terminal de anticipación también se ha anotado dentro de cada elemento.
Por ejemplo, supongamos un lenguaje que consta de los símbolos terminales 'n', '+', '(', ')', los no terminales 'E', 'T', la regla inicial '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 inicial:
El punto '•' indica el marcador de la posición de análisis actual dentro de esta regla. El terminal de anticipación esperado 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 inicial.
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 no terminal que siguen a un '•' deben incluirse recursivamente en el conjunto de elementos hasta que se traten todos esos no terminales. El conjunto de elementos resultante se denomina cierre del conjunto de elementos con el que comenzamos.
Para LR(1) para cada regla de producción se debe incluir un artículo para cada posible terminal de anticipación que siga la regla. Para lenguajes más complejos, esto normalmente resulta en conjuntos de elementos muy grandes, lo cual es la razón de los grandes requisitos de memoria de los analizadores 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. Al principio, ignoramos el problema de encontrar las anticipaciones y solo miramos el caso de un LR(0), cuyos elementos no contienen terminales de anticipación. Entonces el conjunto de elementos 0 (sin búsquedas anticipadas) se verá así:
Para determinar los terminales de anticipación se utilizan los llamados conjuntos PRIMERO y SEGUIDOR. PRIMERO(A) es el conjunto de terminales que puede aparecer como el primer elemento de cualquier cadena de reglas que coincidan con el no terminal A. SEGUIMIENTO(I) de un Ítem I [A → α • B β, x] es el conjunto de terminales que pueden aparecen inmediatamente después del no terminal B, donde α, β son cadenas de símbolos arbitrarias y x es una terminal de anticipación arbitraria. EL SEGUIMIENTO(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 PRIMEROS conjuntos se pueden determinar directamente a partir de los cierres de todos los no terminales en el idioma, mientras que los conjuntos SIGUIENTES se determinan a partir de los elementos en uso de los PRIMEROS conjuntos.
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 completo 0 para un analizador LR(1), creando para cada elemento del conjunto de elementos LR(0) una copia para cada terminal en el siguiente conjunto del no terminal LHS. Cada elemento del siguiente conjunto puede ser un terminal de anticipación 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, conjunto de elementos 1 para el no terminal E, conjunto de elementos 2 para el no terminal T, conjunto de elementos 3 para el terminal n, conjunto de elementos 4 para el terminal '+' y conjunto de elementos 5 para '(' .
Conjunto de artículos 1 (E):
Conjunto de artículos 2 (T):
Conjunto de artículos 3 (n):
Conjunto de elementos 4 ('+'):
Conjunto de elementos 5 ('('):
A partir de los conjuntos de artículos 2, 4 y 5 se producirán varios conjuntos de artículos más. La lista completa es bastante larga y, por lo tanto, no la mencionaremos aquí. El tratamiento detallado de LR(k) de esta gramática se puede encontrar, por ejemplo, en [1].
La anticipación de un elemento LR(1) se utiliza directamente sólo 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
se requiere que el analizador realice 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 cambio/reducción.
Un estado que contiene [A → α • X β, a] se moverá a un estado que contiene [A → α X • β, a] con la etiqueta X.
Cada estado tiene transiciones según Goto.
Si [A → α • b β, a] está en el estado I k y I k se mueve al estado I m con etiqueta b, entonces sumamos la acción
Si [A→α •, a] está en el estado I k , entonces sumamos la acción