In the previous project, you each wrote a lexical analyzer that took an input file and divided it into tokens. Now, you will write a parser that will test those tokens for syntactic correctness. Using BNF (Backus-Naur Form), you will establish a set of grammar rules that define the syntax of our language. A simple example of a pair of BNF rules is:
declaration : TYPE ID ';' | TYPE ID '=' value ';' value : VAL_LITERAL | ID
You must design and implement a grammar that can determine
if a "Good" program is syntactically correct. For this program, you need to
write a function called "parse_string", that can parse its string argument.
If the program is correct, the program should only return
If your program cannot be parsed (for example if there is a problem on line 3),
you should raise a SyntaxError.
If your program has illegal name declarations/usages, you should raise a
You must also implement a symbol table, a simple data structure that will track all of the identifiers that have been declared in the source program that you are compiling. Every time a variable is declared, it should be entered into the symbol table, and every time a variable is used, it should be verified with the symbol table. There are two types of errors that your program needs to identify related to symbol tables:
my_varis used without being declared, your compiler raise a NameError.
var1was declared on line 2, but it's being redeclared on line 5, your compiler raise a NameError.
As with Project 1, your compiler should end after the first error is encountered.
Legal types of expressions that your compiler should accept include:
var1 = 7 + var2 * random(6);
val var3 = (var1 + 76) * 4;
print(var1, var2 + 42);
string are all
legal types, this project will only be testing the use of
In Project 4 (when we learn type checking) other types will be used as well.
The mathematical operations that expressions in your compiler should be able to handle are:
Note that when assignments and compound assignments can be included
inside of mathematical expressions they will (when fully implemented in
Project 3) return the value of the variable being assigned to.
a=(b=2); is a legal statement that assigns
b to the value 2.
The random(expr) command can be used as a value in a mathematical expression and (starting Project 3) will produce a random int x where 0 <= x < expr.
The print command should be able to take one or more of arguments (including expressions) separated by commas.
We have put a reference parser executable named "project2_parser" in your project directory for testing purposes. It takes one argument a "good" file to compile.
When you hand in your program, you must include: