Your parser from the last assignment accepts any program that is syntactically valid, and finds as many problems as possible in programs that have syntax errors. We would like, however, to enforce many rules that a parser and CFG alone cannot guarantee. For example, if we extend the calculator language to distinguish between integer and floating point numbers (as outlined in Section 4.6 of the textbook), then the following calculator program has a type error:
int pi pi := 3.1415926In order to enforce rules like type checking, we’ll need a tool to reject programs that are syntactically valid but violate our semantic rules. We’ll do this via traversal of an abstract syntax tree. We won’t, however, be programming in C++: for this assignment you’ll use Scheme.
We will provide you with a working parser that produces explicit parse trees. (It is, in fact, more general than you will need: it includes an LL(1) parser generator like the one you built for the previous assignment, allowing it to work with any top-down single-lookahead grammar. Your extensions will be calculator-grammar specific.)
More specifically, your task in this assignment is to:
float
routine).
This amounts to modifying the example CFG provided with the
Scheme source code.&nsbp; The current version of that grammar looks
like this:
(define calc-gram
'(("P" ("SL" "$$"))
("SL" ("S" "SL") ())
("S" ("id" ":=" "E") ("read" "id") ("write" "E"))
("E" ("T" "TT"))
("T" ("F" "FT"))
("TT" ("ao" "T" "TT") ())
("FT" ("mo" "F" "FT") ())
("ao" ("+") ("-"))
("mo" ("*") ("/"))
("F" ("id") ("num") ("(" "E" ")"))
))
integer? function
does not do what you want:
(integer? 3.0) => #t
For simplicity’s sake, you may assume that a floating-point constant
is any atom that Scheme accepts as a number, and that contains a
decimal point or an exponent. (This is still a little tricky;
see Section
6.2.4 of the Scheme R5 standard. Note in particular that
the letter ‘e’ can indicate an exponent, an exactness
specification, or a hexadecimal digit, depending on context.)
make-AST
that converts a parse
tree to an abstract syntax tree (AST).
Note that we are not specifying what the AST should look
like. You can get ideas from the text, but what’s there is
incomplete; you’ll have to flesh it out.
check-semantics that walks the
AST and enforces the following semantic rules:
trunc routine cannot be applied to an integer
value.
check-semantics routine should return a list of
all semantic errors, suitable for printing, or () (the
empty list) if the input is semantically correct. If passed
#f (the output of the parser on invalid input), your
code should return the string “semantic analysis inhibited due
to syntax error(s)”.
If everything works correctly, you should be able to type:
(check-semantics (make-AST (parse extended-calc-gram my-program)))
and see a list of errors (if any).
The initial source code for this assignment is available for download HERE. It’s about 480 lines of Scheme code. You should read most of this code carefully to understand how it works (you can skip the details of parse table construction if you like, though I think it’s kind of cool :-).
!).
We will be grading your assignment using the “Dr. Scheme”
interpreter: /u/cs254/bin/drscheme, set at the
“R5RS” language level. You can also
download GUI versions of Dr. Scheme for Windows, MacOS, or Linux,
but please be sure to set the language level correctly, and check that
your code works correctly on the csug installation.
Here are some resources to help you:
As in all assignments this semester, you may work alone or in teams of two. If you choose to work in pairs, I strongly encourage you to read each others’ code, to make sure you have a full understanding of semantic analysis.
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 TAs might not immediately notice.
for loops, while loops, or
if statements (no floating-point conditions or
bounds); nested scopes (no redefinition within a scope);
or functions (must contain a return statement;
arguments and return value must match in number and type).
interpret-AST that takes the AST and an input string as
input, and then walks the tree, accumulating values and printing
results. (You can use display
for output, even though it’s imperative.) Then wrap your routine as
follows:
(define interpret
(lambda (grammar program input)
(let* ((ast (make-AST (parse grammar program)))
(errors (check-semantics ast)))
(if (null? errors) (interpret-AST ast input) errors))))
And now you can type
(interpret my-grammar my-program my-input)
Trivia questions for this assignment can be found in Blackboard. They are due before the beginning of class on Thursday, October 4.
