[SOLVED] YASL Intermediate Code Generation

YASL Intermediate Code Generation

Brian Howard Fall 2015, Version 1.0

Generate an entire program by creating an empty symbol table that maps identifiers to Info, then generate the block inside a new scope whose name is the program name. At the end, halt execution:

t = new SymbolTable[Info]

t.enter(ID)

G program ID ; Block . = G Block (t)

t.exit() HALT

Generate a block by generating in turn each of the declarations, followed by each of the statements of the block. Create a new label, s, to skip around any generated procedure code. Wrap the body of the block in ENTER/EXIT and RESERVE/DROP pairs to manage local variables:

G ConstDecls VarDecls ProcDecls begin Stmts end (t) = s = newLabel

foreach cd ConstDecls: G cd (t)

foreach vd VarDecls: G vd (t)

foreach pd ProcDecls: G pd (t)

LABEL s

n = VarDecls.size

l = t.level

ENTER l

RESERVE n

foreach s Stmts: G s (t)

DROP n

EXIT l
1

BRANCH s

Generate a constant declaration by binding the identifier to a new ConstInfo holding the number:

G const ID = NUM ; (t) = t.bind(ID, new ConstInfo(NUM))

Generate a variable declaration by binding the identifier to a new VarInfo holding the level of the current scope and the next available offset in the scope (starting at 1 and counting down):

t.offset = t.offset 1
G var ID : Type ; (t) = t.bind(ID, new VarInfo(t.level, t.offset))

Generate a procedure declaration by binding the identifier to a new ProcInfo holding the list of parameters and a new label. Within a new scope where all of the parameters have been processed in reverse, generate code for the block preceded by the label and ending with a return:

s = newLabel

t.bind(ID, new ProcInfo(s, Params))

t.enter(ID)

Gproc ID Params ; Block ;(t) = RETURN

foreach p Params.reverse: G p (t)

LABEL s

G Block (t)

t.exit()

Generate a value parameter declaration by binding the identifier to a new VarInfo holding the level of the current scope and the next available parameter offset in the scope (starting at 2 and counting up):

