| Due on
September 18 |
|
Accepted late by
September 19 |
|
Accepted late by
September 20 |
|
Not accepted on or after
September 21 |
| Due on
September 18 |
|
Accepted late by
September 19 |
|
Accepted late by
September 20 |
|
Not accepted on or after
September 21 |
fnDecl ::= name COLON LPAREN maybeformals RPAREN type LCURLY stmtList RCURLYfnDecl ::= name COLON LPAREN maybeformals RPAREN ARROW type LCURLY stmtList RCURLYexp ::= exp COLON exp OTHERWISE expstmt ::= loc MEANS exp OTHERWISE expFor this assignment you will use the parser-generator Bison to write a parser for the A language. The parser will simply check the syntax of the input program, and report errors if any are found. The syntax of A is described in the syntax section of the language description.
This project is intended to be an extension of the previous project code, but will be invoked via a new argument. Your code should be built and invoked via the command sequence
Where file.a is an input file to have it's syntax
checked. Note that there is NO argument to the -p option (no output is printed to stdout for this project)
The only required behavior of your project is that:
syntax error
Parse failed
Although Bison has a facility for printing error diagnostics, doing so is considered an extraneous feature for this assignment. In the starter code (at the end of the .yy file), extra error diagnostics is printed to stdout (it may have to be uncommented) in the hopes that it may be useful. However, if you find the extra output distracting, you can surpress it by redirecting stdout to /dev/null by invoking the compiler as follows:
The boilerplate for the project is already provided, so your job will really be to implement the full grammar for our language. A BNF specification for the grammar is provided here. You should implement this high-level specification in Bison to complete the project.
You are encouraged to build upon your P1 files to complete this project. However, "starter files" are provided here as a starting point: p2.tgz Note that the starter files do not constitute an exact solution to P1, but instead are enough of a solution to continue the project forward. No files with lexical errors will be used in testing from now forward.
To check if an input is part of the grammar, you may consult the P2 oracle
The A grammar in the file a.grammar is ambiguous;
it does not uniquely define the precedences and associativities of
the arithmetic, relational, equality, and logical operators.
You will need to add appropriate precedence and associativity declarations
to your Bison specification (or the appropriate levels in the productions).
Assignment is right associative.
The relational
and equality operators (such as <, <=, and !=) are
non-associative (i.e., expressions like a < b < c
are not allowed and should cause a syntax error).
All of the other binary operators are left associative.
The unary minus and not (!) operators are the highest precedence,
then multiplication and division,
then addition and subtraction,
then the relational and equality operators, then the logical
and operator (and), then the logical or operator (or), and finally the assignment operator (=).
Note that the same token (DASH) is used for both the unary and binary minus operator, and that they have different precedences; however, the A grammar has been written so that the unary minus operator has the correct (highest) precedence; therefore, you can declare DASH to have the precedence appropriate for the binary minus operator.
Bison will print a message telling you how many conflicts it found in your grammar. If the number is not zero, it means that your grammar is still ambiguous and the parser is unlikely to work correctly. Do not ignore this! Go back and fix your specification so that your grammar is not ambiguous.
Besides testing an input, you may find it helpful to print something in the Bison actions. The print output may tell you how far into the parse tree you are getting.
It is a good idea to work incrementally (see Suggestions for How to Work on This Assignment below for more detailed suggestions):
make) and run it on your
test program.
Based on student feedback, the work in this project is somewhat less than in previous semesters. As such, this component of the compiler might seem fairly trivial. Rest assured, additional functionality will be built on top of the foundation you create here.
Because writing test cases is super boring and not really the focus of this course, they are not required. However, it is still recommended that you write some test cases and follow good test-driven-development practice.
The assignment is effectively composed of completing the parser specification (the .yy file). The recommended way to proceed is to testing your parser after each change. If you are working with a partner, it is particularly important that you sync up frequently to make sure the grammar is consistent.
Start by making a very small
change to a.yy.
For example, add the rules and actions for:
type ::= BOOL type ::= VOID
Make sure that you can create and run the parser after making
this small change (using the make all and
make test targets in the directory where you are
working).
Next, add the rules needed to allow programs to include functions with no formal parameters and with empty statement lists only, and include relevant tests cases.
Add productions for the simplest kind of expressions -- just plain identifiers.
If you have a partner, divide up the statement nonterminals into two parts, one part for each person.
Each person should extend their own copy of the bison spec by adding rules for their half of the statements.
Write test inputs for your statements and your partner's statements.
After each person makes sure that their parser
works on their own statements, combine the two by
merging your grammar rules into the other person's
a.yy
Now divide up the expression nonterminals into two parts and implement those using a similar approach. Note that you will also need to give the operators the right precedences and associativities during this step (see above).
Divide up any remaining productions that need to be added, and add them.
Talk about what needs to be tested and decide together what your test suite should include.
Do not try to implement all of your nonterminals at once. Instead, add one new rule at a time to the Bison specification, make the corresponding changes to your work by augmenting your test suite or by writing a A program that includes the new construct you added, and make sure that it is parsed correctly.