Project: Program and Statement Parse

Objectives

  1. Familiarity with writing a recursive-descent parser (for the BL language).
  2. Familiarity with writing layered secondary methods (parse for Program and parse and parseBlock for Statement).
  3. Familiarity with developing and using specification-based test plans.

The Problem

The problem is to complete and carefully test an implementation of a recursive-descent parser for the BL language. This is a fundamental piece of the BL compiler. The parser must follow the context-free grammar (CFG) for the BL language.

As an example of the expected behavior of your parser and the kind of error messages it should generate, a program is available that parses a BL program and pretty prints it if it is syntactically valid, otherwise it prints an error message. To run the program open a terminal window and type the command /class/software/bin/bw-parser < input.bl where input.bl is the name of a BL file in the current directory.

Setup

Only one member of the team should follow the steps to set up an Eclipse project for this assignment. The project should then be shared with the rest of the team by using the Subversion version control system as learned in the Version Control With Subversion lab.

To get started, import the project for this assignment, BLParser, from the BLParser.zip file available at this link. If you don't remember how to do this, see these Setup instructions from an earlier project.

Method

  1. Start by implementing Program1Parse1. Carefully review the Program1Parse1.java skeleton in the src folder. In particular, pay attention to the public instance method parse (corresponding to the program non-terminal symbol in the grammar and whose contract is available here) and to the private static method parseInstruction (corresponding to the instruction non-terminal symbol in the grammar and whose contract is provided in the file itself). Implement the two methods using the grammar as a guide (as discussed in class and in Recursive-Descent Parsing).
    There are several points to keep in mind:
    • The non-terminal symbols program and instruction are not defined recursively in terms of themselves or of each other; therefore, recursion is not called for here.
    • Both program and instruction's rewrite rules refer to the block non-terminal, which is processed by the Statement secondary method parseBlock (see here for the contract). You will need to use this method in implementing Program1Parse1 and, since Program1Parse1 extends Program1, which in turn uses Statement1, you will call Statement1's version of parseBlock and not the one you will implement as part of this project. The advantage of this is that you will be able to develop, test, and debug the two parts of the parser independently.
    • parse must replace the distinguished parameter this.
    • Your implementation must check for syntax errors as implied by each method's contract. To perform each check use the Reporter.assertElseFatalError(boolean, String) utility method, which, if the given boolean is false, generates an error that terminates the program printing the given String as a message, and if the boolean is true, simply returns without doing anything else. This means that as soon as the parser finds an error, it quits after reporting the error. It does not attempt to continue parsing to catch other possible errors. You will also find useful static methods (e.g., isCondition and isIdentifier) in the Tokenizer utility class.
    • In addition to being responsible for catching any syntax errors in the input BL source program (i.e., determining whether the source program is in the language generated by the context-free grammar for the BL language), your parser is also responsible for checking the following conditions (that cannot be expressed in a context-free grammar) and if they are not satisfied, an error message should be produced and the parser should terminate (again using Reporter.assertElseFatalError(boolean, String)):
      1. The identifier at the end of the program must be the same as the identifier at the beginning of the program.
      2. The identifier at the end of each new instruction definition must be the same as the identifier at the beginning of the definition.
      3. The name of each new user-defined instruction must be unique, i.e., there cannot be two user-defined instructions with the same name.
      4. The name of each new user-defined instruction must not be the name of one of the primitive instructions, i.e., move, turnleft, turnright, infect, or skip.
      The parser is not responsible for making sure that no undefined instruction is called in the program nor that no recursion is present in the program. These conditions can be tested much more easily in the code generation phase, so that's where they will be checked.
  2. In the test folder, carefully review the JUnit test fixtures ProgramTest and Program1Parse1Test. They provide the set-up to systematically test the Program parse method you implemented. ProgramTest provides example test cases for two distinct situations: (1) testing that the parser is correctly parsing valid input and (2) testing that the parser catches errors in invalid input. The second example shows a new feature of JUnit and that is the ability to write test cases that succeed only if the method under test actually generates a specific kind of error (in this case, something called RuntimeException). So if the method under test fails to generate the appropriate error, the test case fails and you will know that your parser is not catching an error that it should. You should create as many test inputs and corresponding test cases to build your confidence that your parser can handle both situations. An additional way to test your implementation is to use the main method included in Program1Parse1.java but this is not a replacement for a systematically designed JUnit test fixture.
  3. Next you need to implement Statement1Parse1. Carefully review the Statement1Parse1.java skeleton in the src folder. In particular, pay attention to the public instance methods parseBlock and parse (corresponding to the block and statement non-terminal symbols in the grammar and whose contracts are available here) and to the private static methods parseIf, parseWhile, and parseCall (corresponding to the if, while, and call non-terminal symbols in the grammar and whose contracts are provided in the file itself). Implement the five methods using the grammar as a guide.
    There are several points to keep in mind:
    • parseBlock parses a (maximally long) sequence of statements from the input and constructs a BLOCK Statement.
    • parse, instead, parses a single statement from the input and constructs an IF or IF_ELSE or WHILE or CALL Statement.
    • This part of the project does involve (indirect) recursion because block is defined in terms of statement, which is defined (through if and while's rules) in terms of block.
    • Both parseBlock and parse must replace the distinguished parameter this.
    • Again your implementation must check for syntax errors as implied by each method's contract using Reporter.assertElseFatalError(boolean, String). The parser should quit as soon as the first error is found.
  4. Testing the Statement part of the parser is done the same way as the Program part. In the test folder, carefully review the JUnit test fixtures StatementTest and Statement1Parse1Test. They provide the set-up to systematically test the Statement parse method you implemented. StatementTest provides example test cases for two distinct situations: (1) testing that the parser is correctly parsing valid input and (2) testing that the parser catches errors in invalid input. In this case, you have two methods to test (parse and parseBlock). You should create as many test inputs and corresponding test cases to build your confidence that your parser can handle both situations. An additional way to test your implementation is to use the main method included in Statement1Parse1.java but this is not a replacement for a systematically designed JUnit test fixture.
  5. When you and your teammate(s) are done with the project, decide who is going to submit your solution. That team member should select the Eclipse project BLParser (not just some of the files, but the whole project) containing the complete group submission, create a zip archive of it, and submit the zip archive to the Carmen dropbox for this project, as described in Submitting a Project. Note that you will only be allowed one submission per group, that is, your group can submit as many times as you want, but only the last submission will be on Carmen and will be graded. Under no circumstance will teammates be allowed to submit separate solutions. Make sure that you and your partner agree on what should be submitted.

Additional Activities

Here are some possible additional activities related to this project. Any extra work is strictly optional, for your own benefit, and will not directly affect your grade.

  1. Test your Program and Statement parsers together with your implementations of Program and Statement kernels. Here is one way to do it. It might be useful to draw some component diagrams showing the various dependencies (implements, extends, or just uses) so that you understand what is going on.
    1. From the previous project, copy your Program2 and Statement2 components into the current project.
    2. In the current project, make copies of your Program1Parse1 and Statement1Parse1 components and name them Program2Parse1 and Statement2Parse1, respectively.
    3. Edit the Program2Parse1 component so that it extends Program2 (instead of Program1).
    4. Edit the Statement2Parse1 component so that it extends Statement2 (instead of Statement1).
    5. Edit the Program2 component so that it uses Statement2Parse1 (instead of Statement1).
    6. Test the parse method in Program2Parse1. It will use your implementations of both parsers and both kernels.