t.param = t.param + 1
G ID : Type (t) = t.bind(ID, new VarInfo(t.level, t.param)

Generate a variable parameter declaration by binding the identifier to a new RefInfo holding the level of the current scope and the next available parameter offset in the scope (starting at 2 and counting up):

t.param = t.param + 1
G var ID : Type (t) = t.bind(ID, new RefInfo(t.level, t.param)

Generate an assignment statement by generating the expression on the right, looking up the identifier on the left to find the address to store into, and then performing the store

2

operation. The lvalue function generates the code to push the address of either a simple variable or a reference (var parameter):

G Expr (t) G ID = Expr ; (t) = lvalue(ID, t)

STORE
info = t.lookup(ID)

lvalue(ID, t) = ADDRESS info.level, info.offsetif info is a RefInfo: LOAD

Generate a procedure call by looking up the identifier to get a ProcInfo, then generating the list of arguments (so each will be pushed to the stack)this is handled by the setup function. A call statement is generated; when the procedure returns, the arguments must be dropped:

ProcInfo(s, params) = t.lookup(ID) setup(params, Args, t)
CALL s
DROP params.size

G ID Args ; (t) =
The setup function is defined by the following cases (note that Nil is an empty list, while

head :: tail is a list with the given head element and rest of the list tail): setup(Nil, Nil, t) = // nothing left

setup((ID : Type) :: params, arg :: args, t) =

G arg (t)

setup((var ID : Type) :: params, ID :: args, t) =

lvalue(ID, t)

Generate a compound statement by generating each of the contained statements in turn:

G begin Stmts end ; (t) = foreach s Stmts: G s (t)

3

setup(params, args, t)

setup(params, args, t)

Generate an if-then statement by generating the test with two new labelsif true, branch to the statement; if false, branch past the statement:

G if Expr then Stmt (t) =
G Stmt (t)

LABEL n

Generate an if-then-else statement by generating the test with two new labelsif true, branch to the first statement; if false, branch to the second statement. A third new label is used to branch past the second statement:

y = newLabel

n = newLabel s = newLabel

G Expr (t, y, n)

G if Expr then Stmt1 else Stmt2 (t) = LABEL y G Stmt1 (t)

BRANCH s

LABEL n G Stmt2 (t)

LABEL s

Generate a while statement by generating the test with two new labelsif true, branch to the statement; if false, branch past the statement. A third new label is used to branch from the end of the statement back to the test:

y = newLabel

n = newLabel

s = newLabel

LABEL s

G while Expr do Stmt (t)=G Expr (t,y,n)

LABEL y

G Stmt (t)

BRANCH s

LABEL n 4

y = newLabel n = newLabel GExpr(t, y, n) LABEL y

Generate a prompt statement by printing the message string (without a trailing newline) and waiting for a line of input. If an identifier is specified along with the string, then generate code to read an integer and assign it to that variable:

lvalue(ID)

STORE
The print function generates code to print a string one character at a time:

foreach c STRING:

G prompt STRING ; (t) =
Gprompt STRING , ID ;(t) = READINT

print(STRING) =

CONSTANT cWRITECHAR

print(STRING) READLINE

Generate a print statement by generating code to print each of its items (strings or integer expressions) on a single line:

foreach it Items:

G print Items ; (t) =

if it is an Expr: G it (t)

WRITEINT
else: // it is a STRING

print(it) WRITELINE

5

print(STRING + )

Generate a boolean binary operation expression as described in class. For relational operators, generate code to evaluate each operand and put the result on the stack, then generate appropriate tests and branches. For logical operators, generate code to evaluate the left operand and then either branch to the code for the right operand or branch directly to the provided yes or no label:

G Expr1 op

Expr2 (t, y, n) =

case And:
s = newLabel

G Expr1 (t, s, n) LABEL s G Expr2 (t, y, n)

case Or:
s = newLabel

G Expr1 (t, y, s) LABEL s G Expr2 (t, y, n)

case EQ:
GExpr1(t); GExpr2(t) SUB;BRANCHZERO y;BRANCH n

case NE:
GExpr1(t); GExpr2(t) SUB;BRANCHZERO n;BRANCH y

case LT:
GExpr1(t); GExpr2(t) SUB;BRANCHNEG y;BRANCH n

case GE:
GExpr1(t); GExpr2(t) SUB;BRANCHNEG n;BRANCH y

case GT:
GExpr2(t); GExpr1(t) SUB;BRANCHNEG y;BRANCH n

case LE:
GExpr2(t); GExpr1(t) SUB;BRANCHNEG n;BRANCH y

6

switch op:

Generate an integer binary operation expression by generating code to evaluate each operand, then performing the desired operation.

G Expr1 (t)

G Expr2 (t)

switch op:

G Expr1 op Expr2 (t) =

case Plus: ADD

case Minus: SUB

case Times: MUL

case Div: DIV

case Mod: MOD

Generate a boolean unary operation expression (the not operator) by generating code to evaluate the operand with the y and n labels swapped:

G not Expr (t,y,n)=G Expr (t,n,y)
Generate an integer unary operation expression (the operator) by generating code to

subtract the expression from zero:

CONSTANT 0 G Expr (t) = G Expr (t)

SUB
Generate a boolean literal expression by branching to the appropriate label:

Gtrue(t,y,n)=BRANCH yGfalse(t,y,n)=BRANCH n

Generate an integer or boolean literal expression (in an integer context) by pushing the corresponding value:

G NUM (t) = CONSTANT n , if the NUM is n G true (t) = CONSTANT 1
Gfalse(t) = CONSTANT 0

7

Generate a variable expression by pushing its address and performing a load:

lvalue(ID) LOAD

If a boolean expression is used in an integer context, wrap it in code to push either 0 (false) or 1 (true) on the stack. Note that this case is only used if none of the above applied:

Stack Frame

G ID (t) =

y = newLabel

n = newLabel s = newLabel

G Expr1 op Expr2 (t,y,n)

GExpr(t) = LABEL yCONSTANT 1

BRANCH sLABEL nCONSTANT 0LABEL s

If we have a procedure with k parameters and n local variables, then the stack frame will be laid out as follows:

FPn

FP1 FP FP+1 FP+2

FP + (k + 1)

For a procedure defined at level l (where the main program is at level 0), its frame pointer (FP) will be stored in display[l].

8