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.
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:
States: There needs to be a State class that will represent being at a particular vertex in the graph. Note that a generalized state does not need to store any information. It's only relevence is how it is linked to other states. Thus, it must contain an arbitrary number of outgoing transitions.
Note, however, that there are a couple of ``special'' kinds of states. Specifically, each state machine has a starting point, and should thus be represented by an InitialState object. Similarly, there must be at least one failure state that should be represented by a FailureState object.
An InitialState should be the kind of state that is created and used to begin processing. There should be only one in a state machine, and no transition should point at an initial state.
Transitions: There must be a Transition class whose objects are used to represent the directed edges in a state machine graph. Each transition contains both the symbols for which that transition applies and the target state to which that transition leads.
Again, there are special kinds of transitions. For example, there are default transitions (which we have labeled as the ``otherwise'' transitions) which are taken from a state iff no other transition from that state applies to the current input symbol. A DefaultTransition or OtherwiseTransition class should therefore behave somewhat differently than normal transitions which are used only if the input symbol applies.
There may be other kinds of special transitions. Consider that there are common groups of input symbols that you may want to indentify in a number of places within a given state machine. For example, a DigitTransition could be a transition that applies when the input symbol is from 0 through 9.
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.
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.
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.