3.7 Analizadores Sintácticos LR

En esta sección se analiza una técnica eficiente de análisis sintáctico ascendente que se puede utilizar para analizar una clase más amplia de gramáticas independientes del contexto. La técnica se denomina análisis sintáctico LR(k); la "L" es por el examen de la entrada de izquierda a derecha (en inglés, left-to right), la "R" por construir una derivación por la derecha (en inglés, rightmost derivation) en orden inverso, y la k por el número de símbolos de entrada de examen por anticipado utilizados para tomar las decisiones del análisis sintáctico. Cuando se omite, se asume que k es l. El análisis sintáctico LR es atractivo por varias razones.

• Se pueden construir analizadores sintácticos LR para reconocer prácticamente todas las construcciones de los lenguajes de programación para los que se pueden escribir gramáticas independientes del contexto.
• El método de análisis sintáctico LR es el método de análisis por desplazamiento y reducción sin retroceso más general que se conoce, y sin embargo se puede aplicar tan eficientemente como los otros métodos de desplazamiento y reducción.
•  La clase de gramáticas que pueden analizarse con los métodos LR es un supraconjunto de la clase de gramáticas que se pueden analizar con analizadores sintácticos predictivos.
•  Un analizador sintáctico LR puede detectar un error sintáctico tan pronto como sea posible hacerlo en un examen de izquierda a derecha de la entrada.

El principal inconveniente del método es que supone demasiado trabajo construir un analizador sintáctico LR a mano para una gramática de un lenguaje de programación típico. Se necesita una herramienta especializada - un generador de analizadores sintácticos LR- . Por fortuna, existen disponibles estos generadores, el programa Y ACC. Con este generador se puede escribir una gramática independiente del contexto y el generador produce automáticamente un analizador sintáctico para dicha gramática. Si la gramática contiene ambigüedades u otras construcciones difíciles de analizar en un examen de izquierda a derecha de la entrada, el generador puede localizar dichas construcciones e informar al diseñador del compilador de su presencia.

Después de estudiar la operación de un analizador sintáctico LR, se introducen tres técnicas para construir una tabla de análisis sintáctico LR para una gramática. El primer método, llamado LR sencillo (SLR, en inglés) es el más fácil de implantar, pero el menos poderoso de los tres. Puede que no consiga producir una tabla de análisis sintáctico para algunas gramáticas que otros métodos sí consiguen. El segundo método, llamado LR canónico, es el más poderoso y costoso. El tercer método, llamado LR con examen por anticipado (LALR, en inglés), está entre los otros dos en cuanto a poder y costo. El método LALR funciona con las gramáticas de la mayoría de los lenguajes de programación y, con un poco de esfuerzo, se puede implantar en forma eficiente. En esta sección se consideran más adelante algunas técnicas para comprimir el tamaño de una tabla de análisis sintáctico LR.

El algoritmo de análisis sintáctico L.R

En la figura  se muestra la forma esquemática de un analizador sintáctico LR. Consta de una entrada, una salida, una pila, un programa conductor y una tabla de análisis sintáctico con dos partes (acción e ir_a). El programa conductor es el mismo para todos los analizadores sintácticos LR; sólo cambian las tablas de un analizador a otro. El programa analizador lee caracteres de un buffer de entrada de uno en uno.

El programa utiliza una pila para almacenar una cadena de la forma s₀X₁s₁X₂S₂ ... X_ms_m, donde s_m está en la cima. Cada X₁ es un símbolo gramatical y cada s1 es un símbolo llamado estado. Cada símbolo de estado resume la información contenida debajo de él en la pila, y se usan la combinación del símbolo de estado en la cima de la pila y el símbolo en curso de la entrada para indexar la tabla de análisis sintáctico y determinar la decisión de desplazamiento a reducción del analizador. En una implantación no es necesario que los símbolos de la gramática aparezcan en la pila; sin embargo, siempre se incluirán en las siguientes exposiciones, para facilitar la explicación del comportamiento de un analizador sintáctico LR.

La tabla de análisis sintáctico consta de dos partes, la función acción, que indica una acción del analizador, y la función ir_a, que indica las transiciones entre estados. El programa que maneja el analizador sintáctico LR se comporta como sigue: determina Sm, el estado de la cima de la pila, y a1, el símbolo en curso de la entrada.

Después consulta la entrada acción [sm, a₁] de la tabla de acciones del analizador para el estado s_my la entrada a₁, que puede tener uno de estos cuatro valores:

1. desplazar s, donde s es un estado,
2. reducir por una producción gramatical A->β.
3. aceptar y
4. error.

