NAME
Set::FA::Element - Discrete finite automaton element for Set::FA
SYNOPSIS
use Set::FA::Element;
my $fa = Set::FA::Element->new(
id => "oddmachine",
data => \$data,
states => [ qw( none even odd ) ],
accept => [ 'odd' ],
transitions => [
[ 'none', qr/./, 'odd' ],
[ 'odd' , qr/./, 'even' ],
[ 'even', qr/./, 'odd' ]
],
actions => {
even => { exit => \&foo },
odd => { entry => \&bar }
}
);
#
# perform multiple transitions on input
#
foreach $str (@inputs) {
if ($fa->accept($str)) {
print "Accepted $str\n";
} else {
print "Rejected $str\n";
}
$fa->reset;
}
#
# step through transitions
#
while ($input) {
$input = $fa->step($input);
}
if ($fa->final) {
print "Accept\n";
} else {
print "Reject\n";
}DESCRIPTION
This module provides a simple finite automaton object. The FA object is capable of deterministic operation either by processing a scalar value or list of scalars, or by stepping through execution a single transition at a time.
CONSTRUCTOR
new PROPERTIES
A new FA object is constructed. PROPERTIES is a hash that must contain the following elements:
- states
-
The value associated with this key must be a reference to an array of scalar values representing the names of the states in the FA. At least one state must be defined. The first element is distinguished as the start state.
PROPERTIES may also contain the following optional entries:
- accept
-
This entry is a reference to a list of state names which are considered final states.
- actions
-
This element is a reference to a hash indexed by valid state names, containing references to hashes that may contain the following entries:
- entry
-
This contains a reference to a subroutine that is executed when the corresponding state is entered. The subroutine is called with a reference to the object as an argument.
- exit
-
This contains a reference to a subroutine that is executed when the corresponding state is exited. The subroutine is called with a reference to the object as an argument.
- data
-
A scalar data payload field for the FA. This field has little use outside of the Set::FA environment.
- id
-
A scalar identifier for the FA element. This field has little use outside of the Set::FA environment.
- transitions
-
This element is a value containing a reference to an list of 3-tuple lists of the form
[ CURRENT, PATTERN, NEXT ].- CURRENT
-
This is the name of the current state. The rule will only be applied when the FA is in this state.
- PATTERN
-
This is either a regular expression or a code reference. If a code reference is supplied, the subroutine is supplied a reference to the object and the input scalar as arguments and should return the unmatched portion of the input on success or undef on failure.
- NEXT
-
This is the state to which the FA transitions if PATTERN matches.
Note: it is very easy to construct a FA that doesn't terminate. See "Infinite Loops" in NOTES for a discussion of how to avoid infinite executuion.
METHODS
accept INPUT
Processes the INPUT and returns true if the FA is in an accept state when the entire input has been consumed, false otherwise.
advance INPUT
Processes the INPUT and returns the state that the FA is in after the input has been consumed.
clone
Returns a deep copy of the FA element or false on failure.
data [ SCALAR ]
If no argument is given, the current value of the data field is given. If the SCALAR argument is given, it is assigned to the data field.
final [ STATE ]
If no argument is given, returns true if the FA is in an accept state, false otherwise. If STATE is supplied as an argument; returns true if STATE is defined as an accept state, false otherwise.
id [ SCALAR ]
If no argument is given, the current value of the id field is given. If the SCALAR argument is given, it is assigned to the id field.
reset
Resets the state to the initial state.
state [ STATE ]
If no argument is given, returns the current state of the FA. If STATE is supplied, returns true if the state is defined for the FA, false otherwise.
step INPUT
Processes the INPUT for a single transition, returning the unconsumed portion of the input.
EXPORT
None by default.
NOTES
Infinite Loops
Infinite loops are an unfortunate side-effect of any useful programming language. Certain enhancements to the standard concept of FAs that have been included here make it relatively easy to shoot yourself in the foot.
First, any input for which there is no transition defined is treated as a transition to the current state. However, since variable length patterns are allowed, no input is consumed. Those familiar with theoretical computer science should recognize "no input is consumed" as a big, red warning flag. To avoid troubles, consider using a fall-through transition rule like [ 'foo', '.', 'foo' ] to consumer input for input that you don't care too much about.
Secondly, be careful with code references in transition rules. They can be very powerful in their ability to insert data into the input and even change the entire input (technically, this gives our enhanced FAs all the power of a Turing machine). But this leads to the same problem as before. Input may not be consumed or may grow. A simple fall-through rule won't help to avoid this problem, so the programmer must take care to guarantee that input is actually being consumed.
Interface
This module is considered alpha, meaning that the interface may change in future releases without backward compatibility.
AUTHOR
Mark Rogaski, <mrogaski@cpan.org>