Lenguajes y Compiladores Análisis Sintáctico Parte...

Universidad Nacional San Luis GonzagaFacultad de Ing. De Sistemas

Universidad Nacional San Luis GonzagaFacultad de Ing. De Sistemas

Lenguajes y Compiladores

Análisis Sintáctico

Parte II

Teoría Lenguajes

1

Parte II

Análisis AscendenteAnálisis Ascendente

� El análisis ascendente es conocido como análisis por desplazamiento y reducción.

� Intenta construir el árbol sintáctico comenzando por las hojas y avanzando hacia la raíz.

� Se puede considerar este proceso como una

Teoría Lenguajes 2

� Se puede considerar este proceso como una reducción de la cadena de entrada al símbolo inicial.

� Existen los siguientes métodos:� Sintáctico LR y sus variantes

� Sintáctico por Precedencia de operadores

� Para la gramática:

S → aABe

A → Abc bB → d

La frase abbcde se puede reducir a S:


Teoría Lenguajes 3

La frase abbcde se puede reducir a S:

abbcde

aAbcde

aAde

aABe

S

� Se usaron las siguientes producciones:

A → bA → Abc

B → dS → aABe


Teoría Lenguajes 4

S → aABeEstas reducciones trazan la siguiente derivación por la

derecha en orden inverso:

S → aABe → aAde → aAbcde → abbcde

DefiniciónDefinición

� Si S →* αAw → αβw →* xw es a rightmost derivation (derivación más a la derecha)

Se dice que αAw, αβw y xw son formas sentenciales derecha.

• La forma sentencial derecha αβw puede ser reducida

Teoría Lenguajes 5

• La forma sentencial derecha αβw puede ser reducidacon la producción A → β a la forma sentencial αAw.

• La subcadena β es “a handle” de αβw (mango o mando de αβw).

• El análisis ascendente está basado en el uso del mango para encontrar la reducción a realizar

EjemploEjemplo

� Para la gramática S → Ac Bd

A → aAb ab

B → aBbb abb

� Para la forma sentencial aabbbbd el único mango es

Teoría Lenguajes 6

� Para la forma sentencial aabbbbd el único mango es abb ya que usando B → abb, podemos reducirla a aBbbd que es una forma sentencial derecha. Observe que ab es el lado derecho de la producción A → abpero ab no es mango de aabbbbd ya que de aplicar

A → ab se tendría aAbbbd que no es una forma sentencial derecha.

Ejemplo de reconocimientoEjemplo de reconocimiento

� Para la gramática( 1 ) E → E + E

( 2 ) E → E * E

( 3 ) E → (E)

( 4 ) E → id

Teoría Lenguajes 7

( 4 ) E → id

� Considere la cadena de entrada id + id * id

� Se muestra los pasos realizados por el analizador por desplazamiento y reducción.

� Note que siempre a la derecha del mango sólo hay símbolos terminales

Ejemplo de reconocimientoEjemplo de reconocimiento

Forma sentencial derecha

Mango Producción dereducción

id + id * id id E → id

E + id * id id E → id

E + E * id id E → id

Teoría Lenguajes 8

E + E * id id E → id

E + E * E E * E E → E * E

E + E E + E E → E + E

E

Análisis Ascendente por desplazamiento y reducción (AADR)Análisis Ascendente por desplazamiento y reducción (AADR)

� Hay que resolver dos problemas:� Determinar el mango

� Escoger la producción para la reducción caso exista más de una.

� Para el análisis ascendente por desplazamiento y

Teoría Lenguajes 9

� Para el análisis ascendente por desplazamiento y reducción se usa una pila para guardar los símbolos gramaticales, un buffer de entrada para la cadena a analizar.

� El símbolo $ sirve para marcar el fondo de la pila y el final de la cadena de entrada.

Pila Entrada Acción

1. $ id + id * id$ desplazar

2. $id + id * id$ reducir por E → id

3. $E + id * id$ desplazar

4. $E + id * id$ desplazar

5. $E + id * id$ reducir por E → id

AADRAADR

Teoría Lenguajes 10

5. $E + id * id$ reducir por E → id

6. $E + E * id$ desplazar

7. $E + E * id$ desplazar

8. $E + E * id $ reducir por E → id

9. $E + E * E $ reducir por E → E * E

10. $E + E $ reducir por E → E + E

11. $E $ aceptar

� Aunque las acciones básicas realizadas por el AADR son el desplazamiento y la reducción, en realidad existen cuatro acciones:

• Desplazar: el símbolo de la entrada se empila, se toma otro símbolo de entrada

• Reducir: Desempila el tope y empila el lado

AADRAADR


• Reducir: Desempila el tope y empila el lado izquierdo de la producción que se está reduciendo

• Aceptar: fin del análisis sintáctico con éxito ($ en la entrada y $S en el tope de la pila)

• Error: hay un error de sintaxis y se llama a la rutina de recuperación de errores

� Para usar el método de desplazamiento y reducción es necesario que la gramática no sea ambigua.

� EjemploProp → if Expr then Prop

if Expr then Prop else Prop

AADRAADR


if Expr then Prop else Prop

otro

� Si tenemos:Pila: ... if Expr then Prop

Entrada: else ...$

� Si no es posible escoger de manera única la producción para la reducción esa gramática no es LR(1).

� Ejemplo:1 prop → id ( lista-param)

AADRAADR


1 prop → id ( lista-param)

2 prop → exp := exp

3 lista-param → lista-param, paramparam4 param → id

5 exp → id ( lista-exp) id

6 lista-exp → lista-exp, exp exp

AADRAADR

� Si tenemos:Pila: ... id1(id

Entrada: ,id) ...$

� ¿Cuál es la reducción a aplicar?

� Si id1 es un nombre de procedimiento entonces


� Si id1 es un nombre de procedimiento entonces usaremos la producción 4, si id1 es un arreglo usaremos la producción 5.

� Una solución es que el léxico determine si el token es un nombre de procedimiento para lo cual tendría que consultar la tabla de símbolos pero ayudaría al sintáctico.

Análisis Sintáctico LRAnálisis Sintáctico LR

Programa para

a + b $

Salida

Entrada

Pila


Programa paraParser LR

Acción$

Z

Y

XSalidaPila

ir-a

Análisis Sintáctico LRAnálisis Sintáctico LR

� El analizador LR consta de:

� Una entrada

� Una pila

� Un programa conductor


Un programa conductor

� Una tabla de análisis sintáctico dividida en dos partes:

»Acción: indica la acción del analizador.

»Ir - a: indica las transiciones entre estados.

Codificación de la tabla LRCodificación de la tabla LR

� Acción� di indica desplazar, empilar la entrada y el estado i

� rj indica reducir por la producción número j


� acep indica aceptar

� un blanco indica error de sintaxis

� Ir-a� Indica el estado a empilar junto a un no terminal

Uso de la tabla LRUso de la tabla LR

� Normalmente se usa la sección Acción de la tabla para realizar un desplazamiento o una reducción� Desplazamiento: empilar entrada y estado indicado

� Cuando se reduce se usa la sección Ir-a de la tabla:� Desempilar hasta encontrar, en la pila, el símbolo más a


� Desempilar hasta encontrar, en la pila, el símbolo más a la izquierda de la producción usada

� Accesar la tabla con la combinación

(tope expuesto, lado izquierdo de la producción usada)

en la sección Ir-a y empilar el lado izquierdo de la producción y el estado hallado en la tabla

Ejemplo de Análisis Sintáctico LREjemplo de Análisis Sintáctico LR

� Para la gramática( 1 ) E → E + T

( 2 ) E → T

( 3) T → T * F

( 4) T → F


( 4) T → F

( 5 ) F → (E)

( 6 ) F → id

� Analizar la frase id + id * id

Ejemplo de Tabla LREjemplo de Tabla LR

Acción ir-aEstado

id + * ( ) $ E T F

0 d5 d4 1 2 31 d6 acep2 r2 d7 r2 r23 r4 r4 r4 r44 d5 d4 8 2 3


4 d5 d4 8 2 35 r6 r6 r6 r66 d5 d4 9 37 d5 d4 108 d6 d119 r1 d7 r1 r110 r3 r3 r3 r3

11 r5 r5 r5 r5

Ejemplo de análisis LREjemplo de análisis LR


(1) 0 id * id + id $ desplazar(2) 0 id 5 * id + id $ reducir por F → id(3) 0 F 3 * id + id $ reducir por T → F


(3) 0 F 3 * id + id $ reducir por T → F(4) 0 T 2 * id + id $ desplazar(5) 0 T 2* 7 id + id $ desplazar(6) 0 T 2* 7 id 5 + id $ reducir por F → id(7) 0 T 2* 7 F 10 + id $ reducir por T → T * F



(8) 0 T 2 + id $ reducir por E → T(9) 0 E 1 + id $ desplazar(10) 0 E 1 + 6 id $ desplazar(11) 0 E 1 + 6 id 5 $ reducir por F → id


(11) 0 E 1 + 6 id 5 $ reducir por F → id(12) 0 E 1 + 6 F 3 $ reducir por T → F(13) 0 E 1 + 6 T 9 $ E → E + T(14) 0 E 1 $ aceptar


� Pasos del analizador:� Se comienza con 0 en la pila e id en la entrada

Accion[0,id] = d5: empilar id y 5

� Acción [5,+] = r6: se usará la producción F → id para reducir,


reducir,

desempilar hasta encontrar id

el tope expuesto es 0 y el no terminal del lado izquierdo de la producción es F

