tema 2.2. ampliación del lenguaje y su procesador ... · traducción de expresiones booleanas en...

Procesadores de Lenguaje

Tema 2.2. Ampliación del lenguaje y su procesador: Optimización de la traducción

Ingeniería en InformáticaFacultad de Informática – Universidad Complutense de Madrid

Curso 2009-2010

ProfesorFederico Peinado

Elaboración del materialJosé Luis SierraFederico Peinado

Optimización de la traducción

� En general, optimizar un traductor es hacer que genere programas equivalentes pero más eficientes en tiempo de ejecución o consumo de memoria� Disciplina fundamental en el diseño de compiladores reales

� Hay distintos aspectos que pueden ser optimizados:� Las estrategias de traducción a seguir� El código objeto una vez generado

Procesadores de LenguajeIngeniería en Informática

� El propio código fuente

� Nosotros sólo veremos algunos casos básicos, aunque Aho et al. enseñan métodos más complejos y sistemáticos

2.2- 1

� Cuando una instrucción if-then-else no tiene bloque elsese genera siempre un código en el bloque then con un salto totalmente innecesario a la instrucción siguiente

� Ejemplo:

Traducción de instrucciones if-then-else sin bloque else

x ≡ Mem[0]...

apila-dir(0)apila(5)igual

012


� La traducción se puede optimizar generando o no el código de ese salto según el bloque else esté vacío o no

2.2- 2

if x = 5 then x := x + 1;

igualir-f(9)apila-dir(0)apila(1)sumadesapila-dir(0)ir-a(9)

23456789

� En nuestras ecuaciones semánticas de la gramática de atributos esta optimización queda así:

Ampliación de la propuesta: if-then-else sin bloque else

...

IIf ::= if Exp then I PElse

IIf.cod = Exp.cod || ir-f( PElse.etqi ) || I.cod ||

PElse.cod

Exp.etqh = IIf.etqh

I.etqh = Exp.etq + 1

Procesadores de LenguajeIngeniería en Informática 2.2- 3

I.etqh = Exp.etq + 1

PElse.etqh = I.etq

IIf.etq = PElse.etq

PElse ::= else I

PElse.cod = ir-a(I.etq) || I.cod

I.etqh = PElse.etqi = PElse.etqh + 1

PElse.etq = I.etq

PElse ::= λPElse.cod = λλλλPElse.etq = PElse.etqi = PElse.etqh

� Y en los esquemas de traducción optimizados queda así:


global cod, etq;...IIf::= { var etqaux}

