CIT 594 Assignment 6: Robot Grammar
CIT 594, Spring 2005


General Idea:

We're going to develop a simple little language to control a software "robot." The robot has certain commands it can follow, such as moving and turning, and certain tests it can perform, such as testing what is in front of it. In this assignment I will define, using BNF, the programming language for this robot.

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.


You will need a simple tokenizer. StringTokenizer can be used for this purpose, if you use a simple decorator class to add the ability to classify tokens and to push back unwanted tokens. The kinds of tokens you will need to recognize are:

As you can see, there is nothing fancy about the tokenizer; don't make it complicated. Do write some JUnit tests for it, though.

Here is the grammar you will be using:

<variable> ::= <name>

<object> ::= <name>

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

<command> ::=
              <move> <expression> <eol>
            | "turn" <direction> <eol>
            | "take" <object> <eol>
            | "drop" <object> <eol>
            | "set" <variable> <expression> <eol>
            | "repeat" <expression> <block>
            | "while" <condition> <block>
            | "if" <condition> <block> [ "else" <block> ] 
            | "stop" <eol>

<move> ::= "forward" | "back"

<direction> ::= "right" | "left" | "around"

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

<condition> ::=
              <expression> <comparator> <expression>
            | "seeing" <object>
            | "holding" <object>

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

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

<eol> ::= "\n" { "\n" } 
<expression> ::= <term> { <add_operator> <term> }

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

<factor> ::=
               | <integer>
               | "distance"
               | "(" <expression> ")"

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

<multiply_operator> ::= "*" | "/" | "%"
JUnit tests are expected, as usual.

Due date:

Thursday, March 3, before midnight.