Mark Rogaski > Set-FA-0.101 > Set::FA::Element

Download:
Set-FA-0.101.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.101   Source  

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>

SEE ALSO ^

Set::FA.

syntax highlighting: