| 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.1.2 Definición Formal de las Relaciones de Precedencia de Operadores

> Siempre se pueden crear relaciones de precedencia de operadores de la forma que se considere adecuada y esperar que el algoritmo de análisis sintáctico por precedencia de operadores funcione correctamente al guiarse por ellas. Para un lenguaje de expresiones aritméticas, como el generado por la gramática (4.17), se pueden usar las siguientes técnicas heurísticas para producir un conjunto adecuado de relaciones de precedencia. Obsérvese que la gramática (4.17) es ambigua, y las formas de frase derechas podrían tener muchos mangos. Se establecen las siguientes reglas para seleccionar mangos "apropiados" para reflejar un determinado conjunto de reglas de asociatividad y precedencia para operadores binarios.

> Si el operador Ө 1, tiene mayor precedencia que el operador Ө 2, hágase Ө 1> Ө 2 y

> Ө 2 < Ө 1 . Por ejemplo, si * tiene mayor precedencia que + hágase * > + y + < *. Estas relaciones garantizan que, en una expresión de la forma E+ E*E+E, el central E*E será el mango que se reducirá primero.

> Si Ө 1 y Ө 2 son operadores de igual precedencia (de hecho, pueden ser el mismo operador), entonces hágase Ө 1> Ө 2 y Ө 2 > Ө 1 si los operadores son asociativos por la izquierda, o hágase Ө 1| < Ө 2 ¿ y Ө 2 < Ө 1 si son asociativos por la derecha.

> Por ejemplo, si + y - son asociativos por la izquierda, entonces hágase +> + ,+>-, - > - y - > +. Si ↑ es asociativo por la derecha, entonces hágase ↑ < ↑. Estas relaciones garantizan que para E—E+E se seleccionará E — E como mango y que para E ↑ E ↑ E se seleccionará la última E ↑ E.

> Hágase Ө < id, id > Ө, Ө < (, ( < Ө , ) > Ө, Ө > ), Ө > $, y $ < Ө para todos los operadores Ө, Hágase también

> ( = ) $ < ( $ < id
> (< ( id > $ )>$
> ( < id id > ) ) > )

> Estas reglas garantizan que tanto id como (E) se reducirán a E. Asimismo, $ sirve como marcador de los extremos izquierdo y derecho, lo cual hace que los mangos se encuentren entre los dos símbolos $ siempre que sea posible.

> Ejemplo 4.28. La figura 4.25 contiene las relaciones de precedencia de operadores para la gramática (4.17), asumiendo que:

> ↑ tiene la mayor precedencia y es asociativo por la derecha,
> + y / tienen la siguiente mayor precedencia y son asociativos por la izquierda, y + y - tienen la menor precedencia y son asociativos por la izquierda.

> (Los espacios en blanco señalan entradas de error.) El lector debe practicar con la tabla para comprobar si funciona correctamente, ignorando por el momento los problemas con el menos unario. Pruébese la tabla con la entrada id * (id ↑ id) —id/id, por ejemplo:

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