<commit_before>Compiladores 
============

Bajar: dcc.fceia.unr.edu.ar/lcc/T-521-Compiladores/Public/entrega1 && /test.tgz

* [2013-08-21 Wed]

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 \cap NT = \emptyset
- Un símbolo start \in NT.
- Un conjunto finito de reglas de producción.

  \alpha : secuencia de 0 o mas \beta_i, \beta_i \inc NT \union T

**** Ejemplo 1: Una gramatica que balancee paréntesis.

Gramática:

  T = { ( , ) }
  NT = { \alpha }
  start = \alpha

Reglas de producción:

- \alpha : e //* vacío *//
- \alpha : ( \alpha ) 


Funciona? 

((())) \rightarrow^1 (((\alpha))) \rightarrow^2 ((\alpha)) \rightarrow^2 (\alpha) \rightarrow^2 \alpha(start)


**** Ejemplo 2: Una calculadora.

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.

#+BEGIN_EXAMPLE

       +             +              
      / \           / \     
     +   4    ó    2   +    
    / \               / \       
   2   3             3   4       


Asociativo: 
Izquierda           Derecha

#+END_EXAMPLE


**** Shift Reduce
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. 


#+BEGIN_EXAMPLE
- expr : NRO 
  | expr + expr
  | expr * expr
  | ( expr )   

#+END_EXAMPLE


**** Cuándo usamos %right en C?

a = b = c == (a = (b = c))

--- a == (-(-(-a)))

**** Operaciones no asociativas en C?

a < b < c --> a < b && b < c

**** No asociativo 

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:

  \alpha : sentencia
  \alpha : 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

*** Gramáticas libres de contexto.
    
*** Gramatica de tiger

%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
       
       
* [2013-08-22 Tue]

** Los constructores de AST

#+BEGIN_SRC ocaml

   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

#+END_SRC
                  
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 }


** Acciones semanticas y atributos de terminal y no terminales.

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 + $3; } \leftarrow  
    $$     $1     $3

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



* [2013-08-26 Mon]
  
** Empecemos a unir los pedazos.

El main de TIGER, en tigermain tendremos

#+BEGIN_SRC ocaml

<include tigermain.ml>

#+END_SRC

Ya es claro que tener un compilador operativo implica unas cuantas operaciones (generción del parser etc) 
Para facilitar esto usaremos make.


#+BEGIN_SRC makefile

<include makefile de tiger>

#+END_SRC


** Variables escapadas

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

#+BEGIN_SRC tiger
  let var x := let var y := let var z := 0 in z end in y end in x end //TODO: revisar 
#+END_SRC
  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.

#+BEGIN_SRC tiger

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. */

#+END_SRC

Supongamos una función recursiva con una anidada

#+BEGIN_SRC tiger 

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

#+END_SRC
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.

#+BEGIN_SRC 
  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.
*/
#+END_SRC 
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.

#+BEGIN_SRC 

incluir<tigertab.sig>  

#+END_SRC

Una posible implementacion es usar el modulo Hash (Standard) o, cin mosml, Polyhash (no standard).


* [2013-08-28 Wed]

** Tablas y cálculo de escapes.

Un poco de la implementación de las tablas hash.

#+BEGIN_SRC ocaml 

insert <tigertb.sml>

structure tigertab :> tigertab =
struct
  open Polyhash
  type (''a, 'b) Tabla = (''a, 'b) hash_table

  fun name x = x

#+END_SRC

#+BEGIN_SRC ocaml 

insert <tigerescp.sml>

#+END_SRC  

El cálculo de escapes se hace luego del parsing. 


** Pretty-printing: está para ver el AST.

Basado en unos combiadores hechos por J.Hughes, 

#+BEGIN_SRC ocaml

insert <tigerpp.sig>

insert <tigerpp.sml>

#+END_SRC



* [2013-08-29 Thu]

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 ttomar 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

#+BEGIN_SRC ml

*include tigertips*

#+END_SRC

Es más, 

#+BEGIN_SRC m

