| 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.2 Eliminación de Recursión Inmediata y no Inmediata

> Cuando se tiene la siguiente producción.

> A → Aα| β

> Esta se puede expresar de otra forma:

> A → Aα
> A → β

> Donde α y β son cadenas de terminales. Así que si comenzamos a derivar por la izquierda tenemos:

> I
> A => β
> I
> A => Aα => Aαα => Aααα => βααα

> Aquí vemos que la derivación por la izquierda la podemos continuar indefinidamente. Para poder expresar las derivaciones, se usa la siguiente nomenclatura:

> +
> A => A α

> Quiere decir que al menos hay una derivación que comienza con Aα.

> Cuando tenemos una derivación infinita por la izquierda decimos que existe RECURSIÓN IZQUIERDA.

> Y esta recursión izquierda es necesario eliminarla de la siguiente manera:

> De los siguientes árboles de análisis sintáctico, tenemos:

> Así cuando se tienen las producciones de la siguiente forma:

> A→ A’ α
> A→ β

> Se debe de aplicar la siguiente fórmula 1:

> A→ β A’
> A’→ αA’
> A’→ λ

> Elimine la recursividad izquierda a la siguiente gramática:

> E → E+T | T …… (1)
> T → T*F | F ……. (2)
> F → (E) | id …….. (3)

> Se identifica si cada una de las producciones tiene la forma:

> A→ A α| β

> Las producción 1 y 2, tienen recursividad izquierda, por lo que:

> E → E+T | T
> A→ A α| β

> Se igualan los símbolos iguales:

> A = E
> α = + T
> β = T

> E → TE’
> E’ → +TE’
> E’→ ε

> A la producción T → T*F | F, también se le aplica el mismo proceso:

> A = T
> α = *F
> β = F

> Se aplica la fórmula 1:

> T→ FT’
> T’→ *FT’
> T’→ ε

> La gramática con la recursividad izquierda eliminada es:

> E → TE’
> E’ → +TE’
> E’→ λ

> T→ FT’
> T’→ *FT’
> T’→ λ
> F→ (E)| id

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