Semana # 14

 

 

Analizadores sintácticos LR

 

Existen tres técnicas para construir tablas de análisis sintáctico LR para una gramática. El primer método, llamado LR (SLR) es el más fácil, pero menos poderoso. El segundo método, llamado LR canónico, es el más poderoso y costoso. El tercer método, llamado LR con examen anticipado (LALR) está entre los oros dos en poder y costo.

         El analizador sintáctico LR consta de una entrada, una salida, un programa conductor y una tabla de análisis sintáctico con dos partes: Acción r ir_a. El programa lee caracteres de un buffer de entrada de uno en uno. Utiliza una pila para almacenar una cadena de la forma:

 

s₀X₁ s₁X₂ ... s_mX_m^, donde s_m

 

está en la cima. Cada X_i es un símbolo gramatical y cada s_i es un símbolo llamado estado. Cada símbolo de estado resume la información contenida debajo de él en la pila.

 

 

 

         La tabla de análisis sintáctico consta de dos partes: una acción del analizador y la función ir_a (indica transiciones entre estados).

         Las entradas pueden ser uno de los siguientes cuatro valores:

·       Desplazar s, donde s es un estado

·       Reducir por una producción gramatical A à B

·       Aceptar

·       Error

 

La función ir_a toma un estado y un símbolo gramatical como argumentos y produce un estado. La función ir_a de una tabla es la función de transiciones de un autómata finito determinista.

 

 

¿Cómo se sabe si una gramática es LR?

 

         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.

 

¿Cuál es diferencia entre LR y LL?

 

         Para que una gramática sea LR(k), hay que ser capaz de reconocer la presencia del lado derecho de la producción, habiendo visto todo lo que deriva de dicho lado derecho con k símbolos de examen por anticipado. En las tablas LL(k) hay que ser capaz de reconocer el uso de una producción viendo solo los primeros k símbolos de los que deriva su lado derecho.

 

 

Operación cerradura

 

1)    Inicialmente, todo elemento de I se añade a cerradura(I).

2)    Si A àa.Bb está en la cerradura(I) y Bàg es una producción, entonces añadese el elemento Bà.g a cerradura(I), si todavía no está ahí. Se aplica esta regla hasta que no se puedan añadir más elementos a la cerradura(I).