La función ir_a toma un estado y un símbolo gramatical como argumentos y produce un estado. Se verá que la función ir a de una tabla de análisis sintáctico construida a partir de una gramática G utilizando el método SLR, LR canónico o LALR es la función de transiciones de un autómata finito determinista que reconoce los prefijos viables de G. Recuérdese que los prefijos viables de G son aquellos prefijos de formas de frase derecha que pueden aparecer en la pila de un analizador sintáctico por desplazamiento y reducción, porque no sobrepasan el mango situado más a la derecha. El estado inicial de esta AFD es el estado puesto inicialmente en la cima de la pila del analizador LR.

Una configuración de un analizador sintáctico LR es un par cuyo primer componente es el contenido de la pila, y el segundo, la entrada todavía sin procesar

(s₀ X₁ s₁ X₂ s₂ ... X_m s_m, a₁ a_i+1…a_n$)

Esta configuración representa la forma de frase derecha

X₁X₂…X_ma_i a_i+1…a_n

Fundamentalmente de la manera en que lo haria un analizador sintáctico por desplazamiento y reducción; sólo es nueva la presencia de los estados en la pila.

El siguiente movimiento del analizador se determina leyendo a₁, el símbolo de la entrada en curso, y S_m, el estado del tope de la pila, y consultando, después la entrada acción [s_m, a₁] de la tabla de acciones del analizador. Las configuraciones obtenidas después de cada uno de los cuatro tipos de movimiento son las siguientes:

1. Sí acción [sm, a1] = desplazar s, el analizador ejecuta un movimiento de desplazamiento, entrando en la configuración

(s₀ X₁ s₁ X₂s₂ … X_ms_m a_i s,  a_i+1 …a_n$ )

Aquí, el analizador ha desplazado a la pila al símbolo de entrada en curso a y al siguiente estado s, que está dado en acción[s_m, a_i]; a_{i_1} se convierte en el símbolo de entrada en curso.

1. Si acción [sm, ai] = reducir A -> β, entonces el analizador ejecuta un movimiento de reducción, entrando en la configuración

(s₀ X₁ s₁ X₂s₂ … X_m-r s_m-r A s,  a_i a_i+1 …a_n$ )

donde s = ir _a(s_m-r,  A], y r es la longitud de β, el lado derecho de la producción. Aquí el analizador extrajo primero 2r símbolos de la pila (r símbolos de estados y r símbolos de la gramática), exponiendo el estado Sm-r· Luego introdujo A, el lado izquierdo de la producción, y s, la entrada de ir_a[s_m-r, A], en la pila. En un movimiento de reducción no se modifica el símbolo de entrada en curso. Para los analizadores LR que se construirán, X_m-r+1… X_m, la secuencia de símbolos gramaticales extraídos de la pila, siempre concordarán con β, el lado derecho de la producción con que se efectúa la reducción.

Después de un movimiento de reducción, se genera la salida de un analizador LR ejecutando la acción semántica asociada a la producción con que se efectúa la reducción. Por el momento, se asumirá que la salida consiste únicamente en imprimir la producción con que se efectúa la reducción.

1. Si acción [s_m, a_i] = aceptar, el análisis sintáctico ha terminado.
2. Si acción[s_m, a_i) = error, el analizador ha descubierto un error y llama a una rutina de recuperación de errores.

Gramáticas LR

¿Cómo se construye una tabla de análisis sintáctico LR para una determinada gramática?

Una gramática para la que se puede construir una tabla de análisis sintáctico se denomina gramática LR. Hay gramáticas independientes del contexto que no son LR, pero en general se pueden evitar en las construcciones típicas de los lenguajes de programación. Intuitivamente, para que una gramática sea LR basta con que un analizador sintáctico por desplazamiento y reducción que opere de izquierda a derecha pueda reconocer los mangos cuando aparezcan en la cima de la pila.

Un analizador LR no tiene que examinar la pila completa para saber cuándo aparecen los mangos en la cima. Por el contrario, el símbolo del estado en la cima de la pila contiene toda la información necesaria. Es un hecho curioso que, si se puede reconocer un mango conociendo sólo los símbolos gramaticales de la pila, entonces existe un autómata finito que puede, leyendo los símbolos gramaticales de la pila de arriba a abajo, determinar el mango, si existe, que está en el tope de la pila. La función ir_a de una tabla de análisis sintáctico LR es esencialmente dicho autómata finito. Sin embargo, el autómata no necesita leer la pila para cada movimiento. El símbolo estado almacenado en la cima de la pila es el estado en que estaría el autómata finito reconocedor de los mangos si hubiera leído los símbolos gramaticales de la ·pila desde abajo hasta la cima. Por tanto, el analizador sintáctico LR puede determinar a partir del estado de la cima de la pila todo lo que se necesita saber sobre lo que hay en ella.