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 for the calculator language we have been developing in class.  We provide a basic scanner and parser (written in C).  Given this initial code base, you must:

  1. Translate the code we provide into C++.  Obviously, you must make any changes needed for the code to compile without errors under g++.  In addition, you must replace any calls to C libraries (e.g. for I/O) with the standard C++ equivalents (no printf!). 
  2. Extend the language with types and declarations, as shown in Figure 4.11 in the book. 
  3. Implement exception-based syntax error recovery, as described in Section 2.3.4 on the CD. 
  4. Output a syntax tree with the structure suggested (but not completely defined) in Example 4.15 and Figure 4.12.  Your output should be in linear, parenthesized form reminiscent of (but not the same as) what you generated in Assignment 1.  More specifically, every parent and its children in the tree should be represented a parenthesized list, recursively.  For example, the tree
                a
              / | \
             b  c  d
            /|  |
           e f  g
    would be represented by the string (a (b e f) (c g) d).  If you are familiar with Lisp or Scheme, this is the standard notation for trees in these languages. 

When run, your program should read a calculator program from standard input, and then 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. 

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 option 3 and 4 (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 to reproduce your tests.  Extra credit will be given to students who provide particularly well designed test mechanisms in their submission. 

When match sees a token other than the one it expects, it could simply throw a syntax_error exception.  The resulting algorithm would recover by deletion only.  An attractive alternative is to mirror Wirth's recovery algorithm and have match insert what it expects and continue (presumably after printing an error message).  You may implement either strategy.  For extra credit, try both and compare the results (see below). 

Division of labor and writeup

As in all assignments this semester, you may work alone or in teams of two.  Be sure to follow all the rules on the Grading page.  As with all assignments, use the turn-in script:  ~cs254/bin/TURN_IN.  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 TA might not immediately notice. 

Extra Credit Suggestions

  1. Experiment with mechanisms to improve the quality of your error recovery.  What are the best places to put handlers?  Does the immediate error recovery problem, described in the text, pertain to exception-based recovery?  If so, what can you do about it? 
  2. Compare deletion-only recovery (in which match throws syntax_error when it sees a token it does not expect) with a mixed strategy, in which match inserts what it expects.  Which approach seems to result in better recovery?  Why? 
  3. Implement the type checking described in Section 4.6. 
  4. After parsing and checking, execute (interpret) the calculator program.
  5. Extend the calculator language in other interesting ways.  You might, for instance, add arrays, strings, loops, or subroutines. 
  6. Generate equivalent output code in some existing language (e.g. C). 

Trivia Assignment

Before the beginning of class on Tuesday, September 20, each student should send e-mail to cs254 containing answers to the following questions: 

  1. Are you working alone or in a team?  If a team, who is your partner? 
  2. Explain two reasons why syntax error recovery is important. 
  3. Give the idiomatic C++ replacement for
        printf("%d + %d = %d\n", a, b, a+b);
  4. Write the tree from Figure 4.12 in linear parenthesized form. 

MAIN DUE DATE: 

Wednesday September 28, at 11:59pm; no extensions. 
Last Change:  19 September 2011 / Michael Scott's email address