CIT 594 Assignment 6: Recognizer
Spring 2009, David Matuszek

Purposes of this assignment:

General Idea:

In this assignment I will define, using BNF, a small programming language. This language is a simplified and greatly modified version of the language Logo.

Your assignment is to write a recognizer for programs in this language. A recognizer is a program that, given a stream of tokens, decides whether or not that stream of tokens constitutes a grammatically correct program in the language. The meaning of the program, if any, is outside the scope of this assignment.

Necessary files:

This program will require the use of your Tokenizer and its associated classes (from Assignment 4). It will not require your BnfTokenizer--the grammar listed here is to be hard-wired into your program, not read in as data.


Here is the grammar you will be using. This is standard BNF, with quotes around all terminals, but to help you read it a bit more easily, I've put terminals (keywords and symbols) in red and other Token types in GREEN.

<program> ::= <command> { <command> } { <procedure> }

<command> ::= <move> <expression> <end>
            | "penup" <end>
            | "pendown" <end>

            | "color" <color> <end>
            | "home" <end>
            | "set" <variable> <expression> <end>

            | "repeat" <expression> <block>
            | "while" <condition> <block>
            | "if" <condition> <block> [ "else" <block> ]

            | "call" NAME [ <expression> { "," <expression> } ] <end>

<move> ::= "forward"
         | "right"
         | "left"

<color> ::= "red" | "orange" | "yellow" | "green" | "blue"
          | "purple" | "violet" | "brown" | "black" | "white"
          | "gray" | "pink" | <expression>

<block> ::= "{" <end> { <command> } "}" <end>

<condition> ::= <expression> <comparator> <expression>

<comparator> ::= "<" | "=" | ">"

<procedure> ::= "define" NAME { <variable> } <block>

<end> ::= EOL { EOL }     

<expression> ::= <term> { <add_operator> <term> } 

<term> ::= <factor> { <multiply_operator> <factor> }

<factor> ::= <variable>
           | NUMBER
           | "(" <expression> ")"

<add_operator> ::= "+" | "-"

<multiply_operator> ::= "*" | "/"

<variable> ::= NAME


Here are the values for the various colors:

  • red = 0xFF0000
  • orange = 0xFF9900
  • yellow = 0xFFFF00
  • green = 0x00FF00
  • blue = 0x0000FF
  • purple = violet = 0x9900FF
  • brown = 0x996600
  • black = 0x000000
  • white = 0xFFFFFF
  • gray = 0xCCCCCC
  • pink = 0xFFCCCC

The Color class has a constructor that takes a single integer; this allows you to construct any other colors you like.

Recommended approach:

To get started, do the following:

  1. Create the Recognizer project, and in it a recognizer package, and in that a Recognizer class.
  2. In Eclipse, add the tokenizer package to your Java build path (Project -> Properties -> Java build path -> Projects). Do not copy those classes into your new project--remember the DRY principle.
  3. To the Recognizer class, add stubs for each method you will need. This will be one method stub for every nonterminal (<command>, <move>, etc.). Note that you do not need method stubs for NAME, NUMBER, or EOL, because your tokenizer provides these.
  4. Use Eclipse to generate a JUnit 4 TestCase for the Recognizer class. Have it generate all the test method stubs for you.
  5. Run JUnit to ensure everything is set up correctly.

I believe you will find that the easiest way to do this assignment is as follows:

  1. Pick some test method stub in and fill it with actual tests. This should be some test that doesn't depend on code you haven't yet written. For example, <comparator> doesn't depend on anything else, but <condition> depends on <comparator>, so write the test code for <comparator> first.
  2. Run the test. It should fail. Make certain that it does.
  3. Write the code for the method you are testing (that is, fill in the method stub in the Recognizer class).
  4. Test and debug, test and debug, until your test passes. If you wrote adequate tests, you should be done with this method. If your tests pass and you know the method isn't finished, add a test that fails.
  5. Repeat until all methods have been coded.

Structure of the assignment:

The above are requirements. You may have additional classes and methods as needed, and they should be documented and unit tested as appropriate.

Due date:

Thursday, March 19, before midnight.

Turn in a jar file, not a zip file. Use Eclipse's Export.. to a jar file, and follow the steps to include all source code and all code on the build path. This is necessary because we will need your Tokenizer classes in order to test your Recognizer.

The jar file should also include your generated Javadoc files.