[Perl-flat-cvs-notify] blokhead/lib/FLAT DFA.pm,1.1,1.2 FA.pm,1.7,1.8 NFA.pm,1.6,1.7 Regex.pm,1.3,1.4

[<per...@li...>]

Update of /cvsroot/perl-flat/blokhead/lib/FLAT
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv27791/lib/FLAT

Modified Files:
	DFA.pm FA.pm NFA.pm Regex.pm 
Log Message:
POD stubs for all public modules, with all method definitions

updated Regex.pm for clearer handling of "[foo]" extended characters..
  this really needs to be made uniform across all modules, so we always
  handle input strings, alphabets the same way



Index: DFA.pm
===================================================================
RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/DFA.pm,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** DFA.pm	22 Feb 2006 04:58:23 -0000	1.1
--- DFA.pm	24 Feb 2006 06:20:25 -0000	1.2
***************
*** 87,88 ****
--- 87,105 ----
  
  1;
+ 
+ __END__
+ 
+ =head1 NAME
+ 
+ FLAT::DFA - Deterministic finite automata
+ 
+ =head1 SYNOPSIS
+ 
+ A FLAT::DFA object is a finite automata whose transitions are labeled
+ with single characters. Furthermore, each state has exactly one outgoing
+ transition for each available label/character.
+ 
+ =head1 USAGE
+ 
+ FLAT::DFA is a subclass of FLAT::NFA and its objects provide the same
+ methods.

Index: NFA.pm
===================================================================
RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/NFA.pm,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** NFA.pm	24 Feb 2006 01:04:52 -0000	1.6
--- NFA.pm	24 Feb 2006 06:20:25 -0000	1.7
***************
*** 271,275 ****
  }
  
- ##########
- 
  1;
--- 271,305 ----
  }
  
  1;
+ 
+ __END__
+ 
+ =head1 NAME
+ 
+ FLAT::NFA - Nondeterministic finite automata
+ 
+ =head1 SYNOPSIS
+ 
+ A FLAT::NFA object is a finite automata whose transitions are labeled
+ either wtih characters or the empty string (epsilon).
+ 
+ =head1 USAGE
+ 
+ In addition to implementing the interface specified in L<FLAT>, FLAT::NFA
+ objects provide the following NFA-specific methods:
+ 
+ =over
+ 
+ =item $nfa-E<gt>epsilon_closure(@states)
+ 
+ Returns the set of states (without duplicates) which are reachable from
+ @states via zero or more epsilon-labeled transitions.
+ 
+ =item $nfa-E<gt>trace($string)
+ 
+ Returns a list of N+1 arrayrefs, where N is the length of $string. The
+ I-th arrayref contains the states which are reachable from the starting
+ state(s) of $nfa after reading I characters of $string. Correctly accounts
+ for epsilon transitions.
+ 
+ =back

Index: Regex.pm
===================================================================
RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/Regex.pm,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** Regex.pm	21 Feb 2006 20:43:09 -0000	1.3
--- Regex.pm	24 Feb 2006 06:20:25 -0000	1.4
***************
*** 100,102 ****
  __END__
  
! TODO: documentation
--- 100,171 ----
  __END__
  
! =head1 NAME
! 
! FLAT::Regex - Regular expressions
! 
! =head1 SYNOPSIS
! 
! A FLAT::Regex object is a regular expression.
! 
! =head1 USAGE
! 
! In addition to implementing the interface specified in L<FLAT>, FLAT::Regex
! objects provide the following regex-specific methods:
! 
! =over
! 
! =item FLAT::Regex-E<gt>new($string)
! 
! Returns a regex object representing the expression given in $string. C<|>
! and C<+> can both be used to denote alternation. C<*> denotes Kleene star, and
! parentheses can be used for grouping. No other features or shortcut notation
! is currently supported (character classes, {n,m} repetition, etc).
! 
! Whitespaces is ignored. To specify a literal space, use C<[ ]>. This syntax
! can also be used to specify atomic "characters" longer than a single
! character. For example, the expression:
! 
!   [foo]abc[bar]*
! 
! is treated as a regular expression over the symbols "a", "b", "c", "foo",
! and "bar". In particular, this means that when the regular expression is
! reversed, "foo" and "bar" remain the same (i.e, they do not become "oof" and
! "rab").
! 
! The empty regular expression (epsilon) is written as C<[]>, and the null
! regular expression (sometimes called phi) is specified with the C<#>
! character. To specify a literal hash-character, use C<[#]>. Including
! literal square bracket characters is currently not supported.
! 
! =item $regex-E<gt>as_string
! 
! Returns the string representation of the regex, in the same format as above.
! It is NOT necessarily true that
! 
!   FLAT::Regex->new($string)->as_string
! 
! is the same as $string, especially if $string contains unneeded whitespace
! or redundant parentheses.
! 
! =item $regex-E<gt>as_perl_regex
! 
! Returns an equivalent Perl regular expression. The Perl regex will NOT be
! anchored to the beginning and end of the string. In particular this means
! that
! 
!   $string =~ $regex->as_perl_regex
! 
! and
! 
!   $regex->contains($string)
! 
! may not be equivalent.
! 
! The Perl regex will not contain capturing parentheses. "Extended" characters
! that are written as "[stuff]" in FLAT regexes will be written without the
! square brackets in the corresponding Perl regex. So the following:
! 
!   FLAT::Regex->new("[foo][bar]*")->as_perl_regex
! 
! will be equal to "(?:foo(?:bar)*)".
! =back

Index: FA.pm
===================================================================
RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/FA.pm,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** FA.pm	23 Feb 2006 19:46:12 -0000	1.7
--- FA.pm	24 Feb 2006 06:20:25 -0000	1.8
***************
*** 304,305 ****
--- 304,463 ----
  
  1;
+ 
+ __END__
+ 
+ =head1 NAME
+ 
+ FLAT::FA - Base class for regular finite automata
+ 
+ =head1 SYNOPSIS
+ 
+ A FLAT::FA object is a collection of states and transitions. Each state
+ may be labeled as starting or accepting. Each transition between states
+ is labeled with a transition object.
+ 
+ =head1 USAGE
+ 
+ FLAT::FA is a superclass that is not intended to be used directly. However,
+ it does provide the following methods:
+ 
+ =head2 Manipulation & Inspection Of States
+ 
+ =over
+ 
+ =item $fa-E<gt>get_states
+ 
+ Returns a list of all the state "names" in $fa.
+ 
+ =item $fa-E<gt>num_states
+ 
+ Returns the number of states in $fa.
+ 
+ =item $fa-E<gt>is_state($state_id)
+ 
+ Returns a boolean indicating whether $state_id is a recognized state "name."
+ 
+ =item $fa-E<gt>delete_states(@states)
+ 
+ Deletes the states given in @states and their corresponding transitions. The
+ remaining states in the FA may be "renamed" (renumbered)! Return value not
+ used.
+ 
+ =item $fa-E<gt>add_states($num)
+ 
+ Adds $num states to $fa, and returns a list of the new state "names."
+ 
+ =item $fa-E<gt>get_starting
+ 
+ =item $fa-E<gt>get_accepting
+ 
+ Returns a list of all the states which are labeled as starting/accepting,
+ respectively.
+ 
+ =item $fa-E<gt>set_accepting(@states)
+ 
+ =item $fa-E<gt>unset_accepting(@states)
+ 
+ =item $fa-E<gt>set_starting(@states)
+ 
+ =item $fa-E<gt>unset_starting(@states)
+ 
+ Sets/unsets a list of states as being labeled starting/accepting,
+ respectively.
+ 
+ =item $fa-E<gt>is_starting($state)
+ 
+ =item $fa-E<gt>is_accepting($state)
+ 
+ Returns a boolean indicating whether $state is labeled as starting/accepting,
+ respectively.
+ 
+ =item $fa-E<gt>prune
+ 
+ Deletes the states which are not reachable (via zero or more transitions)
+ from starting states. Returns a list of the "names" of states that were
+ deleted.
+ 
+ =back
+ 
+ =head2 Manipulation & Inspection Of Transitions
+ 
+ Each transition between states is a transition object, which knows how
+ to organize several "labels." Think of this as the mechanism by which
+ multiple arrows in the state diagram between the same states are collapsed
+ to a single arrow. This interface is abstracted away into the following
+ public methods:
+ 
+ =over
+ 
+ =item $fa-E<gt>set_transition($state1, $state2, @labels)
+ 
+ Resets the transition between $state1 and $state2 to a transition
+ initialized using data @labels. If @labels is omitted or contains
+ only undefined elements, then the call is equivalent to C<remove_transition>.
+ 
+ =item $fa-E<gt>add_transition($state1, $state2, @labels)
+ 
+ Adds @labels to the transition between $state1 and $state2.
+ 
+ =item $fa-E<gt>get_transition($state1, $state2)
+ 
+ Returns the transition object stored between $state1 and $state2, or
+ undef if there is no transition.
+ 
+ =item $fa-E<gt>remove_transition($state1, $state2)
+ 
+ Removes the transition object between $state1 and $state2.
+ 
+ =item $fa-E<gt>successors(\@states)
+ 
+ =item $fa-E<gt>successors($state)
+ 
+ =item $fa-E<gt>successors(\@states, $label)
+ 
+ =item $fa-E<gt>successors($state, $label)
+ 
+ =item $fa-E<gt>successors(\@states, \@labels)
+ 
+ =item $fa-E<gt>successors($state, \@labels)
+ 
+ Given a state/set of states, and one or more labels, returns a list of
+ the states (without duplicates) reachable from the states via a single
+ transition having any of the given labels. If no labels are given, returns
+ the states reachable by any (single) transition.
+ 
+ Note that this method makes no distinction for epsilon transitions, these
+ are only special in FLAT::NFA objects.
+ 
+ =item $fa-E<gt>alphabet
+ 
+ Returns the list of characters (without duplicates) used among all
+ transition labels in the automaton.
+ 
+ =back
+ 
+ =head2 Conversions To External Formats
+ 
+ =over
+ 
+ =item $fa-E<gt>as_graphviz
+ 
+ Returns a string containing a GraphViz (dot) description of the automaton,
+ suitable for rendering with your favorite GraphViz layout engine.
+ 
+ =item $fa-E<gt>as_summary
+ 
+ Returns a string containing a plaintext description of the automaton,
+ suitable for debugging purposes.
+ 
+ =back
+ 
+ =head2 Miscellaneous
+ 
+ =over
+ 
+ =item $fa-E<gt>clone
+ 
+ Returns an identical copy of $fa.
+ 
+ =back