Step 2: Parser -- Due: Wednesday, September 13, 11:59pm

Introduction

Your goal in this step is to generate the parser for the project's grammar. By the end of this step your compiler should be able to take a source file as the input and parse the content of  that file returning "Accepted" if the file's content is correct according to the grammar or "Not Accepted" if it is not.

Now the scanner created in the first step will be modified to feed the parser.  Instead of printing the tokens, the scanner has to return what token is recognized in each step. The following diagram shows the basic structure of a simple compiler and hightlights the steps that will be completed at the end of this step:

Parser structure

Parser Generation Tools and Their Tutorials

Similar to the scanner case, there are tools that automatically generate parsers based on context-free grammar descriptions. More precisely, there are parser generators for two main classes of context-free grammars: LR(1) and LL(k). Please, refer to the textbook or one of the references at the end of this handout for the theory of LL(k) and LR(k) parsing.

For this project we recommend two main parser generation tools:

The Task

At this step you have to create the code for the parser of your compiler. We recommend you to do that using one of the tools described above, although the whole parser could be written manually without the help of any tool.

The following basic steps should be followed:

  1. Write the parser using one of the tools suggested above;
  2. Modify your lexer in the first step to feed tokens to parser instead of printing them;
  3. Your parser should print "Accepted" to the standard output if the input file is accepted by the language's grammar or "Not Accepted" otherwise;
  4. Make sure your parser doesn't produce any shift-reduce errors. You may loose points if you have such errors.

Note: Your output should be exactly Accepted or Not Accepted
Check the spellings and case of the letters and do not add any other characters including dots, exclamation marks, etc.

Testcases

Testcases can be downloaded here.

How to handle "Not Accepted"

         Java and ANTLR

ANTLR uses classes that implement the interface ANTLRErrorStrategy to handle errors during compilation. When an error occurs during parsing, your parser will call reportError on whatever ANTLRErrorStrategy is attached to the parser (depending on how you write your grammar, it may also call recoverInline). DefaultErrorStrategy is the class that implements the necessary methods; you can extend this class to create your own error strategy (in the example below, called CustomErrorStrategy). To set a new error strategy, use the following code:

ANTLRErrorStrategy es = new CustomErrorStrategy();
parser.setErrorHandler(es);

         C/C++ and Flex/Bison

When an error occurs in Bison/YACC, the error handler "yyerror" will be invoked. You should customize this handler to print the message and terminate the current program.

Submission

You will lose 20% of total credit if you failed to follow the following rules.

Expected Directory Structure of Your Project

See this page for instructions regarding the directory structure of your project.

Expected Behavior of Your Compiler

Assuming the above directory structure is used

         If Java and ANTLR are used, the following command will be run from the root of your project directory

         $ java -cp lib/antlr.jar:classes/ Micro <path to test cases>/test.micro
         Accepted
$

         If C/C++ and Flex/Bison are used,

         $ <build directory>./Micro path_to_your_testcases/test.micro
         Accepted
$

References

Submitting your project

First, make sure that your directory structure is correct and you are submitting only the required files. Then, follow the instructions about the turnin command and note that the step name for this step is step2 (use -p step2). Also, if you are working in a pair, submit from the same login (also called your group account) every time.