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 syntax error recovery and to generate syntax trees for an extended version of the calculator language discussed in the text and in lecture.  We are providing a basic scanner and parser; starting from this initial code base, you must:

  1. Modify the scanner to recover from lexical errors.  You may assume that there is always white space between a number and a following identifier.  As a result, it should always be the case (in this particular language) that when the scanner encounters an unacceptable character it is either (a) at the beginning of a token—in which case it can delete characters until it sees one that can start a token, print an error message saying it did so, and start over; (b) immediately after a sequence of characters that comprise a complete, valid token—in which case it can simply return that token (and worry about the next character the next time it is called); or (c) immediately after a sequence of characters that comprise a prefix of a valid, but incomplete token—in which case it can delete everything it has seen so far, print an error message saying it did so, and again start over.  Examples of this final case include seeing something other than ‘=’ following a ‘:’ or ‘=’; seeing something other than a digit as the second character of a token beginning with ‘.’; or seeing something other than a digit after the ‘e’, “e+”, or “e-”, that had seemed to start the exponent part of a real number. 
  2. Extend the calculator language (scanner and parser) with explicit declarations, integer and real numbers, end-of-statement semicolons, and if and while statements, as shown in the grammar below
  3. Implement the parser error recovery mechanism of Niklaus Wirth, described in Section 2.3.5 on the textbook’s companion site (Examples 2.45 through 2.48). 
  4. Output a linearized syntax tree (AST).  Each tree node will be represented either as a (parenthesized) tuple, with a fixed number of fields, or as a (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 original 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

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. 

The initial source code for this assignment is available HERE.  As currently written, it prints a trace of predictions and matches.  You should disable that. 

Extended Language

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

P→  SL  $$
SL→  S ; SL  |  ε
S→  int id := E  |  real id := E  |  id := E  |  read TP id  |  write E
 |  if C then SL end  |  while C do SL end
TP→  int  |  real  |  ε
C→  E  RO  E
E→  T  TT
TT→  AO  T  TT  |  ε
T→  F  FT
FT→  MO  F  FT  |  ε
F→  ( E )  |  id  |  i_num  |  r_num  |  trunc ( E )  |  float ( E )
RO→  ==  |  <>  |  <  |  >  |  <=  |  >=
AO→  +  |  -
MO→  *  |  /

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

i_num  =  d+
r_num  =  ( d+ . d* | d* . d+ ) ( e ( + | - | ε ) d+ | ε )
where d stands for any decimal digit. 

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.  The new nonterminal RO is meant to suggest a “relational operator.”  Identifiers are intended to be declared before use, either with an int or real statement that provides an initial value or with a read statement that indicates a type.  The scope of each declaration extends from the declaration itself through the end of the current statement list.  As an additional extension, integers and real numbers are not intended to be mixed in expressions unless explicitly converted with trunc and float.  Note, however, that we will not be checking these semantic requirements in the current assignment (unless you choose to pursue extra credit). 

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:

    [ (int "n")
      (read "n")
      (int "cp")
      (:= "cp" "2")
      (while (> "n" "0")
        [ (int "found")
          (:= "found" "0")
          (int "cf1")
          (:= "cf1" "2")
          (int "cf1s")
          (:= "cf1s" (* "cf1" "cf1"))
          (while (<= "cf1s" "cp")
            [ (int "cf2")
              (:= "cf2" "2")
              (int "pr")
              (:= "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 for clarity only, and need not be generated by your code.  The rest of the syntax is meant to mirror the likely internal structure of an AST in C++, and should be generated by your code.  As noted above, square brackets delimit lists, which have an arbitrary number of elements.  Parentheses delimit tuples (structs), which have a fixed number of fields.  An if node, for example, has two children: a condition and a body.  The condition is a tuple containing a relational operator and its operands; the body is a list of statements that should be executed when the relation is true.  The program as a whole is likewise a statement list. 

The executable /u/cs254/bin/ast_gen on the csug machines contains an AST generator for the extended calculator grammar, which you can use to check your code.  It reads a program from standard input and prints the corresponding AST on standard output.  It was used to generate the tree above.  (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.)  Note that the generator does not perform syntax error recovery, and is therefore not a complete solution for this project.  For a syntactically correct program, however, it will display (a pretty printed version of) the output we expect you to produce.  Please ensure that the non-whitespace characters in your output match what the generator gives you; your “correctness” score will depend on this. 

Suggestions

You do not have to build the syntax tree as an explicit data structure in your program in order to generate the right output.  You are welcome to build it if you want to, though, and extra credit options 2, 3, and 5 (realized as separate, post-parsing traversals of the tree) will be easier if you do. 

We’ve given you a trivial Makefile.  You should add to it a target test that causes make to pipe sample calculator programs (of your choosing) into your parser.  This will make it easier for the TAs to reproduce your tests.  Extra credit will 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 match sees a token other than the one it expects, it will insert the expected token and continue (presumably after printing an error message).  When a recursive descent routine sees a token that is not in any of its PREDICT sets, it will delete tokens until it finds something in either its FIRST set or its FOLLOW set.

Extra Work for CSC 454

Students in 454 must implement immediate error detection:  epsilon productions should be predicted only when the upcoming token is in the context-specific FOLLOW set. 

Division of labor and writeup

As in most 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. 

Be sure to follow all the rules on the Grading page.  As with 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.  Note that only one turn-in of the main assignment 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; (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). 

Trivia Assignment

By end of day on Friday, September 23, each student should complete the T2 trivia assignment found on Blackboard. 

MAIN DUE DATE: 

Friday October 7, at noon; no extensions. 
Last Change:  03 October 2022 / Michael Scott's email address