| 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 Analizador Top-Down

> Analizadores sintácticos descendentes construyen el árbol buscando derivaciones a la izquierda hasta que concuerde con la entrada.

> Los no terminales son procedimientos y los terminales son lecturas de la entrada.

> La parte derecha de una producción propone la secuencia de llamadas a procedimientos y lecturas.

> TIPOS DE ANALIZADORES DESCENDENTES

> Análisis sintáctico por descenso recursivo:

> 1. Puede realizar retrocesos: analizar varias veces la entrada hasta encontrar las derivaciones correctas.

> Ejemplo:

> S ÆcAd
> A Æab|a
> Entrada: cad

> Analizadores sintácticos predictivos:

> Gramáticas sin recursión por la izquierda y factorizada por la izquierda implica un analizador descendente sin retroceso, si hay ambigüedad entonces no puedo aplicarlo. De la gramática se extrae el diagrama de transiciones.

> Criterios a cumplir

> Eficiencia: en lo posible el tiempo de análisis debe ser proporcional al tamaño del archivo.

> La acción a realizar debe decidirse conociendo un número limitado de componentes léxicos de la entrada.

> Deben evitarse los retrocesos, para lo cual las acciones a realizar se deben poder predecir con exactitud.

> Dada la expresión: “2 – 3 + 5”.

> El analizador sintáctico utiliza las reglas de producción de la gramática para construir el árbol sintáctico:

> E → E + E
> E →¨E – E
> E → n

> Problemas en el análisis descendente:

> La recursividad a izquierdas da lugar a un bucle infinito de recursión.

> Problemas de indeterminismo cuando varias alternativas en una misma producción comparten el mismo prefijo. No sabríamos cual elegir.

> Probaríamos una y si se produce un error haríamos backtracking. Si queremos que el método sea determinista hay que evitarlas.

> Existen transformaciones de gramáticas para su la eliminación. Estas transformaciones no modifican el lenguaje que se esta reconociendo, pero si que cambian el aspecto de la gramática, que es en general menos intuitiva.

> Los analizadores descendentes hacen el análisis de la Raíz a las Hojas.

> Obtener la tabla de análisis de la siguiente gramática:

> Factorizada queda como:

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