if Exp then{emite(ir - f( ?));


{emite(ir - f( ?));etqaux ← etq;etq ← etq + 1}

IPElse( out etqi){parchea(etqaux, etqi)}


global cod, etq;...PElse( out etqi)::= { var etqaux}

else{emite(ir-a( ?));

etqaux ← etq;

Continuación…


etqaux ← etq;etq ← etq + 1;etqi ← etq}

I{parchea(etqaux, etq)}

PElse( out etqi)::= λ{etqi ← etq}

� Es habitual traducir las expresiones booleanas para que se calcule solamente el valor de aquellos operandos imprescindibles para conocer el resultado de la expresión

� Usamos las mismas ideas de las sentencias condicionales

� Esquema de E0 and E1

� Si E0 es falso, todo vale falso; y si no, vale lo que valga E1

Traducción de expresiones booleanas en circuito corto


E1.etq + 1

2.2- 6

Traducción de Eo

ir-f

Traducción de E1

ir-a

apila(0)

E0.etq

E1.etq + 2

E1.etq

� Esquema de E0 or E1

� Si E0 no es falso, todo vale lo que valga E0 (verdadero); y si no, vale lo que valga E1


Traducción de Eo

copia Eo.etq


ir-v

desapila

Traducción de E1

E1.etq

Eo.etq + 1

* copia duplica la cima de la pila (lo copia otra vez apilándolo encima)* ir-v realiza el salto si hay verdad en la cima de la pila (lo contrario de ir-f)* desapila descarta la cima de la pila

� copia

� ir-v( i)


Pila [CPila + 1] ← Pila[CPila]CPila ← CPila + 1CProg ← CProg + 1

si Pila[CPila] ≠≠≠≠ 0CProg ← i


� desapila

2.2- 8

CProg ← isi no CProg ← CProg + 1fsiCPila ← CPila - 1

CPila ← CPila - 1CProg ← CProg + 1

� Ejemplo:


� Ejemplo:0123456789

apila-dir(0)apila-dir(1)igualir-f(8) apila-dir(1)apila-dir(2)igualir-a(9)apila(0)copia

x ≡ Mem[0]y ≡ Mem[1]z ≡ Mem[2]u ≡ Mem[3]v ≡ Mem[4]w ≡ Mem[5]r ≡ Mem[6]...


(x=y) and (y=z) or (u=v) and (w = r)

9101112131415161718192021

copiair-v(21)desapilaapila-dir(3)apila-dir(4)igualir-f(20)apila-dir(5)apila-dir(6)igualir-a(21)apila(0)

� Para facilitar esta generación de código optimizado es conveniente modificar la gramática incontextual para discriminar explícitamente los operadores lógicos del resto� Añadiendo un par de producciones para los operadores:

Ampliación de la propuesta: Expresiones booleanas en circuito corto

...ExpS ::= ExpS or Term...Term ::= Term and Fact


� Eliminando los operadores de las otras producciones:

2.2- 10

Term ::= Term and Fact

...OpAd ::= + | - | or...OpMul ::= * | / | div | mod | and

� De esa forma podemos definir las partes correspondientes a la traducción optimizada en la gramática de atributos:

Ampliación de la propuesta: Expresiones booleanas en circuito corto

...ExpS ::= ExpS or Term

ExpSo.cod = ExpS 1.cod || copia || ir-v(Term.etq) ||desapila || Term.cod

ExpS1.etqh = ExpS o.etqhTerm.etqh = Exps 1.etq + 3


Term.etqh = Exps 1.etq + 3ExpSo.etq = Term.etq

...Term ::= Term and Fact

Termo.cod = Term 1.cod || ir-f(Fact.etq + 1) ||Fact.cod || ir-a(Fact.etq + 2) || apila(0)

Term1.etqh = Term o.etqhFact.etqh = Term 1.etq + 1Termo.etq = Fact.etq + 2

� La optimización propuesta para la traducción de las expresiones booleanas produce saltos consecutivos ineficientes al anidar operadores lógicos

� Ejemplo:

Optimización de la evaluación en circuito corto

x ≡ Mem[0]...

apila-dir(0)apila(5)igualcopia

0123


(x=5) or (x > 6) or (x < -1)

copiair-v(9)desapilaapila-dir(0)apila(6)mayorcopiair-v(15)desapilaapila-dir( 0)apila(-1)menor

3456789

101112131415

� La traducción se puede optimizar , por segunda vez, haciendo que los saltos lleguen al final del anidamiento(que sean “saltos completos”)

� Ejemplo:


x ≡ Mem[0]...

apila-dir(0)apila(5)igualcopia

0123


(x=5) or (x > 6) or (x < -1)

copiair-v(15)desapilaapila-dir(0)apila(6)mayorcopiair-v(15)desapilaapila-dir( 0)apila(-1)menor

3456789

101112131415

� La idea ahora es fijar siempre las etiquetas de los saltos condicionales desde las estructuras de nivel superior� Los saltos ir-f / ir-v serán completos: tendrán como dirección

de destino el valor de un atributo heredado etqfh / etqvhque indica el final del anidamiento de operadores and / or


Eo and E1

Traducción de Eo Traducción de Eo

Eo or E1


Traducción de Eo

ir-f

Traducción de E1

copia

desapila

Traducción de Eo

ir-v

Traducción de E1

etqvh

copia

desapila

etqfh

� Así se expresan los valores de etqfh y etqvh en las ecuaciones semánticas de las expresiones y de cualquier otra estructura que utilice expresiones :

Ampliación de la propuesta: Optimización del circuito corto

...IWhile::= while Exp do I

Exp. etqfh = Exp . etqvh = Exp.etq...Iif:: if Exp then I PElse


Iif:: if Exp then I PElseExp. etqfh = Exp . etqvh = Exp.etq

...

Exp ::= ExpS OpComp ExpSExpS0.etqfh = ExpS 0.etqvh = ExpS 0.etq ExpS1.etqfh = ExpS 1.etqvh = ExpS 1.etq

...


...Exp ::= ExpS

ExpS.etqfh = Exp.etqfhExpS.etqvh = Exp.etqvh

ExpS ::= ExpS OpAd TermExpS1.etqfh = ExpS 1.etqvh = ExpS 1.etq Term.etqfh = Term.etqvh = Term.etq

ExpS ::= TermTerm.etqfh = ExpS.etqfhTerm.etqvh = ExpS.etqvh

Continuación…


Term.etqvh = ExpS.etqvhTerm ::= Term OpMul Fact

Term1.etqfh = Term 1.etqvh = Term 1.etqFact.etqfh = Fact.etqvh = Fact.etq

Term ::= FactFact.etqfh = Term.etqfhFact.etqvh = Term.etqvh

Fact ::= not FactFact 1.etqfh = Fact 1.etqvh = Fact 1.etq

Fact ::= ( Exp )Exp.etqfh = Fact.etqfhExp.etqvh = Fact.etqvh

...


...ExpS ::= ExpS or Term

ExpS0.cod = ExpS 1.cod || copia || ir-v( ExpS0.etqvh ) || desapila || Term.cod

ExpS1.etqfh = ExpS 1.etq + 2Term.etqfh = Term.etqExpS1.etqvh = ExpS 0.etqvh

Continuación…


1 0

Term.etqvh = ExpS 0.etqvhTerm ::= Term and Fact

Term0.cod = Term 1.cod || copia || ir-f( Term0.etqfh ) || desapila || Fact.cod

Term1.etqfh = Term 0.etqfhFact.etqfh = Term 0.etqfhTerm1.etqvh = Term 1.etq + 2Fact.etqvh = Fact.etq

� La anterior gramática de atributos no es l-atribuida : ¡hay muchas categorías sintácticas que heredan de sí mismas!� Por ejemplo: Exp.etqfh = Exp.etqvh = Exp.etq

� Esto es un problema que requiere volver a utilizar la idea del parcheo (ahora en la propia gramática de atributos), parcheando muchos saltos, todos con el mismo destino

� Para ello añadimos dos atributos sintetizados que



� Para ello añadimos dos atributos sintetizados que almacenan listas de instrucciones pendientes de parchear� Los saltos ir-f con valor indefinido se guardarán en listaf

� Los saltos ir-v con valor indefinido se guardarán en listav

� Y también añadimos una función semántica parchea que realiza el parcheo “masivo” de las dos listas de instrucciones, dada la dirección de destino que hay que usar en las instrucciones de salto de cada una de ellas� parchea (cod , listaf , listav , etqf , etqv )

2.2- 18

� Así quedan las ecuaciones semánticas de la traducción:


...IWhile::= while Exp do I

IWhile.cod = parchea(Exp.cod, Exp.listaf, Exp.listav, Exp.etq, Exp.etq) ||

ir-f(I.etq + 1) || I.cod || ir-a(IWhile.etqh)

...


...IIf:: if Exp then I PElse

IIf.cod = parchea(Exp.cod, Exp.listaf, Exp.listav,Exp.etq, Exp.etq) ||

ir-f(PElse.etqi) || I.cod || PElse.cod

...


... Exp ::= ExpS OpComp ExpS

Exp.cod = parchea(ExpS 0.cod, ExpS 0.listaf, ExpS 0.listav,ExpS0.etq, ExpS 0.etq) ||

parchea(ExpS 1.cod, ExpS 1.listaf, ExpS 1.listav,ExpS1.etq, ExpS 1.etq) || OpComp.op

Exp.listaf = Exp.listav = []Exp ::= ExpS

Exp.listaf = ExpS.listafExp.listav = ExpS.listav

Continuación…


Exp.listav = ExpS.listavExpS ::= ExpS OpAd Term

ExpS0.cod = parchea(ExpS 1.cod,ExpS 1.listaf,ExpS 1.listav,ExpS1.etq,ExpS 1.etq) ||

parchea(Term.cod,Term.listaf,Term.listav,Term.etq,Term.etq) ||

OpAd.opExpS0.listaf = ExpS 0.listav = []

ExpS ::= TermExpS.listaf = Term.listafExpS.listav = Term.listav

...


... Term ::= Term OpMul Fact

Termo.cod = parchea(Term1.cod, Term1.listaf, Term1.listav,Term1.etq, Term1.etq) ||

parchea(Fact.cod, Fact.listaf, Fact.listav,Fact.etq, Fact.etq) || OpMul.op

Termo.listaf = Termo.listav = []Term ::= Fact

Term.listaf = Fact.listafTerm.listav = Fact.listav

Fact ::= not Fact

Continuación…


Fact ::= not FactFact 0.cod = parchea(Fact 1.cod, Fact 1.listaf, Fact 1.listav,

Fact 1.etq, Fact 1.etq)Fact 0.listaf = Facto.listav = []

Fact ::= idenFact.listaf = Fact.listav = []

Fact ::= númeroFact.listaf = Fact.listav = []

Fact ::= ( Exp )Fact.listaf = Exp.listafFact.listav = Exp.listav

...


... ExpS ::= ExpS or Term

ExpS0.cod = parchea(ExpS 1.cod, ExpS 1.listaf, [], ExpS1.etq + 2, ?) ||

copia || ir-v(?) || desapila ||parchea(Term.cod, Term.listaf, [], Term.etq, ?)

ExpS0.listav = ExpS 1.listav ++ Term.listav ++ [ ExpS1.etq + 1 ]ExpS0.listaf = []

Term ::= Term and Fact

Continuación…


Term ::= Term and FactTerm0.cod = parchea(Term 1.cod, [], Term 1.listav,

?, Term 1.etq + 2) ||copia || ir-f(?) || desapila ||parchea(Fact.cod, [], Fact.listav, ?, Fact.etq)

Term0.listf = Term 1.listaf ++ Fact.listaf ++ [ Term1.etq + 1 ]Term0.listav = []

* [ ] y ? se usan en parchea cuando realmente sólo interesa parchear una lista

* ++ es la concatenación de listas

� En los esquemas de traducción optimizados queda así:


global cod, etq;...IWhile ::= { var etqaux1, etqaux2}

while{etqaux1 ← etq} Expdo


do{ parchea(Exp.listav,Exp.listaf,etq,etq);

emite(ir-f( ?));etqaux2 ← etq;etq ← etq + 1}

I{emite(ir-a(etqaux1));

etq ← etq + 1;parchea(etqaux2,etq)}

* parchea(lv, lf, ev, ef) realiza parcheo masivo de lv con ev y de lf con ef


global cod, etq;...ExpS( in listavh0, listafh0; out listav0, listaf0) ::=

{ var etqaux} ExpS( in listavh1, listafh1; out listav1, listaf1){parchea([], listaf1, ?, etq + 2)}or

Continuación…


or{emite(copia);

emite(ir-v(?));emite(desapila);etqaux ← etq + 1; etqaux ← etq + 3;}

Term( in listavh2, listafh2; out listav2, listaf2){parchea([], listaf2, ?, etq);

listav0 = listav1 ++ listav2 ++ [etqaux];listaf0 = [];}

...

� Aunque la tarea del traductor no es interpretar el código fuente, precalcular el valor de las expresiones constantes será una excepción que realizaremos para optimizar el código fuente

� Esta optimización puede hacerse de varias formas

� Realizando dos pasadas

1. Transformando el código fuente

2. Traduciendo el código fuente transformado

� Realizando una pasada de transformación y traducción

Traducción con precálculo de expresiones constantes


� Realizando una pasada de transformación y traducción

� El código fuente se transforma según se traduce (se complica un poco el proceso, pero será nuestro enfoque )

� Realizando una pasada y trabajando sobre una representación intermedia del programa

� A partir del código fuente se genera una representación intermedia del programa (= árbol de sintaxis abstracta)

� Se transforma la representación intermedia del programa

� Se genera código a partir de la representación intermedia del programa transformada

2.2- 25

� Reglas de optimización� Una expresión constante se ve reemplazada por su valor

� true y false son expresiones constantes de valor cierto y falso

� Número es expresión constante de valor valor(Número.lex)

� Cualquier operación Op sobre expresiones constantes X e Y es expresión constante de valor opera(valor(X), valor(Y))

� La asignación de una expresión constante X a una variable Id añade Id.lex a una tabla de variables constantes varscte (formada por pares lexema-valor) con el valor asociado valor(X)

Traducción con precálculo de expresiones constantes


pares lexema-valor) con el valor asociado valor(X)

