5: Recognizer for "Bugs" Language
Spring 2008, David Matuszek
In this assignment I define a BNF grammar for a small programming language, which I am calling Bugs.
Your assignment is to write a recognizer (
for productions (rules) in that grammar. A recognizer is a program that,
given a stream of tokens and a nonterminal, decides whether or not that stream
of tokens is an instance of that nonterminal. The meaning of the production,
if any, is outside the scope of this assignment.
There will be no "main program." Instead, you should have JUnit tests for
every nonterminal, and every definition of that nonterminal, defined in the
grammar. When your test methods can accept every correct input, and
reject every incorrect input (either by reporting
false or throwing an exception),
you are done.
For example, one of the nonterminals is
<factor> ::= <function call> | <NAME> | <NUMBER> | "(" <expression> ")"
The stream of tokens
SYMBOL:( NUMBER:2 SYMBOL:+ NUMBER:3 SYMBOL:)
(the tokenization of the String
"(2+3)") is recognized
by this production.
There is a nonterminal called
<program>. For this assignment, there is nothing
special about this nonterminal.
This class defines an enum
Token.Type.EOF; these denote keywords, words, numbers, punctuation marks (including operators), errors, end-of-line, and end-of-file, respectively. It has two fields,
which, for easy access, are not
This is starter code for your assignment. It recognizes
. It has some helper classes which you should get familiar with (generate and read the Javadoc!), and, most importantly, it has methods
pushBack(), which hide the ugly details of using a
StreamTokenizer. You should familiarize yourself with all the "helper" methods--they are useful!
More starter code.
This is just a
RuntimeExceptionwith a more specific name.
The complete grammar is on a separate page for easy reference.
For each nonterminal
xxx in the grammar (excluding
<EOL>), you should have one
Name your methods the same as the nonterminals they recognize, but with the
is- prefix. See Recognizer.java for
examples, which has the required methods for
<multiplyOperator>, plus some very useful (private)
Provide complete JUnit tests for all public methods. Write Javadoc comments for all non-private methods.
Caution: Some definitions contains braces
} as metasymbols,
and some definitions
"}" as terminals.
Don't get these confused!
The easiest way to do this assignment is as follows:
into an actual test. For example,
<comparator>doesn't depend on anything else, but
<comparator>, so write the test code for
Thursday, February 28, before midnight. Zip up the directory
containing your files and submit the
.zip file via blackboard.