Compiling 3

• SL4
• Generating code for expressions
• Generating code for branches and loops

SL4

• Simple imperative language
• All variables hold integers
• Expressions with + - * / function calls
• Assignment var = expr;
• Branch statement

  if (expr rel expr) stat else stat

  • else part is optional
  • rel is one of == != < <= > >=
  • stat is a simple statement or a block (sequence of statements enclosed in { })
• Repetition statement

  while (expr rel expr) stat

  Need as built-in because we don't have closures

SL4 Functions

• funName(param 1, param2, ...) {
    var varName1;
    var varName2;
    ...
    stat1
    stat2
    ...
    return expr;
  }

• Parameters and return values are integers
• Local variables are declared at the top of the function (like in C)
• Local variables are initialized with 0
• Return must be the last statement in the function body

SL4 Example Program

main() {
  print(fac(3));
  return 0;
}

fac(n) {
  var f;
  var i;
  f = 1;
  i = 1;
  while (i <= n) {
    f = f * i;
    i = i + 1;
  }
  return f;
}

• Program execution starts in main
• print is a special function that prints an integer

SL4 Compiler

• Compiles to Java bytecodes
• Uses BCEL
• Generates one class
• SL4 functions → JVM static methods
• public static void main(String[]) calls main()
• print method is always added
• About 250 lines of Scala: SL4.scala

Compiling Arithmetic Expressions

• Expression tree contains subexpressions with correct precedence

    +
   / \
  3   *
     / \
    4   5

• Push left, push right, apply operator

  case Operator(left, right, op) => {
    codeof(left)
    codeof(right)
    il.append(InstructionFactory.createBinaryOperation(op, Type.INT))
  } 

• iconst 3
  iconst 4
  iconst 5
  imul
  iadd

Compiling Expressions

• Constant: Translate to iconst
• Variable: Translate to iload
• Fortunately, BCEL keeps tracks of indexes

  mg.getLocalVariables().find(_.getName() == name) match { case Some(v) => 
    il.append(InstructionFactory.createLoad(v.getType, v.getIndex))
  }

• Function call: Push the arguments, call the function

  args.foreach(codeof _)
  il.append(factory.createInvoke(className, f.name,
    Type.INT, f.params.map(x => Type.INT).toArray, // return type, param types
    Constants.INVOKESTATIC))

• Special case for print

Compiling Branches

• IfStat(BoolOp(expr1, expr2, rel), body1, optBody2) becomes

    expr1
    expr2
    isub
    if !rel goto :label1
    body1
    goto :label2
  :label1 nop
    body2
  :label2 nop

• Code for computing branch condition

  codeof(expr1)
  codeof(expr2)
  il.append(InstructionFactory.createBinaryOperation("-", Type.INT))
  val instr1 = InstructionFactory.createBranchInstruction(notrel2op(rel), null)
  il.append(instr1)
   ...
  instr1.setTarget(il.append(InstructionConstants.NOP))

• The inverted relation is precomputed

  val notrel2op = Map(">=" -> Constants.IFLT, ">" -> Constants.IFLE, 
    "<=" -> Constants.IFGT, "<" -> Constants.IFGE, 
    "!=" -> Constants.IFEQ, "==" -> Constants.IFNE)

Compiling Loops

• WhileStat(BoolOp(expr1, expr2, rel), body) becomes

  :label1 nop
    expr1
    expr2
    isub
    if !rel goto :label2
    body
    goto :label1
  :label2 nop

• Code for body is generated recursively

  val loc = il.append(InstructionConstants.NOP)
  codeof(expr1)
  codeof(expr2)
  il.append(InstructionFactory.createBinaryOperation("-", Type.INT))
  val instr = InstructionFactory.createBranchInstruction(notrel2op(rel), null)
  il.append(instr)
  codeofBlock(body)
  il.append(InstructionFactory.createBranchInstruction(Constants.GOTO, loc))
  instr.setTarget(il.append(InstructionConstants.NOP))

• That's all. Now you know how to write a compiler

What Did We Achieve?

• Parsing: Use Scala combinator parser to turn program text into tree structure
• Evaluating expressions: Simple recursive algorithm on tree structure
• Symbol table: holds (name, value) pairs
• Scope: Use different tables in different places of the program
• Closures: Code + bindings of free variables
• SL1 Interpreter: A language with closures
• Type checking: Compute type assignments and verify type correctness (SL3)
• SL4 Compiler
• What else does the Java compiler do? (Not much...classes, fields, exceptions)

Lab

• Check into eCampus in the usual way
• This lab uses Scala, not Java
• Scribe puts in report
• Buddy puts in comment “I worked with (scribe's name)”
• Reminder: Please install SWI-Prolog before Thursday's lecture

Step 1: Try the Compiler

1. In Eclipse, make a Scala project Lab18
2. Add SL4.scala
3. Start the program and paste in the factorial program from slide 4. Hit Ctrl+D/Ctrl+Z. What happens?
4. Where is the compiled program?
5. What happens when you run it?
6. Run javap -c. How many functions are in the class file?
7. What code is generated for the while loop?

Step 2: Rewrite Factorial

1. Rewrite the factorial program to be recursive, not iterative. What is your code?
2. What happens when you compile and run it?
3. What code is generated for the if statement?

Step 3: Improve the Compiler

1. The parts of the compiler that generate code for if and while statements contain identical code for generating the branch condition. What is that code?
2. Make a separate function codeofBoolOp that generates this code and deals with the fact that you need to set the branch target later. What is your function?
3. Try your changed compiler with the programs in step 1 and 2 to make sure that it still works.

Step 4: The if/if/else ambiguity

1. The grammar

   stat ::= "if" "(" expr ")" stat ( "else" stat )? | expr ";"

   is ambiguous. There are two possible parse trees for if (c1) e1 if(c2) e2 else e3. What are these parse trees?

2. In Java, which of them is actually being used?
3. In SL4, which of them is actually being used?