|
Blackboard
|
|
|
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 and a basic scanner and a parser. Starting from this initial code base, you must:
=’
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.
if statements, and do/check
statements, as shown in the grammar below.
[ (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. It’s a single Rust source file.
You can modify it directly, and feed it to the Rust compiler,
rustc.
Alternatively, you may wish to incorporate it into a project managed by
Rust’s cargo utility.
As currently written, the starter code prints a trace of predictions and
matches. You should disable that.
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 |readTPid|writeE
|ifC SLfi|doSLod|checkCTP → int|real| εC → E CO 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)CO → ==|!=|<|>|<=|>=AO → +|-MO → *|/
Here the new nonterminal C represents a comparison.
The new nonterminal CO is a “comparison operator.”
A do loop is intended to iterate until some
check-ed comparison inside it evaluates to false—
“check C” is analogous to “if
(!C) break” in C.
Integer and real numbers are differentiated by the presence or absence of a decimal point:
wherei_lit=d+
r_lit= (d+.d* |d*.d+ ) (e(+|-| ε )d+ | ε )
d stands for any decimal digit and e is
the actual letter e.
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::End.)
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.
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
do
check n > 0
int found := 0
int cf1 := 2
int cf1s := cf1 * cf1
do
check cf1s <= cp
int cf2 := 2
int 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
Note that while all three check statements in this program
are the first thing in their do loop, this is not required in
general: check, like C’s break, can appear
an arbitrary number of times, anywhere inside the loop.
Your AST for the primes-printing program should look like this:
[ (int "n")
(read "n")
(int "cp")
(:= "cp" "2")
(do
[ (check (> "n" "0"))
(int "found")
(:= "found" "0")
(int "cf1")
(:= "cf1" "2")
(int "cf1s")
(:= "cf1s" (* "cf1" "cf1"))
(do
[ (check (<= "cf1s" "cp"))
(int "cf2")
(:= "cf2" "2")
(int "pr")
(:= "pr" (* "cf1" "cf2"))
(do
[ (check (<= "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 memory (though it isn’t actually the
syntax Rust would use for debug printing); it should be generated by
your code.
As noted above, 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 two children: a condition
and a body. 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.
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.
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.
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.
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 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.
A variety of good resources for Rust are available on the web. You may wish to consult the following:
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.
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.
float is always of type int;
(e) the argument of trunc is always of type real;
(f) every check statement appears inside a
do statement, and every do statement
has at least one check statement that is inside it
and not inside any nested do.
for
loops, or subroutines.
Before 5pm on Friday, September 22, complete the T2 trivia assignment found on Blackboard.
