| 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.2.7 Análisis Sintáctico LR(1)

> Las gramáticas de tipo LR(k) delimitan un conjunto muy extenso de gramáticas para las cuales siempre podemos encontrar, mediante un algoritmo de análisis determinista, árboles de derivación derechos.

> Informalmente, decimos que una gramática es LR(k) si para cualquier

> S = α 0 rm α 1…rm α m = z,

> Podemos determinar (a) el mango de cada forma sentencial derecha, y (b) qué no-terminal va a reemplazar en la pila al mango, escaneando αi de izquierda a derecha, pero no más de k símbolos, a partir del final del mango.

> Sea αi-1 = αAω y αi = αβω, en donde β es el mango de αi. Sea además β = X1 X2 …Xr. Si la gramática en cuestión es LR(k), podemos asegurar los siguientes tres hechos:

> 1. Si conocemos αX1 X2 … Xj y los primeros k símbolos de Xj+1 … Xr ω, podemos estar seguros de que el final derecho de el mango no se alcanzará hasta que j = r.

> 2. Conociendo αβ, y como mucho los primeros k símbolos de w, podemos afirmar que β es el mango, y que β se va a reducir por A.

> 3. Si αi-1 = S, podemos afirmar que la cadena de entrada va a ser aceptada.

> Definición 2 Sea G = (VN, VT, P, S) una CFG. Se define la gramática aumentada de G como

> G’ = (VN {S’}, VT , P {S → S’ }, S’)

> Definición 3 Sea G = (VN, VT , P, S) una CFGy sea G’ = (VN ‘, VT ‘, P’, S’) su gramática aumentada. Decimos entonces que G es LR(k), con k 0 si las tres condiciones siguientes

> 1. S’ G’rm α A ω G’rm αβω,

> 2. S0 G’rm γ Bx G’rm αβ y, y

> 3. FIRSTk(ω) = FIRSTk(y), implican que αAy = γBx. Más aun, α = γ, A = B y x = y. Siendo ω, y, x VT *, α, β, γ, (VT VN)*, A, B, VN. Además, una gramática se denomina LR si es LR(k) para algún k.

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