Monday, May 16, 2005

Intermediate Trees

Well, I have Intermediate Tree (IT) output from my tiger compiler. I received some help with the IT generation, but the text output is just not readable. So, what I did was generated a graphical representation using graphviz.

The most difficult thing about IT generation is following static links. I am going to show you the tree and the code that generates it.


/* define a recursive function */
let

/* calculate n! */
function nfactor(n: int): int =
if n = 0
then 1
else n * nfactor(n-1)

in
nfactor(10)
end


and here is the tree

The tree on the right shows the main code

Can you guess what tree the following code will generate

let

type any = {any : int}
var buffer := getchar()

function readint(any: any) : int =
let var i := 0
function isdigit(s : string) : int =
ord(buffer)>=ord("0") &
ord(buffer)<=ord("9")
function skipto() =
while buffer=" " | buffer="\n"
do buffer := getchar()
in skipto();
any.any := isdigit(buffer);
while isdigit(buffer)
do (i := i*10+ord(buffer)-ord("0");
buffer := getchar());
i
end

type list = {first: int, rest: list}

function readlist() : list =
let var any := any{any=0}
var i := readint(any)
in if any.any
then list{first=i,rest=readlist()}
else nil
end

function merge(a: list, b: list) : list =
if a=nil then b
else if b=nil then a
else if a.first < b.first
then
list{first=a.first,rest=merge(a.rest,b)}
else
list{first=b.first,rest=merge(a,b.rest)}

function printint(i: int) =
let function f(i:int) = if i>0
then (f(i/10);
print(chr(i-i/10*10+ord("0"))))
in if i<0 then (print("-"); f(-i))
else if i>0 then f(i)
else print("0")
end

function printlist(l: list) =
if l=nil then print("\n")
else (printint(l.first); print(" ");
printlist(l.rest))

var list1 := readlist()
var list2 := (buffer:=getchar();
readlist())


/* BODY OF MAIN PROGRAM */
in printlist(merge(list1,list2))
end



Well, the tree could take up a whole room, so here is the
condensed version


If you find too many long left/right subtrees, well they are due to static links. The language is tiger, see Andrew Appel's Home Page for more details

WARNING: The IT have not been checked for correctness, I can only hope they are correct.
Post a Comment