Assignment 2:  Syntax Error Recovery

During the last assignment you probably encountered a wide variety of error messages.  The nature of these messages depends on both the language definition and the compiler or interpreter.  You may have noticed that across languages and implementations these messages differ greatly in their usefulness and specificity.  One feature common to all of the languages you used is syntax error recovery.  In the simplest sense, syntax error recovery is the mechanism by which a compiler or interpreter continues to parse a program (and find more syntax errors) after it encounters an instance of invalid syntax. 

Your task in this assignment is to implement a front end, in Rust, that incorporates syntax error recovery and that generates syntax trees for an extended version of the calculator language discussed in the text and in lecture.  We are providing starter code with input buffering routines, an ad-hoc scanner, and the driver for a table-driven parser.  The scanner implements simple recovery from lexical errors (for the base calculator language), but the parser currently panics (prints an error message and halts) if it encounters a syntax error.  We are also providing a parser generator that takes a CFG as input and generates LL(1) parsing tables in the form of initialized Rust data structures.  Starting from this initial code base, you must:

  1. Extend the calculator grammar (input to the parser generator) with explicit declarations, integer and real numbers, if/elsif/else statements, and while/do statements, as shown in the grammar below
  2. Extend the scanner to recognize the additional tokens of the extended language.  You may assume that the language requires there to be whitespace between a number and a following identifier.  As a result, it should be possible (in this particular language) to recover from lexical errors without ever needing to back up more than one character. 

    The code we are giving you already handles three error cases: unrecognized characters at the start of a token, anything other than ‘=’ following ‘:’, or a letter immediately following an integer constant.  You will need to extend this to handle, in a similar fashion, the two-character ‘<>’ and ‘==’ signs and the fraction and exponent parts of real-number constants. 

  3. Implement table-driven syntax error recovery, as described in class.  Briefly, you should pretend to insert any expected (top-of-stack) token that does not appear on the input and, when unable to make a prediction for some nonterminal X at top-of-stack, delete tokens until you find something in FIRST(X) or FOLLOW(X) (stopping if you encounter end-of-file).  Several (not necessarily all) of the places you will need to modify in the parser are marked with *** comments. 
  4. Define new AST node types (in attributes.rs) to represent declarations, if and while statements, and trunc and float expressions.  These can be patterned after node types for the base calculator language, which we are giving you. 
  5. Write action routines to build an AST.  These go in a big match statement in actions.rs.  Their numbers (match labels) must correspond to brace-enclosed action routine markers in the CFG you give to the parser generator.  The code we are giving you has a few action routines already present, to give you an idea what they look like.  You will need to implement more.  (Our sample solution has a total of just over 40 action routines, many of which are simple “copy rules.”) 
  6. Output (a linearized representation of) the syntax tree (AST) at the end of a successful parse.  We have provided output formatting routines for the node types needed by the base calculator language.  You will need to define similar routines for your new node types. 

    Each tree node will be represented either as a (parenthesized) tuple, with a fixed number of fields, or as a (square-bracketed) list, with an arbitrary number of elements.  In a tuple, you can think of the first field as a subtree parent and the rest of the fields as its children.  As an simple example, the tree for the sum-and-average program we used as an example in lecture (in the base calculator language) would be output as [ (read (a)) (read (b)) (:= (sum) (+ (a) (b))) (write (sum)) (write (/ (sum) (2))) ].  More detail on the AST structure can be found below

    As a debugging aid, the code we are giving you prints a trace of predictions, matches, and action routine invocations.  You should disable this trace in the code you hand in. 

When run, your program should read an extended calculator program from standard input and then print, to standard output, either syntax error messages or a correct syntax tree.  (It’s ok for lexical errors not to inhibit construction of the AST, if the scanner’s repairs are acceptable to the parser.)

Starter Code

The initial source code for this assignment is available as a “tarball” file.  You should download it on a csug machine and unpack it from the shell:

    tar -xzf calc_parse.tgz
Then cd into the calc_parse directory and run
    cargo init
That will initialize a standard Rust project, with dependence tracking and git-based version control. 

In the src subdirectory, file tables.rs has been automatically generated from the calc_gram.txt file in the root directory.  When you make changes to the grammar (to add features and/or action routines), you must re-run the parser generator:

    table_gen < calc_gram.txt > src/tables.rs
The table_gen tool resides in ~cs254/bin, which you should already have put on your shell's search path during assignment 1.  If you’re curious how the parser generator works (or if you want to download it so you can run it on your own machine—note that it’s written in OCaml), you can find it in HERE.  The binary is really all you need, however.  If you’re a Rust enthusiast, you’re welcome to automate the table_gen step, so the cargo build command will automatically regenerate tables.rs whenever calc_gram.txt has changed.  If you don’t know how to do that, don’t worry: regenerating the file explicitly is fine. 

To invoke the Rust compiler, type

    cargo build
This will recompile all and only the files that have changed since your last rebuild.  (For Unix hackers: cargo subsumes the functionality of traditional make files.) 

You can run the executable version of your code directly:

    ./target/debug/calc_parse
Better, type
    cargo run
That will rebuild your code if necessary and then run the executable. 

As you work on the code, I strongly recommend that you make use of the git support established by cargo init.  At frequent intervals, type

    git commit -am 'log message'
If you add any files to the project, type
    git add 'filename'
before your next commit.  If you run into trouble and need to back out recent changes, consult any decent git tutorial on the web. 

Sample Solution

If you’d like to test the behavior/output of your code, our sample solution (without source!) can be found at ~cs254/bin/calc_parse.  It incorporates immediate error detection. 

If you find a bug in the starter code, the parser generator, or the sample solution, please email the instructor and grad TA, so we can fix it as quickly as possible. 

Extended Calculator Language

Here is an LL(1) grammar for the extended calculator language: 

SL→  S  SL  |  ε
S→  TP id := E  |  read TP id  |  write E
 |  if C then SL  EL end  |  while C do SL end
TP→  int  |  real  |  ε
EL→  elsif  C  then  SL  EL   |  else  SL   |  ε
C→  E  RO  E
E→  T  TT
TT→  AO  T  TT  |  ε
T→  F  FT
FT→  MO  F  FT  |  ε
F→  ( E )  |  id  |  i_lit  |  r_lit  |  trunc ( E )  |  float ( E )
RO→  ==  |  <>  |  <  |  >  |  <=  |  >=
AO→  +  |  -
MO→  *  |  /

Here the new nonterminal C represents a comparison.  The new nonterminal RO is a “relational operator.” 

Integer and real number constants are differentiated by the presence or absence of a decimal point:

i_lit  =  d+
r_lit  =  ( d+ . d* | d* . d+ ) ( e ( + | - | ε ) d+ | ε )
where d stands for any decimal digit and e is the actual letter e.  Note that digits are required on both sides of the decimal point. 

As explained in lecture, $$ is a special token created by the scanner when it detects the end of the input; it is not a part of the actual program text.  (In the starter code we have given you, it is TokTp::Stop.)  We have left the augmenting production

P  →  SL $$
out of the grammar above.  It will be inserted for you automatically by the parser generator. 

Parser Generator Input Requirements

In the code we are giving you, the file calc_gram.txt looks like this:

SL -> S SL
   ->
S  -> Id Gets E {3}
   -> Read Id
   -> Write E {5}
E  -> T {7} TT
T  -> F {11} FT
TT -> AO T TT
   ->
FT -> MO F FT
   ->
AO -> Plus
   -> Minus
MO -> Times
   -> DivBy
F  -> Id {13}
   -> Num {17}
   -> LParen E RParen {19}
The start symbol is the left-hand side of the first production.  The augmenting production, as noted above, is added by the parser generator, table_gen.  All productions for a given nonterminal must be consecutive, with the left-hand side elided on all but the first.  Epsilon productions simply have an empty right-hand size. 

Every symbol’ name must have the form of a valid Rust enum constant (this facilitates generation of tables.rs).  Your scanner should recognize the actual characters (e.g., “:=”, not “Gets”), however.  It should return both the enum constant and the text of the token as part of its Token-typed return value. 

Action routines take the form of natural numbers in braces (e.g., “{13}”.  When the parser comes upon one in the process of parsing a right-hand side, it will call routine do_action, passing the natural number (e.g., 13) as parameter.  Code for action routines thus take the form of match statement arms in actions.rs.  Action routine numbers don’t have to be consecutive, or appear in any particular order.  The initial calc_gram.txt file has seven routines for illustration purposes only.  You will need to replace most of these in your code. 

Action routine numbers 0 and 1, and symbol names Goal and Stop, are reserved by table_gen for use in the augmenting production; you can’t use these yourself. 

Intended Semantics

Unless you choose to do so for extra credit, you will not be checking semantic ruiles in the current assignment.  If you’re interested, however, identifiers are intended to be declared before use, with an int or real type specifier on a read or assignment statement that provides an initial value.  The scope of each declaration extends from the declaration itself through the end of the current statement list.  Integers and real numbers are not intended to be mixed in expressions unless explicitly converted with trunc and float

As it turns out, if we assume that integers are unbounded, our extensions make the calculator language Turing complete (if still quite impractical).  As an illustration, here is a program that calculates the first n primes:

    read int n
    int cp := 2
    while n > 0 do
        int found := 0
        int cf1 := 2
        int cf1s := cf1 * cf1
        while cf1s <= cp do
            int cf2 := 2
            int pr := cf1 * cf2
            while pr <= cp do
                if pr == cp then
                    found := 1
                end
                cf2 := cf2 + 1
                pr := cf1 * cf2
            end
            cf1 := cf1 + 1
            cf1s := cf1 * cf1
        end
        if found == 0 then
            write cp
            n := n - 1
        end
        cp := cp + 1
    end 

Syntax Tree Structure

Your AST for the primes-printing program should look like this:

    [ (decl (n) (int))
      (read (n))
      (decl (cp) (int))
      (:= (cp) (2))
      (while (> (n) (0))
        [ (decl (found) (int))
          (:= (found) (0))
          (decl (cf1) (int))
          (:= (cf1) (2))
          (decl (cf1s) (int))
          (:= (cf1s) (* (cf1) (cf1)))
          (while (<= (cf1s) (cp))
            [ (decl (cf2) (int))
              (:= (cf2) (2))
              (decl (pr) (int))
              (:= (pr) (* (cf1) (cf2)))
              (while (<= (pr) (cp))
                [ (if (== (pr) (cp))
                    [ (:= (found) (1))
                    ] [
                    ]
                  )
                  (:= (cf2) (+ (cf2) (1)))
                  (:= (pr) (* (cf1) (cf2)))
                ]
              )
              (:= (cf1) (+ (cf1) (1)))
              (:= (cf1s) (* (cf1) (cf1)))
            ]
          )
          (if (== (found) (0))
            [ (write (cp))
              (:= (n) (- (n) (1)))
            ] [
            ]
          )
          (:= (cp) (+ (cp) (1)))
        ]
      )
    ] 
Indentation and line breaks are shown here for clarity only, and need not be generated by your code.  Otherwise, the output above is what our sample solution produces, using (extensions of) the fmt routines we’ve given you in attributes.rs.  As noted near the top of these instructions, square brackets delimit lists, which have an arbitrary number of elements.  Parentheses delimit tuples or structs, which have a fixed number of fields.  An if node, for example, has three children: a condition, a body for its then clause, and a body for its else clause.  The condition is a tuple containing a comparison operator and its operands; the body is a list of statements that should be executed when the comparison is true or false, respectively.  The program as a whole is likewise a statement list.  Conditional statements with elsif clauses should produce the same AST as equivalent nested if statements.  So, for example, the input if a < b then write c elsif d < e then write f else write g end should yield the tree [ (if (< (a) (b)) [ (write (c)) ] [ (if (< (d) (e)) [ (write (f)) ] [ (write (g)) ]) ]) ]

A note for those new to the Linux command line:  If you paste characters into the terminal window as standard input, you have to hit control-D to indicate end-of-file before the generator will do anything.  You will almost certainly want to put your sample calculator programs into text files and feed them into your code using shell indirection:

    calc_parse < test_file1.txt

Extra Work for CSC 454

Students in 454 must implement immediate error detection:  epsilon productions should be “undone” before recovering when the upcoming token turns out not to be in the local FOLLOW set of the top-of-stack nonterminal. 

Suggestions and Hints

You will want to test your code on a variety of calculator programs, both correct and incorrect.  Your turn-in should include the test programs you used, and your README file should explain how to run them.  (We will of course run additional tests of our own.)  Extra credit may be given to students who provide particularly well designed test mechanisms in their submission. 

Note that your code will employ both insertions and deletions: when the match routine (function eat in the starter code) sees a token other than the one it expects, it will print an appropriate error message and then return, as if it had inserted and then matched the expected token, leaving the remaining token stream unchanged.)  When the main loop of the parser encounters an Err entry in the parse (prediction) table, it will delete tokens until it finds something in either the FIRST set or the FOLLOW set of the top-of-stack nonterminal.

A variety of good resources for Rust are available on the web.  You may wish to consult the following:

Pointers to other resoruces can be found at the main language site, but the above should be ample for the current assignment. 

Division of labor and writeup

As in other assignments this semester, you may work alone or in teams of two.  If you would like to work on a team but are in need of a partner, consider posting a note to the Blackboard discussion board.  If you are working in a team, a reasonable division of work would be for one student to update the scanner and implement error recovery and the other to build the AST.  If you’re implementing immediate error recovery, scanner updates might better be assigned to the person building the AST. 

Be sure to follow all the rules on the Grading page.  As in all assignments, use the turn-in script:  ~cs254/bin/TURN_IN on the csug machines.  Put your write-up in a README.txt or README.pdf file in the directory in which you run the script.  Be sure to describe any features of your code that the TAs might not immediately notice.  Only one turn-in of the main assignment (and only one README) is required per team, but each student must complete the trivia (on Blackboard) separately. 

Extra Credit Suggestions

  1. If you are in CSC 254, complete the extra work for 454. 
  2. Implement static semantic checks to ensure that (a) every variable is declared before use; (b) no variable is ever re-declared in the same scope; (c) arithmetic and relational operators are applied only to operands of the same type; (d) the argument of float is always of type int; (e) the argument of trunc is always of type real.
  3. After parsing and checking, execute (interpret) the calculator program.
  4. Extend the calculator language in other interesting ways.  You might, for instance, add arrays, strings, for loops, or subroutines. 
  5. Translate your AST into equivalent output code in some existing language (e.g., C). 

Grading Rubric

Trivia Assignment

Before class on Thursday, February 13, complete the T2 trivia assignment found on Blackboard

MAIN DUE DATE: 

Sunday March 2, by 11:59 pm; no extensions. 
Last Change:  12 February 2025 / Michael Scott's email address