Download Presentación de PowerPoint

Compiladores e intérpretes
Generación de código intermedio II
Profesor: Eridan Otto
Generación de código intermedio II
• Uso de notación polaca
• En parser desendente recursivo
Compiladores e intérpretes
Generación de código intermedio II:Uso de notación polaca
–
–
El código se genera cuando se encuentra el operador
Ejemplo:
Pila
$
$S
$SA
$SAB
$SABC
$SAT1
$ST2
$
Entrada
SABC*+:=$
ABC*+:=$
BC*+:=$
C*+:=$
*+:=$
+:=$
:=$
$
Godigo Generado
(*,B,C,T1)
(+,A,T1,T2)
(:=,T2, ,S)
(end,, ,)
Compiladores e intérpretes
Generación de código intermedio II:En parser desendente recursivo
–
–
–
–
–
Se pueden utilizar las rutinas de las analizadores sintácticos desendentes para ir
creando Arboles de Sintaxis Abstracta (ASA), a partir del código. Recordar un
no terminal es un procedimiento.
Supongamos que se genera con el análisis un arbol binario con tres campos por
nodo:
– Info, información del nodo
– Izda, puntero al subarbol izquierdo
– Dcha, puntero al subárbol derecho
Se pueden definir las funciones:
– CreaNodo: crea nodo del árbol
– CreaHoja :crea hoja del árbol
Se añade un parámetro a cada procedimiento que genera el árbol, el cual
contiene la referencia al árbol hasta el momento
Una vez el árbol terminado, sepuede recorrer y generar grafos dirigidos para
optimizar las expresiones matemáticas
Compiladores e intérpretes
Generación de código intermedio II:En parser desendente recursivo
–
–
Ejemplo, código para producción E::= identificador:=E’
Regla semántica CreaHoja(‘identificador’,id.puntero):=E’.nodo
Funcion E(VAR arbol:arbol)
c:=GetToken
IF c=‘identificador’ THEN
BEGIN
nodo:= CreaHoja(‘identificador’,token.puntero(c))
c:= GetToken
if c= ‘:=‘ THEN
BEGIN
arbol:=CreaNodo(‘:=‘,arbol,NIL)
E’(nodo.dcha(arbol))
ELSE
error()
ELSE
error()
END
Compiladores e intérpretes
Generación de código intermedio II:En parser desendente recursivo
–
–
Definición dirigida por sintaxis para construir un ASA de una gramática para
expresiones matemáticas.
Por ejemplo, al analizar a-4+2+c se genera el siguiente árbol de sintáxis
abstracta:
En líneas punteadas aparece el arbol sintáctico con nodos etiquetados E y T usando
atributo sintetizado .nodo, como puntero a un nodo del árbol ASA
Para las producciones T::=id y T::=num, hay un puntero a una hoja identificador o
valor numérico
Compiladores e intérpretes
Generación de código intermedio II:En parser desendente recursivo
–
Ejemplo: a-4+2+c
E.nodo
E.nodo
E.nodo
T.nodo
id
-
T.nodo
+ +
+
+
T.nodo
T.nodo
id
num 2
id
num
id
Entrada
id c
4
+
Entrada
id a
Ejemplo: a-4+2+c, ASA
+
a
c
2
4
Compiladores e intérpretes
Generación de código intermedio II:En parser desendente recursivo
–
Ejercicio: derivar de a+a*(b-c)+(b-c)*d su ASA y optimizar
+
*
+
a
-
*
a
c
b
c
b
-optimizando, generando
Un grafo dirigico acíclico
d
+
*
+
*
a
d
b
c
Compiladores e intérpretes
Generación de código intermedio II:Generación de cuartetos
–
Asignación y expresiones matemáticas con cuartetos
Compiladores e intérpretes
Generación de código intermedio II:Generación de cuartetos
–
Asignación y expresiones matemáticas con cuartetos, Ejercicio, derivar los
cuartetos a partir de la sintaxis para a:= b*c+d
S
id
:=
E.codigo=(*,b,c,t1) (+,t1,d,t2) (:=,t2,a,)
E.valor=t2
E.codigo=(*,b,c,t1) (+,t1,d,t2)
E
E.valor=t1
E.codigo=(*,b,c,t1)
E
+
E.valor=b
E.codigo=‘’ E
*
E E.valor=c
E.codigo=‘’
id
id
E
E.valor=d
E.codigo=‘’
id
Compiladores e intérpretes
Generación de código intermedio II:Generación de cuartetos
–
Asignación y expresiones booleanas.
– Para el código intermedio se supondrá valor 0 representa a falso y valor 1
reprenta a verdadero.
– Representación de una expresión booleana para los operadores lógicos, con
el flujo de control del código intermedio. Por ejemplo, dadas las
expresiones E1 or E2 ,si se determina que E1 es verdadera, la expresión
completa es verdadera, sin nececitar evaluar E2 . And al contrario requiere
de E1 fala para ser toda la expesión falsa. Agregando a las definiciones de
asignación:
Compiladores e intérpretes
Generación de código intermedio II:Generación de cuartetos
–
Asignación y expresiones booleanas.
Eo:=E1 ‘and’ E2
Eo:=id1 relop id2
relop := < | > | <= |>= |= | <>
Eo.true:=newlabel
Eo.false:=newlabel
Eo.sale:=newlabel
Eo.valor:=newtemp
Eo.codigo:=
Gen(relop, id1 , id2, Eo.true)
Gen(GOTO, ,, Eo.false)
Gen(LABEL, , Eo.true)
Gen(:=, 1 , , Eo.valor)
Gen(GOTO, ,, Eo.sale)
Gen(LABEL, , Eo.false)
Gen(:=, 0 , , Eo.valor)
Gen(LABEL, , Eo.sale)
Compiladores e intérpretes
Generación de código intermedio II:Generación de cuartetos
–
–
Ejercicio, genere código intermedio para: a>b or c<d
Sentencias de control de flujo , las expresiones booleanas se definieron en el
contexto de su utilidad para las definiciones condicionales y de ciclo
– Ejercicio:Escriba las reglas semánticas para IF E THEN S, de manera de
generar los cuartetos correspondientes
Compiladores e intérpretes
Generación de código intermedio II:Generación de cuartetos
–
Sentencia de repetición
– Escriba las reglas semánticas para REPEAT S UNTIL E,
de manera de generar los cuartetos correspondientes