Analizador sintáctico LR

Los analizadores sintácticos LR, también conocidos como Parser LR, son un tipo de analizadores para algunas gramáticas libres de contexto. Pertenece a la familia de los analizadores ascendentes, ya que construyen el árbol sintáctico de las hojas hacia la raíz. Utilizan la técnica de análisis por desplazamiento reducción. Existen tres tipos de parsers LR: SLR (K), LALR (K) y LR (K) canónico.

Un analizador LR consta de:

Un programa conductor
Una entrada
Una salida
Una tabla de análisis sintáctico, compuesta de dos partes (ACCIÓN Y GOTO).

Cabe acotar que el programa conductor es siempre igual, solo variando para cada lenguaje la tabla de análisis sintáctico.

El algoritmo para reconocer cadenas es el siguiente: dado el primer carácter de la cadena y el estado inicial de la tabla, buscar qué acción corresponde en la tabla de acción.

Si el estado es shiif n (n ∈ N), se coloca el carácter y el número de estado n en la pila, se lee el siguiente carácter y repite el procedimiento, solo que esta vez buscando en el estado correspondiente.

SI ACCIÓN = REDUCE n (n ∈ N), se sacan de la pila tantas tuplas (estado, símbolo) como el largo de la cola de la producción en el n-ésimo lugar, y se reemplaza por la cabeza de esta producción. El nuevo estado sale de buscar en la tabla GOTO usando para ubicarlo el número de estado que quedó en el tope de la pila, y el no terminal en la cabeza.

En la tabla acción también se encontrará ACEPTAR (que se toma la cadena como válida) y se termina el análisis o ERROR (que se rechaza la cadena).

Algoritmo para generar un autómata LR(0)

Para generar un autómata LR(0) sobre la base de una gramática G, primero se debe definir:

Gramática ampliada: Dada una gramática G, se define la gramática ampliada G'a:

1. Se agrega una producción S'->S#, donde S es el símbolo inicial (el # representa el fin de cadena).

2. Se pasan todas las producciones a ítems de configuración (se verá este concepto en un instante) con el punto al principio de la cola.

3. Se define S' como el símbolo inicial de la gramática.

Ítem de configuración: un ítem de configuración es una producción que tiene un carácter especial (generalmente un punto) en algún lugar de la cola. Por ejemplo: la producción S->ABC genera los siguientes ítems,{ S->.ABC, S->A.BC, S->AB.C S->ABC.}. Como veremos en un instante, y hablando informalmente, el punto representa el lugar actual en donde se puede encontrar en un momento en el parseo en una producción.

Clausura de un ítem: se define a la clausura de un ítem (y de forma informal) a: dado un ítem S->A.cB (A, B e V*, c e Vt unión VN) al conjunto formado por

1. S->A.cB

2. Si c es un no terminal, se agregan todos los ítems que tengan a c como cabeza de la producción y el punto al principio de la cola.

3. Si p es un ítem que pertenece a la clausura, la clausura de p pertenece a la clausura, siempre y cuando ya no esté agregada.

En otras palabras, y para que se entienda el concepto, la clausura de un ítem representa todas las producciones que se pueden aplicar a una cadena válida a partir del punto del ítem.

Finalmente, la construcción del autómata es así:

Se amplía la gramática.
Dado el símbolo inicial de la gramática ampliada, se calcula su clausura y esta se define como un estado inicial.
Para cada estado: se agrupan las producciones según el carácter que está después del punto, si todavía no se definió el estado, se corre el punto un carácter a la derecha, se crea el nuevo estado con esta producciones, y la clausura de cada una de ellas, se define el carácter que estaba después del punto en el estado de origen como el carácter de la transición.
Si el estado tiene en alguna producción el punto al final, este estado se marca como un estado final del autómata.
Se sigue hasta que ya no se tenga más estados nuevos posibles.

Estrictamente hablando, el autómata LR es un autómata determinista, aunque, en general, su utilidad radica en ser la base para la construcción de la tabla LR(0).

Véase también

Analizador sintáctico

Datos: Q1756442