Lab for Automated Reasoning and Analysis LARA

Labs 02

This assignment is the first part of the Tool compiler project. Make sure you read the general project overview page first. Please also send Philippe an email as soon as possible stating who are the (two) members of your group.

Test case corpus

Write two small Tool programs per person (four per group of two) to constitute a corpus of test cases that we will use throughout the compiler project. Make sure you follow strictly the grammar! We will check that all benchmarks are correct Tool programs and distribute the test suite, so that everyone can have a substantial code base to test their compiler on. The programs don't have to be particularly complex, but it is in your own interest to write interesting ones, as you will use them to test your implementation of the various steps of the project.

Your programs should be written in a single .tool file each. Please make sure that you can compile and run them using our reference implementation (see the Tool compiler project page to find it).


Write the lexer for Tool. Here are some details you should pay attention to:

  • Make sure you recognize keywords as their own token type. while, for instance, should be lexed as the token type WHILE, not as an identifier representing an object called “while”.
  • Make sure you correctly register the position of all tokens.
  • In general, it is good to output as many errors as possible (this helps whoever uses your compiler). For instance, if your lexer encounters an invalid character, it can output an error message, skip it, and keep on lexing the rest of the input. After lexing, the compiler still won't proceed to the next phase, but this helps the user correct more than one error per compilation. Use the special BAD token type to mark errors and keep lexing as long as it is possible.


Here are some classes and stubs. Mind the package names when you insert them into your project.

  • Tokens.scala: stub for a file describing token types and tokens.
  • Positional.scala: the positional trait, nothing to change in there.
  • Lexer.scala: stub for the Lexer trait.
  • Reporter.scala: the complete Reporter trait, nothing to change.
  • Compiler.scala: the main class for the compiler, that combines the other traits. Contains only a testing method for now, you don't have to edit it.
  • Main.scala: some code to help you test your lexer.
  • Factorial.tool: an example Tool program.

Mind the package names. The structure of your project should be as follows:

 └── tool
      ├── Compiler.scala
      ├── Main.scala
      ├── Positional.scala
      ├── Reporter.scala
      └── lexer
           ├── Lexer.scala
           └── Tokens.scala

If you're not so much into Eclipse, you can use this ANT script to build your program: build.xml. In fact, given how annoying Eclipse can be sometimes, it could be a good idea to use Eclipse to edit the code and compile it in a console. It's your call. The build file also generates a script, toolc which you can use to try out your compiler. Note that this script should also work for the following labs.

Example output

For reference, here is a possible (incomplete) output for the factorial program:

OBJECT(1:1) IDFactorial(1:8) LBRACE(1:18) DEF(2:5) MAIN(2:9) LPAREN(2:13) RPAREN(2:14)
COLON(2:16) UNIT(2:18) EQSIGN(2:23) ... RPAREN(13:59) RPAREN(13:60) SEMICOLON(13:61)
RETURN(14:9) IDnum_aux(14:16) SEMICOLON(14:23) RBRACE(15:5) RBRACE(16:1) EOF(16:2)


Hand in your project directory (src and below) compressed in a zip file through Moodle by Tuesday, September 29th, 11:55pm (23h55). Please make sure of the following:

  • send us a .zip file, not a .rar file
  • do not include .class files
  • do not include .svn directories and the like
cc09/labs_02.txt · Last modified: 2009/09/23 00:43 by philippe.suter