We’re now ready to actually generate working code. Your task, should you accept it, is to change your interpreter to a compiler for arithmetic expressions. Generate code for the following “features”:

• Numbers (PUSH)
• Addition / subtraction (DADD, DSUB)
• Multiplication / division (DMUL, DDIV)
• Variable assignment (DSTORE)
• Variable access (DLOAD)
• Edit: variable assignments do NOT have to work like expressions, i.e. you don’t have to support “x = y = 5”!

A common problem with code generation is that you have to distinguish between compile time and run time. These are two separate phases, which is different from the way most interpreters work. Compile time is the first phase, in which you parse statements and generate code. You can use the JVM debugger to check this phase for errors, have a look at the symbol table and the results of the parser. When running the generated code, you cannot simply attach a debugger to it. This means that in the case of a wrong result, you have to manually check the bytecode to see what’s wrong. You do not see that stack, you have no variable names and there are no explicit control structures. You can use the Navigator view in Eclipse to open the .class files in your bin folder and see the bytecode. To make sure the bytecode is working, manually interpret it in your head. Keep track of the values on the stack by writing them on a sheet of paper. Check out the BCEL manual for help on the bytecode!

And if anybody happens to know a good bytecode debugger, please let everyone know on the mailing list…

We’ve made the jump from interpretation to actual compiling of expressions. To start your code-generating compiler, download the BCEL library from http://jakarta.apache.org/bcel/.

Add the library to your project build path and write an example Java program as shown in the lecture. Run the BCELifier tool that comes with the library and take a good look at the output. Refer to the BCEL manual to get a better understanding of the code. Now, modify your interpreter to initialize the bytecode generation facilities. Remove the call to your recursive interpreter. This will cause your tests to fail, so delete or ignore them for now. Write a simple test which evaluates a string which only contains a number. Include the code produced by BCELifier in your parser method. You can leave the hardcoded numerical value in the code. Check that a .class file is generated and load it using the Java ClassLoader, invoke the generated method using java.lang.reflect, and return the result produced by the generated code.

We will start to generate code from the input text in the next homework.

Homework #4 (due Nov. 27th, see last entry!) requires you to implement the following:

• extend the parser to handle if, else, and while statements. The new grammar rules are:

  ifStat ::= 'if' condExpr '{' block '}' ('else' '{' block '}')?
  whileStat ::= 'while' condExpr '{' block '}'
  condExpr ::= expr (bop expr)?
  bop ::= '<' | '>' | '==' | ...

  A conditional expression (condExpr) is true if its value is > 0, and false otherwise.

• parse function declarations:

  funcDecl ::= name '(' paramDeclList ')' '{' block '}'
  paramDeclList ::= name*

  Extend your symbol table to be able to store a function declaration.

• interpret function calls:

  factor ::= number | name | name '(' expr* ')'

  Make sure to handle parameter symbols correctly when calling functions. It should be possible to access globals from a function, but you may choose to make function execution free of side effects. Please make a comment or two about how your implementation works in the code!

Please remember to write simple test cases first (if without else, functions without parameters…). Develop iteratively, adding features as you go. Do not attempt to get everything right on first attempt…

Please implement the following extensions to your interpreter:

• identifiers longer than one character
• floating point numbers

To do this, you have to implement a simple scanner, as demonstrated in the lecture. Create a Token class which contains information about a word. Tokens are created by the scanner using a finite automaton and then interpreted by the parser. As usual, create tests first!

I was asked what the criteria for evaluation of the homeworks are. The tests are very important, as is a consistent and readable code style. If the functionality is complete and working, and the tests make sense and cover most of the implementation, you will get full score. Comments are welcome, but not required, and I prefer meaningful method and variable names. In extreme cases, I may deduct points for code I’m not able to comprehend, so keep it simple 🙂

Requirements for the second homework:

• parse variables
• interpret assignments and keep a symbol table
• treat assignments as expressions, i.e. handle statements such as “x = y = 5”

As usual, follow a test-driven programming style, and write unit test for each feature of your interpreter.

Hint: use the grammar given in the lecture to check your interpreter logic.

block ::= stat*
stat ::= expr | assign
assign ::= name '=' expr
expr ::= term ('+'|'-' term)*
term ::= factor ('*'|'/' factor)*
factor ::= number | '(' expr ')' | name
number ::= '0'...'9'
name ::= 'a'...'z' | 'A'...'Z'

When handling assignments like expressions, you have to extend this grammar in some way.

A student has asked me how repository folders should be named to avoid confusion. I suggest the following:

• Call the Eclipse project exactly as the CVS module name, e.g. “compilerbau” or something similarly short, no blanks please
• Create a normal Java project with a src and a bin folder!
• Inside the source folder, put your homework in a Java package, e.g. “de.uniks.compilerbau.homework01” for your first homework

Remember, this is only a suggestion, but you should really use Java packages. If you haven’t, you can use Eclipse’s refactoring tools to move your code into a package.

For those who joined the GForge project, your CVS repositories should be ready by now!

Check your GForge account, you should be member of your own project whose name ends with your initials. E.g. with my initials “JS”, my project would be called “Compilerbau WS09/10 (JS)”. This project would have a CVS called “cc09js”. To access it, create a CVS repository location in Eclipse, like this (but replacing my initials with your own, of course):

After creating the location, you can use it to submit your homework.

For clarification, here is a what you need to do to complete your first homework assignment:

1. Write unit tests for
   • parsing single digits
   • interpreting an addition of those digits and computing the correct result
   • interpreting subtraction, multiplication, and division
   • correctly computing order of operations (“Punkt vor Strich”)
   • parsing parentheses and interpreting them recursively (hint: separate parsing of factors, terms, and expressions)
2. Once your tests are in place (and you have a red bar), start to implement the functionality required for each test. Start with the simple tests and approach the complicated ones from there, just as it was shown in the lecture.
3. A GUI for the interpreter is not required, but you may add one if you like.
4. To submit your homework, join the GForge project (see my previous entry on this page). I will contact you once your CVS is ready. Commit your project to CVS from Eclipse using Team/Share project.

Feel free to ask me if you have any questions. If the CVS doesn’t work or you have problems using it, you can submit your homework via Email.

The GForge project of the lecture is now online at https://gforge.cs.uni-kassel.de/projects/compilerbau09/.

Please create a GForge account (if you don’t already have one) and join the project as well as the discussion mailing list. Please note that this project is not intended for submissions of your homework. After you join the project, you will receive your own, separate GForge project and CVS repository to commit your homeworks to!

Please be patient, it may take a few days until your project is set up. Until then, you can submit the current homework to me via Email. Please export your Eclipse project as a ZIP file (using File/Export…/General/Archive File) and attach it to the mail. The deadline for homework submission is Friday before the lecture.