| 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.8 Definición de Elementos LR(1)

> La forma general de un elemento LR(1) es [A → α • β, a] en donde A → αβ es una producción de la gramática, y a un terminal, ó $.

> A este tipo de elemento se le denomina elemento de análisis sintáctico LR(1).

> El número 1 denota la longitud del símbolo a, o símbolo de anticipación del elemento. Este símbolo no va a tener efecto en aquellos elementos en los cuales la cadena β ≠ γ¸ ya que no van a dictar una reducción.

> Sin embargo, un elemento [A → α •, a] indica que se aplique una reducción siempre que el siguiente símbolo a la entrada sea a.
> Obviamente, las a’s van a formar un subconjunto de FOLLOW(A), y pueden formar un subconjunto propio de este, como debería ser en el ejemplo anterior.

> Definición 13 Sea una gramática G = (VN, VT , S, P). Sea γ un prefijo viable de G. Sean A → αβ P y a VT {$}. Se dice que el elemento LR(1) [A → α • β, a] es válido para γ si existe una derivación:

> S rm δAw rm δαβω, en donde

> 1. γ = δα y

> 2. a es el primer símbolo de ω, ó ω = λ¸ y a = $.

> El procedimiento de construcción de la colección de conjuntos de elementos LR(1) válidos es muy similar al que hace lo propio con la colección de conjuntos de elementos LR(0). Se trata de modificar los procedimientos cerradura e ir_a.

> Definición 14 Sea I un conjunto de elementos. Se define la función cerradura(I) como el conjunto resultante de aplicar:

> begin
> repeat
> for cada elemento [A → α • Bβ, a] I, cada
> producción B → γ G′ y cada b VT tal que
> b FIRST(βa) y [B → • γ, b] I, entonces
> Añadir [B → γ, b] a I
> until no se puedan añadir más elementos a I;
> end;

> Esta definición ha cambiado respecto de la definición 11 en la que se describía la función cerradura para la colección de conjuntos de elementos SLR(1).

> Ahora hay que tener en cuenta los símbolos terminales que pueden aparecer, en formas sentenciales derechas, inmediatamente a continuación del no terminal mediante el cual se podría aplicar una reducción.

> La forma de trabajar del procedimiento es la siguiente:
> Partiendo de un conjunto I con unos determinados elementos iniciales, se toma en consideración el elemento [A → α • Bβ, a].
> Se supone que este elemento es válido para un prefijo viable ± concreto, en el cual se tiene como sufijo α, o dicho de otra forma δ = μα. Por lo tanto, existe una derivación derecha

> S rm μAay rm μαBβay

> Ahora supongamos que, a partir de βay se deriva la cadena de terminales bt en donde t V * T.

> Entonces, para cada producción B → φ, se va a tener una derivación más a la derecha:

> S rm μα Bbt rm μφ bt

> Por lo tanto, [B → •φ, b] será un elemento válido para el mismo prefijo viable δ. Lo que se hace, al fin, es incluir todos los elemento formados por las producciones B → φ y los símbolos terminales que están en el conjunto FIRST(βa) ≡ FIRST(βay).

> Definición 15 Sea I un conjunto de elementos, y X VN VT {$}. Se define la función ir_a(I,X) como el conjunto de elementos resultante de aplicar el siguiente procedimiento:

> begin
> Sea J el conjunto de elementos [A → αX • β, a] tal que
> [A → α • Xβ, a] está en I. El estado resultante es el que viene dado por cerradura(J).
> end;

> La función ir a es idéntica a la anterior.

> Definición 16 Sea G = (VN, VT , S, P) una CFG. Sea G′ la gramática aumentada de G, en donde el símbolo inicial es ahora S′. La colección de conjuntos de elementos LR(1) es la resultante de aplicar el siguiente procedimiento sobre G′.

> begin
> C = {cerradura({[S′ → •S, $]})};
> repeat
> for cada I C, y cada X VN VT {$} tal que
> ir a(I,X) ≠ y I C do
> añadir ir a(I,X) a C
> until no se puedan añadir más conjuntos a C
> end;

> 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