| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV Introducción 4.1 Frases, formas sentenciales, Handles (Mangos), Prefijo Viable 4.2 Eliminación de Recursión inmediata y no inmediata 4.3 Factorización de Gramáticas

4.4 Analizador Top-Down

4.4.1 Análisis Sintáctico por Descenso Recursivo sin Retroceso y con Retroceso

4.4.2 Análisis Sintáctico LL(1)

4.4.2.1 Cálculo de First y Follow

4.4.2.2 Definición de Gramáticas LL(1) con reglas Épsilon

4.4.2.3 Algoritmo de análisis sintáctico LL(1)

4.5 Analizador Bottom-UP

4.5.1 Análisis Sintáctico por Precedencia de Operadores

4.5.1.1 Definición de Gramáticas de Operadores

4.5.1.2 Definición Formal de las Relaciones de Precedencia de Operadores

4.5.1.3 Funciones Firstop y Lastop

4.5.1.4 Obtención de la tabla de precedencia de Operadores

4.5.1.5 Algoritmo de análisis Sintáctico por Precedencia de Operadores

4.5.2 Análisis Sintáctico LR

4.5.2.1 Algoritmo de Análisis Sintáctico LR

4.5.2.2 Análisis Sintáctico LR(0)

4.5.2.2.1 Construcción de la Máquina LR(0)

4.5.2.2.2 Construcción de la Tabla LR(0)

4.5.2.2.3 Análisis Sintáctico SLR

4.5.2.2.4 Obtención de Estados SLR

4.5.2.2.5 Construcción de la Máquina de Estados SLR

4.5.2.2.6 Construcción de la Tabla SLR

4.5.2.2.7 Análisis Sintáctico LR(1)

4.5.2.2.8 Definición de elementos LR(1)

4.5.2.2.9 Construcción de conjuntos de elementos

4.5.2.2.10 Construcción de Máquina de estados LR(1)

4.5.2.2.11 Construcción de la Tabla LR(1)

UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

4.5.2.1 Algoritmo de Análisis Sintáctico LR

> La siguiente figura muestra una 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. El programa conductor y una tabla de análisis sintáctico con dos partes. El programa conductor es el mismo para todos los analizadores sintácticos LR; solo 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 S0 X1S1 X2S2... XmSm donde Sm esta en la cima. Cada X1 es un símbolo gramatical y cada Si es un símbolo llamado estado. Cada símbolo de estado resume la información contenida debajo de el 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 ai, el símbolo en curso de la entrada.

> Después consulta la entrada acción[Sm, ai] de la tabla de acciones del analizador para el estado Sm, y la entrada ai que puede tener uno de estos cuatro valores:

> 1. Desplazar S, donde S es un estado,
> 2. Reducir por una producción gramatical ,
> 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 vera 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 LARL es la función de transacciones de un autómata finito determinista que reconoce los prefijos viables de G. 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

> Esta configuración representa la forma de frase derecha

> Fundamentalmente de la manera en que lo haría un analizador sintáctico por desplazamiento y reducción; solo es nueva la presencia de los estados en la pila. El siguiente movimiento del analizador se determina leyendo ai, el símbolo de la entrada en curso, y sm, el estado del tope de la pila y consultando después la entrada acción de la tabla de acciones del analizador.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello