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 we have been discussing in class. We provide a
basic scanner and parser (written in C). Given this
initial code base, you must:
printf!).
if and while
statements, as shown in the grammar below.
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.
Here is an LL(1) grammar for the calculator language, extended with
if and while statements:
P → SL $$ SL → S SL | ε S → id:= E |readid|writeE |ifC SLend|whileC SLendC → E ro E E → T TT T → F FT F → (E)|id|litTT → ao T TT | ε FT → mo F FT | ε ro → ==|!=|<|>|<=|>=ao → +|-mo → *|/
As it turns out, 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
while n > 0
found := 0
cf1 := 2
cf1s := cf1 * cf1
while cf1s <= cp
cf2 := 2
pr := cf1 * cf2
while pr <= cp
if pr == cp
found := 1
end
cf2 := cf2 + 1
pr := cf1 * cf2
end
cf1 := cf1 + 1
cf1s := cf1 * cf1
end
if found == 0
write cp
n := n - 1
end
cp := cp + 1
end
$$
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 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).
As in most 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.
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.
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?
Before the beginning of class on Tuesday, September 18, each
student should send e-mail
to cs254 containing answers to the following
questions:
scan.h define an
enum type named token.
You will need to change this definition for the current
assignment: show how.
printf("%d + %d = %d\n", a, b, a+b);
