Project 2
Due on September 13th 11:59 PM (Accepted with no penalty).
Accepted late by September 14th 11:59 PM for 1 penalty
Accepted late by September 15th 11:59 PM for 2 penalties
Not accepted on or after September 16th 12:00 AM
Each penalty incurs a 15% stacking reduction on the project grade or uses 1 "penalty token". Penalty tokens are applied by course personnel to your maximum benefit.
  • drewno_mars.grammar - The BNF grammar to implement in Bison
  • Starter files - Files to get you started on the project, such as a skeleton bison spec to implement the parser. If you don't want to use your completed code from the previous project.
  • The oracle - Submit an input file (i.e. a source file in the Drewno Mars language, potentially with errors), and the oracle will say what the correct output should be for this project.

None yet!


For this assignment you will use the parser-generator Bison to write a parser for the Drewno Mars language. The parser will simply check the syntax of the input program, and report errors if any are found. The syntax of Drewno Mars 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

make all ./dmc <> -p

Where 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:

  • If the input file contains syntactically correct Drewno Mars code, then no output should be printed
  • If the input file contains syntactically incorrect Drewno Mars code, print the message
    syntax error
    Parse failed

    to stderr (i.e. print to std::cerr).

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:

./dmc <> -p 1> /dev/null

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.


Getting Started

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

Operator Precedences and Associativities

The Drewno Mars grammar in the file drewno_mars.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 (<, <=, 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 Drewno Mars 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):

  • Add a few grammar productions to your bison spec.
  • Write an input file (i.e. a test program) that uses the new language constructs.
  • Rebuild the parser (using make) and run it on your test program.

Suggestions for how to Work on this Assignment

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 drewno_mars.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 drewno_mars.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 Drewno Mars program that includes the new construct you added, and make sure that it is parsed correctly.