CISC323: Introduction to Software Engineering (Winter 2003)

Assignment 3 (Design Patterns)

Due Fri, March 14

The purpose of this assignment is to give you practise with design patterns, in particular, the visitor pattern. Other concepts that you will learn about along the way are grammars, parsing, and parser generation.

Introduction

Grammars Grammars define the syntactic structure of languages. Computer languages are defined typically through grammars given in Backus-Naur Form (BNF). The following grammar in BNF defines the set of all arithmetic expressions over the natural numbers and the operations +, -, *, and /.

<expr>  ::= <sum> 
<sum>   ::= <term> ( ("+" | "-") <term> )*
<term>  ::= <atom> ( ("*" | "/") <atom> )*
<atom>  ::= <nat> | "(" <sum> ")"
<nat>   ::= <digit> ( <digit> )*
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

The grammar consists of productions. Each production has a left-hand side and a right-hand side, separated by ::=. The right-hand side is a finite, possibly empty sequence of three different kinds of symbols:

non-terminal symbols (enclosed in angle brackets < >)
terminal symbols (enclosed in quotes " ")
meta symbols

The above grammar contains the following

terminal symbols: "+", "-", "*", "/", "(", ")", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"
non-terminal symbols: <expr>, <sum>, <term>, <atom>, <nat>, <digit>
meta symbols: (, |, ), *

The terminal symbols are elements of the language that is being defined. The non-terminal and meta symbols are elements of the grammar. Non-terminal symbols can be thought of as place holders for sequences of terminal symbols. Meta symbols allow one production to summarize a whole set of productions. The meta symbol | denotes alternatives while the meta symbol * allows repetition of the previous sequence 0 or more times. For instance, the production

<atom>  ::= <nat> | "(" <sum> ")"

stands for the two productions

<atom>  ::= <nat>
<atom>  ::= "(" <sum> ")"

The production

<nat>   ::= <digit> ( <digit> )*

stands for the infinite set of productions

<nat>   ::= <digit> 
<nat>   ::= <digit>  <digit> 
<nat>   ::= <digit>  <digit> <digit>
...

The production

<sum> ::= <term> ( ("+" | "-") <term> )*

stands for the infinite number of productions:

<sum> ::= <term> 
<sum> ::= <term> "+" <term>
<sum> ::= <term> "-" <term>
<sum> ::= <term> "+" <term> "+" <term>
<sum> ::= <term> "+" <term> "-" <term>
<sum> ::= <term> "-" <term> "+" <term>
<sum> ::= <term> "-" <term> "-" <term>
<sum> ::= <term> "+" <term> "+" <term> "+" <term>
...

Every grammar typically contains a non-terminal symbol that is not contained in the right-hand side of any production. That non-terminal is called start symbol. The above grammar has the start symbol <expr>.

Parse trees, parsing, parsers, and parser generators Given a grammar, we can determine which words the grammar generates. We do that by building a parse-tree. A parse-tree is build from the start symbol of the grammar by choosing a leaf in the tree that contains a non-terminal, finding a production that has that non-terminal on the left-hand side, and then adding the terminal and non-terminal symbols occurring on the right-hand side of that production as new children of that leaf. The parse-tree is complete if all its leaves contain terminal symbols only. In that case, the sequence of leaves read from left to right constitutes the expression generated by the tree. An expression is said to be syntactically correct with respect to some grammar if there is a parse tree for that expression that was built using the grammar. The process of building a parse tree for an expression is also called parsing. The following picture illustrates the process of parsing by creating a parse tree for the expression 2 * 3 + 4.

A parser is a tool that takes a sequence of symbols as input and then attempts to find a parse tree for it. Every compiler contains a parser. If program P is contained in file f, the parser opens f, reads in the sequence of characters in f, and attempts to build a parse tree for P using the grammar of the programming language. If P is syntactically correct, its parse tree is handed off to the later stages of the compiler like the optimizer and code generator. If P is not syntactically correct, an error is reported. A parser generator is a tool that takes a grammar as input and generates a parser for the language defined by the grammar. In other words, it outputs a parser for that language. Parser generators are used a lot in industry. Examples for parser generators include YACC (generates C code), Cup (generates Java code), and JavaCC (generates Java code).

Question 1 For each of the following expressions, decide whether it is syntactically correct with respect to the grammar above. If your answer is positive, also draw the parse tree of that expression.

2 + 3 * 4 + 5
(2 * (3 / 3)) + 4
-222 + 1
((222))

