Description

Introduction

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

like this:

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 “statement=23”

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 “foo”

x “foo=bar”

x “false”

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.

Your task

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.