let 
  type A = array of int
  var a := A[10] of 0
  type b = array of int
  var b := B[10] of 1
end

#+END_SRC

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:

1) Espacios de nombre de tipos.
2) Espacios de nombre de funciones y variables.
3) Los nombres de miembros de records. (uno por cada record)

#+BEGIN_SRC 
 let type i = {i:int}
     var i : i:= {i=1}
 in
     i.i
 end
#+END_SRC

Debido a esto usaremos dos diccionarios: *1* (tenv) y para *2* (venv)

#+BEGIN_SRC ml

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} 

#+END_SRC

El módulo tigertrans es el que produce el código intermedio. Acá lo definimos.

#+BEGIN_SRC ml

<include tigertrans.sml>

#+END_SRC

Por supuesto, en tigertemp definimos

#+BEGIN_SRC ml

<include tigertemp.sig>

#+END_SRC

La implementación

#+BEGIN_SRC 

<include tigertemp.sml>

#+END_SRC

Ahora sí modulo tigerseman 

#+BEGIN_SRC ml

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

#+END_SRC


* [2013-09-02 Mon]

** Volvamos a los tipos internos de Tiger.

#+BEGIN_SRC 

tigerty.sml?

#+END_SRC

** Asuntos a tener en cuenta.

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.

#+BEGIN_SRC ml

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..                                       

#+END_SRC 

Lo mejor es que estas declaraciones den origen a estos tipos (asumimos que tenemos int/string).

#+BEGIN_EXAMPLE
("I", TTipo("int", SOME(TInteger RW)))
("S", TTipo("string", SOME(String)))
#+END_EXAMPLE

Dos tipos iguales

#+BEGIN_SRC tiger

type A = B
type B = A /* Ciclo */

#+END_SRC

Por qué razón son ilegales? Los dos dependen mutuamente, y pueden dar lugar a estos tipos internos:

#+BEGIN_EXAMPLE
("A", TTipo("B", NONE))
("B", TTipo("A", NONE))
#+END_EXAMPLE

Que pasa acá

#+BEGIN_SRC tiger

type A = int
var x := 1
type A = B
type B = A

#+END_SRC

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

#+BEGIN_SRC tiger

type A = array of B
type B = array of A

#+END_SRC

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:

#+BEGIN_SRC ml

datatype Void = Void of Void

#+END_SRC

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

#+BEGIN_EXAMPLE
   (pred, succ)
#+END_EXAMPLE


| 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.

#+BEGIN_SRC ml

tigerseman.ml (<tab_vars>)

#+END_SRC

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.

#+BEGIN_SRC ml

tigerseman.ml (<transProg>)

#+END_SRC




* [2013-09-05 Thu]

** Seguimos con el frame estático.

#+BEGIN_SRC ml

<tigerframe.sig>

#+END_SRC

Dos implementaciones de sort topológico.

Problema: Un conjunto A, a; \in 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)

#+BEGIN_SRC ml

---

#+END_SRC

* Footnotes

[fn:1] El segundo id debe ser un nombre de tipo, pero no podemos saberlo, lo chequeamos mas adelante.<commit_msg>- Notes update<commit_after>Compiladores 
============

Bajar: dcc.fceia.unr.edu.ar/lcc/T-521-Compiladores/Public/entrega1 && /test.tgz

* [2013-08-21 Wed]

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 \cap NT = \emptyset
- Un símbolo start \in NT.
- Un conjunto finito de reglas de producción.

  \alpha : secuencia de 0 o mas \beta_i, \beta_i \inc NT \union T

**** Ejemplo 1: Una gramatica que balancee paréntesis.

Gramática:

  T = { ( , ) }
  NT = { \alpha }
  start = \alpha

Reglas de producción:

- \alpha : e //* vacío *//
- \alpha : ( \alpha ) 


Funciona? 

((())) \rightarrow^1 (((\alpha))) \rightarrow^2 ((\alpha)) \rightarrow^2 (\alpha) \rightarrow^2 \alpha(start)


**** Ejemplo 2: Una calculadora.

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.

#+BEGIN_EXAMPLE

       +             +              
      / \           / \     
     +   4    ó    2   +    
    / \               / \       
   2   3             3   4       


Asociativo: 
Izquierda           Derecha

#+END_EXAMPLE


**** Shift Reduce
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. 


#+BEGIN_EXAMPLE
- expr : NRO 
  | expr + expr
  | expr * expr
  | ( expr )   

#+END_EXAMPLE


**** Cuándo usamos %right en C?

a = b = c == (a = (b = c))

--- a == (-(-(-a)))

**** Operaciones no asociativas en C?

a < b < c --> a < b && b < c

**** No asociativo 

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:

  \alpha : sentencia
  \alpha : 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

*** Gramáticas libres de contexto.
    
*** Gramatica de tiger

%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
       
       
* [2013-08-22 Tue]

** Los constructores de AST

#+BEGIN_SRC ocaml

   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

#+END_SRC
                  
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 }


** Acciones semanticas y atributos de terminal y no terminales.

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 + $3; } \leftarrow  
    $$     $1     $3

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



* [2013-08-26 Mon]
  
** Empecemos a unir los pedazos.

El main de TIGER, en tigermain tendremos

#+BEGIN_SRC ocaml

<include tigermain.ml>

#+END_SRC

Ya es claro que tener un compilador operativo implica unas cuantas operaciones (generción del parser etc) 
Para facilitar esto usaremos make.


#+BEGIN_SRC makefile

<include makefile de tiger>

#+END_SRC


** Variables escapadas

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

#+BEGIN_SRC tiger
  let var x := let var y := let var z := 0 in z end in y end in x end //TODO: revisar 
#+END_SRC
  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.

#+BEGIN_SRC tiger

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. */

#+END_SRC

Supongamos una función recursiva con una anidada

#+BEGIN_SRC tiger 

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

#+END_SRC
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.

#+BEGIN_SRC 
  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.
*/
#+END_SRC 
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.

#+BEGIN_SRC 

incluir<tigertab.sig>  

#+END_SRC

Una posible implementacion es usar el modulo Hash (Standard) o, cin mosml, Polyhash (no standard).


* [2013-08-28 Wed]

** Tablas y cálculo de escapes.

Un poco de la implementación de las tablas hash.

#+BEGIN_SRC ocaml 

insert <tigertb.sml>

structure tigertab :> tigertab =
struct
  open Polyhash
  type (''a, 'b) Tabla = (''a, 'b) hash_table

  fun name x = x

#+END_SRC

#+BEGIN_SRC ocaml 

insert <tigerescp.sml>

#+END_SRC  

El cálculo de escapes se hace luego del parsing. 


** Pretty-printing: está para ver el AST.

Basado en unos combiadores hechos por J.Hughes, 

#+BEGIN_SRC ocaml

insert <tigerpp.sig>

insert <tigerpp.sml>

#+END_SRC



* [2013-08-29 Thu]

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 ttomar 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

#+BEGIN_SRC ml

*include tigertips*

#+END_SRC

Es más, 

#+BEGIN_SRC m

let 
  type A = array of int
  var a := A[10] of 0
  type b = array of int
  var b := B[10] of 1
end

#+END_SRC

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:

1) Espacios de nombre de tipos.
2) Espacios de nombre de funciones y variables.
3) Los nombres de miembros de records. (uno por cada record)

#+BEGIN_SRC 
 let type i = {i:int}
     var i : i:= {i=1}
 in
     i.i
 end
#+END_SRC

Debido a esto usaremos dos diccionarios: *1* (tenv) y para *2* (venv)

#+BEGIN_SRC ml

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} 

#+END_SRC

El módulo tigertrans es el que produce el código intermedio. Acá lo definimos.

#+BEGIN_SRC ml

<include tigertrans.sml>

#+END_SRC

Por supuesto, en tigertemp definimos

#+BEGIN_SRC ml

<include tigertemp.sig>

#+END_SRC

La implementación

#+BEGIN_SRC 

<include tigertemp.sml>

#+END_SRC

Ahora sí modulo tigerseman 