JavaCC In this assignment, you will be given code that you will have to extend. The code contains a parser. That parser was generated using the parser generator JavaCC (Java Compiler Compiler). The parse tree created by the parser supports the visitor pattern. For this assignment, you don't need to run JavaCC. You just use the parser. If you're interested, here's more information on JavaCC.

Main Part

First, download the code:

For Solaris/Unix/Linux users: Download the code A3Code.tar.gz into some directory d. Unpack it using gunzip A3Code.tar.gz and tar xfv A3Code.tar. Add d to your classpath.
For Windows users: Download A3.zip and unzip it. Look here for instructions on how to get the code to run in JBuilder. Look here for instructions on how to get the code to run in Ready To Program.

The code contains a parser for our arithmetic expressions generated by JavaCC. Moreover, it contains a toplevel driver program ExprMain.java. When you invoke that program, it will first prompt you for an expression. If the input expression is not syntactically correct with respect to the grammar given above, the parser raises an ParseException, outputs an appropriate error message and terminates. If the input expression is syntactically correct, the program will then output a menu of of 6 actions and ask you to input the corresponding number. The first 2 actions are already implemented, the last 4 are not. For each of the first 2 actions the code contains a visitor that performs that action. The first 2 actions are:

Print: The expression is just printed back on the screen. Implemented by PrintVisitor.java.
Count parentheses: The number of opening and closing parentheses in the expression is counted and output. Implemented by CountParensVisitor.java.

After you have selected an action, the program will then perform that action by invoking the corresponding visitor on the parse tree of the expression. Note that each visitor implements the interface in Visitor.java.

Question 2 It is your task to extend that driver program ExprMain.java to perform the final 4 actions on the input expression. More precisely, for each of the following tasks you have to write a visitor that implements the interface in Visitor.java and performs that task:

Write a visitor CountNestingVisitor that counts and outputs the maximal nesting of parentheses in the expression. The nesting of a number in an expression is the number of parentheses that it is inside of. The maximal nesting of an expression e is the maximum of the nestings of all numbers in e. For instance, when run on the expression (2 * (3 + 1)) - (3 - 1) your visitor should print something like:
```
      Maximal nesting of parentheses in expression: 2
      
```
Write a visitor CountOpsVisitor that counts and outputs the number of operators in the expression. For instance, when run on the expression (2 * (3 + 1)) - (3 - 1) your visitor should print something like:
```
      Number of operators in expression: 4
      
```
Write a visitor LookForDivZeroVisitor that outputs true if the expression represented by the parse tree contains a division by zero. You don't need to evaluate any subexpressions. The visitor should only determine whether the expression contains a division that is immediately followed by a zero. For instance, when run on the expressions (2 * (3 + 1)) / (3 - 3), (2 * (3 + 1)) / (0), or 3 / (4 - 4) your visitor should print something like:
```
      There are no occurences of division by zero in the expression
      
```
However, when run on 2 + 4 / 0 - 3 your visitor should print something like
```
      There are occurences of division by zero in the expression
      
```
Write a visitor EvaluateVisitor that evaluates the expression and outputs its value. For instance, (2 * (3 + 1)) - (3 - 1) your visitor should print something like
```
      The value of the expression is: 6
      
```
You should interpret the operators +, -, *, and / by the corresponding Java operators on integers. For instance, the evaluation of 3 / 2 should return 1.

Hints

Start by looking at the visitors PrintVisitor, and CountParensVisitor. Copy and modify the code appropriately.
Since your visitors will operate on the trees returned by the parser, you will have to understand their structure. A class diagram that identifies the objects that make up a parse tree and their relationships is here [pdf, ps].
Each of the visitors can be implemented in less than 150 lines of code. So, if you find yourself writing a lot of code, chances are your implementation is unnecessarily complicated.
You only need to create new visitors and add the corresponding invocations in ExprMain.java. You should not add or modify any other classes.
You may find the following Java constructs useful: getClass returns the type of an object. For instance,
```
      System.out.println("class: " + n.getClass());
      
```
would print the type of the node n. Java also offers the instanceof infix predicate that returns true if an object has a given type. For instance,
```
      if (n instanceof T) System.out.println("yes");
      else System.out.println("no");
      
```
prints "yes" if n is of type T, and "no" otherwise.
Whenever you're unsure about, for instance, the Java syntax, or which methods are available on a given type, the Java API documentation is a good place to look. Make sure you use the documentation of your version of Java. A link to the API documentation of Java 1.4 is here.

Hand in

Completed assignment coversheet
For Question 1: Yes/no answers and drawing of parse tree if answer is positive.
For Question 2: Listing of all your visitor classes and of the toplevel driver ExprMain.java.

Juergen Dingel
Last modified: Thu Feb 20 09:07:45 EST 2003