| 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 Analizador Button-Up

> Algoritmo de análisis sintáctico LR

> La tabla acción, A[s,a] si desplazar, reducir, aceptar o señalar un error cuando el estado s esta en la cima de la pila y a es el siguiente token de la entrada.

> La tabla ir_a, G[s, X], da el nuevo estado a poner en el la cima de la pila. Esta función, para los terminales, está codificada en la propia tabla acción.

> Para las acciones se van a utilizar los siguientes códigos:

> di significa desplazar y meter en la pila el estado i, rj significa reducir por la producción con número j, acep significa aceptar, y el espacio en blanco significa error.

> Entrada: una cadena w y las tablas de análisis sintáctico LR acción e ir_a para la Gramática G.

> Salida: Si w está en L(G), un análisis sintáctico ascendente de w; sino indica error.

> Método: Inicialmente, en la pila esta el estado inicial 0, y w# en la entrada.

> apuntar ae al primer símbolo de w#
> repeat forever begin
> sea s el estado en la cima de la pila y a el símbolo apuntado por ae;
> if A[s,a] = desplazar’s then meter a y después s’ en la cima de la pila;
> avanzar ae al siguiente símbolo de entrada;
> else if A[s,a]=reducir A->B then sacar 2 x B símbolos de la pila;
> sea s’ estado que ahora está en la cima de la pila;
> meter A y de después G[s’, A] en la cima de la pila;
> emitir la producción A → B;
> else if A[s, a]= aceptar then return
> else error
> end

> Ejemplo:

> Ejemplo conflicto SHIFT-REDUCE

> Análisis SLR

> Es la técnica más sencilla que permite un análisis LR con previsión de LookAhead de un símbolo.

> Clase gramatical LR(1) más simple .

> Ante un conflicto DESPLAZAMIENTO-REDUCCIÓN: un elemento y otro en el mismo conjunto se calcula el SIGUIENTE(B), si no incluye el símbolo de detrás de la marca en el item se puede resolver el conflicto.

> Ante un conflicto REDUCE-REDUCE: en el mismo conjunto, si son disjuntos SIGUIENTE(A) y SIGUIENTE(B) se puede resolver.

> SLR

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