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 an extended version of the calculator language discussed in the text and in class. We provide a basic scanner and parser (written in C). Given this initial code base, you must:
checkstatements, as shown in the grammar below.
a / | \ b c d /| | e f gwould 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.
Here is an LL(1) grammar for the calculator language, extended with
P → SL $$ SL → S SL | ε S →
id:= R |
R → E ET E → T TT T → F FT F →
ET → ro E | ε TT → ao T TT | ε FT → mo F FT | ε ro →
Here the new nonterminal R is meant to suggest a
As in C, a value of 0 is taken to be false; anything else is
true. The relational operators (
<> [not equal],
>=) produce either 0 or 1 when evaluated.
do loop is intended to iterate until some
check-ed relation inside it evaluates to false—
check R” is analogous to “
) break” in C.
As it turns out, if we assume that integers are unbounded, the 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 n cp := 2 do check n > 0 found := 0 cf1 := 2 cf1s := cf1 * cf1 do check cf1s <= cp cf2 := 2 pr := cf1 * cf2 do check pr <= cp if pr == cp found := 1 fi cf2 := cf2 + 1 pr := cf1 * cf2 od cf1 := cf1 + 1 cf1s := cf1 * cf1 od if found == 0 write cp n := n - 1 fi cp := cp + 1 od $$
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 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 for the TAs to
reproduce your tests. Extra credit will be given to students who
provide particularly well designed test mechanisms in their
Note that your code will employ both insertions and deletions:
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.
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.
As in most assignments this semester, you may work alone or in teams of
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
Put your write-up in a
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 is required per team, but each
student must mail in the trivia separately.
checkstatement appears inside a
dostatement, and every
dostatement has at least one
checkstatement that is inside it and not inside any nested
forloops, or subroutines.
Before the beginning of class on Wednesday, September 21, each
student should send e-mail
firstname.lastname@example.org containing answers to the following
token. You will need to change this definition for the current assignment: show how.
printf("%d + %d = %d\n", a, b, a+b);