Version 1.2: Corrected definition of peek() method

Version 1.3: Added testRDParser and a corresponding task in the build.xml file

Collaboration

This assignment must be done individually. If you want to team up with someone to tackle some or all of the extra credit parts, you're free to do so for that bit.

Files

Download the hw3.zip distribution files (link), and add the contents to your tigerc project.

Your Job

Complete the TigerParseRD class to implement a recursive-descent parser for the Tiger language. Because this project has a short time frame and is a branch off of the main trajectory of the compiler project for this course (we'll implement a full LALR(1) parser over next two weeks), you need only cover a subset of the language:

    E   -->  <int_const> | <string_const> | <nil> |<break> | LVal
            | E Op E | - E |  LVal := E | while E do E 
            | for <id> := E to E do E | let Decl in ESeq end | ( ESeq )
  LVal  -->  <id>
  Decl  --> var <id> := E
  ESeq  --> E | ESeq ; E
  
     Op  =  {+, -, *, /, =, <>, <, <=, >, >=, &, |}

Precedence

In order of highest precedence to lowest:

  1. Unary minus (- E)
  2. * and /
  3. + and -
  4. =, <>, >, <, >=, and <=
  5. & and |
  6. :=

Associativity

All arithmetic and logical operators (+, -, *, /, &, |) are left associative. Comparison operators (=, <>, >, <, >=, and <=) are not associative (for example, a=b=c is a syntax error).

The assignment operator, :=, is also nonassociative, but it is unclear from the language specification whether this is a requirement of the syntax (in which case you must handle it here in the grammar) or of the type system (which would allow you to delay this problem to the semantic analysis phase, where it is much easier to handle). You may choose either interpretation here.

Creating an LL(1) Grammar

Once you have an LL(1) grammar, creation of a recursive descent parser is quite straightforward. It's the grammar construction that's the really challenging part. Begin your work on this project with this effort. Verify that you do have an LL(1) grammar by eliminating ambiguity (highly likely, after you've refactored for precedence and associativity), checking for left recursion, and calculating the Predict sets for each production in your grammar.

Regarding Syntax-Directed Translation

For those who've read ahead in the text, you are not expected to add any syntax-directed translation actions to the parser. It suffices to have a parser that accepts all and only syntactically legal programs (even if not semantically valid).

Extras

(Optional, but rewarding, both personally and materially)

Personally, I find parsers very satisfying to write, either by hand or by specification. Once you get the hang of things, I hope you will agree.

If, after completing a parser for the above subset, you want to tackle other parts of the language, there are several directions for exploration. In order, roughly, of increasing challenge:

Turn In:

John H. E. Lasseter