Parser Assignment

The second step in building a compiler is to construct a parser. You will build upon the code from the scanner assignment, using the Bison Parser Generator to create a parser for C-Flat. It is up to you to carefully read this document and decide what all of the relevant elements of C-Flat are. Make sure that you include declarations, definitions, statements, expressions, and any other program elements. If you think that the specification is not clear, be sure to ask for a clarification.

Your program must be written in plain C (not C++) and use bison to generate the parser. You must have a Makefile such that when you type make, all the pieces are compiled and result in a binary program called cflat. make clean should also delete all temporary files, so that the program can be made again from scratch.

Your program will be invoked as follows: 

./cflat -parse sourcefile.cflat
If the input has valid C-flat syntax, then you should output nothing and exit with status 0 to indicate success. If the input does not parse correctly, then you must emit parse error: followed by a reasonable error message (see the yyerror routine) and exit with status 1. In the input does not scan correctly, then you must emit scan error: followed by a reasonable error message and exit with status 1. If your program is invoked with the -scan flag, then it must function correctly according to the Scanner Assigment. If your previous assignment had some bugs, then it is your responsibility to fix them.

Note that Bison will tell you if your grammar has errors. In particular, your grammar must not have any shift-reduce or reduce-reduce conflicts. To eliminate them, you may only re-write the production rules, you may not apply disambiguating rules or apply other "tricks" found in Bison. The purpose of this rule is to force you to understand the limitations of the LALR(1) grammar class.

A compiler has many odd corner cases that you must carefully handle. You must test your program extensively by designing and testing a large number of test cases. To encourage you to test thoroughly, we will also require you to turn in ten testing input files. Five should be named good[1-5].cflat and should be valid C-flat programs. Five should be named bad[1-5].cflat and should contain at least one parse error.

For this assignment, your grade will be based upon the following:

  • Correctness of your output on the test cases. We will construct some hidden test cases and add to them all of the test cases submitted by students. Your grade will depend upon the fraction of the tests that your parser correctly processes. In addition, for every test that you write that detects a bug in someone else's parser, you will receive one extra credit point, up to a maximum of five points. (70 percent)
  • Correctness of the grammar, including elimination of shift-reduce and reduce-reduce conflicts by the re-writing of production rules. (10 percent)
  • Correctness of the -scan option. (10 percent)
  • Good programming style. Each of the program components (main, scanner, parser) should be cleanly separated into multiple source files, complex or repetetive tasks should be broken into multiple functions, identifiers should be sensibly chosen, and the code generally commented and readable. (10 percent)

    • To turn in the assignment, copy your source files, Makefile, and testing files into your dropbox directory, which is: 

    /afs/nd.edu/coursefa.08/cse/cse40243.1/dropbox/YOURNAME/parser