Ir-a [0,F] = 3

empilar F y 3

Gramática de operadoresGramática de operadores

� Son gramáticas que cumplen:

� Ningún lado derecho de la producción es ε� No tiene dos no terminales adyacentes

� Las gramáticas de operadores permiten la construcción manual de analizadores por


construcción manual de analizadores por desplazamiento y reducción

� Estas gramáticas permiten implementar el análisis sintáctico por precedencia de operadores.

� Tiene restricciones que hace que su uso sea limitado para un tipo especial de gramáticas.

Ejemplos de gramáticas de operadoresEjemplos de gramáticas de operadores

� La siguiente gramática

E → EAE (E) -E idA → + - * / ↑↑↑↑No es una gramática de operadores, pero se puede


No es una gramática de operadores, pero se puede transformar fácilmente a

E → E + EE - EE * EE / EE ↑↑↑↑ E (E) -E id

Que sí es una gramática de operadores y permite aplicar el método de precedencia de operadores.

Análisis Sintáctico por Precedencia de Operadores (ASPO)Análisis Sintáctico por Precedencia de Operadores (ASPO)

� Se deben definir tres relaciones de precedencia

disjuntas <. , >. e =. entre algunos pares de terminales.

� Estas reglas de precedencia guían la selección de mangos con el siguiente significado


mangos con el siguiente significado

Relación Significado

a <. b a cede precedencia a b

a =. b a tiene la misma precedencia que b

a .> b a tiene más precedencia que b

ASPOASPO

� Para determinar la precedencia de operadores se puede:� Hacer un estudio intuitivo basado en el concepto de precedencia de operadores y determinar por ejemplo

que + <. *. Esto resolverá las ambigüedades de la


que + <. *. Esto resolverá las ambigüedades de la última gramática propuesta.

� Construir una gramática no ambigua que refleje la precedencia de operadores como la gramática usada en el ejemplo de análisis LR.

� Ejemplo de análisis por precedencia de operadores

� Relación de precedencia de operadores

id + * $

id .> .> .>

ASPOASPO


.> .> .>+ <. .> <. .>* <. .> .> .>$ <. <. <.

� Dada la frase: id + id * id

� Se insertan las precedencias considerando que la frase comienza y termina con $.

� Para insertar la precedencia entre dos terminales se busca el operador de precedencia en la matriz . Para

ASPOASPO


busca el operador de precedencia en la matriz . Para el primer caso caso se busca entre la fila de $ y la

columna de id (resulta <. ).� La cadena con las relaciones de precedencia

resultante es: $ <. id >. + <. id >. * <. id >. $

� Para encontrar el mango se usa el siguiente algoritmo:

� Buscar desde el extremo izquierdo el primer .>

� Luego buscar hacia atrás el primer <. Saltando los =.

ASPOASPO


� Luego buscar hacia atrás el primer <. Saltando los =.

� El mango es todo lo que está entre <. y .>� Para la frase mostrada el primer mango sería id

entonces se reduce a E obteniendo la forma sentencial E + id * id. Luego de reducir todos los id se obtiene E + E * E.

� Eliminando los no terminales se tiene: $+*$

� Insertando las relaciones de precedencia se

obtiene: $ <. + <. * .>$� El mango es E * E que se reduce a E.

<. .>

ASPOASPO


� Quedando $+$ ($E + E$) o $ <. +.> $ � El proceso se repite hasta tener $$ en la frase (sin

considerar los no terminales).

� En una implementación no es necesario:

� Insertar las precedencias en la frase

� Examinar toda la frase para determinar el mango.

� Se debe usar una pila para guardar los elementos de la entrada ya examinados.

ASPOASPO


de la entrada ya examinados.

� Se usa la matriz de precedencia de operadores para determinar el mango

Algoritmo para ASPOAlgoritmo para ASPO

� Si se cumple <. o =. entre el tope de la pila y el elemento de la entrada se realiza un desplazamiento (empilar entrada y avanza la entrada).

� Si se cumple .> ya se encontró el mango y hay que

reducir (desempilar hasta encontrar la relación <.)


reducir (desempilar hasta encontrar la relación <.)� Si no cumple ninguna relación de precedencia se ha

detectado un error de sintaxis.

Algoritmo para ASPOAlgoritmo para ASPO

repetirsi Tope(Pila) <. Entrada o Tope(Pila) =. Entrada entonces Empilar(Entrada, Pila)

Lexico(Entrada)sino si Tope(Pila) >. Entrada

entonces repetir


Desempilar(X, Pila)hasta Tope(Pila) <. Xfrepetir

fsifsi

hasta Tope(Pila) = $ y Entrada = $frepetir

Lenguajes y Compiladores Análisis Sintáctico Parte...

Documents

Transcript of Lenguajes y Compiladores Análisis Sintáctico Parte...