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 that the identity holds. 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.

As testcases, you can use the ones that you and the other students in this class wrote. They're available for download here. As usual, your compiler needs to work on these examples, but this may not be sufficient. Some corner cases may not be covered in those.

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, for instance. (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 pretty-printed 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 src directory should be as following:

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

You have to write the parser manually, as a series of mutually recursive functions. You are not allowed to use parser combinators or other such libraries.

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. 26th, 11.55pm (23h55).