Task Design a program that discovers whether a user
presses a sequence of alphanumeric keys according to some regular
expression or finite state machine. Running the program on the
specification of a regular expression should open a 100 x 100 window and
accept key events. The window should be white for the initial
state, yellow for intermediate states (not initial, not final),
green when the sequence is an acceptable string (final state),
and red when a mismatch has been discovered. As soon as the
sequence of key events satisfies the given regular expression, the program
should shut down with a positive acknowledgment. Conversely, the program
should stop with a negative acknowledgment when a key event violates the
given specification.
Example Assume that the specified regular expression is
equivalent to
a(b|c)*d
Then (1) key sequences such as "abbbcd" and "ad" are accepted, (2) key
sequences such as "b" and "d" are unacceptable, and (3) key sequences
such as "abc" and "abbb" are strict prefixes.
Configuration The program is configured with a
"program" in a domain-specific programming language (DSL) for
the specification of finite state machines (FSM). Your program should
read the specification from a file whose path is given the command line.
To keep the specification programming-language neutral, the DSL is a
dialect of XML (eXtensible Markup Language). Here is the formal grammar:
FSM = <fsm initial=State>
<final label=State></final> ...1
<transition current=State next=State>
<action key=AlphaNumeric></action> ...1
</transition> ...1
</fsm>
State = String
AlphaNumeric = the one-char strings 'a' thru 'z', 'A' thru 'Z', and '0' thru '9'
The notation ...1 means "a sequence of at least one of the
preceding XML elements".
Informally, a FSM specification consists of a single XML element that
specifies the initial state via an "initial" attribute; the final states
and transition between states are listed as the content of the elements,
i.e., as sequences of elements. The "final" XML element just names the
"accepting" states of the FSM. Each transition element specifies the
origin and destination states via attributes and the alphanumeric keys
that enable the transition as a sequence of content elements.
Here are two sample specifications for
a(b|c)*d:
<fsm initial="a">
<final label="d"></final>
<transition current="a" next="bc">
<action key="a"></action>
</transition>
<transition current="bc" next="bc">
<action key="b"></action>
<action key="c"></action>
</transition>
<transition current="bc" next="d">
<action key="d"></action>
</transition>
</fsm>
|
<fsm initial="a">
<final label="d" />
<transition current="a" next="bc">
<action key="a" />
</transition>
<transition current="bc" next="bc">
<action key="b" />
<action key="c" />
</transition>
<transition current="bc" next="d">
<action key="d" />
</transition>
</fsm>
|
Your program should print a reasonably informative, one-line error message
if anything goes wrong with the configuration step.
Deliverable Send in a tar.gz bundle via email that
contains a single directory. When I unpack the bundle on the standard
departmental LINUX boxes (login-linux is a good example), I expect to be
able to cd into this directory and run your solution as
$ ./1.xyz 1.xml
where 1.xml is a file I will supply.