� La asignación de una expresión no constante a una variable Idelimina Id de la tabla de variables constantes varscte

� Una variable Id de la tabla de variables constantes varscte es expresión constante de valor varscte.valor(Id.lex)

� Una instrucción if-then-else con expresión constante como condición es equivalente a su bloque then si la condición vale cierto , y a su bloque else si vale falso

� Una instrucción while-do con expresión constante como condición es equivalente a λλλλ

� Etc.

2.2- 26

Ampliación de la propuesta: Precálculo de expresiones constantes

Prog ::= Decs & IsProg.cod = Decs.cod ++ "&" ++ Is.codIs.varscteh = []Prog.varscte = Is.varscte

Decs ::= Decs ; DecDecso.cod = Decs1.cod ++ ";" ++ Dec.cod

Decs ::= Dec


Decs ::= DecDecs.cod = Dec.cod

Dec ::= Tipo idenDec.cod = Tipo.cod ++ " " ++ iden.lex

Tipo ::= boolTipo.cod = "bool"

Tipo ::= intTipo.cod = "int"


Is ::= Is ; I Iso.cod = si I.cod ≠ λ

Is1.cod ++ ";" ++ I.codsi no Is1.cod

Is1.varscteh = Iso.varscteh I.varscteh = Is1.varscteIso.varscte = I.varscte

