CS 12 -- Lab 5

We seek to perform parsing using a state machine. In this lab, we need to implement classes that, through good object oriented design, allow us to represent a state machine. We should then be able to write code that constructs the state machine and then uses it to parse a particular kind of input, determining whether that input can be successfully identified by the state machine.

See the solution.


Classes for a state machine

A state machine comprises states (vertices) and transitions (directed edges). We must represent each as objects in our programs. Specifically, each state contains a number of outgoing transitions, each of which correspond to particular input to the machine. We need a way to represent these states and transitions, and a strategy for traversing that structure as we process input.

First, we need classes that will represent the structure itself:

Second, we need an outer class that encapsulates the entire state machine and its interaction with the ``outside world''. Specifically, there must be an IntegerParser class. An object of this class constructs and controls a state machine, built from State and Transition objects, that is capable of parsing an integer. An IntegerParser should have one public method (in addition to a constructor) that provides its basic interface to other classes:

public boolean parse (String s)

This method should use the state machine contained by the IntegerParser object to determine if the String object to which s points is an integer, and returns the result of that parsing. Thus, this method must traverse the state machine, using one character from the String at a time, until either a failure state or a success state is achieved.


Your assignment

Write the classes described above. You may choose to write other classes not described if you find that they would be helpful. Be sure to choose good names for such classes so that their use is obvious. Also be sure to divide the tasks cleanly into the classes and their methods. Use good object oriented design -- wise use of inheritence should make the interaction with states and transitions simple.

Finally, write a main() method in IntegerParser that creates an IntegerParser object and passes a few strings to it -- some that are integers, some that are not. Show that your code correctly identifies integers, both positive and negative.


What you must submit

Once you have written and tested the various classes, you must use the cs12-submit command to submit them. Submit this assignment as lab-5 when you use the cs12-submit command.


This assignment is due on Sunday, October 26th, at 11:59 pm.

Scott F. Kaplan
Last modified: Sun Nov 5 22:48:52 EST 2000