Analizador LR canónico

En informática, un analizador LR canónico o analizador LR(1) es un analizador LR(k) para k=1, es decir, con un solo terminal de anticipación. El atributo especial de este analizador es que cualquier gramática LR(k) con k>1 puede transformarse en una gramática LR(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 grande, repetitiva y difícil de entender rápidamente. LR(k) puede manejar todos los lenguajes libres de contexto deterministas. 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 LL(1). Recientemente, sin embargo, un "analizador LR(1) mínimo" cuyos requisitos de espacio están cerca de los analizadores LALR, está siendo ofrecido por varios generadores de analizadores.

Como la mayoría de los analizadores, el analizador LR(1) es generado automáticamente por compiladores-compiladores como GNU Bison, MSTA, Menhir, HYACC, LRSTAR.

Historia

En 1965, Donald Knuth inventó el analizador LR(k) (Lde izquierda a derecha, analizador de derivación más a la derecha) 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 tanto a la izquierda como a la derecha de las declaraciones encontradas en el archivo de entrada. Knuth demostró que alcanza su máximo poder de reconocimiento de idioma para k=1 y proporcionó un método para transformar LR(k), k > 1 gramáticas en gramáticas LR(1).

Los analizadores canónicos LR(1) tienen la desventaja práctica de tener enormes requisitos de memoria para su representación de tabla de analizador interna. 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 idioma ligeramente menor. Los analizadores LALR(1) han sido las implementaciones más comunes del LR Parser.

Sin embargo, un nuevo tipo de analizador LR(1), algunas personas lo llaman "analizador LR(1) mínimo" fue presentado en 1977 por David Pager, quien demostró que se pueden crear analizadores LR(1) cuyos requisitos de memoria rivalicen con los de los analizadores LALR(1). Recientemente, algunos generadores de analizadores están ofreciendo analizadores Minimal LR(1), que no solo resuelven el problema de requisitos de memoria, sino también el problema del conflicto misterioso inherente a los generadores de analizadores LALR(1). Además, los analizadores Minimal LR(1) pueden usar acciones shift-reduce, lo que los hace más rápidos que los analizadores Canonical LR(1).

Resumen

El analizador LR(1) es un autómata determinista y, como tal, su funcionamiento se basa en tablas de transición de estado estático. Estos codifican la gramática del idioma que reconoce y normalmente se denominan "tablas de análisis sintáctico".

Las tablas de análisis del analizador LR(1) se parametrizan con un terminal de búsqueda anticipada. Las tablas de análisis simples, como las utilizadas por el analizador LR(0), representan reglas gramaticales de la forma

A1 → A B

lo que significa que si tenemos entrada A seguida de B entonces reduciremos el par a A1 sin importar lo que sigue. Después de parametrizar dicha regla con un lookahead tenemos:

A1 → A B, a

lo que significa que la reducción ahora se realizará solo si el terminal anticipado es a. 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.

A1 → A B, a

A2 → A B, b

A3 → A B, c

A4 → A B, d

No sucedería lo mismo si no se tuviera en cuenta una terminal 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,

E1 → B C, d

puede declararse un error, lo que hace que el analizador se detenga. Esto significa que la información anticipada también se puede utilizar para detectar errores, como en el siguiente ejemplo:

A1 → A B, a

A1 → A B, b

A1 → A B, c

E1 → A B, d

En este caso, A B se reducirá a A1 cuando la búsqueda anticipada sea a, b o c, y se informará de un error cuando la búsqueda anticipada sea d.

La anticipación 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 debe combinarse con el siguiente en lugar del estado anterior. Eso significa que en el siguiente ejemplo

• Secuencia de entrada: A B C
• Reglas:

A1 → A B

A2 → B C

la secuencia se puede reducir a

A2

en lugar de

A1 C

si la búsqueda anticipada después de que el analizador pasara al estado B no fuera aceptable, es decir, no existiera ninguna regla de transición. Las reducciones se pueden producir directamente desde un terminal como en

X → y

que permite que aparezcan múltiples secuencias.

Los analizadores sintácticos LR(1) tienen el requisito de que cada regla se exprese de forma LR(1) completa, es decir, una secuencia de dos estados con una anticipación específica. Eso hace reglas simples como

X → y

requiriendo una gran cantidad de reglas artificiales que esencialmente enumeran las combinaciones de todos los posibles estados y terminales anticipadas que pueden seguir. Aparece un problema similar para implementar reglas sin anticipación como

A1 → A B

donde se deben enumerar todas las anticipaciones posibles. Esa es la razón por la que los analizadores LR(1) no pueden implementarse en la práctica sin optimizaciones de memoria significativas.

Construcción de tablas de análisis LR(1)

Las tablas de análisis sintáctico LR(1) se construyen de la misma manera que las tablas de análisis sintáctico LR(0) con la modificación de que cada elemento contiene un terminal de búsqueda anticipada. 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 una terminal diferente.

Elementos del analizador

A partir de las reglas de producción de un idioma, primero se deben determinar los conjuntos de elementos para este idioma. En palabras sencillas, un conjunto de elementos es la lista de reglas de producción, de la que podría formar parte el símbolo actualmente procesado. 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 acción del analizador se aplicarán. Cada elemento contiene un marcador, para señalar 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 búsqueda anticipada, por lo que el terminal de búsqueda anticipada también se ha anotado dentro de cada elemento.

Por ejemplo, suponga un idioma que consta de los símbolos terminales 'n', '+', '(', ')&# 39;, los no terminales 'E', 'T', la regla inicial 'S' y las siguientes reglas de producción:

S → E

E → T

E → (E)

T → n

T → + T

T → T + 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:

[S → • E, $]

El punto '•' denota el marcador de la posición de análisis actual dentro de esta regla. El terminal anticipado esperado para aplicar esta regla se indica después de la coma. El '$' El signo se utiliza para denotar 'fin de entrada' se espera, como es el caso de la regla inicial.

Sin embargo, este no es el conjunto completo de elementos 0. Cada conjunto de artículos debe estar 'cerrado', lo que significa que todas las reglas de producción para cada no terminal siguiendo un '•' tienen que incluirse recursivamente en el conjunto de elementos hasta que se solucionen todos esos no terminales. El conjunto de elementos resultante se llama el 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 anticipado que siga la regla. Para lenguajes más complejos, esto suele dar como resultado conjuntos de elementos muy grandes, que es la razón de los grandes requisitos de memoria de los analizadores LR(1).

En nuestro ejemplo, el símbolo de inicio 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 búsquedas anticipadas y solo observamos el caso de un LR(0), cuyos elementos no contienen terminales anticipadas. Entonces, el conjunto de elementos 0 (sin anticipación) se verá así:

[S → • E]

[E → • T]

[E → • (E)]

[T → • n]

[T → • + T]

[T → • T + n]

Conjuntos PRIMERO y SIGUIENTE

Para determinar las terminales anticipadas, se utilizan los llamados conjuntos FIRST y FOLLOW. 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. SEGUIR(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 arbitraria de anticipación. SEGUIR(k,B) de un conjunto de elementos k y un B no terminal es la unión de los conjuntos de seguimiento de todos los elementos en k donde '•' es seguido por B. Los PRIMEROS conjuntos se pueden determinar directamente a partir de los cierres de todos los no terminales en el lenguaje, mientras que los conjuntos SEGUIR se determinan a partir de los elementos en uso de los PRIMEROS conjuntos.

En nuestro ejemplo, como se puede verificar a partir de la lista completa de conjuntos de elementos a continuación, los primeros conjuntos son:

FIRST(S) = { n, '+', '('

FIRST(E) = { n, '+', '('

FIRST(T) = { n, '+'

Determinación de terminales anticipadas

Dentro del conjunto de elementos 0, se pueden encontrar los siguientes conjuntos:

SÍGUE(0,S) = { $ }

SÍGUE(0,E) = { $, ')}

SÍGUE(0,T) = { $, '+', ')

A partir de esto, se puede crear el conjunto completo de elementos 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 conjunto de seguimiento puede ser un terminal anticipado válido:

[S → • E, $]

[E → • T, $]

[E → • T,)]

[E → • (E), $]

[E → • (E),]

[T → • n, $]

[T → • n, +]

[T → • n,)]

[T → • + T, $]

[T → • + T, +]

[T → • + T,)]

[T → • T + n, $]

[T → • T + n, +]

[T → • T + n,)]

Crear nuevos conjuntos de elementos

El resto de los conjuntos de elementos se pueden crear mediante el siguiente algoritmo

1. Para cada símbolo terminal y noterminal Una aparición después de un '•' en cada elemento ya existente k, crear un nuevo elemento set m añadiendo a m todas las reglas de k donde '•' es seguido por A, pero sólo si m no será el mismo que un elemento ya existente establecido después del paso 3.

2. cambiar todos los '•'s para cada regla en el nuevo elemento establecer un símbolo a la derecha

3. crear el cierre del nuevo conjunto de elementos

4. Repetir desde el paso 1 para todos los conjuntos de elementos recién creados, hasta que no aparezcan nuevos conjuntos

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 artículos 5 para '('.

Conjunto de artículos 1 (E):

[S → E •, $]

Conjunto de elementos 2 (T):

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

·

·

·

Conjunto de elementos 3 (n):

[T → n •, $]

[T → n •, +]

[T → n •,)]

Conjunto de elementos 4 ('+'):

[T → + • T, $]

[T → + • T, +]

[T → • n, $]

[T → • n, +]

[T → • + T, $]

[T → • + T, +]

[T → • T + n, $]

[T → • T + n, +]

·

·

·

Conjunto de elementos 5 ('('):

[E → (• E), $]

[E → • T,)]

[E → • (E),]

[T → • n,)]

[T → • n, +]

[T → • + T,)]

[T → • + T, +]

[T → • T + n,)]

[T → • T + n, +]

·

·

·

De los conjuntos de elementos 2, 4 y 5 se producirá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 puede, p. se encuentra en [1].

Ir a

La anticipación de un elemento LR(1) se usa 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

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

Se requiere que el analizador realice la reducción [E → T] si el siguiente símbolo es '$', pero para hacer un cambio 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.

Acciones de cambio

Si [A → α • b β, a] está en el estado I_k y I_k pasa al estado I_m con etiqueta b, luego sumamos la acción

acción[I]_k, b] = "shift m"

Reducir acciones

Si [A→α •, a] está en el estado I_k, entonces agregamos la acción

acción[I]_k, a] = "reducir A → α"