Examenes2005 08

Examen de Compiladores: Junio 2004
David Fernández-Amorós compila@ii.uned.es

(2pt). Dada la gramática, A → aAa | , construya una tabla de análisis sintáctico descendente.
En primer lugar vamos a calcular los conjuntos PRIMERO y SIGUIENTE:
PRIMERO(A)= {a, }
SIGUIENTE(A)= {a,$}
La tabla de análisis sintáctico sería la siguiente:

NO
TERMINAL
A

SÍMBOLO DE ENTRADA
a
A
A

→
→

$
aAa

A→

¿Es LL(1)?No, porque tiene dos entradas para M(A,a), puesto que A → aAa pertenece a la entrada
porque a ∈ PRIMERO(A) y A → también está en la entrada porque a ∈ SIGUIENTE(A).
Además la gramática incumple la tercera propiedad de las gramáticas LL(1), ya que hay
una producción que deriva la cadena vacía (trivialmente, A → ) y la otra (A → aAa) tiene
derivaciones que comienzan con a, que es un terminal deSIGUIENTE(A).
Quizá sea conveniente resaltar que, a pesar de una opinión más generalizada de lo que
debería, esta gramática no es ambigua.
Analice la cadena de entrada aaaa y comente los problemas que encuentre.

PILA
$A

ENTRADA
aaaa Error

ACCIÓN

Cuadro 1: Análisis de la cadena de entrada aaaa
Se produce un error porque hay más de una entrada en la tabla. No se puede continuar
con el análisisporque no tenemos mecanismos de resolución de conflictos.
(6pt). Dada la siguiente gramática de operadores que genera expresiones lógicas,
E → E ∧ E | E ∨ E | ¬ E | E ⇔ E | id

1

Examen de Compiladores: Junio 2004
David Fernández-Amorós compila@ii.uned.es

cuya precedencia de operadores es, de menor a mayor; ⇔, ∨, ∧, ¬: Construya la tabla de
precedencia de operadores, suponiendo que los operadores ∧,∨ y ⇔ son asociativos por la
izquierda y el operador ¬ asociativo por la derecha.
¬
∧
∨ ⇔
¬ <·
·> ·> ·>
∧ <·
·> ·> ·>
∨ <· <·
·> ·>
⇔ <· <· <·
·>
id ·> ·> ·> ·>
$ <· <· <· <·

id
<·
<·
<·
<·

$
·>
·>
·>
·>
·>

<·

Figura 1: Tabla de precedencia de operadores
Analice la cadena de entrada a ∨ b ∧ ¬ c mediante el algoritmo de análisis sintáctico por
precedencia de operadores. Dibuje el árbol dederivación.
Lo primero que debemos considerar es que después del análisis léxico, los tokens que
pasarían al analizador sintáctico serían:
id ∨ id ∧ ¬id
El análisis en cuestión puede verse en el cuadro 2. El árbol de derivación está en la figura 2

PILA
$
$<·id1
$E
$E<·∨
$E<· ∨ <·id2
$E < <· ∨ E
$E<· ∨ E<·∧
$E<· ∨ E<· ∧ <·¬
$E<· ∨ E<· ∧ <·¬<·id3
$E<· ∨ E<· ∧ <·¬<·E
$E<· ∨ E<· ∧ E
$E<· ∨ E
$E

ENTRADAid1 ∨ id2 ∧ ¬id3 $
∨id2 ∧ ¬id3 $
∨id2 ∧ ¬id3 $
id2 ∧ ¬id3 $
∧¬id3 $
∧¬id3 $
¬id3 $
id3 $
$
$
$
$
$

ACCIÓN
desplazar
reducir por E → id
desplazar
desplazar
reducir por E → id
desplazar
desplazar
desplazar
reducir por E → id
reducir por E → ¬E
reducir por E → E ∧ E
reducir por E → E ∨ E
aceptar

Cuadro 2: Análisis sintáctico
2

Examen de Compiladores: Junio 2004
David Fernández-Amoróscompila@ii.uned.es

}}
}}
}
}
}}

E
id

E ee
∨
E
id

ee
ee
ee







Eb

bb
bb
bb
b

∧
¬

ÑÑ
ÑÑ
Ñ
Ñ
ÑÑ

Ea

aa
aa
aa
a

E
id

Figura 2: Árbol de derivación
(2pt). Sea la gramática de atributos del cuadro , en la que tenemos un atributo heredado (h) y
otro sintetizado (s).
PRODUCCIÓN
REGLAS SEMÁNTICAS
S → E1 *E2
E1 .h := 2*S.h; E2 .h := S.h; S.s := E1 .s * E2 .s; print(S.s)
print(E.h); E.s := num.val;E → num

Cuadro 3: Gramática de atributos
Coloque las acciones semánticas en el lugar adecuado para cada producción.
El esquema de traducción adecuado puede verse en el cuadro 4.
¿Qué se imprime para el caso de S.h = 1 y la entrada 3*4?
En la figura 3 podemos ver en líneas de puntos el árbol sintáctico. En trazo fijo se pueden
observar las dependencias entre los atributos. Siguiendo el ordenvisitaprof, se visitarían los
nodos según el orden que se muestra en los círculos. Algunos nodos se visitan dos veces,
una para cada atributo. Los nodos cuyo número de orden lleva un asterisco ejecutarían la
acción semántica de imprimir el valor del atributo correspondiente. Así, en el caso que nos
ocupa lo que se imprimiría sería: 2 1 12.
¿Se podría realizar la evaluación de ambos atributos en una...