| 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 Análisis Sintáctico por Precedencia de Operadores

> Para una pequeña, pero importante, clase de gramáticas, se pueden construir con facilidad a mano eficientes analizadores sintácticos por desplazamiento y reducción. Estas gramáticas tienen la propiedad (entre otros requisitos fundamentales) de que ningún lado derecho de la producción es ε ni tiene dos no terminales adyacentes. Una gramática con esta última propiedad se denomina gramática de operadores.

> Ejemplo: La siguiente gramática para expresiones:

> E → EAE │(E)│ - E│id
> A →+ │-│*│/│↑

> No es una gramática de operadores, porque el lado derecho EAE tiene dos (de hecho tres) no terminales consecutivos. Sin embargo, si se sustituye cada una de sus alternativas por A, se obtiene la siguiente gramática de operadores:

> E→ E+E│ E-E│ E*M | E/E │ E ↑ E │ (E) │ - E | id (4.17)

> A continuación se describe una técnica de análisis sintáctico fácil de implantar llamada análisis sintáctico por precedencia de operadores. Históricamente, la técnica se describió primero como una manipulación de componentes léxicos sin hacer referencia a ninguna gramática subyacente. De hecho, cuando se termina de construir un analizador sintáctico por precedencia de operadores a partir de una gramática, se puede efectivamente prescindir de la gramática, utilizando los no terminales de la pila tan solo como indicadores de los atributos asociados a los no terminales.

> Como técnica general de análisis sintáctico, el análisis por precedencia de operadores tiene varios inconvenientes. Por ejemplo, es difícil manejar componentes léxicos como el signo menos, que tiene dos precedencias distintas (dependiendo de si es unario o binario). Peor aún, como la relación entre una gramática para el lenguaje que está siendo analizado y el mismo analizador sintáctico por precedencia de operadores es muy frágil, no siempre se puede tener la seguridad de que el analizador acepta exactamente el lenguaje deseado. Por último, sólo una pequeña clase de gramática puede analizarse usando las técnicas de precedencia de operadores.
> Sin embargo, dada su sencillez, se han construido con éxito muchos compiladores que utilizan las técnicas de análisis sintáctico por precedencia de operadores para expresiones.

> Con frecuencia, estos analizadores utilizan el descenso recursivo, para proposiciones y construcciones de alto nivel Incluso se han construido analizadores sintácticos por precedencia de operadores para lenguajes completos.
> En el análisis sintáctico por precedencia de operadores, se definen tres relaciones de precedencia disjuntas, <, =; y >, entre algunos pares de terminales. Estas relaciones de precedencia guían la selección de mangos y tienen los siguientes significados:

> Relación Significado
> a < h
> a = h a > b
> a “cede la precedencia a" b
> a "tiene la misma precedencia que" b a "tiene más precedencia que" b

> Se debe prevenir al lector de que aunque estas relaciones pueden parecer similares a las relaciones aritméticas "menor que", "igual a" y "mayor que", las relaciones de precedencia tienen propiedades muy diferentes. Por ejemplo, se podría tener a < b y a > b para el mismo lenguaje, o podría no cumplirse ninguna de a < b, a = b y a > b para algunos terminales a y b.

> Hay dos maneras habituales de determinar qué relaciones de precedencia deben cumplirse entre un par de terminales. El primer método que se estudia es intuitivo y se basa en las nociones tradicionales de asociatividad y precedencia de operadores. Por ejemplo, si * tiene mayor precedencia que +, se hace -+- < * y * > +.

> El segundo método para seleccionar las relaciones de precedencia de operadores consiste en construir primero una gramática no ambigua para el lenguaje una gramática que refleje la asociatividad y precedencia correctas en sus árboles de análisis sintáctico. Para la otra fuente habitual de ambigüedad, el else ambiguo, la gramática es un modelo útil.

> Una vez obtenida una gramática no ambigua, existe un método mecánico para, a partir de ella, construir las relaciones de precedencia de operadores. Estas relaciones podrían no ser disjuntas, y podrían analizar un lenguaje distinto del generado por la gramática, pero con las clases estándar de expresiones aritméticas, se encuentran pocos problemas en la práctica.

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