Analizador sintáctico LR

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

1. Un programa conductor
2. Una entrada
3. Una salida
4. Una tabla de análisis sintáctico, compuesta de 2 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 shift 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 buscamos 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 quedo en el tope de la pila, y el no terminal en la cabeza.
En la tabla acción también encontraremos ACEPTAR que se toma la cadena como valida y se termina el análisis o ERROR que se rechaza la cadena.

Proceso de análisis LR.

En términos generales un analizador sintáctico LR transfiere símbolos de su entrada a la pila hasta que los símbolos superiores de la pila sean iguales al lado derecho de alguna regla de reescritura de la gramática en que se basa el analizador. Al llegar a este punto el analizador sintáctico puede reemplazar estos símbolos con el no terminal que se encuentra en el lado izquierdo de la regla de reescritura antes de transferir otros símbolos de la entrada a la pila.
De esta manera, la pila acumula cadenas de terminales y no terminales, que a su vez son reemplazados por no terminales “más altos” de la gramática. Por último, todo el contenido de la pila se reduce al símbolo inicial de la gramática, indicando que los símbolos leídos hasta ese punto forman una cadena que puede derivarse con la gramática.

Con base a este esquema general los analizadores sintácticos LR(k) se clasifican como analizador sintáctico ascendente, ya que sus actividades corresponden a la construcción de ocurrencias de no terminales a partir de sus componentes, hasta generar el símbolo inicial de la gramática. Los analizadores sintácticos LL(k) se conocen como analizadores sintácticos descendentes ya que comienzan con el símbolo inicial de la pila y dividen los no terminales de la pila hasta generar una cadena similar a la entrada.

Un analizador sintáctico LR(k) se basa en un autómata de pila construido a partir de una gramática independiente del contexto, con la excepción de que el autómata se construye con lo pasos siguientes:

Pasos para construir un Autómata

1. Establecer cuatro estados: inicial (i), aceptación (ƒ) y dos llamados p y q.
2. Introducir las transiciones (i, l, l; p, #) y (q, l, #; ƒ, l), # no pertenece a la gramática.
3. Para cada símbolo terminal x en la gramática, introducir la transición (p, x, l; p, x) que sirve para que el autómata transfiera a la pila los símbolos de entrada mientras se encuentra en el estado p. Esta transición se denomina operación de desplazamiento.
   
4. Para cada regla de reescritura N à w (w representa una cadena de uno o más símbolos) que exista en la gramática, introducir la transición (p, l, w; p ,N). La presencia de estas transiciones significa que si los símbolos de la porción superior de la pila concuerdan con los del lado derecho de la regla de reescritura, entonces es posible reemplazar estos símbolos con en no terminal de la parte izquierda de esa regla. Transición denominada operación de reducción.
5. Introducir la transición (p, l,S; q, l), donde S es el símbolo inicial de la gramática. Es decir, si se han reducido a S los símbolos de la pila, el autómata puede pasar al estado q a la vez que extrae S de la pila.

Implantación de analizadores sintácticos LR(k).

Al tratar de convertir los autómatas de pila a un programa aparecen dos problemas. El primero es el referente al no determinismo (al igual que con los analizadores LL(k)), con los analizadores LR(k) si se presenta una opción, no se sabe si desplazar o reducir. Además, si la opción es reducir, puede haber más de una reducción posible. Estos problemas se resuelven con las aplicaciones del principio de preanálisis.

El segundo problema viene dado por la interrogación de la pila, ya que para el preanálisis sólo se dispone de un elemento de la pila, el de la cima. La solución está en el uso de las tablas de análisis sintáctico LR(k). Las columnas de la tabla se rotulan con los símbolos de la gramática (terminales y no terminales) junto con la marca de fin de cadena (FDC). Las filas se etiquetan con números que representan símbolos especiales (componentes léxicos, que representan patrones que pueden aparecer en la pila).

El análisis sintáctico de cualquier cadena comienza asignando el valor uno a una variable de símbolo especial e insertando este valor en la pila vacía. Desde este momento a la inserción de un símbolo en la pila le sigue la inserción de un símbolo especial. Es decir, el contenido de la pila alternará entre símbolos terminales, no terminales y símbolos especiales, donde cada uno de estos últimos representan el patrón de lo que yace debajo de él. Por lo tanto, se puede conocer la estructura interna de la pila observando el símbolo especial de la cima.

Tablas de análisis sintácticos LR.

La tabla de un analizador sintáctico LR(1) se basa en la existencia de un autómata finito que acepta exactamente las cadenas de símbolos de la gramática (terminales y no terminales) que conducen a operaciones de reducción. Para conseguirlo no sigue un proceso de prueba y error, sino una secuencia bien definida de eventos guiados por los símbolos que se detectan en la cadena analizada. La idea es comenzar el proceso de análisis sintáctico siguiendo la ruta determinada por la cadena de entrada hasta encontrar un estado de aceptación. En este punto, la ruta recorrida por el autómata finito corresponde al patrón de símbolos que el analizador ha desplazado a la pila. El proceso de análisis retrocede, entonces, por esta ruta recorriendo los símbolos que deben examinarse de la pila durante la operación de reducción. A partir de aquí, el analizador recorre el arco del diagrama de transiciones del autómata finito que tenga la etiqueta equivalente al no terminal colocado en la pila por la operación de reducción correspondiente. Una vez completada la operación de reducción, los símbolos de la pila corresponderán una vez más a los símbolos de la ruta que recorre el autómata finito.

Los valores de los símbolos especiales representan los estados del autómata finito. Las casillas de desplazamiento de la tabla corresponden a los arcos rotulados con terminales, mientras que el símbolo especial que se encuentra en esa casilla representa el estado final del arco. Las casilla de reducción indican que el analizador ha llegado a un estado de aceptación en el autómata finito, y proporciona la información necesaria para realizar el proceso de retroceso. Las casilla de las columnas etiquetadas con no terminales permitirán al analizador sintáctico establecer una nueva dirección en el diagrama después del retroceso.

Comparación entre analizadores sintácticos LR(k) y LL(k).

La colección de analizadores sintácticos LR(k) es más poderosa que la de los analizadores LL(k) (por ejemplo ningún LL(k) puede manejar el lenguaje{ : } { : } x n N x y n N n n n Î È Î que si es manejable por LR(1)).
Existen lenguajes independientes del contexto que ningún analizador LR(k) puede reconocer. Un analizador LR(k) debe ser determinista y, puesto que su estructura se basa en un autómata de pila, se debe deducir que los analizadores sintácticos LR(k) sólo pueden analizar los lenguajes que aceptan los autómatas de pila deterministas.

Véase también

• Analizador sintáctico
• Intérpretes
• Compiladores
• Token
• Analizador sintáctico LL

Fuente

• Analizadores Ascendentes
• Análisis sintáctico LR: SLR (LR simple)
• Traductores e Intérpretes UCAB : Algoritmo de Análisis Sintáctico LR
• Análisis Sintáctico Ascendente
  
• Teoría sobre autómatas