Purposes:

• To give you more practice with Eclipse and JUnit testing
• To familiarize you with BNF grammars
• To improve your understanding of recursion
• To teach the method of recursive descent

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:

Recognizer.java, RecognizerTest.java

Details:

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"

<expression> ::= <term>
                     | <term> <add_operator> <expression>

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

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

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

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

Cautions:

• Note that the <procedure> definition contains braces and brackets as metasymbols. Do not confuse these with terminals (as in <block>)
• I'm still working on this assignment, so there may be some (hopefully minor) changes in the grammar if I discover problems. Check the course web page for updates.

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... Recognizer.java into a new project in Eclipse (but don't import RecognizerTest.java). 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 RecognizerTest.java file into yours. This may involve replacing some constructors or method stubs.
5. Create an AllTests.java 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 RecognizerTest.java 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 RecognizerTest.java 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 RecognizerTest.java 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:

• Name your submission file as userid-n, where userid is your user id and n is the assignment number (for example, matuszek-3).
• Put your files in a single directory, and zip up that directory.
• Do not include your javadoc files.