This week and the next one, you'll work on the second part of the Tool compiler project. Your goal is to manually implement a recursive-descent parser to transform programs described by the Tool grammar into Abstract Syntax Trees. You also need to write a pretty-printer for these trees. This assignment is rather long and we can only recommend that you start early, that you make sure you understand every step, and that you ask otherwise.

One way to partially check your implementation is to use the pretty-printer to output the parsed AST (reproducing the input file from the trees, if you want). If you then re-parse this output and re-pretty-print it, you should obtain exactly the same result. In other “words”: for all input programs , you should have . While this condition is necessary to ensure you have properly written your parser and printer, it is not sufficient, and you are as usual responsible for checking the details of your implementation before you submit it.

Define a class hierarchy to represent nodes in the Abstract Syntax Trees. You should at least have individual nodes corresponding to each production in the grammar, and you can have more if you feel they can be useful. You can refer yourself to the AST structure for the while language from the first lab for an example.

Write a recursive-descent Parser for Tool by manually writing mutually recursive procedures, as sketched in the lecture on recursive descent parsing, and generating the appropriate Abstract Syntax Trees. The stub we give you hints at how to implement this.

• It's not allowed in Tool to have a variable with a name that matches a keyword. You will never have a variable or a class called length (although that would be allowed in Java or Scala, for instance).
• You need to properly encode the operator precedence as in Java and Scala. From highest priority to lowest: !, then * and /, then + and -, then < and ==, then &&, then ||. Except for the unary operators, all operators are left-associative. There is no precedence between operators of the same level. For instance: 4 / 3 * 6 reads as ((4 / 3) * 6) and 6 * 4 / 3 as ((6 * 4) / 3.
• An else keyword always applies to the closest if. You can add comments to mark the end of if blocks in your pretty-printer to make sure you parse things properly.

if(expr1) if(expr2) a=1; else a=2;

…could be reprinted as:

if(expr1) if(expr2) a=1; else a=2; /* end if */ /* end if */

…and should not produce:

if(expr1) if(expr2) a=1; /* end if */ else a=2; /* end if */

Write a pretty-printer for the AST hierarchy you defined in the previous step. Your pretty-printer should transform any valid AST into the corresponding textual representation in the Tool programming language. You can have a look at the pretty-printer for the while language from the first lab if you need inspiration. The output does not need to be exactly as the input file; whitespaces can be placed differently, comments must disappear (do not store them in the AST!) and parentheses can be added (or removed), as long as the program keeps the original intended meaning. Re-parsing the output and re-printing it should yield an identical result, though.

You can use the following stubs:

• Trees.scala contains a stub for the AST hierarchy. Note that tree nodes are Positional objects and you will need to set their position appropriately by copying the information from the relevant tokens.
• Parser.scala contains a stub for the LL parser.
• TreePrinter.scala contains a stub for the pretty-printer. Note that applying the printer to a tree returns a string and prints out no output directly.
• Compiler.scala combines the Reporter and Parser traits to form the compiler. Note that it doesn't need to explicitly refer to Lexer, since Parser already extends Lexer. For this Lab, the compiler just parses the file and pretty-prints it. You have nothing to change in that file.

As usual, mind the package names. The structure of your project should be as following:

src
 └── tool
      ├── Compiler.scala        (given this week)
      ├── Main.scala            (given in Lab 02)
      ├── Positional.scala      (given in Lab 02)
      ├── Reporter.scala        (given in Lab 02)
      ├── TreePrinter.scala     (stub given this week)
      │
      ├── lexer
      │    ├── Lexer.scala      (completed as part of Lab 02)
      │    └── Tokens.scala     (completed as part of Lab 02)
      │
      └── parser
           ├── Parser.scala     (stub given this week)
           └── Trees.scala      (stub given this week)

Submit an archive of your src directory (containing only .scala files, no binaries, no .svn, no script, no README, please) through Moodle before Tuesday, Oct. 13th, 11.55pm (23h55).