Is ::= I

Continuación…


Is ::= IIs.cod = I.codI.varscteh = Is.varsctehIs.varscte = I.varscte

I ::= IAsigI.cod = IAsig.codIAsig.varscteh = I.varsctehI.varscte = IAsig.varscte

I ::= IIfI.cod = IIf.codIIf.varscteh = IIf.varsctehIIf.varscte = IIf.varscte


I ::= IWhileI.cod = IIIf.codIWhile.varscteh = IWhile.varsctehIWhile.varscte = IWhile.varscte

I ::= ICompI.cod = IComp.codIComp.varscteh = I.varsctehI.varscte = IComp.varscte

Continuación…


I.varscte = IComp.varscteIComp ::= begin IsOpc end

IComp.cod = "begin "++IsOpc.cod++" end"IsOpc.varscteh = IComp.varsctehIComp.varscte = IsOps.varscte

IsOpc ::= λIsOpc.cod = λIsOpc.varscte = IsOpc.varscteh

IsOpc ::= IsIsOpc.cod = Is.codIs.varscteh = IsOpc.varsctehIsOpc.varscte = Is.varscte


IAsig ::= iden := ExpIAsig.cod = iden.lex ++ ":=" ++ si Exp.cte entonces Exp.val

si no Exp.codIAsig.varscte = si Exp.cte entonces

añade(IAsig.varscteh,<iden.lex,Exp.val>)si no elimina(IAsig.varscteh,iden.lex)

Exp.varscteh = IAsig.varscte

Continuación…


Exp.varscteh = IAsig.varscteIIf ::= if Exp then I PElse

IIF.cod = si Exp.cte si Exp.val entonces I.cod si no PElse.cod

si no "if "++Exp.cod++ " then "++I.cod++PElse.cod IIF.varscte = si Exp.cte

si Exp.val entonces I.varscte si no PElse.varscte

si no I.varscte ∩ PElse.varscteI.varscteh = IIf.varscteh

PElse.varscteh = IIf.varscteh


PElse ::= else IPElse.cod = " else" ++ I.codI.varscteh = PElse.varscteh

PElse.varscte = I.varsctePElse ::= λλλλ

Continuación…


PElse ::= λλλλPElse.cod = λλλλPElse.varscte = PElse.varscteh

IWhile ::= while Exp do IIWHile.cod = si Exp.cte ∧∧∧∧ ¬¬¬¬Exp.val entonces λλλλ

si no "while "++Exp.cod++" do "++I.codI.varscteh = Exp.varscteh = [] IWhile.varscte = si Exp.cte ∧∧∧∧ Exp.val entonces

IWhile.varsctehsi no I.varscte


Exp ::= ExpS OpComp ExpSExp.cod = (si ExpSo.cte entonces ExpSo.val

si no ExpSo.cod) ++ OpComp.cod ++(si ExpS1.cte entonces ExpS1.val

si no ExpS1.cod)Exp.cte = ExpSo.cte ∧ ExpS1.cte

Continuación…


Exp.cte = ExpSo.cte ∧ ExpS1.cteExp.val = eval(OpComp.cod,ExpSo.val, ExpS1.val)ExpSo.varscteh = ExpS1.varscteh = Exp.varscteh

Exp ::= ExpSExp.cod = ExpS.codExp.cte = ExpS.cteExp.val = ExpS.valExpS.varscteh = Exp.varscteh


ExpS ::= ExpS OpAd TermExpSo.cod = (si ExpS1.cte entonces ExpS1.val

si no ExpS1.cod) ++ OpAd.cod ++(si Term.cte entonces Term.val

si no Term.cod)ExpSo.cte = ExpS1.cte ∧ Term.cte

Continuación…


ExpSo.cte = ExpS1.cte ∧ Term.cteExpSo.val = eval(OpAd.cod,ExpS1.val,Term.val)ExpS1.varscteh = Term.varscteh = ExpSo.varscteh

Exp ::= ExpSExp.cod = ExpS.codExp.cte = ExpS.cteExp.val = ExpS.valExpS.varscteh = Exp.varscteh


Term ::= Term OpMul FactTermo.cod = (si Term1.cte entonces Term1.val

si no Term1.cod) ++ OpMul.cod ++(si Fact.cte entonces Fact.val

si no Fact.cod)Termo.cte = Term1.cte ∧ Fact.cte

Continuación…


Termo.cte = Term1.cte ∧ Fact.cteTermo.val = eval(OpMul.cod,Term1.val,Fact.val)Term1.varscteh = Fact.varscteh = Termo.varscteh

Term ::= FactTerm.cod = Fact.codTerm.cte = Fact.cteTerm.val = Fact.valFact.varscteh = Term.varscteh


Fact ::= not FactFacto.cod = "not " ++ (si Fact1.cte entonces “pendi ente"

si no Fact1.cod)Facto.cte = Fact1.cteFacto.val = eval("not",Fact1.val)Fact1.varscteh = Facto.varscteh

Fact ::= ( Exp )

Continuación…


Fact ::= ( Exp )Fact.cod = "("++ (si Exp.cte entonces Exp.val

si no Exp.cod) ++ ")"Fact.cte = Exp.cteFact.val = Exp.valExp.varscteh = Fact.varscteh

Fact ::= num Fact.cte = trueFact.val = toNum(num.lex)Fact.cod = “pendiente 2"


ExpS ::= ExpS or TermExpSo.cod =

si ExpS1.cte ∧ ExpS1.val entonces "true"si no si ExpS1.cte ∧ ¬Term.cte entonces Term.codsi no si ExpS1.cte ∧ Term.val entonces "true"

∧ ¬

Continuación…


si no si ExpS1.cte Term.val entonces "true"si no si ExpS1.cte ∧ ¬Term.val entonces "false"si no si Term.cte ∧ Term.val entonces "true"si no si Term.cte entonces ExpS1.codsi no ExpS1.cod ++ " and "++Term.cod

ExpSo.cte = (ExpS1.cte ∧ ExpS1.val) ∨(Term.cte ∧ Term.val) ∨ExpS1.cte ∧ Term.cte

ExpS1.varscteh = Term.varscteh = ExpSo.varscteh


Term ::= Term and FactTermo.cod =

si Term1.cte ∧ ¬Term1.val entonces "false"si no si Term1.cte ∧ ¬Fact.cte entonces Fact.codsi no si Term1.cte ∧ ¬Fact.val entonces "false"

∧

Continuación…


si no si Term1.cte Fact.val entonces "false"si no si Term1.cte ∧ Fact.val entonces "true"si no si Fact.cte ∧ ¬Fact.val entonces "false"si no si Fact.cte entonces ExpS1.codsi no Term1.cod ++ " and "++Fact.cod

Termo.cte = (Term1.cte ∧ ¬ Term1.val) ∨(Fact.cte ∧ ¬ Fact.val) ∨Term1.cte ∧ Fact.cte

Term1.varscteh = Fact.varscteh = Termo.varscteh


Fact ::= iden Fact.cte = <iden,_> ∈ Fact.varsctehFact.val = valorDe(iden.lex, Fact.varscteh)Fact.cod = iden.lex

Fact ::= true

Continuación…


Fact ::= trueFact.cte = trueFact.val = trueFact.cod = true

Fact ::= falseFact.cte = trueFact.val = falseFact.cod = “pendiente 3"


fun eval(op,v1,v2)si v1 = '?' ∨ v2 = '?' entonces '?'si no si op = '+' entonces v1+v2

si no si op = '*' entonces v1*v2....

ffun

Continuación…


ffun

fun eval(op, v)si v = '?' entonces '?'si no si op = 'not'

si v=0 entonces 1si no entonces 0

...ffun

� A veces el código objeto generado contiene grupos de instrucciones inútiles o ineficientes que pueden eliminarseo sustituirse por otros (= hacer optimización peephole )

� Existen situaciones triviales de tratar y otras más complejas

� Ejemplos:

Traducción con sustitución de grupos de instrucciones

apila - dir(1)ir - a(...) ir-a(...)

...


apila - dir(1)desapila-dir(1) λ

ir-a( k)I

(si k está fuera del grupo I y no hay ningúnsalto al grupo I en todo el programa)

ir-a( k)

ir - a(...)...ir-a(...)....

I

...ir-a(...)....

I

apila(1)multiplica

λ

Críticas, dudas, sugerencias…


Federico Peinadowww.federicopeinado.es

tema 2.2. ampliación del lenguaje y su procesador ... · traducción de expresiones booleanas en...

Documents