| 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.1 Frases, formas sentenciales, Handles (Mangos), Prefijo Viable

> Concepto de mango y prefijo viable.

> El mango de una cadena es una subcadena que concuerda con el lado derecho de una producción y cuya reducción al no terminal del lado izquierdo de la producción representa un paso a lo largo de la inversa de una derivación por la derecha.

> Formalmente, un mango de una forma de frase derecha γ es una producción A → β y una posición de γ donde la cadena β podría encontrarse y sustituirse por A para producir la forma de la frase derecha previa en una derivación por la derecha de γ. Es decir, si:

> S αAω αβω, entonces, A → β si la posición que sigue de α es un mango de αβω.

> Los prefijos de las formas de frase derecha que pueden aparecer en la pila de un analizador sintáctico por desplazamiento y reducción se denominan prefijos viables. Una definición equivalente de prefijo viable es la de que es un prefijo de una forma de frase derecha que no continúa más allá del extremo derecho del mango situado más a la derecha de esta forma de frase.

> Si se tiene la siguiente gramática:

> E → E+E
> E → E*E
> E → (E)
> E → id

> Obtener la siguiente cadena

> id + id* id

> Se aplica la derivación por la izquierda

> E E+E id + E id + E * E id + id * E id + id * id

> Derivación
> E id

> Reducción
> E ß id

> id +id *E
> id + E * E
> id + E
> E + E

> *
> E <= id + id * id
> E + id * id
> E + E * id
> E * id

> E * E
> E

> Antes Cadena de caracteres Después
> Palabra

> Antes = Prefijo

> Después = Postfijo

> Si se tiene la siguiente gramática:

> EXPR → TERM | EXPR + TERM | EXPR – TERM
> TERM → FACTOR | TERM * FACTOR | TERM / FACTOR
> FACTOR → X | Y | (EXPR)
> Derivar la siguiente cadena

> X + Y - X*Y

> I
> EXPR=> EXPR – TERM
> => EXPR + TERM - TERM
> => TERM + TERM - TERM
> => FACTOR + TERM – TERM
> => X + TERM – TERM
> => X + FACTOR – TERM
> => X + Y - TERM
> => X + Y – TERM * FACTOR
> => X + Y – FACTOR * FACTOR
> => X + Y – X * FACTOR
> => X + Y – X * Y

> El árbol es:

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