CIT 594 Assignment 6: Recognizer for Robot Grammar
Spring 2012, David Matuszek

Enter a title before removing this line.


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. That is all that a recognizer does. The meaning of the program, if any, is outside the scope of this assignment.


Use the Tokenizer from Assignment 4. You will need to add one more TokenType, KEYWORD. Any token that matches the pattern for NAME, but is also one of the boldface words below (program, set, repeat, etc.), should be returned as a KEYWORD.

Here is the grammar you will be using:

<variable> ::= <name>

<thing> ::= <name>

<program> ::= "program" <block> { <procedure> }

<command> ::= <thought> | <action>

<thought> ::= 
            "set" <variable> <expression> ";"
          | "repeat" <expression> <block>
          | "while" <condition> <block>
          | "if" <condition> <block> [ "else" <block> ]
          | "call" <name> { <expression> }  ";"

<action> ::= 
           <move> <expression> ";"
         | "turn" <direction> ";"
         | "take" <thing> ";"
         | "drop" <thing> ";"
         | "stop" ";"

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

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

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

<condition> ::=
              <expression> <comparator> <expression>
            | "seeing" <thing>
            | "holding" <thing>
            | "not" <condition>

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

<procedure> ::= "def" <name> { <variable> } <block>

<expression> ::= [ <addOperator> ] <term> { <addOperator> <term> }

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

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

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

<multiplyOperator> ::= "*" | "/" | "%"

You should have a method for each of the nonterminals in the above grammar, with the same name as the nonterminal. For example, you should have a public boolean program(). JUnit tests are expected, as usual.

Because arithmetic expression are especially tricky to get right, I am supplying some starter code, and

Due date

Your program is due before 6am February 28. Zip up the entire directory for this project, and submit via Blackboard. Only assignments submitted via Blackboard will be accepted--any assignments emailed to me will be discarded without comment. A late penalty of 5 points per day (out of 100 points) will apply.

Because many of you are interviewing this semester, a limited number of 48-hour extensions will be available. To get an extension, email me before 5pm Friday, stating the reason you need the extension. No extensions will be granted after Friday. If you get an extension and fail to get the project in by the extended due date, late points will be counted from the original due date.