CIT 594 Assignment 3: Recognizer
Spring 2004, David Matuszek


General Idea:

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

Your assignment is to write a recognizer for programs in that 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.

Supplied files:,


Here is the grammar you will be using:

<variable> ::= ":" <name>

<name> ::= <letter> { <letter> | <digit> }

<integer> ::= <digit> { <digit> }

<command> ::= <move> <expression> <eol>
            | "penup" <eol>
            | "pendown" <eol>
            | "color" <colorname> <eol>
            | "home" <eol>
            | "set" <variable> <expression> <eol>
            | "repeat" <expression> <block>
            | "while" <condition> <block>
            | "if" <condition> <block>

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

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

<block> ::= "[" <eol> { <command> } "]" <eol>

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

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

<procedure> ::= "to" <name> { <variable> } <eol> [ { <command> } ] "end" <eol>

<eol> ::= "\n"
I have already done the following rules for you:
<expression> ::= <term>
                     | <term> <add_operator> <expression>

<term> ::= <factor>
             | <factor> <multiply_operator> <term>

<factor> ::= <name>
               | <number>
               | "(" <expression> ")"

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

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


Your Tokenizer class should be almost, but not quite, ready for this assignment. You need to add one method (and the corresponding JUnit test!):

public void pushBack(Token previousToken)
Returns one Token to the tokenizer object, so that the next time you ask for the next() token you will get this one back.

This is actually fairly easy to do. Create one private Token instance variable in your Tokenizer class, and when asked for the next() token, check to see if you have one in this variable (null will mean no Token). If so, return it and set the variable to null. You will also need to modify (and test) hasNext() to take the pushback token into account.

Notes: red = 0xFF0000, orange = 0xFF9900, yellow = 0xFFFF00, green = 0x00FF00, blue = 0x0000FF, purple = violet = 0x9900FF, brown = 0x996600, black = 0x000000, white = 0xFFFFFF, gray = 0xCCCCCC, pink = 0xFFCCCC. At least, these are the colors I would use. Feel free to modify these values and/or to add extra colors.

Recommended approach:

To get started, do the following:

  1. Download my files and Import... into a new project in Eclipse (but don't import Also Import... the files you wrote for the Tokenizer assignment.
  2. To my 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> or <number>, because your tokenizer provides these.
  3. Use Eclipse to generate a TestCase for the Recognizer class. Have it generate all the test method stubs for you.
  4. Copy my methods from my file into yours. This may involve replacing some constructors or method stubs.
  5. Create an test suite.
  6. Run JUnit to ensure everything is set up correctly.

Here's why I suggest the above. If you start by importing my class, Eclipse won't add test method stubs to it (or if it will, I haven't yet discovered how). This would mean you would have to write all the test method stubs by hand, which is boring and error prone. If instead you let Eclipse generate the class, it will be correct and complete, and you can add my code simply by cutting and pasting.

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.

Due date:

Thursday, February 5, before midnight. Turn in your program via blackboard, and follow these conventions: