| 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.4.2.2 Definición de Gramáticas LL(1) con reglas Épsilon

> Es posible tomar una decisión errónea al construir un árbol de análisis sintáctico, ya que había diversas alternativas en una determinada situación (por ejemplo, hablando informalmente, la gramática no tenía suficiente precisión). Por consiguiente, postulamos la siguiente regla para los analizadores sintácticos: Para cada producción de la forma:

> A → Jl | J2 |...| Jn

> Siempre debemos ser capaces de elegir la alternativa correcta para la generación de un árbol de análisis sintáctico.
> Para cumplir esta regla necesitamos información adicional, a saber:

> 1) El conjunto de todos los símbolos terminales que pueden aparecer al principio de una frase que puede derivarse de una secuencia arbitraria de símbolos;

> 2) El conjunto de todos los símbolos terminales que pueden aparecer después de uno no terminal.

> Éstos son los conjuntos llamados PRIMERO y SIGUIENTE.
> Sean G (N, T, P, S) una gramática y α una secuencia arbitraria de símbolos, es decir, α ε (N u T)*. Definimos entonces el conjunto de terminales que pueden aparecer al principio de cualquier frase derivable de α como:

> PRIMERO(α) = {t | t ε Tε α tα'}, donde Tε = T U { λ }.

> Sea X un símbolo no terminal. Entonces, SIGUIENTE(X) es el conjunto de todos los símbolos terminales que pueden aparecer inmediatamente a la derecha de X:

> SIGUIENTE(X) = {t | t ε Tε S αXtβ}.

> Si tenemos la siguiente gramática, el proceso para determinar si es una gramática LL(1) es como sigue:

> W → YZ
> V → Wx

> Donde, x es un elemento de SIGUIENTE(Z) o, de manera más general, cualquier elemento de SIGUIENTE(W) está en el conjunto SIGUIENTE(Z).

> Una gramática independiente del contexto G (N, T, P, S) se denomina gramática LL(1), si tiene las siguientes características:

> 1) Para cada producción de la forma:

> A → J1 | J2 | ... | Jn

> Se requiere que: PRIMERO(Ji) PRIMERO(Jj) = i ≠ j.

> 2) Si puede derivarse la cadena vacía λ de un símbolo no terminal X, se requiere que:

> PRIMERO(X) SIGUIENTE(X) = .

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