labs_03.md

Lab 03: Parser

Introduction

Starting from this week you will work on the second stage of the Amy compiler, the parser. The task of the parser is to take a sequence of tokens produced by the lexer and transform it into an Abstract Syntax Tree (AST).

For this purpose you will write a grammar for Amy programs in a Domain Specific Language (DSL) that can be embedded in Scala. Similarly to what you have seen in the Lexer lab, each grammar rule will also be associated with a transformation function that maps the parse result to an AST. The overall grammar will then be used to automatically parse sequences of tokens into Amy ASTs, while abstracting away extraneous syntactical details, such as commas and parentheses.

As you have seen (and will see) in the lectures, there are various algorithms to parse syntax trees corresponding to context-free grammars. Any context-free grammar (after some normalization) can be parsed using the CYK algorithm. However, this algorithm is rather slow: its complexity is in O(n^3 * g) where n is the size of the program and g the size of the grammar. On the other hand, a more restricted LL(1) grammar can parse inputs in linear time. Thus, the goal of this lab will be to develop an LL(1) version of the Amy grammar.

The Parser Combinator DSL

In the previous lab you already started working with Silex, which was the library we used to tokenize program inputs based on a prioritized list of regular expressions. In this lab we will start using its companion library, Scallion: Once an input string has been tokenized, Scallion allows us to parse the token stream using the rules of an LL(1) grammar and translate to a target data structure, such as an AST.

To familiarize yourself with the parsing functionality of Scallion, please make sure you read the Introduction to (Scallion) Parser Combinators. In it, you will learn how to describe grammars in Scallion's parser combinator DSL and how to ensure that your grammar lies in LL(1) (which Scallion requires to function correctly).

Once you understand parser combinators, you can get to work on your own implementation of an Amy parser in Parser.scala. Note that in this lab you will essentially operate on two data structures: Your parser will consume a sequence of Tokens (defined in Tokens.scala) and produce an AST (as defined by NominalTreeModule in TreeModule.scala). To accomplish this, you will have to define appropriate parsing rules and translation functions for Scallion.

In Parser.scala you will already find a number of parsing rules given to you, including the starting non-terminal program. Others, such as expr are stubs (marked by ???) that you will have to complete yourself. Make sure to take advantage of Scallion's various helpers such as the operators method that simplifies defining operators of different precedence and associativity.

An LL(1) grammar for Amy

As usual, the Amy specification will guide you when it comes to deciding what exactly should be accepted by your parser. Carefully read Section 2 (Syntax).

Note that the EBNF grammar in Figure 2 merely represents an over-approximation of Amy's true grammar -- it is too imprecise to be useful for parsing: Firstly, the grammar in Figure 2 is ambiguous. That is, it allows multiple ways to parse an expression. E.g. x + y * z could be parsed as either (x + y) * z or as x + (y * z). In other words, the grammar doesn't enforce either operator precedence or associativity correctly. Additionally, the restrictions mentioned throughout Section 2 of the specification are not followed.

Your task is thus to come up with appropriate rules that encode Amy's true grammar. Furthermore, this grammar should be LL(1) for reasons of efficiency. Scallion will read your grammar, examine if it is in LL(1), and, if so, parse input programs. If Scallion determines that the grammar is not in LL(1), it will report an error. You can also instruct Scallion to generate some counter-examples for you (see the checkLL1 function).

Translating to ASTs

Scallion will parse a sequence of tokens according to the grammar you provide, however, without additional help, it does not know how to build Amy ASTs. For instance, a (non-sensical) grammar that only accepts sequences of identifier tokens, e.g.

many(elem(IdentifierKind)): Syntax[Seq[Token]]

will be useful in deciding whether the input matches the expected form, but will simply return the tokens unchanged when parsing succeeds.

Scallion does allow you to map parse results from one type to another, however. For instance, in the above example we might want to provide a function f(idTokens: Seq[Token]): Seq[Variable] that transforms the identifier tokens into (Amy-AST) variables of those names.

For more information on how to use Scallion's Syntax#map method please refer to the Scallion introduction.

Notes

Understanding the AST: Nominal vs. Symbolic Trees

If you check the TreeModule file containing the ASTs, you will notice it is structured in an unusual way: There is a TreeModule class extended by NominalTreeModule and SymbolicTreeModule. The reason for this design is that we need two very similar ASTs, but with different types representing names in each case: Just after parsing (this assignment), all names are just Strings and qualified names are essentially pairs of Strings. We call ASTs that only use such String-based names Nominal -- the variant we will be using in this lab. Later, during name analysis, these names will be resolved to unique identifiers, e.g. two variables that refer to different definitions will be distinct, even if they have the same name. For now you can just look at the TreeModule and substitute the types that are not defined there (Name and QualifiedName) with their definitions inside NominalTreeModule.

Positions

As you will notice in the code we provide, all generated ASTs have their position set. The position of each node of the AST is defined as its starting position. It is important that you set the positions in all the trees that you create for better error reporting later. Although our testing infrastructure cannot directly check for presence of positions, we will check it manually.

Pretty Printing

Along with the stubs, we provide a printer for Amy ASTs. It will print parentheses around all expressions so you can clearly see how your parser interprets precedence and associativity. You can use it to test your parser, and it will also be used during our testing to compare the output of your parser with the reference parser.

Skeleton

As usual, you can find the skeleton in the git repository. This lab builds on your previous work, so -- given your implementation of the lexer -- you will only unpack two files from the skeleton.

The structure of your project src directory should be as follows:

amyc
 ├── Main.scala                   (updated)
 │
 ├── ast                          (new)
 │    ├── Identifier.scala
 │    ├── Printer.scala
 │    └── TreeModule.scala
 │
 ├── lib
 │    ├── scallion_3.0.6.jar      (new)
 │    └── silex_3.0.6.jar
 │
 ├── parsing
 │    ├── Parser.scala            (new)
 │    ├── Lexer.scala
 │    └── Tokens.scala
 │
 └── utils
      ├── AmycFatalError.scala
      ├── Context.scala
      ├── Document.scala
      ├── Pipeline.scala
      ├── Position.scala
      ├── Reporter.scala
      └── UniqueCounter.scala

Reference compiler

Recall you can use the reference compiler for any doubts you have on the intended behaviour. For this lab you can use the command:

java -jar amyc-assembly-1.7.jar --printTrees <files>

Deliverables

You are given 2 weeks for this assignment.

Deadline: Friday November 5 at 11 pm.

Submission: one team member submits a zip file submission-groupNumber.zip to the moodle submission page.