In this question, you will use a stack to implement a parser for a simple programming-like
language. Much like the Java compiler tells you if there are syntactic errors in your code, your
parser will check whether a given statement's syntax is correct or not with respect to the rules of
this simple language.
One can define the syntax of a language using substitution rules. For example, a substitution rule
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
means that whenever the term digit occurs in a rule, it can be replaced by the character '0', or the
character '1', or '2', and so on.
Rules can be recursive: for example, using the digit rule, we can define a recursive rule to
describe what a non-negative integer should be:
integer → digit | digit integer
This means that an integer is a single digit (base case), or a single digit preceding an integer
(recursive case). Here we allow an integer to start with 0, for simplicity.
We can define a variable in a similarly recursive way, namely as a sequence of letter characters.
letter → a | b | ::: | z | A | B | ::: | Z
variable → letter | letter variable
We next use integer’s and variable’s to define possible statement’s in a simple programming-
like language, which is generated by the following substitution rules:
assignment → variable = integer
bool → true | false
statement → assignment | if bool then statement else statement end
When you look at the starter code, you will see that there are two levels of string parsing that are
done. The first level splits the input string into “tokens”. The second level parses the tokens and
checks if a sequence of tokens defines a valid statement. This is the part that you will implement.
There are a few points to note about the token parsing level that is given to you. The token
parsing uses “regular expressions” rather than the recursive definition above. We chose to use
regular expressions to split tokens just because it is easy to do so in Java. The splits into tokens
are defined by the space characters. In particular, we require each assignment to be a single
token, and so an assignment cannot contain any space characters. For example, “foo=23” is a
valid assignment whereas “foo = 23” which contains spaces is not a valid assignment. The
splitter which generates the sequence of tokens from the input string would treat “foo = 23” (with
spaces) as three separate tokens rather than as one assignment token. Another point about
token parsing is that the keywords if, then, else, end, true, false are special tokens in the
language. The token parser ensures that these keywords cannot be variables within an
assignment. For example, “if=3” is not a valid assignment according to the token parser (see
isAssignment() method in LanguageTester).
For any valid statement in the language, one assignment would be executed. For the case of
an if-then-else statement, the one that is executed depends on the bool conditions. Your task,
however, is not to decide which assignment is executed. Rather, your task is to decide whether
a given input string is a valid statement or not, according to the above rules.
For example, here are some examples of valid statement’s:
x “foo=23” (with no spaces, see above)
x “if true then a=2 else b=31 end”
x “if false then if true then c=5 else d=5 end else b=31 end”
and here are some examples of invalid statement’s:
x “if=3” (invalid, keyword cannot be a variable)
x “foo = 23” (with spaces)
x “if true then a=2 else b=31” (missing end)
x “if a=2 then a=2 else b=31 end” (invalid bool)
x “if true a=2 else b=31 end” (missing then)
There are four Java classes given in the starter code:
x StringSplitter: This class implements a “lexical analyzer”, namely a StringSplitter object that
reads a string and splits it into tokens. It is fully implemented for you.
x StringStack: Implementation of the Stack ADT for non-empty strings.
x LanguageParser: A partial implementation of the (token) parser. You need to implement
the isStatement( ) method in this class.
x Tester: Used to test the correctness of your isStatement() method. The class has examples
of how to use the StringSplitter class. Your LanguageParser class will be tested with a more
extensive set of examples than what is given to you here.
As in Assignment 1, we strongly encourage you to write and share your own tester classes.
Implement the isStatement() method of LanguageParser which processes an input string. It
returns true if the input string defines a valid statement, and it returns false otherwise.
Your solution must be non-recursive, that is, your isStatement() method cannot call itself.
Your solution must use a StringStack. You may use only one StringStack object, and your
method must only do one pass over the tokens, i.e. each token will be read from the
StringSplitter object exactly once.
To make the task simpler, you are allowed to push any non-empty strings you want on the stack.
i.e. You are not limited to pushing only tokens from the language.
Submit a zipped folder A2Q1submit.zip file to the A2Q1 mycourses assignment
folder. The folder should contain your class LanguageParser.java
For your interest:
The simple language defined above is an example of what is called a context-free grammar. The
subject is very important in computer science. You will study this subject if you take COMP 330.
Also, the provided code uses Java regular expressions in a few places. Java regular expressions
are based on a more general theory of regular expressions which you will also learn about in
COMP 330. Regular expressions are commonly used in solving problems which involves text
processing and you are encouraged to learn about them.