En informática , un analizador sintáctico LR canónico o un analizador sintáctico LR (1) es un analizador sintáctico 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 extensa, 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 a favor de alternativas menos potentes como el analizador LALR y LL (1) . Recientemente, sin embargo, varios generadores de analizadores sintácticos ofrecen un "analizador sintáctico LR (1) mínimo" cuyos requisitos de espacio están cerca de los analizadores sintácticos LALR [ cita requerida ] .
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]
Historia
En 1965 Donald Knuth inventó el LR (k) analizador ( L eft a derecha, R ightmost derivación parser) un tipo de desplazamiento y reducción analizador , como una generalización de existentes analizadores de precedencia . 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 lenguaje para k = 1 y proporcionó un método para transformar las gramáticas LR (k), k> 1 en gramáticas LR (1). [1]
Los analizadores sintácticos Canonical LR (1) tienen la desventaja práctica de tener enormes requisitos de memoria para la representación interna de la tabla del analizador sintáctico. 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 una capacidad de reconocimiento de idioma ligeramente menor. [4] Los analizadores LALR (1) han sido las implementaciones más comunes del analizador LR.
Sin embargo, un nuevo tipo de analizador LR (1), algunas personas llaman "analizador LR mínimo (1)", fue introducido en 1977 por David Pager [5], quien demostró que se pueden crear analizadores sintácticos LR (1) cuyos requisitos de memoria compiten con los de analizadores sintácticos LALR (1). Recientemente [ ¿cuándo? ] , algunos generadores de analizadores sintácticos ofrecen analizadores sintácticos mínimos LR (1), 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 sintácticos LALR (1). [ cita requerida ] 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).
Descripción general
El analizador sintáctico 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".
Las tablas de análisis sintáctico del analizador LR (1) están parametrizadas con un terminal de búsqueda anticipada. Las tablas de análisis simple, como las que utiliza el analizador LR (0), representan las reglas gramaticales de la forma.
- A1 → A, B
lo que significa que si pasamos del estado A al estado B, entonces pasaremos al estado A1 [ incomprensible ] . Después de parametrizar dicha regla con una anticipación, tenemos:
- A1 → A, B, a
lo que significa que la transición ahora se realizará solo si el terminal de búsqueda anticipada es un . Esto permite lenguajes más ricos en los que una regla simple puede tener diferentes significados según el contexto de búsqueda anticipada. Por ejemplo, en una gramática LR (1), todas las siguientes reglas pasan a un estado 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
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,
- E1 → B, C, d
se puede declarar un error, haciendo 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:
- 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 el lookahead sea a, b o c, y se informará un error cuando el lookahead 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 debería combinarse con el siguiente en lugar del estado anterior. Eso significa que en el siguiente ejemplo
- Secuencia de estados: A, B, C
- Reglas:
- A1 → A, B
- A2 → B, C
la secuencia de estados se puede reducir a
- A, A2
en vez de
- A1, C
si la búsqueda anticipada después de que el analizador pasara al estado B no era aceptable, es decir, no existía una regla de transición. Los estados se pueden producir directamente desde una terminal como en
- X → y
lo que permite que aparezcan secuencias de estados.
Los analizadores sintácticos LR (1) tienen el requisito de que cada regla debe expresarse de una manera 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 estados posibles y terminales de anticipación que pueden seguir. Aparece un problema similar para implementar reglas que no sean de anticipación, como
- A1 → A, B
donde se deben enumerar todas las posibles búsquedas anticipadas. Esa es la razón por la que los analizadores sintácticos LR (1) no se pueden implementar prácticamente sin optimizaciones de memoria significativas. [5]
Construcción de tablas de análisis sintáctico LR (1)
Las tablas de análisis sintáctico LR (1) se construyen de la misma forma que las tablas de análisis sintáctico LR (0) con la modificación de que cada elemento contiene una terminal de búsqueda anticipada . Esto significa que, a diferencia de los analizadores sintácticos LR (0), se puede ejecutar una acción diferente si el elemento a procesar es seguido por un terminal diferente.
Elementos del analizador
Partiendo de las reglas de producción de un idioma, en primer lugar hay que determinar los conjuntos de elementos para este idioma. 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 procesado 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 acción del analizador se deben aplicar. Cada elemento contiene un marcador, para anotar en qué punto aparece el símbolo procesado actualmente en la regla que representa el elemento. Para los analizadores sintácticos LR (1), cada elemento es específico de una terminal de búsqueda anticipada, por lo que la terminal de búsqueda anticipada también se ha anotado dentro de cada elemento.
Por ejemplo, suponga 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:
- 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 de los analizadores sintácticos 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 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 anota después de la coma. El signo '$' se utiliza para indicar que se espera el 'final de la entrada', como es el caso de la regla de inicio.
Sin embargo, este no es el conjunto completo de elementos 0. Cada conjunto de elementos debe estar 'cerrado', lo que significa que todas las reglas de producción para cada no terminal después de un '•' deben incluirse de forma recursiva 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 siguiendo la regla. Para lenguajes más complejos, esto generalmente da como resultado conjuntos de elementos muy grandes, que es la razón de los grandes requisitos de memoria de los analizadores sintácticos 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 los prospectos y solo observamos el caso de un LR (0), cuyos elementos no contienen terminales de búsqueda anticipada. Entonces, el conjunto de elementos 0 (sin lookaheads) se verá así:
- [S → • E]
- [E → • T]
- [E → • (E)]
- [T → • n]
- [T → • + T]
- [T → • T + n]
FIRST y FOLLOW conjuntos
Para determinar los terminales de búsqueda anticipada, se utilizan los denominados conjuntos FIRST y FOLLOW. PRIMERO (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. SEGUIR (I) de un elemento 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 yx es una terminal de búsqueda anticipada arbitraria. 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 '•' es seguido por 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 FOLLOW se determinan a partir de los elementos en uso de los conjuntos FIRST.
En nuestro ejemplo, como se puede verificar de la lista completa de conjuntos de elementos a continuación, los primeros conjuntos son:
- PRIMERO (S) = {n, '+', '('}
- PRIMERO (E) = {n, '+', '('}
- PRIMERO (T) = {n, '+'}
Determinación de terminales de búsqueda anticipada
Dentro del conjunto de elementos 0, los siguientes conjuntos pueden ser:
- 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 sintáctico 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 una terminal de búsqueda anticipada válida:
- [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 no terminal A que aparece 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 '•' es seguido por A, pero solo si m no será el mismo que un elemento ya existente configurado después del paso 3.
- 2. Mueva todos los '•' para cada regla en el nuevo elemento, establezca 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, 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 elementos 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, +]
- ·
- ·
- ·
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í. El tratamiento detallado de LR (k) de esta gramática se puede encontrar, por ejemplo, en [1] .
Ir
La búsqueda anticipada 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 que haga 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 contenga [A → α • X β, a] se moverá a un estado que contenga [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 se mueve al estado I m con la etiqueta b, entonces agregamos 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 → α"
Referencias
- ↑ a b c Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha" (PDF) . Información y control . 8 (6): 607–639. doi : 10.1016 / S0019-9958 (65) 90426-2 . Archivado desde el original (PDF) el 15 de marzo de 2012 . Consultado el 29 de mayo de 2011 .
- ^ "¿Qué es Menhir?" . INRIA, proyecto CRISTAL . Consultado el 29 de junio de 2012 .
- ^ "HYACC, generador de analizador sintáctico LR (1) mínimo" .
- ^ Franklin L. DeRemer (1969). "Traductores prácticos para idiomas LR (k)" (PDF) . MIT, Tesis Doctoral. Archivado desde el original (PDF) el 5 de abril de 2012.
- ^ a b Pager, D. (1977), "Un método general práctico para construir analizadores LR (k)", Acta Informatica 7 , págs. 249-268
enlaces externos
- Página HTML práctica de construcción del analizador LR (k) , David Tribble
- Construcción de conjuntos de primero y siguiente en Python (Narayana Chikkam)