Hispanopedia Wiki
Articulo de referencia

Analizador LR canónico

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 progr...

Hispanopedia WikiContenido en espanolLectura gratuita

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, de izquierda a 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 puede transformarse 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 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.

Como la mayoría de los analizadores sintácticos, el analizador LR(1) es generado automáticamente por compiladores como GNU Bison , MSTA, Menhir, [ 2 ] HYACC, [ 3 ] y LRSTAR. [ 4 ]

Historia

En 1965, Donald Knuth inventó el analizador LR(k) ( de 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 izquierdas como derechas de las sentencias encontradas en el archivo de entrada. Knuth demostró que alcanza su máxima capacidad 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 LR(1) canónicos tienen la desventaja práctica de requerir una enorme cantidad de memoria para la representación de su tabla de análisis interna. En 1969, Frank DeRemer propuso dos versiones simplificadas del analizador LR llamadas LALR y SLR . Estos analizadores requieren mucha menos memoria que los analizadores LR(1) canónicos, pero tienen una capacidad de reconocimiento de lenguaje ligeramente menor. [ 5 ] Los analizadores LALR(1) han sido las implementaciones más comunes del analizador LR.

Sin embargo, en 1977 David Pager [ 6 ] introdujo un nuevo tipo de analizador LR(1), al que algunos denominan "analizador LR(1) mínimo", demostrando que se pueden crear analizadores LR(1) con requisitos de memoria similares a los de los analizadores LALR(1). Recientemente , 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 misterioso problema de conflicto inherente a los generadores de analizadores LALR(1). 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.

Descripción general

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 . Estas tablas codifican la gramática del lenguaje que reconoce y se denominan habitualmente "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

A1 → AB

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:

A1 → AB, a

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 dependiendo del contexto de anticipación. 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.

A1 → AB, a
A2 → AB, b
A3 → AB, c
A4 → AB, d

Lo mismo no sería cierto si no se tuviera en cuenta un terminal de anticipación. Los errores de análisis sintáctico pueden identificarse sin que el analizador tenga que leer toda la entrada declarando algunas reglas como errores. Por ejemplo,

E1 → BC, d

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

A1 → AB, a
A1 → AB, b
A1 → AB, c
E1 → AB, d

En este caso, AB se reducirá a A1 cuando la anticipación sea a, b o c, y se informará un error cuando la anticipación sea d.

La anticipación también puede ser útil para decidir cuándo reducir una regla. La anticipación puede ayudar a evitar la reducción de una regla específica si 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

  • Secuencia de entrada: ABC
  • Normas:
A1 → AB
A2 → BC

La secuencia se puede reducir a

Un A2

en lugar de

A1 C

si la búsqueda anticipada 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 una terminal como en

X → y

lo que permite que aparezcan múltiples secuencias.

Los analizadores LR(1) tienen el requisito de que cada regla debe expresarse de manera completa LR(1), es decir, una secuencia de dos estados con una anticipación específica. Eso hace que las reglas simples como

X → y

lo que requiere 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

A1 → AB

donde deben enumerarse todas las posibles anticipaciones. Esa es la razón por la que los analizadores LR(1) no pueden implementarse prácticamente sin optimizaciones de memoria significativas. [ 6 ]

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

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 va seguido de un terminal distinto.

Elementos del analizador

Partiendo de las reglas de producción de un lenguaje, primero se deben determinar los conjuntos de elementos para dicho lenguaje. En otras palabras, un conjunto de elementos es la lista de reglas de producción a las que puede pertenecer el símbolo que se está procesando. Un conjunto de elementos tiene una correspondencia uno a uno con un estado del analizador sintáctico, 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 deben aplicar. Cada elemento contiene un marcador que indica en qué punto de la regla que representa el símbolo que se está procesando aparece. Para los analizadores sintácticos LR(1), cada elemento es específico de un terminal de anticipación, por lo que este terminal 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:

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 analizadores LR(0). El conjunto de elementos 0, que representa el estado inicial, se creará a partir de la regla de inicio:

[S → • E, $]

El punto '•' indica la posición actual del análisis 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 final de la entrada, al igual que en la regla inicial.

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 sigue a un '•' deben incluirse recursivamente en el conjunto de elementos hasta que se hayan procesado todos esos 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 terminal de anticipación posible que siga a la regla. En lenguajes más complejos, esto suele resultar en conjuntos de elementos muy grandes, lo que explica los elevados 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 tanto, todas las reglas de producción aparecerán en el conjunto de elementos 0. Al principio, ignoramos el problema de encontrar las aserciones anticipadas y solo consideramos el caso de un LR(0), cuyos elementos no contienen terminales de aserción anticipada. Así, el conjunto de elementos 0 (sin aserciones anticipadas) se verá así:

[S → • E]
[E → • T]
[E → • ( E )]
[T → • n]
[T → • + T]
[T → • T + n]

Conjuntos PRIMERO y SIGUIENTE

Para determinar los terminales de anticipación, se utilizan los conjuntos FIRST y FOLLOW. FIRST(A) es el conjunto de terminales que pueden aparecer como el primer elemento de cualquier cadena de reglas que coincida 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 α y β 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 conjuntos FOLLOW 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 que se utilizan en los conjuntos FIRST.

En nuestro ejemplo, como se puede comprobar en la lista completa de conjuntos de elementos que aparece a continuación, los primeros conjuntos son:

PRIMERO(S) = { n, '+', '(' }
PRIMERO(E) = { n, '+', '(' }
PRIMERO(T) = { n, '+' }

Determinación de terminales de anticipación

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

SEGUIR(0,S) = { $ }
SEGUIR(0,E) = { $ }
SEGUIR(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 del conjunto follow del no terminal LHS. Cada elemento del conjunto follow puede ser un terminal lookahead válido:

[S → • E, $]
[E → • T, $]
[E → • ( E ), $]
[T → • n, $]
[T → • n, +]
[T → • + T, $]
[T → • + T, +]
[T → • T + n, $]
[T → • T + n, +]

Creación de 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 no terminal A que aparezca después de un '•' en cada conjunto de elementos k ya existente, cree un nuevo conjunto de elementos m agregando a m todas las reglas de k donde '•' va seguido de A, pero solo si m no será igual a un conjunto de elementos ya existente después del paso 3.
2. Desplaza todos los '•' de cada regla en el nuevo conjunto de elementos un símbolo a la derecha.
3. crear el cierre del nuevo conjunto de elementos
4. Repita desde el paso 1 para todos los conjuntos de elementos recién creados, hasta que no aparezcan más conjuntos nuevos.

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):

[S → E •, $]

Conjunto de artículos 2 (T):

[E → T •, $]
[T → T • + n, $]
[T → T • + n, +]

Conjunto de elementos 3 (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, +]

A partir 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 indicará aquí. Tenga en cuenta que esta gramática en particular no es LR(1), ya que dos de los conjuntos de elementos (no enumerados anteriormente) contienen conflictos de desplazamiento/reducción. El tratamiento detallado de esta gramática como LR(k) se puede encontrar, por ejemplo, en.

Ir a

La anticipación 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

[E → T •, $]
[T → T • + n, $]
[T → T • + n, +]

El analizador sintáctico debe realizar la reducción [E → T] si el siguiente símbolo es '$', pero realizar un desplazamiento si el siguiente símbolo es '+'. Cabe destacar 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, reportaría un conflicto entre desplazamiento y reducción.

Un estado que contiene [A → α • X β, a] pasará 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 la etiqueta b, entonces añadimos la acción

acción[I k , b] = "desplazar m"

Reducir acciones

Si [A→α •, a] está en el estado I k , entonces añadimos la acción

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

Referencias

  1. 1 2 3 Knuth, DE (julio de 1965). "Sobre la traducción de lenguas de izquierda a derecha". Information and Control . 8 (6): 607– 639. doi : 10.1016/S0019-9958(65)90426-2 .
  2. ↑ "¿Qué es un menhir?" . INRIA, proyecto CRISTAL . Consultado el 29 de junio de 2012 .
  3. ↑ "HYACC, generador de analizadores LR(1) mínimo" .
  4. ↑ "Generador de analizadores LRSTAR" .
  5. ↑ Franklin L. DeRemer (1969). "Traductores prácticos para lenguas LR(k)" (PDF) . Tesis doctoral del MIT. Archivado del original (PDF) el 5 de abril de 2012.
  6. 1 2 Pager, D. ( 1977), "Un método general práctico para construir analizadores LR(k)", Acta Informatica 7 , págs. 249–268 
  • Página HTML sobre la construcción práctica del analizador LR(k) , David Tribble
  • Construcción de conjuntos primero y segundo en Python (Narayana Chikkam)