CIT 594 Assignment 7: Recognizer for Logo Language
Spring 2014, David Matuszek

Purposes

General Idea

In this assignment I will define, using EBNF, 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 only result of a recognizer method is true if the input is grammatically correct, and false if it is not. The “meaning” of the program, if any, is outside the scope of this assignment.

Supplied files

Recognizer.zip

Details

Here is the grammar you will be using. Terminals are quoted and black, to help distinguish them from the EBNF nonterminals and metasymbols. Reminder: “|” means “or”, “[]” means optional, and “{}” means zero or more.

<program> ::= <command> { <command> } { <procedure> }
Note: If you have not already done so, follow the instructions in Notes on the Tokenizer Assignment to eliminate the need for an EOI token. If anything follows the last <procedure>, it should be reported as an error.
<command> ::= <move> <expression> <eol>
            | "penup" <eol>
            | "pendown" <eol>
            | <color> <eol>
            | "home" <eol>
            | "jump" <expression> <expression> <eol>
            | "set" <variable> <expression> <eol>
            | "repeat" <expression> <block>
            | "while" <condition> <block>
            | "if" <condition> <block> [ "else" <block> ]
            | "do" <name> { <expression> } <eol>
            
<move> ::= "forward"
         | "right"
         | "left"
         | "face"

<color> ::= "red" | "orange" | "yellow" | "green" | "cyan" 
          | "blue" | "purple" | "magenta" | "pink" | "olive" 
          | "black" | "gray" | "white"| "brown" | "tan"
          | "color" <expression> <expression> <expression>

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

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

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

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

<variable> ::= <name>

<eol> ::= <newline> { <newline> }

// I have already done the following rules for you:       
  
<expression> ::= <term> { <addOperator> <unsignedTerm> }

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

<unsignedTerm> ::= <unsignedFactor> { <multiplyOperator> <factor> }

<factor> ::= [ <addOperator> ] <unsignedFactor>

<unsignedFactor> ::= <variable>
                   | <number>
                   | "getX"
                   | "getY"
                   | "(" <expression> ")"

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

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

// The following very basic definitions should be done by your Tokenizer,
// but are included here for completeness.

<name> ::= Any sequence of letters, digits, and underscores, beginning with a letter.

<number> ::= A literal number, either integer or double.

<newline> ::= "\n"

The Tokenizer

Use your Tokenizer from a previous assignment. Include a copy of this class (and its associated tests) in your Recognizer project.

The Tokenizer should have the constructor public Tokenizer(Reader reader, Set<String> keywords). The keywords are the terminals (indicated in black and boldface in the above EBNF grammar) that the Tokenizer would otherwise report as a NAME. That is, symbols such as + and } are not keywords, but red and if are keywords.

The SyntaxException class

Just a trivial class to give a good name to the kind of exceptions we have to deal with. Implements the three usual constructors for Exception classes, but that's all.

The test classes

Should be self explanatory. AllTests runs all tests listed in it.

Cautions

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 Tokenizer files.
  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 the tokenizer provides these.
    You should have the following methods. Each will be public boolean and will take no arguments.
    Required methods Recommended methods Supplied methods 
    isProgram
isCommand
isMove
isColor
isBlock
isCondition
isComparator
isProcedure
isEol
    		 
    isPenup
isPendown
isHome
isJump
isSet
isRepeat
isWhile
isIf
isDo        
    isExpression
isTerm
isFactor
isAddOperator
isMultiplyOperator
isVariable
isNumber
  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. 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 copying and pasting.

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

  1. Test your Tokenizer and make sure it is still working.
  2. 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.
  3. Run the test. It should fail. Make certain that it does.
  4. Write the code for the method you are testing (that is, fill in the method stub in the Recognizer class).
  5. 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.
  6. Refactor to clean up the code as best you can. Test to make sure you haven't introduced any errors.
  7. Repeat until all methods have been coded.

Due date

Zip your entire Eclipse project and turn it in to Canvas before 6 a.m. Tuesday, March 25. Late programs, even if only a minute late, will be penalized 10 points for the first week. Programs later than a week may or may not be accepted for grading.