#+BEGIN_SRC ml

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

#+END_SRC


* [2013-09-02 Mon]

** Volvamos a los tipos internos de Tiger.

#+BEGIN_SRC 

tigerty.sml?

#+END_SRC

** Asuntos a tener en cuenta.

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.

#+BEGIN_SRC ml

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..                                       

#+END_SRC 

Lo mejor es que estas declaraciones den origen a estos tipos (asumimos que tenemos int/string).

#+BEGIN_EXAMPLE
("I", TTipo("int", SOME(TInteger RW)))
("S", TTipo("string", SOME(String)))
#+END_EXAMPLE

Dos tipos iguales

#+BEGIN_SRC tiger

type A = B
type B = A /* Ciclo */

#+END_SRC

Por qué razón son ilegales? Los dos dependen mutuamente, y pueden dar lugar a estos tipos internos:

#+BEGIN_EXAMPLE
("A", TTipo("B", NONE))
("B", TTipo("A", NONE))
#+END_EXAMPLE

Que pasa acá

#+BEGIN_SRC tiger

type A = int
var x := 1
type A = B
type B = A

#+END_SRC

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

#+BEGIN_SRC tiger

type A = array of B
type B = array of A

#+END_SRC

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:

#+BEGIN_SRC ml

datatype Void = Void of Void

#+END_SRC

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

#+BEGIN_EXAMPLE
   (pred, succ)
#+END_EXAMPLE


| 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.

#+BEGIN_SRC ml

tigerseman.ml (<tab_vars>)

#+END_SRC

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.

#+BEGIN_SRC ml

tigerseman.ml (<transProg>)

#+END_SRC




* [2013-09-05 Thu]

** Seguimos con el frame estático.

#+BEGIN_SRC ml

<tigerframe.sig>

#+END_SRC

Dos implementaciones de sort topológico.

Problema: Un conjunto A, a; \in 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)

#+BEGIN_SRC ml

---

#+END_SRC


* [2013-09-09 Mon]

** Vemos cómo tipar funciones

Procedemos por partes:

1) 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. 

#+BEGIN_SRC 

fun decFunc( {name, params, body, result}, nl ) (tenv, venv) = 
 let 
    val formals = map (fn x => transTy(tenv v1#2 x)) params
    val tipfun => case
#+END_SRC

#+BEGIN_SRC 

  val name = case name of 
       | "_tigermain" => "tigermain"
       | name => "." ^ name ^ makestring(nl) ^ "_" ^ newlabel() 

#+END_SRC


** Tenemos est problema: Como acceder desde un marco de activacion a otro marco de activacion.

1) solución lambda lifting (Functional programming, de harrison)

#+BEGIN_EXAMPLE 
  
  \x.\y.\z = ( x + y + z )
 (completar el ejemplo)

#+END_EXAMPLE

La ventaja de esta solucion, e que funciona y es conceptualmente sencilla.
Desventajas: puede consumir mucho stack

2) 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. 

3)  Volvamos al esquema de \-lifting. El sigt programa Oberon.

#+BEGIN_EXAMPLE

< Ejemplo de lambda lifting en C >

#+END_EXAMPLE

3) 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

#+BEGIN_EXAMPLE

f() 
{

}

g() 
{

}

#+END_EXAMPLE

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 \leftarrow *R

P_llamante - P_llamada } veces

R \leftarrow *R

SL_llamante \leftarrow R  

** Lenguaje intermedio (IL o IR representacion)

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.

#+BEGIN_SRC ml

<TigerTree.sml>

#+END_SRC


* Footnotes

[fn:1] El segundo id debe ser un nombre de tipo, pero no podemos saberlo, lo chequeamos mas adelante.
{'fraction_non_alphanumeric': 0.08653010275728329, 'fraction_numerical': 0.008091300180549673, 'mean_word_length': 2.460126484652167, 'pattern_counts': {'":': 0, '<': 52, '<?xml version=': 0, '>': 86, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4567514', 'n_tokens_mistral': 16549, 'n_tokens_neox': 15644, 'n_words': 6031}