Compiladores ============
Bajar: dcc.fceia.unr.edu.ar/lcc/T-521-Compiladores/Public/entrega1 && /test.tgz
Pasemos a discribir la gramática de tiger. Usaremos gramáticas líbres de contexto.
- Un conjunto finito de símbolos terminales T (Tokens).
- Un conjunto finito de símbolos no terminales NT ; T ∩ NT = ∅
- Un símbolo start ∈ NT.
- Un conjunto finito de reglas de producción.
α : secuencia de 0 o mas β_i, β_i \inc NT \union T
Gramática:
T = { ( , ) } NT = { α } start = α
Reglas de producción:
- α : e //* vacío *//
- α : ( α )
Funciona?
((())) →^1 (((α))) →^2 ((α)) →^2 (α) →^2 α(start)
T = { +, *, NRO, (, ) } NT = { expr }
start = expr
Reglas de produción:
- expr : NRO
expr + expr expr * expr ( expr )
Acá aparecen problemas:
2 + 3 + 4 NRO + NRO + NRO expr + expr + expr ----------- ----
+— expr + expr -> expr
2 + 3 + 4 NRO + NRO + NRO expr + expr + expr ---- ------------
+— expr + expr -> expr
Tenemos dos formas de reducir.
+ +
/ \ / \
+ 4 ó 2 +
/ \ / \
2 3 3 4
Asociativo:
Izquierda Derecha
Este conflicto se conoce como “problema shift-reduce” y no es grave. Se puede eliminar de vairas maneras.
a) Reescribir la grámatica agregando más NT, para forzar un shift ó un reduce. b) Agregar directivas para indicar cómo resolver las ambigüedad.
En particular usaremos: %left (asocia a izquierda) %right (asocia a derecha) %noasoc (no asociativo)
Ahora, nuestra glc es:
%left + %left *
El orden establece precedencia, de menor a mayor.
- expr : NRO | expr + expr | expr * expr | ( expr )
a = b = c == (a = (b = c))
— a == (-(-(-a)))
a < b < c –> a < b && b < c
De hecho bison tiene uan directiva
%expect n
Espere n conflictos shift-reduce, para tranquilizar al programador. Uno de estos conflictos se conoce como el dangling else, y aparece en los lenguajes derivados de ALGOL, que introdujo nocion de sentencia compuesta.
Usado en C y Pascal
sent: if ( cond ) sent sent: { sentencias } * sentencias compuestas *
Otra opcion es usar una construccion (Fortran, Ada, etc) donde una construccion se cierra por otra palabra clave:
Ej. (ada)
sent: if conf then sentencia end if
El dangling else:
en C
if (cond_1) if (cond_2) sent_1 else | sent_1 | -> a que if pertenece?
Por convención el else paretence al if mas próximo. En ADA no ocurre.
if cond_1 then if cond_2 then sent_1 else sent_2 end if end if
Hay problemas mas graves (de hecho fatales) llamados reduce-reduce. Estos aparecen cuando tenemos reglas de produccion:
α : sentencia α : sentencia
La glc para C, que aparece en un apendice del K&R tiene un conflicto reduce-reduce.
decl : id_tipo -> id_var id_var : id id_tipo : id
a) Agregar cosas para que el scanner lo diferencie. Haskell resuelve este problema diferenciando los tipos de las vars, utilizando mayusculas y minusculas respectivamente.
b) LLevar la cuenta de las definiciones concretas.
c) El algortimo del avestruz. Patear el problema y resolverlo más adelante.
LALR(n)-> Look ahead left recursive - nivel n
El formato de la especificación de la GLC es
%{ Código ML
%}
Directivas y definiciones de tokens.
%%
Reglas de prod y acciones semanticas.
%%
Más codigo ML
%token EOF %token ARRAY OF VAR FUNCTION %token LET IN END IF THEN ELSE WHILE DO FOR TO BREAK %token PTO DOSP DOSPIG COMA PCOMA IGUAL PI PD CI CD LI LD %token AMPER PIPE MENOR MENIG MATOR MAGIG DIST %token MAS MENOS POR DIV NIL
Appel por simplicidad reconoces los numeros negativos en el parser con una regla como
expr MENOS NEG
Pero hay un problema no podemos escribir el entero minimo va de -2^w a 2^w-1
Pero lo podemos arreglar así: En el scanner reconocemos el |entero mínimo| 2^32 {ABS MIN INT}
%token ABS MININT
Hasta ahora hemos tratado con tokens generados de manera única.
| entrada | token |
----------------+
| “while” | WHILE |
Ahora debemos tratar con tokes no únicos, nro, Strings, ids, etc.
%token<int> NRO %token<string> LITERAL ID
Dejamos esto y veamos las reglas de producción:
%start prog
%% prog: expr EOF expr: NRO \| MENOS ABSMININT \| PI PD * unit * \| NIL \| LITERAL \| BREAK \| L\_value * valor izquierdo * \| L\_value DOSPIG expr \| PI expr PCOMA explist PD \| expr PIPE expr \| expr AMPR expr \| expr IGUAL expr \| expr DIST expr \| \| expr DIST expr \| expr MAS expr \| \| expr DIV expr \|
%left PIPE %left AMPER %nonasoc IGUAL MENOR … DIST * comparaciones * %left MAS MENOS %left POR DIV
Y ahora tenemos el problema del uso del menos. Para indicar que el opuesto tiene mas presedencia que la resta No podemos hacer esto:
%left MAS MENOS | … |— Mismo token %right MENOS |
Para esto generamos un token trucho (nunca sera generador por el scanner) lo usamos para la asociatividad y precedencia del opuesto.
%right UMENOS
y en las reglas de produccion
expr: MENOS expr %prec UMENOS
Seguimos \| PI expr PD \| id PI args PD * llamada a función * \| IF expr THEN expr \| IF expr THEN expr ELSE \| WHILE expr DO expr \| FOR id DOSPIG expr TO expr DO expr \| LET decs IN END * let unit * \| LET desc IN expr END \| LET desc IN expr PCOMA exprlist END \| L_value CI expr CD \| id LI rec_field LD
Seguimos con los NT Usados.
exprlist : expr PCOMA explist \| expr ;
rec_fields : id IGUAL expr COMA rec_fields \| id IGUAL expr \| * nada * ;
decs : dec decs
;
dec : TYPE id IGUAL ty \| vardec \| fundec
ty: id \| LI tyfld LD \| ARRAY of id
id: ID
tyflds : tyfields COMMA tyflds
;
tyfield: id DOSP id [fn:1]
vardec: VAR id DOSPIG expr \| VAR id DOSP id DOSPIG expr
fundec: FUNCTION id PI args PD IGUAL expr \| FUNCTION id PI args PD DOSP id \| IGUAL expr
args : expr COMA args \| expr \| expr ;
L_value : id \| L_value PTO id \| L_value CI expr CD
structure tigaerabs =
struct
type symbol = string
type pos = int
datatype var = SimpleVar of symbol
| FieldVar of var *symbol
| SuscriptVar of var *exp
and
exp = VarExp of var *pos
| UnitExp of pos
| NilExp of pos
| IntExp of int *pos
| StringExp of string *pos
| CallExp of {func: symcol, args:explist}*pos
| OpExp of {left:exp, oper:oper, right:exp}*pos
| RecordExp of { fields: symbol*exp list, ytp:symbol}*pos
| SeqExpOf of explist*pos
| AssignExpOf { var:var, exp:exp}*pos
| IfExpOf { test:exp, then':exp, else':exp option }*pos
| WhileExpOf { test:exp, body: exp}*pos
Viene un problema fuera de fase: el for. Un for DEFINE implícitamente su índice (Como ada). Así que podemos hacer:
\| ForExp of { var:symbol, escapa: bool ref, lo:exp, hi: exp, body: exp}
Debemos saber si el índice es por una función definida dentro del for.
for i:=1 to 10 do ( let function f():int=i in f() + 1 end; () ) \| LetExp of { desc: des list, body: exp } * pos \| BreakExp of pos \| ArrayExp of { type: symbol, size: exp, init: exp} * pos \| and dec = FunctionDec of ( name:symbol, parms: field list, result: symbol option, body: exp} * pos ) list \| VarDec of { name: symbol, escape: bool ref, typ: symbol option, init: exp} * pos and ty = NameTy of symbol \| RecordTy of field list \| ArrayTy of symbol
and oper = PlusOp | MinusOp | TimesOp | DivideOp \| EqOp | Neqop | LtOp | LeOp \| GtOp | GeOp withtype field = { name: symbol, escape: bool ref, typ: ty }
En 1969 D.E.Knuth definió las gramáticas con atributos, es decir, GLC donde los terminales y no terminales podrían “arrastrar” valores de un cierto tipo (atributos) de uno de ellos en base a los atributos existentes.
expr = expr + expr { $$ = $1 +
Usemos esto. Declaramos los tipos de los atributos en las directivas.
%type<tigerabs.exp> prog expr %type<tigerabs.ty> ty
%type<string> id
id : ID { $1}
%type<tigerabs.var> L\_value
Y con esto rellenamos las acciones semanticas.
Necesitamos tambien la posicion para esto, declaramos en tigernlin.sm
var nlin = ref 1
En el codigo ml del parser
fun P() = !tigerlin.nlin
expr: NRO { IntExp($1, P()) } \| MENOS ABSMININT { IntExp( valOf Int.minInt, P()) } \| PI PD { UnitExp(P()) } \| NIL { NilExp(P()) } \| LITERAL { StringExp($1, P()) \| L\_value { VarExp( $1, PC ) } \| L\_value DOSPIG expr { AssignExp({ var=$1, exp=$3 }, P())}
Habrán notado que no tenamos and, or o not, en el AST. De hecho, Tiger no tiene booleanos. Tiger hace como C: Cualquier expresión entera que evalúe a cero es falase, distinto de cero true.
Así:
\| expr PIPE expr \| expr AMPER expr
a | b == if a then 1 else b a & b == if a then b else 0
\| expr PIPE expr { IfExp({test=$1, then’=IntVal(1, P()), else’=Some($3)} P()) } \| expr AMPER expr { IfExp({test=$1, then’=$3 else’=IntVal(1, P()) } P()) }
… \| expr MENOR expr { OpExp({left = $1, oper = LtOp, right= $3}, P()) } \| MENOS expr %prec UMENOS { OpExp({left = IntExp(0, P()), oper = MinusOp, right= $2}, P()) }
\| PI expr PD { $2 }
\| IF expr THEN expr { IfExp({test=$2, then’=$4, else’=NONE } P()) } \| IF expr THEN expr ELSE expr { IfExp({test=$2, then’=$4, else’=Some($6)} P()) }
Para evitar el dangling else usamos
* menor precedencia *
%nonassoc THEN %left ELSE %nonassoc DOSPIG
El main de TIGER, en tigermain tendremos
<include tigermain.ml>
Ya es claro que tener un compilador operativo implica unas cuantas operaciones (generción del parser etc) Para facilitar esto usaremos make.
<include makefile de tiger>
Tiger permite funciones anidadas. Las reglas de scope establecen que las variables definidas en las funciones y lets anidantes son visibles en las anidadas. En el caso de las funciones esto es un problema. Las variables se definen en:
- Lets, que no crean marcos de activación
let var x := let var y := let var z := 0 in z end in y end in x end //TODO: revisar
x,y,z comaprten el marco de activación.
- For, su indice tambien comparte el marco de activacion.
- Definicion de función, los argumentos crean un nuevo marco.
Una variable es escapada si se crea un nuevo marco de activación, pero es accedida desde otro.
let var x:=10
function f(y:int)=
(for i:=1 to 10 do
let function g():int x + y + i
in end)
in
x end
/* x, y, i son escapadas. */
Supongamos una función recursiva con una anidada
let function f(i:int) =
let function g():int = i
in
if i > 1 then f(i-1)
else g()
end
in f(1000);0 end
Necesitaremos (más adelante) un mecanismo para que g acceda a la última i de f. Esto se facilita si las escapadas se alojan en, memoria dentro del marco de activación de su definición.
Pero para esto, debemos delimtar las escapadas, recorriendo el AST. Ir llevando cuenta de qué variables fueron definidas y en que marcos de activación. Para esto viene comodo una tabla hash, en general las tablas se pueden implementar de dos maneras.
Ej.
let var x:=1
function f(i:int)
let var z := 2
in end
in x end
/*
{x} dentro del let mas grande
{x,i,z} dentro de la definicion de funcion.
*/
Las tablas crecen al entrar a un scope y se achican al salir de él.
- Una forma de hacer esto es la manera imperativa: Se lleva la cuenta de qué variables se han definido el último scope, y al abandonarlo se sacan esas variables. Hay que llevarla cuenta de qué variables fueron ocultadas y despues restaurarlo.
- manera funcional: Cada vez que se ingrasa a un scope se crea una nueva tabla a parir de las vigente, y se descarta al abandonar ese scope.
Nota: los compiladores se pueden clasificar en:
- Narrow: apenas tiene una porción de AST suficiente, aplica todas las etapas hasta la emisión de código. Usa mejor la memoria, la sincronización es una pesadilla
- Borad: procesa todo el AST en cada operación. Usa mal la memoria, pero es mas sencillo.
Tiger será broad, excepto en la etapa semantica, y de generción de código intermedio que será narrow.
Es conveniente definir un modulo para diccionario que oculte la implementación. Para propósitos de debug, tendrá bastante ventajas.
incluir<tigertab.sig>
Una posible implementacion es usar el modulo Hash (Standard) o, cin mosml, Polyhash (no standard).
Un poco de la implementación de las tablas hash.
insert <tigertb.sml>
structure tigertab :> tigertab =
struct
open Polyhash
type (''a, 'b) Tabla = (''a, 'b) hash_table
fun name x = x
insert <tigerescp.sml>
El cálculo de escapes se hace luego del parsing.
Basado en unos combiadores hechos por J.Hughes,
insert <tigerpp.sig>
insert <tigerpp.sml>
Terminado el cálculo de escapes viene la etapa de análisis semantico que incluye verificar el tipado del AST y que genera código intermedio. Es lo suficientemente dura como para perder la calma. El modulo debe tomar un AST con los escapes y devoler un nuevo record
{exp, ty}
- exp: código intermedio
- ty: tipo del programa
Para el momento, exp será un tipo trucho para no mezclar las dos cosas
datatype exp = SCAF (* de scafolding *)
Para ty definiremos los tipos que manejamos.
En tigertips.sml definimos
*include tigertips*
Es más,
let
type A = array of int
var a := A[10] of 0
type b = array of int
var b := B[10] of 1
end
Si a y b TIENEN distinto tipo, para poder discrinar estos dos tipos se agrega a la signatura unique
Cuantos espacios de nombres tiene Tiger? Tres Tipos de espacios:
- Espacios de nombre de tipos.
- Espacios de nombre de funciones y variables.
- Los nombres de miembros de records. (uno por cada record)
let type i = {i:int}
var i : i:= {i=1}
in
i.i
end
Debido a esto usaremos dos diccionarios: 1 (tenv) y para 2 (venv)
datatype EnvEntry =
VIntro (* int RO *) of {access: tigertrans.access, level: int}
| Var of {access: tigertrans.access, level: int}
| Fuct {ty: Tipo:, level: tigertemp.label, formals: Tipo list, extern:bool}
El módulo tigertrans es el que produce el código intermedio. Acá lo definimos.
<include tigertrans.sml>
Por supuesto, en tigertemp definimos
<include tigertemp.sig>
La implementación
<include tigertemp.sml>
Ahora sí modulo tigerseman
signature tiegersman =
sig
type venv = (string, EnvEntry) tigertab.Tabla
type tenv = (string Tipo) tigertab.Tabla
type expty (* codigo intermedio)
val tab_vars: venv
val tab_tenv: tenv
val transExp: venv * tenv * tigerabs.exp -> expty
val transDec: venv * tenv * tigerabs.dec -> (tenv*tenv)
val transTy: tenv * tigerabs.ty -> Tipo
val transProg: tigerabs.exp -> tigertrans.frag list
end
tigerty.sml?
Inicialmente tendremos
(“int”, TInteger, RW) (“string”, TString)
Durante todo el análisis semántico necesitaremos comprar los tipos. Esto no es elemental, y lo haremos con una función checkTipos, que tendrá esta pinta.
fun checkTipos t1 t2 =
case (t1, t2) of
(TInteger _, TInteger _) => true
// Tstring, Tunit => true
| TRecord(_, u1), TRecord(_, u2) => u1 = u2
| TRecord _, TNil => true
| TNil, TRecord _ => true
| TNil, TNil => false (* nil = nil *)
| TArray(_, u1), TArray(_, u2) => u1 = u2
| etc..
Lo mejor es que estas declaraciones den origen a estos tipos (asumimos que tenemos int/string).
("I", TTipo("int", SOME(TInteger RW)))
("S", TTipo("string", SOME(String)))
Dos tipos iguales
type A = B
type B = A /* Ciclo */
Por qué razón son ilegales? Los dos dependen mutuamente, y pueden dar lugar a estos tipos internos:
("A", TTipo("B", NONE))
("B", TTipo("A", NONE))
Que pasa acá
type A = int
var x := 1
type A = B
type B = A
a) Podemos tomar que sea el primer A. (Esto es legal) b) Podemos tomar el último A (Estos es ilegal)
Elegimos el segundo por el ppio de mínimo asombro.
Lo mismo podemos hacer con arreglos
type A = array of B
type B = array of A
Con los records no tenemos este problema gracias al nil. Por eso tiger pide que se detecten clicos en un batch de types, y se marquen como errores. Si esto no se hace, no ocurre nada terriblemente grave (último ejercicio del libro de appel) La razon es que no podemos construir ningun valor de ese tipo (conseguimos un tipo sin valores)
De hecho, en ML es correcto:
datatype Void = Void of Void
Como detectar ciclos en forma útil (que podemos reemplazar todos los NONE en TTipo, por SOME)?
Depende de qué dependencias tengamos entre los tipos del batch. Notemos estas dependencias de esta manera
(pred, succ)
| Construccion | Genera |
| type A = B | (B,A) |
| type A = Array of B | (B,A) |
Una vez conseguidos los pares pred/succ de batch, los ordenamos mediante un sort topológico.
tigerseman.ml (<tab_vars>)
Otro problema fuera de fase:
Si emitimos assembler y ensablador debemos linkear nuestro código con el runtime, la libc y el startup (arranca crt*.o). Este último se ocupa de disponer el escenario para la ejecución (argumentos, enviroment, señales, etc) y llama a la función main. Debemos ver como enganchar nuestro código Tiger con el startup. La manera que elegimos es:
- Un main en el runtime y desde allí llamar a una función tigermain (el ’’ está para que no haya colisión con otros símbolos Tiger)
- Embeber nuestro código tiger en una función trucha llamada _tigermain.
tigerseman.ml (<transProg>)
<tigerframe.sig>
Dos implementaciones de sort topológico.
Problema: Un conjunto A, a; ∈ A. Un conjunto de restricciones de tipo pred/succ (a_i, a_j) a_i; precede a a_j
Se busca una ssecuencia de olos a_i quee no viole estas restricciones. Normalmente esta secuencia, si existe no es única. Si hay ciclos es imposible. Una implementación (scada de Haskel)
---
Procedemos por partes:
- Introducimos el tipo de función, en EnvV. esto es necesario si queremos que la función puede ser recursiva.
Antes del examen de su body.
fun decFunc( {name, params, body, result}, nl ) (tenv, venv) =
let
val formals = map (fn x => transTy(tenv v1#2 x)) params
val tipfun => case
val name = case name of
| "_tigermain" => "tigermain"
| name => "." ^ name ^ makestring(nl) ^ "_" ^ newlabel()
- solución lambda lifting (Functional programming, de harrison)
\x.\y.\z = ( x + y + z ) (completar el ejemplo)
La ventaja de esta solucion, e que funciona y es conceptualmente sencilla. Desventajas: puede consumir mucho stack
- solución: tabla display ( Dijkstra )
Toda función construye un arreglo con todos los frames pointers de los ultimos marcos de activación de las funciones anidantes.
- Volvamos al esquema de -lifting. El sigt programa Oberon.
< Ejemplo de lambda lifting en C >
- Static link
Una mejora para el -lifting es juntar las variables escapadas en estructura y pasar sólo el puntero a esas estructuras.
La otra cosa que se puede hacer es pasar sólo un puntero, y rescatar los recorriendo los m. de a. como difernecias una lista enlazada.
Ventajas: creación muy rapida y constante. Desventaja: Acceso lineal.
La expriencia indica que SL es la mejor alternativa. Ahora hay que buscar cómo gestionar el SL en llamados a funciones.
Llamamos P_llamante y P_llamada a las profundidades de las anidantes de las funciones llamadas y llamantes.
Resp
1^er caso
P_llamante = P_llamda
f()
{
}
g()
{
}
2^do caso
P_llamante < P_llamada
Por scope, debe ser
P_llamada = P_llamante + 1
3^er caso
P_llamante > P_llamada
No hay restricciones. #
R \letfarrow SL_llamante R ← *R
P_llamante - P_llamada } veces
R ← *R
SL_llamante ← R
Este leguaje se defini para acercarse al assembler. Su diseño varía según qué optimizaciones se quieran hacer y existen lenguajes intermedios de alto, medio y bajo nivel. El lenguaje intermedio para tiger se llama Tree.
<TigerTree.sml>
Empesemos a esbozar la traducción de código intermedio. Es una etpa angosta: se tipa el programa al mismo tiempo que generamos código.
| --- exp --> |
sema | | translate
| <-- tree -- |
Se puede ver como una especie de semántica denotacional. Presenta algunos problemas en el sentido que nos faltará contexto para saber cómo deberá usarse un código Ej:
a > b
Si se usa en :
if (a > b) then ... deberá manejar un salto
ó
c: = a > b ... deberá devolver 0 ó 1
Otro problemas es empaquetar y desepmaquetar el código:
tigertrans exp Ex, Nx, Cx Number, Condition, Expr. fun seq() fun unEx()
Ahora, desempaquetaremos una sentencia
fun unNx
El tercer desempaquetador
fun unCx
Veamos cómo se pueden integrar seman y translate.
En seman:
trexp(BreakExp, nl) = { exp = SCAF, ty = TUnit }
Cambiamos esto a
trexp(BreakExp, nl) = { exp = breakExp(), ty = TUnit }
fun breakExp() =
Nx(JUMP(hd (!salida), [hd (!salida)]))
Salida es una pila de labels que se marcan dónde terminan la iteración. Son generadas y sacadas por funciones en translate.
def preForWhile() = salida := newLabel() :: (!salida) def postForWhile() = salida := tt(!salida)
Corresponde a las expresiones del tipo:
R{ m_1 = exp_1 ... m_n = exp_n}
Cosas a tener en cuenta:
- A diferencia de las estrucutras de C, tiger no pide que la posición de los miembros siga la secuencia de declaración.
Vamos a tomar la filosofía ML, que reordena (lexico-gráficamente los nombres). Así:
{c = 10, b = 9, a = 8}
| 8 | 9 | 10 |
| a | b | c |
Ademas, la ordenacion permite ver si hay nombres repetidos. Tambien permite que no se deba seguir la secuencia en la declaracion:
let type R = { next:R, i:int, j:string }
var r:R = R{ j = "hola", next = nil, i = 15 }
in 0 end
Por esto, cuando se analiza una declaracion de un record, se ordenan los nombres y se le agrega un entero que indica que orden tiene la secuencia (empezando por 0)
Al igual que los areglos, los records son dinámicos y la creacion la hacemos en el runtime, usando stdarg.h por razones obvias.
En el rutime:
#include <stdlib.h>
#include <stdarg.h>
long *makeRecord(long cts, ...)
{
long *p, *q;
va_list lst;
va_start(lst, ctos);
p = q = malloc(ctos * sizeof(long))
while(ctos--)
*q++ = va_arg(lst, long);
va_end(lst)
return p;
}Veamos el codigo intermedio para la creacion, debe evaluar las expreciones para los miembros y luego llamar a makeRecord.
insert <fun recordExp> ver foto (2013-09-16 15:31 + 2013-06-16 15:46)
El principal problema es ocuparse del STATIC LINK (SL) que va como primer argumento.
fun callExp() { Mucho codigo }
Pasemos una decisión importante:
Qué debe hacer el compilador con expresiones como estas?
2 + 3
Puede generar código para hacer esta suma en tiempo de ejcucion ó puede calcularla en tiempo de compilacición. Supongamos que elegimos esta última. Debemos tener cuidad con cosas como:
2 + x + 3
Tenemos que reconvertir, para evaluar en :
1 + 2 + x == 3 + x
Por supuesto, estos reordenamientos valen si la operación es commutativa. Podemos volver conmutativas la diferencia y el cociente, usando:
a - b = a + (- b) y a/b = a * b^-1
Esto y las leyes de distribución
a ( b + c ) == a b + a c
Nos puede permitir ir desplazando todas las conastantes y evaluarlar en compilacion.
Pero queda en cuestión de qué hacer si hay overflow.
De hecho, hay que cuidar al reordenar :
(INT_MAX - INT_MAX) + 1 /= (INT MAX - (INT_MAX + 1))
Tambien está el problema de que Tiger hace caso omiso de overflows (como C), pero ML sí los detecta. pero ML sí los detecta. Una posible solucion es, si hay overflow, el compilador no evalua, sino que genera código para el cálculo en ejecución.
Declaraciones de Variables
Ver fotos de las 2013-09-18 - 16:06
El codigo intermedio, escrito en TREE, sigue siendo un árbol, y tenemos que tranformarlo en una lista. Haremos esto usando un sistema de reescritura de términos (Term-Rewriting System). Nuestro TRS termina
Def: Un árbol que está canonizado si:
- No Tiene SEQ ni ESEQ.
- El padre de todo CALL, ó EXP ó MOVE(TEMP T, ..)
- Página 176 de Libro
Una vez canonizado el árbol (esto es convertido en una lista), se divide en BLOQUES BASICOS.
Un BB es una secuencia de instrucciones que cumple estas reglas:
- Tiene un solo LABEL, y es la primera instrucción
- Tiene un solo CJUMP ó JUMP al final
Sabemos que todas las instrucciones de un bloque basico son ejecutadas. Ademas un BB se puede cambiar de lugar sin prlboemas. Ayuda a identificar código muerto.
tigercanon.sig : basicBlocks traceSchedule
let
function f(iF:int, j:string):int =
function g(iG:int):int =
function h(iH:int):int =
( if (ih = 2) then f(10,"hola") else 0;
iF + iG + iH + size(j)
in h(iG + 1 ) end
var x := z(iF)
in g(x+1) end
function z(i:int) = 10 * i;
in f(10, "chau") end
[fn:1] El segundo id debe ser un nombre de tipo, pero no podemos saberlo, lo chequeamos mas adelante.