cs152 Project Phase 2: Parser Generation Using bison

All projects can be turned in up to 1 week late. Each day the project is late, 3% will be deducted per day for up to 21%. After a week, projects will not be accepted.

Overview

In the previous phase of the class project, you used the flex tool to create a lexical analyzer for your own custom programming language that reads in an example program (from a text file) and identifies the sequence of lexical tokens in the text file. In this phase of the class project, you will create a parser using the bison tool that will check to see whether the identified sequence of tokens adheres to the specified grammar of your own language. The output of your parser will be the list of productions used during the parsing process. If any syntax errors are encountered during parsing, your parser should emit appropriate error messages.

[The Example MINI-L language is described in detail here. Use the syntax diagrams here to help you design your own grammar.]
[The example output format for the example MINI-L parser is described here.]

Bison

Bison is a tool for generating parsers. Given a specified context-free grammar for a language, bison will automatically produce an LALR(1) bottom-up parser for that language. The parser will ensure that a given sequence of tokens are ordered in such a way that they adhere to the specified grammar of the language. If the tokens fail to parse properly, then appropriate syntax error messages are outputted.

Shift/Reduce and Reduce/Reduce conflicts:
When ambiguities exist in the specified grammar, bison will emit one or more conflicts when it is run. These conflicts do not prevent bison from generating the parser from your specification, but they may unexpectedly affect how your parser behaves. A shift/reduce conflict occurs when the parser may perform either a shift or a reduce. A reduce/reduce conflict occurs when there are two or more production rules that apply to the same sequence of input tokens. In general, reduce/reduce conflicts indicate errors in the grammar (or at least serious ambiguities) and should be eliminated by modifying the grammar specification as needed. Shift/reduce conflicts, on the other hand, are more difficult to completely eliminate, especially when using the special "error" token provided by bison to handle errors. Therefore, you should try to eliminate as many shift/reduce conflicts as you can, but some shift/reduce conflicts may remain as long as they do not adversely affect the behavior of your parser. You can run bison with the -v option to generate an output file containing detailed information about each conflict.

In our department, bison is installed and can be used on lab machines and the "bolt" server.

[A brief introduction to bison can be found here.]
[The detailed manual for bison can be found here.]

Detailed Requirements

1. First, you will need to write the grammar for your custom language, based on the specification you created.
2. Create the bison parser specification file using the grammar. Ensure that you specify helpful syntax error messages to be outputted by the parser in the event of any syntax errors.
   Example: write the bison specification in a file named mini_l.y.
3. Run bison to generate the parser for your custom language using your specification. The -d flag is necessary to create a .h file that will link your flex lexical analyzer and your bison parser. The -v flag is helpful for creating an output file that can be used to analyze any conflicts in bison. The --file-prefix option can be used to change the prefix of the file names outputted by bison.
   Example: execute the command bison -v -d --file-prefix=y mini_l.y. This will create the parser in a file called y.tab.c, the necessary .h file called y.tab.h, and the informative output file called y.output.
4. Ensure that your lexical analyzer from the first phase of the class project has been constructed.
   Example: if your lexical analyzer specification is in a file called mini_l.lex, then use it with flex as follows: flex mini_l.lex. This will create the lexical analyzer in a file called lex.yy.c.
5. Compile everything together into a single executable.
   Example: compile your parser into the executable parser with the following command: gcc -o parser y.tab.c lex.yy.c -lfl. The program parser should now be available for use.

Example Usage

Suppose your parser is in the executable named parser. Then for the MINI-L program fibonacci.min, your parser should be invoked as follows:

cat fibonacci.min | parser

The list of productions taken by your parser during parsing should then be printed to the screen. As one example, the MINI-L parser output will look like this. You do not need to number each production or label each non-terminal with the corresponding production number. Your output will be different because you are writing your own programming language, and therefore have a different specification. The most important thing is that your parser should not output any syntax errors for syntactically correct programs, and your parser should output helpful syntax error messages (for at least the first syntax error) whenever syntax errors do exist in the inputted program.