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

> La intención de las relaciones de precedencia es delimitar el mango de una forma de frase derecha, con < marcando el extremo izquierdo, = apareciendo en el interior del mango y > marcando el extremo derecho. Para mayor precisión, supóngase que se tiene una forma de frase derecha de una gramática de operadores. El hecho de que no aparezcan no terminales adyacentes en los lados derechos de las producciones supone que tampoco ninguna forma de frase derecha tendrá dos no terminales adyacentes.

> Por tanto, se puede escribir la forma de frase derecha como β0a1 β1 . . , an βn, en donde cada βi es o ε (la cadena vacía) o un solo no terminal, y cada ai es un solo terminal.

> Supóngase que entre ai y ai+1 se cumple exactamente una de las relaciones <, =, o >. Además, úsese $ para marcar cada extremo de la cadena y defínanse $ < b y b > $ para todos los terminales b. Ahora supóngase que se eliminan los no terminales de la cadena y se coloca la relación correcta <, = o >, entre cada par de terminales y entre los terminales de los extremos y los símbolos $ que marcan los finales de la cadena. Por ejemplo, supóngase que inicialmente se tiene la forma de frase derecha id + id * id y que las relaciones de precedencia son las de la figura 4.3, Estas relaciones son algunas de las que se podrían escoger para analizar según la gramática.

> Entonces, la cadena con las relaciones de precedencia insertadas es:

> $ < id > + < id > * < id > $

> Por ejemplo, se inserta < entre el $ de la izquierda e id puesto que < es la entrada en la fila $ y la columna id.
> Se puede encontrar el mango mediante el siguiente proceso:
> L. Examínese la cadena desde el extremo izquierdo hasta encontrar el primer >. Esto ocurre entre el primer id y +.
> Después, examínese hacia atrás (a la izquierda) saltando sobre los = hasta en contrar un <. Se examina hacia atrás hasta el símbolo $.

> El mango contiene todo lo que esté a la izquierda del primer > y a la derecha del < encontrado en el paso 2, incluidos los no terminales intermedios o que rodeen a < y >. (Es necesaria la inclusión de los no terminales que rodean para que no aparezcan dos no terminales adyacentes en una forma de frase derecha.). El mango es el primer id.

> En la gramática, entonces se reduce id a E, Llegados a este punto, se tiene la forma de frase derecha E+ id*id. Después de reducir los restantes id a E con los mismos pasos, se obtiene la forma de frase derecha E+ E*E. Considérese ahora la cadena $ + *$ obtenida eliminando los no terminales. Si se insertan las relaciones de precedencia, se obtiene $ < + <*>$que índica que el extremo izquierdo del mango se encuentra entre + y * y que el extremo derecho se encuentra entre * y $. Estas relaciones de precedencia indican que, en la forma de frase derecha E+E*E. el mango es E*E.

> Obsérvese cómo las E que rodean al * se convierten en parte del mango.

> Como los no terminales no influyen en el análisis sintáctico, no hay que preocuparse por diferenciarlos entre sí. Se puede guardar un solo marcador "no terminal" en la pila de un analizador sintáctico por desplazamiento y reducción para indicar las posiciones para los valores de los atributos.

> Por la exposición anterior podría parecer que se debe examinar toda la forma de frase derecha en cada paso para encontrar el mango. Este no es el caso si se usa una pila para almacenar los símbolos de entrada que ya han aparecido y si se utilizan las relaciones de precedencia para guiar las acciones de un analizador sintáctico. Sí se cumplen las relaciones de precedencia < o = entre el símbolo terminal más a la cima de la pila y el siguiente símbolo de entrada, el analizador sintáctico hace un desplazamiento; todavía no ha encontrado el extremo derecho del mango. Si se cumple la relación >, es necesaria una reducción. En este punto, el analizador ya ha encontrado el extremo derecho del mango y se pueden utilizar las relaciones de precedencia para encontrar el extremo izquierdo del mango en la pila.

> Si no se cumple ninguna relación de precedencia entre un par de terminales, entonces es que se ha detectado un error sintáctico y debe invocarse una rutina de recuperación del error, como se estudiará más adelante en esta sección. Las ideas anteriores pueden formalizarse mediante el siguiente algoritmo.

> Algoritmo 4.5. Algoritmo de análisis sintáctico por precedencia de operadores. Entrada. Una cadena de entrada w y una tabla de relaciones de precedencia.

> Salida. Si w está bien formada, resulta una estructura de árbol de análisis sintáctico, con un no terminal de posición E que etiqueta todos los nodos interiores; de lo contrario, resulta una indicación de error.

> Método, inicialmente, la pila contiene $. y el buffer de entrada, la cadena w$. Para hacer el análisis sintáctico, se ejecuta el programa de la figura 4.24.

> (1) apuntar ae al primer símbolo de w$;
> (2) repeat forever
> (3) if $ está en la cima de la pila y ae apunta a $ then
> (4) return
> else begin
> (5) sea a el símbolo terminal más a la cima de la pila y
> sea b el símbolo apuntado por ae;
> (6) if a < b o a = b then begin
> (7) meter b en la pila;
> (8) avanzar ae al siguiente símbolo de entrada;
> end;
> (9) else if a > b then /* reduce */
> (10) repeat
> (11) extraer el elemento de la cima de la pila
> (12) until el terminal de la cima de la pila esté relacionado por <
> con el terminal más recientemente extraído de la pila.
> (13) else error ()
> 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