Menu
▾
▴
perl-flat-cvs-notify — notifies subscribers of cvs commits
You can subscribe to this list here.
| 2006 |
Jan
|
Feb
(32) |
Mar
(25) |
Apr
(13) |
May
(3) |
Jun
|
Jul
|
Aug
(1) |
Sep
(5) |
Oct
(2) |
Nov
|
Dec
(1) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2007 |
Jan
|
Feb
(28) |
Mar
(6) |
Apr
|
May
(3) |
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
|
From: <per...@li...> - 2006-03-03 05:46:21
|
Update of /cvsroot/perl-flat/perl-flat-legacy In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv18396 Modified Files: Makefile.old Log Message: Index: Makefile.old =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/Makefile.old,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** Makefile.old 2 Mar 2006 21:00:27 -0000 1.2 --- Makefile.old 3 Mar 2006 05:46:17 -0000 1.3 *************** *** 149,153 **** H_FILES = MAN1PODS = ! MAN3PODS = lib/FLAT/FA.pm \ lib/FLAT/FA/DFA.pm \ lib/FLAT/FA/NFA.pm \ --- 149,154 ---- H_FILES = MAN1PODS = ! MAN3PODS = lib/FLAT.pm \ ! lib/FLAT/FA.pm \ lib/FLAT/FA/DFA.pm \ lib/FLAT/FA/NFA.pm \ *************** *** 407,410 **** --- 408,412 ---- lib/FLAT/FA/RE.pm \ lib/FLAT/FA.pm \ + lib/FLAT.pm \ lib/FLAT/FA/DFA.pm \ lib/FLAT/FA/PFA.pm \ *************** *** 412,416 **** lib/FLAT/FA/PRE.pm \ lib/FLAT/FA/RE.pm \ ! lib/FLAT/FA.pm $(NOECHO) $(POD2MAN) --section=3 --perm_rw=$(PERM_RW)\ lib/FLAT/FA/DFA.pm $(INST_MAN3DIR)/FLAT::FA::DFA.$(MAN3EXT) \ --- 414,419 ---- lib/FLAT/FA/PRE.pm \ lib/FLAT/FA/RE.pm \ ! lib/FLAT/FA.pm \ ! lib/FLAT.pm $(NOECHO) $(POD2MAN) --section=3 --perm_rw=$(PERM_RW)\ lib/FLAT/FA/DFA.pm $(INST_MAN3DIR)/FLAT::FA::DFA.$(MAN3EXT) \ *************** *** 419,423 **** lib/FLAT/FA/PRE.pm $(INST_MAN3DIR)/FLAT::FA::PRE.$(MAN3EXT) \ lib/FLAT/FA/RE.pm $(INST_MAN3DIR)/FLAT::FA::RE.$(MAN3EXT) \ ! lib/FLAT/FA.pm $(INST_MAN3DIR)/FLAT::FA.$(MAN3EXT) --- 422,427 ---- lib/FLAT/FA/PRE.pm $(INST_MAN3DIR)/FLAT::FA::PRE.$(MAN3EXT) \ lib/FLAT/FA/RE.pm $(INST_MAN3DIR)/FLAT::FA::RE.$(MAN3EXT) \ ! lib/FLAT/FA.pm $(INST_MAN3DIR)/FLAT::FA.$(MAN3EXT) \ ! lib/FLAT.pm $(INST_MAN3DIR)/FLAT.$(MAN3EXT) |
|
From: <per...@li...> - 2006-03-02 21:00:33
|
Update of /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT/FA In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv29905/lib/FLAT/FA Modified Files: DFA.pm NFA.pm PFA.pm PRE.pm RE.pm Log Message: updating comments for hopefully the last time - or at least until I decide to add more info, which is unlikely since FLaT 1.0 is coming up fast Index: DFA.pm =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT/FA/DFA.pm,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** DFA.pm 27 Feb 2006 17:42:18 -0000 1.4 --- DFA.pm 2 Mar 2006 21:00:28 -0000 1.5 *************** *** 609,613 **** =head1 SYNOPSIS ! use DFA; =head1 DESCRIPTION --- 609,613 ---- =head1 SYNOPSIS ! use FLAT::FA::DFA; =head1 DESCRIPTION *************** *** 628,636 **** =head1 BUGS ! Not saying it is bug free, just saying I haven't hit any yet :) =head1 AVAILABILITY ! Anonymous CVS Checkout at L<http://www.brettsbsd.net/cgi-bin/viewcvs.cgi/> =head1 ACKNOWLEDGEMENTS --- 628,636 ---- =head1 BUGS ! I haven't hit any yet, but every now and then C<minimize> makes me pause, thoughthis might have more to do with my lack of intuition than the minimization being done incorrectly. =head1 AVAILABILITY ! Perl FLaT Project Website at L<http://perl-flat.sourceforge.net/pmwiki> =head1 ACKNOWLEDGEMENTS *************** *** 638,642 **** This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. =head1 COPYRIGHT --- 638,645 ---- This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. It then became the basis for my MS research. and thesis. ! ! Mike Rosulek has joined the effort, and is heading up the rewrite of ! Perl FLaT, which will soon be released as FLaT 1.0. =head1 COPYRIGHT Index: PFA.pm =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT/FA/PFA.pm,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** PFA.pm 27 Feb 2006 17:42:18 -0000 1.4 --- PFA.pm 2 Mar 2006 21:00:28 -0000 1.5 *************** *** 912,916 **** =head1 SYNOPSIS ! use PFA; =head1 DESCRIPTION --- 912,916 ---- =head1 SYNOPSIS ! use FLAT::FA::PFA; =head1 DESCRIPTION *************** *** 937,945 **** =head1 BUGS ! Not saying it is bug free, just saying I haven't hit any yet :) =head1 AVAILABILITY ! Anonymous CVS Checkout at L<http://www.brettsbsd.net/cgi-bin/viewcvs.cgi/> =head1 ACKNOWLEDGEMENTS --- 937,945 ---- =head1 BUGS ! I haven't hit any yet :) =head1 AVAILABILITY ! Perl FLaT Project Website at L<http://perl-flat.sourceforge.net/pmwiki> =head1 ACKNOWLEDGEMENTS *************** *** 947,951 **** This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. =head1 COPYRIGHT --- 947,954 ---- This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. It then became the basis for my MS research. and thesis. ! ! Mike Rosulek has joined the effort, and is heading up the rewrite of ! Perl FLaT, which will soon be released as FLaT 1.0. =head1 COPYRIGHT Index: NFA.pm =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT/FA/NFA.pm,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** NFA.pm 27 Feb 2006 17:42:18 -0000 1.3 --- NFA.pm 2 Mar 2006 21:00:28 -0000 1.4 *************** *** 645,649 **** =head1 SYNOPSIS ! use NFA; =head1 DESCRIPTION --- 645,649 ---- =head1 SYNOPSIS ! use FLAT::FA::NFA; =head1 DESCRIPTION *************** *** 665,673 **** =head1 BUGS ! Not saying it is bug free, just saying I haven't hit any yet :) =head1 AVAILABILITY ! Anonymous CVS Checkout at L<http://www.brettsbsd.net/cgi-bin/viewcvs.cgi/> =head1 ACKNOWLEDGEMENTS --- 665,673 ---- =head1 BUGS ! I haven't hit any yet :) =head1 AVAILABILITY ! Perl FLaT Project Website at L<http://perl-flat.sourceforge.net/pmwiki> =head1 ACKNOWLEDGEMENTS *************** *** 675,679 **** This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. =head1 COPYRIGHT --- 675,682 ---- This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. It then became the basis for my MS research. and thesis. ! ! Mike Rosulek has joined the effort, and is heading up the rewrite of ! Perl FLaT, which will soon be released as FLaT 1.0. =head1 COPYRIGHT Index: PRE.pm =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT/FA/PRE.pm,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** PRE.pm 27 Feb 2006 17:42:18 -0000 1.4 --- PRE.pm 2 Mar 2006 21:00:28 -0000 1.5 *************** *** 506,510 **** =head1 SYNOPSIS ! use PRE; =head1 DESCRIPTION --- 506,510 ---- =head1 SYNOPSIS ! use FLAT::FA::PRE; =head1 DESCRIPTION *************** *** 572,580 **** =head1 BUGS ! Not saying it is bug free, just saying I haven't hit any yet :) =head1 AVAILABILITY ! Anonymous CVS Checkout at L<http://www.brettsbsd.net/cgi-bin/viewcvs.cgi/> =head1 ACKNOWLEDGEMENTS --- 572,580 ---- =head1 BUGS ! I haven't hit any yet :) =head1 AVAILABILITY ! Perl FLaT Project Website at L<http://perl-flat.sourceforge.net/pmwiki> =head1 ACKNOWLEDGEMENTS *************** *** 582,586 **** This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. =head1 COPYRIGHT --- 582,589 ---- This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. It then became the basis for my MS research. and thesis. ! ! Mike Rosulek has joined the effort, and is heading up the rewrite of ! Perl FLaT, which will soon be released as FLaT 1.0. =head1 COPYRIGHT Index: RE.pm =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT/FA/RE.pm,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** RE.pm 27 Feb 2006 17:42:18 -0000 1.4 --- RE.pm 2 Mar 2006 21:00:28 -0000 1.5 *************** *** 692,701 **** =head1 SYNOPSIS ! use RE; ! use DFA; my $re = RE->new(); $re->set_re('a|b|(hi)*'); ! my $dfa = $re->to_dfa(); print $dfa->info(); # see stuff on DFA =head1 DESCRIPTION --- 692,706 ---- =head1 SYNOPSIS ! use FLAT::FA::RE; ! use FLAT::FA::NFA; my $re = RE->new(); $re->set_re('a|b|(hi)*'); ! my $nfa = $re->to_nfa(); ! print $nfa->info(); # see stuff on NFA ! my $dfa = $nfa->to_dfa(); print $dfa->info(); # see stuff on DFA + my @removed = $dfa->minimize(); + print $dfa->info(); # see stuff on minimized DFA + print "Removed ".($#removed+1)." states\n"; =head1 DESCRIPTION *************** *** 758,766 **** =head1 BUGS ! Not saying it is bug free, just saying I haven't hit any yet :) =head1 AVAILABILITY ! Anonymous CVS Checkout at L<http://www.brettsbsd.net/cgi-bin/viewcvs.cgi/> =head1 ACKNOWLEDGEMENTS --- 763,773 ---- =head1 BUGS ! C<to_dfa> is broken, and is now listed as C<to_dfa_BROKEN> so there ! is no confusion. I am currently debating whether or not to fix it, ! or reimplement it in FLaT 1.0. =head1 AVAILABILITY ! Perl FLaT Project Website at L<http://perl-flat.sourceforge.net/pmwiki> =head1 ACKNOWLEDGEMENTS *************** *** 768,772 **** This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. =head1 COPYRIGHT --- 775,782 ---- This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. It then became the basis for my MS research. and thesis. ! ! Mike Rosulek has joined the effort, and is heading up the rewrite of ! Perl FLaT, which will soon be released as FLaT 1.0. =head1 COPYRIGHT |
|
From: <per...@li...> - 2006-03-02 21:00:33
|
Update of /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv29905/lib/FLAT Modified Files: FA.pm Log Message: updating comments for hopefully the last time - or at least until I decide to add more info, which is unlikely since FLaT 1.0 is coming up fast Index: FA.pm =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT/FA.pm,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** FA.pm 27 Feb 2006 17:42:18 -0000 1.4 --- FA.pm 2 Mar 2006 21:00:28 -0000 1.5 *************** *** 291,302 **** =head1 SYNOPSIS ! use FA; =head1 DESCRIPTION ! This module is a base finite automata ! used by NFA and DFA to encompass ! common functions. It is probably of no use ! other than to organize the DFA and NFA modules. =head1 AUTHOR --- 291,299 ---- =head1 SYNOPSIS ! use FLAT::FA; =head1 DESCRIPTION ! This module is a base finite automata used by NFA and DFA to encompass common functions. It is probably of no use other than to organize the DFA and NFA modules. =head1 AUTHOR *************** *** 306,326 **** =head1 CAVEATS ! Currently, all states are stored as labels. There is also ! no integrity checking for consistency among the start, final, ! and set of all states. =head1 BUGS ! Not saying it is bug free, just saying I haven't hit any yet :) =head1 AVAILABILITY ! Anonymous CVS Checkout at L<http://www.brettsbsd.net/cgi-bin/viewcvs.cgi/> =head1 ACKNOWLEDGEMENTS ! This suite of modules started off as a homework assignment for a compiler ! class I took for my MS in computer science at the University of Southern ! Mississippi. It then became the basis for my MS research. and thesis. =head1 COPYRIGHT --- 303,321 ---- =head1 CAVEATS ! Currently, all states are stored as labels. There is also no integrity checking for consistency among the start, final, and set of all states. =head1 BUGS ! I haven't hit any yet :) =head1 AVAILABILITY ! Perl FLaT Project Website at L<http://perl-flat.sourceforge.net/pmwiki> =head1 ACKNOWLEDGEMENTS ! This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern Mississippi. It then became the basis for my MS research. and thesis. ! ! Mike Rosulek has joined the effort, and is heading up the rewrite of Perl FLaT, which will soon be released as FLaT 1.0. =head1 COPYRIGHT |
|
From: <per...@li...> - 2006-03-02 21:00:32
|
Update of /cvsroot/perl-flat/perl-flat-legacy/lib In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv29905/lib Modified Files: FLAT.pm Log Message: updating comments for hopefully the last time - or at least until I decide to add more info, which is unlikely since FLaT 1.0 is coming up fast Index: FLAT.pm =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/lib/FLAT.pm,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** FLAT.pm 1 Mar 2006 18:14:25 -0000 1.3 --- FLAT.pm 2 Mar 2006 21:00:27 -0000 1.4 *************** *** 2,10 **** use Carp; - use vars '$VERSION'; - $VERSION = 0.4; - ## let subclasses implement a minimal set of closure properties. ## they can override these with more efficient versions if they like. 1; --- 2,47 ---- use Carp; ## let subclasses implement a minimal set of closure properties. ## they can override these with more efficient versions if they like. 1; + + __END__ + + =head1 NAME + + FLAT - A finite automata base class + + =head1 SYNOPSIS + + N/A - this file is really just a stub of a super class. Use FLAT::FA instead. + + =head1 DESCRIPTION + + This module is a base finite automata used by NFA and DFA to encompass common functions. It is probably of no use other than to organize the DFA and NFA modules. + + =head1 AUTHOR + + Brett D. Estrade - <estrabd AT mailcan DOT com> + + =head1 CAVEATS + + Currently, all states are stored as labels. There is also no integrity checking for consistency among the start, final, and set of all states. + + =head1 BUGS + + I haven't hit any yet :) + + =head1 AVAILABILITY + + Perl FLaT Project Website at L<http://perl-flat.sourceforge.net/pmwiki> + + =head1 ACKNOWLEDGEMENTS + + This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern Mississippi. It then became the basis for my MS research. and thesis. + + Mike Rosulek has joined the effort, and is heading up the rewrite of Perl FLaT, which will soon be released as FLaT 1.0. + + =head1 COPYRIGHT + + This code is released under the same terms as Perl. |
|
From: <per...@li...> - 2006-03-02 21:00:32
|
Update of /cvsroot/perl-flat/perl-flat-legacy In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv29905 Modified Files: META.yml Makefile.PL Makefile.old Log Message: updating comments for hopefully the last time - or at least until I decide to add more info, which is unlikely since FLaT 1.0 is coming up fast Index: META.yml =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/META.yml,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** META.yml 2 Mar 2006 15:52:46 -0000 1.3 --- META.yml 2 Mar 2006 21:00:27 -0000 1.4 *************** *** 2,7 **** #XXXXXXX This is a prototype!!! It will change in the future!!! XXXXX# name: FLAT ! version: 0.4 ! version_from: lib/FLAT.pm installdirs: site requires: --- 2,6 ---- #XXXXXXX This is a prototype!!! It will change in the future!!! XXXXX# name: FLAT ! version: 0.5 installdirs: site requires: Index: Makefile.old =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/Makefile.old,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** Makefile.old 24 Feb 2006 00:03:37 -0000 1.1 --- Makefile.old 2 Mar 2006 21:00:27 -0000 1.2 *************** *** 14,18 **** # NAME => q[FLAT] # PREREQ_PM => { } - # VERSION_FROM => q[lib/FLAT.pm] # --- MakeMaker post_initialize section: --- 14,17 ---- *************** *** 53,61 **** NAME = FLAT NAME_SYM = FLAT ! VERSION = 0.3 VERSION_MACRO = VERSION ! VERSION_SYM = 0_3 DEFINE_VERSION = -D$(VERSION_MACRO)=\"$(VERSION)\" ! XS_VERSION = 0.3 XS_VERSION_MACRO = XS_VERSION XS_DEFINE_VERSION = -D$(XS_VERSION_MACRO)=\"$(XS_VERSION)\" --- 52,60 ---- NAME = FLAT NAME_SYM = FLAT ! VERSION = VERSION_MACRO = VERSION ! VERSION_SYM = DEFINE_VERSION = -D$(VERSION_MACRO)=\"$(VERSION)\" ! XS_VERSION = XS_VERSION_MACRO = XS_VERSION XS_DEFINE_VERSION = -D$(XS_VERSION_MACRO)=\"$(XS_VERSION)\" *************** *** 139,143 **** PARENT_NAME = DLBASE = $(BASEEXT) ! VERSION_FROM = lib/FLAT.pm OBJECT = LDFROM = $(OBJECT) --- 138,142 ---- PARENT_NAME = DLBASE = $(BASEEXT) ! VERSION_FROM = OBJECT = LDFROM = $(OBJECT) *************** *** 261,265 **** DIST_DEFAULT = tardist DISTNAME = FLAT ! DISTVNAME = FLAT-0.3 --- 260,264 ---- DIST_DEFAULT = tardist DISTNAME = FLAT ! DISTVNAME = FLAT- *************** *** 469,474 **** $(NOECHO) $(ECHO) '#XXXXXXX This is a prototype!!! It will change in the future!!! XXXXX#' >> META.yml $(NOECHO) $(ECHO) 'name: FLAT' >> META.yml ! $(NOECHO) $(ECHO) 'version: 0.3' >> META.yml ! $(NOECHO) $(ECHO) 'version_from: lib/FLAT.pm' >> META.yml $(NOECHO) $(ECHO) 'installdirs: site' >> META.yml $(NOECHO) $(ECHO) 'requires:' >> META.yml --- 468,473 ---- $(NOECHO) $(ECHO) '#XXXXXXX This is a prototype!!! It will change in the future!!! XXXXX#' >> META.yml $(NOECHO) $(ECHO) 'name: FLAT' >> META.yml ! $(NOECHO) $(ECHO) 'version: ' >> META.yml ! $(NOECHO) $(ECHO) 'version_from: ' >> META.yml $(NOECHO) $(ECHO) 'installdirs: site' >> META.yml $(NOECHO) $(ECHO) 'requires:' >> META.yml *************** *** 737,741 **** # Creates a PPD (Perl Package Description) for a binary distribution. ppd: ! $(NOECHO) $(ECHO) '<SOFTPKG NAME="$(DISTNAME)" VERSION="0,3,0,0">' > $(DISTNAME).ppd $(NOECHO) $(ECHO) ' <TITLE>$(DISTNAME)</TITLE>' >> $(DISTNAME).ppd $(NOECHO) $(ECHO) ' <ABSTRACT></ABSTRACT>' >> $(DISTNAME).ppd --- 736,740 ---- # Creates a PPD (Perl Package Description) for a binary distribution. ppd: ! $(NOECHO) $(ECHO) '<SOFTPKG NAME="$(DISTNAME)" VERSION="0,0,0,0">' > $(DISTNAME).ppd $(NOECHO) $(ECHO) ' <TITLE>$(DISTNAME)</TITLE>' >> $(DISTNAME).ppd $(NOECHO) $(ECHO) ' <ABSTRACT></ABSTRACT>' >> $(DISTNAME).ppd Index: Makefile.PL =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/Makefile.PL,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** Makefile.PL 21 Feb 2006 14:46:22 -0000 1.3 --- Makefile.PL 2 Mar 2006 21:00:27 -0000 1.4 *************** *** 5,9 **** WriteMakefile( NAME => 'FLAT', - VERSION_FROM => 'lib/FLAT.pm', # finds $VERSION PREREQ_PM => {}, # e.g., Module::Name => 1.1 ($] >= 5.005 ? ## Add these new keywords supported since 5.005 --- 5,8 ---- |
|
From: <per...@li...> - 2006-03-02 15:52:49
|
Update of /cvsroot/perl-flat/perl-flat-legacy In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv25939 Modified Files: META.yml Log Message: please ignore Index: META.yml =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/META.yml,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** META.yml 2 Mar 2006 04:33:29 -0000 1.2 --- META.yml 2 Mar 2006 15:52:46 -0000 1.3 *************** *** 2,5 **** --- 2,6 ---- #XXXXXXX This is a prototype!!! It will change in the future!!! XXXXX# name: FLAT + version: 0.4 version_from: lib/FLAT.pm installdirs: site |
|
From: <per...@li...> - 2006-03-02 04:33:33
|
Update of /cvsroot/perl-flat/perl-flat-legacy In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv16404 Modified Files: META.yml Log Message: minor change to META.yml Index: META.yml =================================================================== RCS file: /cvsroot/perl-flat/perl-flat-legacy/META.yml,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** META.yml 23 Feb 2006 21:04:54 -0000 1.1 --- META.yml 2 Mar 2006 04:33:29 -0000 1.2 *************** *** 2,6 **** #XXXXXXX This is a prototype!!! It will change in the future!!! XXXXX# name: FLAT - version: 0.3 version_from: lib/FLAT.pm installdirs: site --- 2,5 ---- |
|
From: <per...@li...> - 2006-03-01 18:29:32
|
Update of /cvsroot/perl-flat/blokhead/lib/FLAT In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7074/lib/FLAT Modified Files: DFA.pm NFA.pm Log Message: DFA complement, intersection (still needs work) NFA extend alphabet Index: DFA.pm =================================================================== RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/DFA.pm,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** DFA.pm 24 Feb 2006 06:20:25 -0000 1.2 --- DFA.pm 1 Mar 2006 18:29:22 -0000 1.3 *************** *** 14,17 **** --- 14,74 ---- } + sub complement { + my $self = $_[0]->clone; + + for my $s ($self->get_states) { + $self->is_accepting($s) + ? $self->unset_accepting($s) + : $self->set_accepting($s); + } + + return $self; + } + + sub _TUPLE_ID { join "\0", @_ } + sub _uniq { my %seen; grep { !$seen{$_}++ } @_; } + + ## this method still needs more work.. + sub intersect { + my @dfas = map { $_->as_dfa } @_; + + my $return = FLAT::DFA->new; + my %newstates; + my @alpha = _uniq( map { $_->alphabet } @dfas ); + + $_->_extend_alphabet(@alpha) for @dfas; + + my @start = map { $_->get_starting } @dfas; + my $start = $newstates{ _TUPLE_ID(@start) } = $return->add_states(1); + $return->set_starting($start); + $return->set_accepting($start) + if ! grep { ! $dfas[$_]->is_accepting( $start[$_] ) } 0 .. $#dfas; + + my @queue = (\@start); + while (@queue) { + my @tuple = @{ shift @queue }; + + for my $char (@alpha) { + my @next = map { $dfas[$_]->successors( $tuple[$_], $char ) } + 0 .. $#dfas; + + warn "[@tuple] --> [@next] via $char\n"; + + if (not exists $newstates{ _TUPLE_ID(@next) }) { + my $s = $newstates{ _TUPLE_ID(@next) } = $return->add_states(1); + $return->set_accepting($s) + if ! grep { ! $dfas[$_]->is_accepting( $next[$_] ) } 0 .. $#dfas; + push @queue, \@next; + } + + $return->add_transition( $newstates{ _TUPLE_ID(@tuple) }, + $newstates{ _TUPLE_ID(@next) }, + $char ); + } + } + + return $return; + } + sub unset_starting { my $self = shift; Index: NFA.pm =================================================================== RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/NFA.pm,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -d -r1.9 -r1.10 *** NFA.pm 24 Feb 2006 15:41:02 -0000 1.9 --- NFA.pm 1 Mar 2006 18:29:22 -0000 1.10 *************** *** 203,206 **** --- 203,225 ---- return @trace; } + ############ + + sub _extend_alphabet { + my ($self, @alpha) = @_; + + my %alpha = map { $_ => 1 } @alpha; + delete $alpha{$_} for $self->alphabet; + + return if not keys %alpha; + + my $trash = $self->add_states(1); + for my $state ($self->get_states) { + next if $state eq $trash; + for my $char (keys %alpha) { + $self->add_transition($state, $trash, $char); + } + } + $self->add_transition($trash, $trash, $self->alphabet); + } ############ *************** *** 232,236 **** } ! sub _SET_ID { join "\0", sort { $a <=> $b } @_; } # could this be encapsulated as inside of a closure or anonymous function? sub as_dfa { my $self = shift; --- 251,255 ---- } ! sub _SET_ID { join "\0", sort { $a <=> $b } @_; } sub as_dfa { my $self = shift; |
|
From: <per...@li...> - 2006-03-01 18:29:28
|
Update of /cvsroot/perl-flat/blokhead In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7074 Modified Files: MANIFEST Log Message: DFA complement, intersection (still needs work) NFA extend alphabet Index: MANIFEST =================================================================== RCS file: /cvsroot/perl-flat/blokhead/MANIFEST,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** MANIFEST 24 Feb 2006 06:20:25 -0000 1.2 --- MANIFEST 1 Mar 2006 18:29:22 -0000 1.3 *************** *** 11,12 **** --- 11,13 ---- lib/FLAT.pm Makefile.PL + META.yml Module meta-data (added by MakeMaker) |
|
From: <per...@li...> - 2006-03-01 18:29:26
|
Update of /cvsroot/perl-flat/blokhead/dev-scripts In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7074/dev-scripts Modified Files: bloktest.pl Log Message: DFA complement, intersection (still needs work) NFA extend alphabet Index: bloktest.pl =================================================================== RCS file: /cvsroot/perl-flat/blokhead/dev-scripts/bloktest.pl,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** bloktest.pl 24 Feb 2006 01:04:52 -0000 1.7 --- bloktest.pl 1 Mar 2006 18:29:22 -0000 1.8 *************** *** 10,36 **** sub foo { ! FLAT::Regex->new(shift)->as_nfa; ! } ! ! ! for (qw{ ab|cd|[] ab* []* (a|b)* ([]|[])* }, "#*", "###") { ! my $nfa = foo($_); ! ! print "$_ is: "; ! print $nfa->is_finite ? "finite, " : "infinite, "; ! print $nfa->is_empty ? "empty, " : "nonempty, "; ! print "alphabet = ", $nfa->alphabet, "\n"; } - ####### ! my $nfa = foo("ab(c|d)*e"); ! for (qw[ abe abce abcdcdcdcde bcde be abcd ab ]) { ! printf "$_ in the language? %s\n", ! $nfa->contains($_) ? "yes!" : "no"; ! my @t = $nfa->trace($_); ! print "[@$_] " for @t; ! print $/; ! } --- 10,21 ---- sub foo { ! FLAT::Regex->new(shift)->as_min_dfa; } ! my $dfa1 = foo("((a+b)(a+b))*"); ! my $dfa2 = foo("a*"); ! my $result = $dfa1->intersect($dfa2); ! print $result->as_graphviz; |
|
From: <per...@li...> - 2006-03-01 18:14:30
|
Update of /cvsroot/perl-flat/flat4cpan/lib In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23907/lib Modified Files: FLAT.pm Log Message: updated version number Index: FLAT.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT.pm,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** FLAT.pm 23 Feb 2006 21:04:54 -0000 1.2 --- FLAT.pm 1 Mar 2006 18:14:25 -0000 1.3 *************** *** 3,7 **** use vars '$VERSION'; ! $VERSION = 0.3; ## let subclasses implement a minimal set of closure properties. --- 3,7 ---- use vars '$VERSION'; ! $VERSION = 0.4; ## let subclasses implement a minimal set of closure properties. |
|
From: <per...@li...> - 2006-03-01 16:25:34
|
Update of /cvsroot/perl-flat/blokhead/dev-scripts In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12475 Added Files: profile.sh Log Message: added wrapper script for profiler - usage: sh profile.sh profilethis.pl arg1 agr2 argN --- NEW FILE: profile.sh --- #!/bin/sh # profile FLAT code # Usage: # # ./profile.sh <dev-script-name> [arg1 arg2 ... argN] # run with Dprof as debugger perl -d:DProf $@ # process tmon.out file dprofpp |
|
From: <per...@li...> - 2006-02-27 17:42:24
|
Update of /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv31851/lib/FLAT/FA Modified Files: DFA.pm NFA.pm PFA.pm PRE.pm RE.pm Log Message: cleaning up comments Index: DFA.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/DFA.pm,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** DFA.pm 24 Feb 2006 21:27:15 -0000 1.3 --- DFA.pm 27 Feb 2006 17:42:18 -0000 1.4 *************** *** 1,21 **** # $Revision$ $Date$ $Author$ - =head1 NAME - - DFA - A determinisitic finite automata base class - - =head1 SYNOPSIS - - use DFA; - - =head1 DESCRIPTION - - This module is implements a deterministic finite automata, - including the testing of strings accepted by the DFA. - - B<Methods> - - =cut - package FLAT::FA::DFA; --- 1,4 ---- *************** *** 28,37 **** use Data::Dumper; - =item C<new> - - Returns a new FA object - - =cut - sub new { my $class = shift; --- 11,14 ---- *************** *** 45,60 **** } - - =over 1 - - =item C<jump_start> - - Returns an DFA with 1 start state, one final state, and - a single transistion on the given symbol; if a symbol is - not provided, only a single state that is both the start - and end state is returned - - =cut - sub jump_start { my $self = shift; --- 22,25 ---- *************** *** 82,93 **** } - =over 1 - - =item C<load_file> - - Load DFA from file - - =cut - sub load_file { my $self = shift; --- 47,50 ---- *************** *** 104,113 **** } - =item C<load_string> - - Load DFA from string - - =cut - sub load_string { my $self = shift; --- 61,64 ---- *************** *** 144,155 **** } - =over 1 - - =item C<clone> - - Returns a distinct clone of self - - =cut - sub clone { my $self = shift; --- 95,98 ---- *************** *** 167,175 **** } - =item C<to_nfa> - - Returns an NFA; everything is copied exactly, but it is of class NFA - =cut - sub to_nfa { my $self = shift; --- 110,113 ---- *************** *** 187,197 **** } - =item C<minimize> - - Minimizes number of states and transitions required to accept the regular language - described by original $self; returns an array of the states removed - - =cut - sub minimize() { my $self = shift; --- 125,128 ---- *************** *** 334,345 **** } - =item C<delete_state> - - Deletes state and all references to it...if the start start or only final state is deleted, a loud warning, - messages will be issued; accepts an arbitrarily long list of states to delete, so you could - do $dfa->delete_state(@states) or $dfa->delete_state($state); - - =cut - sub delete_state { my $self = shift(); --- 265,268 ---- *************** *** 386,396 **** } - =item C<rename_states> - - Renames a single state; warns and changes nothing if name conflicts - with another state - - =cut - sub rename_state { my $self = shift; --- 309,312 ---- *************** *** 448,457 **** } - =item C<rename_symbol> - - Renames symbol in dfa - - =cut - # Adds symbol sub rename_symbol { --- 364,367 ---- *************** *** 487,496 **** } - =item C<add_transition> - - Adds transition - note, one state per char...no subsets, that is what NFA is for :) - - =cut - sub add_transition { my $self = shift; --- 397,400 ---- *************** *** 501,511 **** } - =item C<get_transition_on> - - Get transitions on input symbol from specified state; this - is not in FA.pm as it is DFA specific. - - =cut - sub get_transition_on { my $self = shift; --- 405,408 ---- *************** *** 521,530 **** } - =item C<reverse_dfa> - - Will return a DFA object that is the reverse of the current one. - - =cut - sub reverse_dfa { my $self = shift; --- 418,421 ---- *************** *** 532,542 **** } - =item C<to_gdl> - - Outputs a Graph Description Language (GDL) file that can be visualized - using the program aiSee http://www.aisee.com/gdl/nutshell/intro.htm - - =cut - sub to_gdl { my $self = shift; --- 423,426 ---- *************** *** 560,569 **** } - =item C<info> - - Diagnostics, transition information - - =cut - sub info { my $self = shift; --- 444,447 ---- *************** *** 598,608 **** } - =item C<serialize> - - Prints a valid string suitable for an input to stdout - - =cut - - sub serialize { my $self = shift; --- 476,479 ---- *************** *** 621,630 **** } - =item C<is_valid> - - Gives true (1) or false (0) as to if a string is valid - - =cut - sub is_valid { my $self = shift; --- 492,495 ---- *************** *** 660,669 **** } - =item C<get_last_state> - - Returns accepting state, undef if string is not valid - - =cut - sub get_last_state { my $self = shift; --- 525,528 ---- *************** *** 693,702 **** } - =item C<get_path> - - Returns path taken - - =cut - sub get_path { my $self = shift; --- 552,555 ---- *************** *** 727,748 **** } - =item C<generate_random> - - Generates random DFA; not implemented - - =cut - sub generate_random { my $self = shift; } - - =item C<pump_strings> - - Generates accepted strings based on string length - closures will not be repeated, but will be denoted with '*'; not implemented. - - =cut - sub pump_strings { my $self = shift; --- 580,587 ---- *************** *** 750,759 **** } - =item C<init_string_pump> - - Used to initiate iterative string pumping; - - =cut - sub init_string_pump { my $self = shift; --- 589,592 ---- *************** *** 761,770 **** } - =item C<pump_next> - - Used to get next pumped string when being used iteratively; - - =cut - sub pump_next { my $self = shift; --- 594,597 ---- *************** *** 774,778 **** 1; ! =back =head1 AUTHOR --- 601,618 ---- 1; ! __END__ ! ! =head1 NAME ! ! DFA - A determinisitic finite automata base class ! ! =head1 SYNOPSIS ! ! use DFA; ! ! =head1 DESCRIPTION ! ! This module is implements a deterministic finite automata, ! including the testing of strings accepted by the DFA. =head1 AUTHOR Index: PFA.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/PFA.pm,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** PFA.pm 24 Feb 2006 21:27:15 -0000 1.3 --- PFA.pm 27 Feb 2006 17:42:18 -0000 1.4 *************** *** 1,27 **** # $Revision$ $Date$ $Author$ - =head1 NAME - - PFA - A parallel finite automata base class - - =head1 SYNOPSIS - - use PFA; - - =head1 DESCRIPTION - - This module is implements a paralle finite automata, - and the conversion of such to a non deterministic - finite automata; - - One key between PFA implementation an PFA & DFA is that the PFA - may contain more than one start node since it may depict - threads of concurrent execution. The main purpose of this - module is to convert a PFA to an PFA. - - B<Methods> - - =cut - package FLAT::FA::PFA; --- 1,4 ---- *************** *** 33,42 **** use Data::Dumper; - =item C<new> - - Returns a new PFA object - - =cut - sub new { my $class = shift; --- 10,13 ---- *************** *** 56,67 **** } - =over 1 - - =item C<load_file> - - Creates PFA from file - - =cut - sub load_file { my $self = shift; --- 27,30 ---- *************** *** 78,87 **** } - =item C<load_string> - - Creates PFA from string - - =cut - sub load_string { my $self = shift; --- 41,44 ---- *************** *** 125,138 **** } - =over 1 - - =item C<jump_start> - - Returns an PFA with 1 start state, one final state, and - a single transistion on the given symbol; if a symbol is - not provided, epsilon is used. - - =cut - sub jump_start { my $self = shift; --- 82,85 ---- *************** *** 158,171 **** } - =over 18 - - =item C<find_tied> - - Determines the tied nodes in $self, and stores them in $self->{_TIED} for - easy lookup. Use $self->is_tied(@testset) to determine if a set of nodes - contains anything tied on lambda - - =cut - sub find_tied { my $self = shift; --- 105,108 ---- *************** *** 188,199 **** } - =over 18 - - =item C<get_tied> - - Determines if any tied nodes are contained in the provided node set - - =cut - sub get_tied { my $self = shift; --- 125,128 ---- *************** *** 201,212 **** } - =over 18 - - =item C<has_tied> - - Determines if all nodes in a tied set are contained in the provided node set - - =cut - sub has_tied { my $self = shift; --- 130,133 ---- *************** *** 232,241 **** } - =item C<extract_tied> - - Extracts all tied nodes in a set and returns a flattened array - - =cut - sub extract_tied { my $self = shift; --- 153,156 ---- *************** *** 263,272 **** } - =item C<to_nfa> - - To NFA Stuff - convert PFA to NFA using subset construction technique - - =cut - sub to_nfa { my $self = shift; --- 178,181 ---- *************** *** 350,361 **** } - =over 18 - - =item C<serialize_name> - - Creates a string based on the items in the array; - - =cut - sub serialize_name { my $self = shift; --- 259,262 ---- *************** *** 365,376 **** } - =over 18 - - =item C<set_start> - - Sets start node, calls FA->add_node - - =cut - sub set_start { my $self = shift; --- 266,269 ---- *************** *** 384,393 **** } - =item C<get_start> - - Returns start nodes - - =cut - sub get_start { my $self = shift; --- 277,280 ---- *************** *** 395,406 **** } - =over 18 - - =item C<set_active> - - Sets active node, calls FA->add_node - - =cut - sub set_active { my $self = shift; --- 282,285 ---- *************** *** 410,419 **** } - =item C<get_active> - - Returns active nodes - - =cut - sub get_active { my $self = shift; --- 289,292 ---- *************** *** 421,430 **** } - =item C<add_node> - - Adds a node label to the node array if it does not already exist (handles dups) - - =cut - sub add_node { my $self = shift; --- 294,297 ---- *************** *** 437,447 **** } - =item C<get_nodes> - - Returns the array of all nodes - - =cut - - # Returns array of nodes sub get_nodes { my $self = shift; --- 304,307 ---- *************** *** 449,459 **** } - =item C<add_transition> - - Adds a transition - adds node and symbol as well - unique nodes and symbols - enforced by PFA->add_node and PFA->add_symbol - - =cut - sub add_transition { my $self = shift; --- 309,312 ---- *************** *** 469,480 **** } - =item C<get_transition_on> - - Returns transition(s), as an array, for a specific node - on a specific input symbol; This is not in FA.pm as it is - PFA specific. - - =cut - sub get_transition_on { my $self = shift; --- 322,325 ---- *************** *** 490,500 **** } - =item C<is_start> - - Checks to see if given node is in the start node array - - =cut - - # Will test if the string passed to it is a node in the set of start nodes sub is_start { my $self = shift; --- 335,338 ---- *************** *** 502,511 **** } - =item C<set_epsilon> - - Sets epsilon symbol - not working with Perl special vars - $,@,%, etc - - =cut - sub set_epsilon { my $self = shift; --- 340,343 ---- *************** *** 515,524 **** } - =item C<get_epsilon_symbol> - - Returns epsilon symbol - - =cut - sub get_epsilon_symbol { my $self = shift; --- 347,350 ---- *************** *** 526,535 **** } - =item C<get_epsilon_transitions> - - Returns all epsilon transitions for a particular node; node must exist - - =cut - sub get_epsilon_transitions { my $self = shift; --- 352,355 ---- *************** *** 544,553 **** } - =item C<delete_epsilon> - - Deletes epsilon symbol - - =cut - sub delete_epsilon { my $self = shift; --- 364,367 ---- *************** *** 556,565 **** } - =item C<set_lambda> - - Sets lambda symbol - not working with Perl special vars - $,@,%, etc - - =cut - sub set_lambda { my $self = shift; --- 370,373 ---- *************** *** 569,578 **** } - =item C<get_lambda_symbol> - - Returns lambda symbol - - =cut - sub get_lambda_symbol { my $self = shift; --- 377,380 ---- *************** *** 580,589 **** } - =item C<get_lambda_transitions> - - Returns all lambda transitions for a particular node; node must exist - - =cut - sub get_lambda_transitions { my $self = shift; --- 382,385 ---- *************** *** 598,607 **** } - =item C<delete_lambda> - - Deletes lambda symbol - - =cut - sub delete_lambda { my $self = shift; --- 394,397 ---- *************** *** 610,620 **** } - =item C<is_node> - - Tests if given string is the name of a node - - =cut - - # Will test if the string passed to it is the same as a label of any node sub is_node { my $self = shift; --- 400,403 ---- *************** *** 622,633 **** } - =item C<add_final> - - Adds a list of node lables to the final nodes array; handles dups, - and ensures nodes are added to set of nodes - - =cut - - # Adds node to final (accepting) node stack sub add_final { my $self = shift; --- 405,408 ---- *************** *** 640,650 **** } - =item C<get_final> - - Returns the array of all final nodes - - =cut - - # Returns array of final nodes sub get_final { my $self = shift; --- 415,418 ---- *************** *** 652,663 **** } - - =item C<is_final> - - Checks to see if given node is in the final node array - - =cut - - # Will test if the string passed to it is the same as a label of any node sub is_final { my $self = shift; --- 420,423 ---- *************** *** 665,676 **** } - =over 1 - - =item C<clone> - - Returns a distinct clone of self - - =cut - sub clone { my $self = shift; --- 425,428 ---- *************** *** 690,700 **** } - =item C<append_pfa> - - Concatenates start node of given PFA to the common final node of self; - usage: my PFA->append_pfa($PFA1); - - =cut - sub append_pfa { my $self = shift; --- 442,445 ---- *************** *** 734,744 **** } - =item C<prepend_pfa> - - Concatenates start node of self to the common final node of the given PFA; - usage: my PFA->prepend_pfa($PFA1); - - =cut - sub prepend_pfa { my $self = shift; --- 479,482 ---- *************** *** 778,788 **** } - =item C<or_pfa> - - Creates a common start node joined by an epsilon transition; - usage: my PFA->or_pfa($PFA1); - - =cut - sub or_pfa { my $self = shift; --- 516,519 ---- *************** *** 826,835 **** } - =item C<interleave_pfa> - - Joins 2 PFAs using an interleave (concurrent process). - - =cut - sub interleave_pfa { my $self = shift; --- 557,560 ---- *************** *** 886,896 **** } - =item C<kleene> - - Wraps given PFA in Kleene Closure - usage: my PFA->kleene(); - - =cut - sub kleene { my $self = shift; --- 611,614 ---- *************** *** 918,929 **** } - =item C<pinch> - - Creates epsilon transitions from all final nodes to a common final node; . - usage: my $PFA3 = PFA->pinch_pfa($PFA1); does nothing if there is only one - final node - - =cut - sub pinch { my $self = shift; --- 636,639 ---- *************** *** 948,958 **** } - =item C<rename_nodes> - - Renames a single node; warns and changes nothing if name conflicts - with another node - - =cut - sub rename_node { my $self = shift; --- 658,661 ---- *************** *** 1032,1048 **** } - =item C<ensure_unique_nodes> - - Compares the names of the nodes in $self and the - provided FA, and only renames a node (in $self) - if a name collision is detected; if the disambiguation - string causes a new collision, a random string is created - using crypt() until there is no collision detected - - Usage: - $self->ensure_unique_nodes($PFA1,'string_to_disambiguate'); - - =cut - sub ensure_unique_nodes { my $self = shift; --- 735,738 ---- *************** *** 1063,1073 **** } - =item C<number_nodes> - - Numbers nodes 0-# of nodes; first appends node name with a - random string to avoid conflicts - - =cut - sub number_nodes { my $self = shift; --- 753,756 ---- *************** *** 1089,1098 **** } - =item C<append_node_names> - - Appends node names with the specified suffix - - =cut - sub append_node_names { my $self = shift; --- 772,775 ---- *************** *** 1109,1119 **** } - - =item C<prepend_node_names> - - Prepends node names with the specified prefix - - =cut - sub prepend_node_names { my $self = shift; --- 786,789 ---- *************** *** 1130,1139 **** } - =item C<rename_symbol> - - Renames symbol in pfa - - =cut - # renames symbol sub rename_symbol { --- 800,803 ---- *************** *** 1171,1180 **** } - =item C<info> - - Return string with info - - =cut - sub info { my $self = shift; --- 835,838 ---- *************** *** 1216,1225 **** } - =item C<serialize> - - Prints a valid string suitable for an input to stdout - - =cut - sub serialize { my $self = shift; --- 874,877 ---- *************** *** 1252,1256 **** 1; ! =back =head1 AUTHOR --- 904,927 ---- 1; ! __END__ ! ! =head1 NAME ! ! PFA - A parallel finite automata base class ! ! =head1 SYNOPSIS ! ! use PFA; ! ! =head1 DESCRIPTION ! ! This module is implements a paralle finite automata, ! and the conversion of such to a non deterministic ! finite automata; ! ! One key between PFA implementation an PFA & DFA is that the PFA ! may contain more than one start node since it may depict ! threads of concurrent execution. The main purpose of this ! module is to convert a PFA to an PFA. =head1 AUTHOR Index: NFA.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/NFA.pm,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** NFA.pm 21 Feb 2006 14:43:40 -0000 1.2 --- NFA.pm 27 Feb 2006 17:42:18 -0000 1.3 *************** *** 1,22 **** # $Revision$ $Date$ $Author$ - =head1 NAME - - NFA - A non deterministic finite automata base class - - =head1 SYNOPSIS - - use NFA; - - =head1 DESCRIPTION - - This module implements a non deterministic finite automata, - including support for epsilon transitions and conversion - to a deterministic finite automata. - - B<Methods> - - =cut - package FLAT::FA::NFA; --- 1,4 ---- *************** *** 28,38 **** use Data::Dumper; - - =item C<new> - - Returns a new FA object - - =cut - sub new { my $class = shift; --- 10,13 ---- *************** *** 47,60 **** } - =over 1 - - =item C<jump_start> - - Returns an NFA with 1 start state, one final state, and - a single transistion on the given symbol; if a symbol is - not provided, epsilon is used. - - =cut - sub jump_start { my $self = shift; --- 22,25 ---- *************** *** 81,93 **** } - - =over 1 - - =item C<load_file> - - Creates NFA from file - - =cut - sub load_file { my $self = shift; --- 46,49 ---- *************** *** 104,113 **** } - =item C<load_string> - - Creates NFA from string - - =cut - sub load_string { my $self = shift; --- 60,63 ---- *************** *** 146,157 **** } - =over 1 - - =item C<clone> - - Returns a distinct clone of self - - =cut - sub clone { my $self = shift; --- 96,99 ---- *************** *** 170,180 **** } - =item C<append_nfa> - - Concatenates start state of given NFA to the common final state of self; - usage: my NFA->append_nfa($NFA1); - - =cut - sub append_nfa { my $self = shift; --- 112,115 ---- *************** *** 216,226 **** } - =item C<prepend_nfa> - - Concatenates start state of self to the common final state of the given NFA; - usage: my NFA->prepend_nfa($NFA1); - - =cut - sub prepend_nfa { my $self = shift; --- 151,154 ---- *************** *** 263,273 **** } - =item C<or_nfa> - - Creates a common start state joined by an epsilon transition; - usage: my NFA->or_nfa($NFA1); - - =cut - sub or_nfa { my $self = shift; --- 191,194 ---- *************** *** 317,328 **** } - - =item C<kleene> - - Wraps given NFA in Kleene Closure - usage: my NFA->kleene(); - - =cut - sub kleene { my $self = shift; --- 238,241 ---- *************** *** 350,361 **** } - =item C<pinch> - - Creates epsilon transitions from all final states to a common final state; . - usage: my $NFA3 = NFA->pinch_nfa($NFA1); does nothing if there is only one - final state - - =cut - sub pinch { my $self = shift; --- 263,266 ---- *************** *** 380,389 **** } - =item C<reverse> - - Reverses an NFA - - =cut - sub reverse { my $self = shift; --- 285,288 ---- *************** *** 409,419 **** } - =item C<rename_states> - - Renames a single state; warns and changes nothing if name conflicts - with another state - - =cut - sub rename_state { my $self = shift; --- 308,311 ---- *************** *** 475,484 **** } - =item C<rename_symbol> - - Renames symbol in nfa - - =cut - # renames symbol sub rename_symbol { --- 367,370 ---- *************** *** 516,527 **** } - =item C<add_transition> - - Adds a transition - adds state and symbol as well - unique states and symbols - enforced by NFA->add_state and NFA->add_symbol; since this is an NFA, transitions - on $symbol from $state may be added to multiple destinations - - =cut - sub add_transition { my $self = shift; --- 402,405 ---- *************** *** 540,551 **** } - =item C<get_transition_on> - - Returns transition(s), as an array, for a specific state - on a specific input symbol; This is not in FA.pm as it is - NFA specific. - - =cut - sub get_transition_on { my $self = shift; --- 418,421 ---- *************** *** 561,570 **** } - =item C<set_epsilon> - - Sets epsilon symbol - not working with Perl special vars - $,@,%, etc - - =cut - sub set_epsilon { my $self = shift; --- 431,434 ---- *************** *** 574,583 **** } - =item C<get_epsilon_symbol> - - Returns epsilon symbol - - =cut - sub get_epsilon_symbol { my $self = shift; --- 438,441 ---- *************** *** 585,594 **** } - =item C<get_epsilon_transitions> - - Returns all epsilon transitions for a particular state; state must exist - - =cut - sub get_epsilon_transitions { my $self = shift; --- 443,446 ---- *************** *** 603,612 **** } - =item C<delete_epsilon> - - Deletes epsilon symbol - - =cut - sub delete_epsilon { my $self = shift; --- 455,458 ---- *************** *** 615,624 **** } - =item C<to_dfa> - - To DFA Stuff - convert NFA to DFA using subset construction technique - - =cut - sub to_dfa { my $self = shift; --- 461,464 ---- *************** *** 681,691 **** } - =item C<move> - - Get all transition states for the specific symbol - **candidate for anonymous sub in NFA->to_dfa() - - =cut - sub move { my $self = shift; --- 521,524 ---- *************** *** 712,722 **** } - =item C<epsilon_closure> - - Peform e-closure - get all the states that the provided subset of states transitions to on epsilon (empty string) - **candidate for anonymous sub in NFA->to_dfa() - - =cut - sub epsilon_closure { my $self = shift; --- 545,548 ---- *************** *** 745,754 **** } - =item C<info> - - Return string with info - - =cut - sub info { my $self = shift; --- 571,574 ---- *************** *** 783,792 **** } - =item C<serialize> - - Prints a valid string suitable for an input to stdout - - =cut - sub serialize { my $self = shift; --- 603,606 ---- *************** *** 812,831 **** } - =item C<generate_random> - - Generates random DFA; not implemented - - =cut sub generate_random { my $self = shift; } - =item C<generate_from_strings> - - Will be used to create an NFA that will accept @THIS, but - not @THAT - - =cut - sub generate_from_strings { my $self = shift; --- 626,633 ---- *************** *** 835,839 **** 1; ! =back =head1 AUTHOR --- 637,655 ---- 1; ! __END__ ! ! =head1 NAME ! ! NFA - A non deterministic finite automata base class ! ! =head1 SYNOPSIS ! ! use NFA; ! ! =head1 DESCRIPTION ! ! This module implements a non deterministic finite automata, ! including support for epsilon transitions and conversion ! to a deterministic finite automata. =head1 AUTHOR Index: PRE.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/PRE.pm,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** PRE.pm 24 Feb 2006 21:27:15 -0000 1.3 --- PRE.pm 27 Feb 2006 17:42:18 -0000 1.4 *************** *** 1,68 **** # $Revision$ $Date$ $Author$ - =head1 NAME - - PRE - A regular expression base class - - =head1 SYNOPSIS - - use PRE; - - =head1 DESCRIPTION - - This module implements a parallel regular expression - parser, and supports the conversion of a PRE to - a parallel finite automata. A homegrown recursive - descent parser is used to build the parse tree, and the method - used to convert the parallel regular expression to a PFA is a - modified Thompson's construction that accounts for the additional - interleave operator (&). - - Recursive Descent-safe Regex Grammar: - - R -> P - - P -> OP' - - P -> '&' OP' | epsilon - - O -> CO' - - O' -> '|' CO' | epsilon - - C -> SC' - - C' -> .SC' | epsilon - - S -> LS' - - S' -> *S' | epsilon - - L -> a | b | c |..| 0 | 1 | 2 |..| (R) | epsilon - - Terminal symbols: a,b,c,..,z,0,1,2,..,9,|,*,(,) - - NOTE: Concatenation operator, '.', is not a terminal symbol - and should not be included in the regex - - FAQ: - Q: Does this support Perl regular expressions? - A: No, just the regular expression using the terminal symbols - listed above. - - B<Valid terminal characters include:> - - I<a b c d e f g h i j k l m n o p q r s t u v w x y z> - - I<A B C D E F G H I J K L M N O P Q R S T U V W X Y Z> - - I<0 1 2 3 4 5 6 7 8 9 + - = ? [ ] { } . ~ ^ @ % $> - - I<: ; < >> - - B<Methods> - - =cut - package FLAT::FA::PRE; --- 1,4 ---- *************** *** 74,85 **** use Data::Dumper; - =over 1 - - =item C<new> - - Create a brand spaking new pRE object; does not accept regex here - - =cut - sub new { my $class = shift; --- 10,13 ---- *************** *** 107,117 **** } - =item C<set_epsilon> - - Not really for public consumption, but could be in the future. Defines - how epsilon (i.e., the null string) is represented in the parse tree. - - =cut - sub set_epsilon { my $self = shift; --- 35,38 ---- *************** *** 122,131 **** } - =item C<get_epsilon_symbol> - - Returns the string representation of the null string - - =cut - sub get_epsilon_symbol { my $self = shift; --- 43,46 ---- *************** *** 133,143 **** } - - =item C<set_pre> - - Defines a regular expression for RE to parse through - - =cut - sub set_pre { my $self = shift; --- 48,51 ---- *************** *** 174,184 **** } - - =item C<get_pre> - - Returns the regular expression set by C<set_pre> as a string - - =cut - sub get_pre { my $self = shift; --- 82,85 ---- *************** *** 186,196 **** } - =item C<set_current> - - Meant for private consumption. Initializes the stack used to store - what part of the regex has yet to be parsed - - =cut - sub set_current { my $self = shift; --- 87,90 ---- *************** *** 201,211 **** } - =item C<reset_current> - - Meant for private consumption. Initializes the stack used to store - what part of the regex has yet to be parsed - - =cut - sub reset_current { my $self = shift; --- 95,98 ---- *************** *** 214,223 **** } - =item C<get_current> - - Returns what is in the _CURRENT_STR stack - - =cut - sub get_current { my $self = shift; --- 101,104 ---- *************** *** 225,236 **** } - =item C<to_pfa> - - Not implemented, but will create an PFA using Thompson's Method; from there - one could do a PFA->to_dfa, and compare the resulting dfa to the one from - RE->to_dfa. - - =cut - sub to_pfa { my $self = shift; --- 106,109 ---- *************** *** 246,255 **** } - =item C<thompson> - - Guts of RE->to_pfa; uses depth first parse tree traversal - - =cut - sub thompson { my $self = shift; --- 119,122 ---- *************** *** 293,302 **** ################################################################ - =item C<parse> - - Parses regular expressin set by RE->set_pre, and stores the parse tree in _PARSE_TREE - - =cut - sub parse { my $self = shift; --- 160,163 ---- *************** *** 310,319 **** } - =item C<cat_endmarker> - - Adds '#', or the end of regex marker to the parse tree; not for public consumption - - =cut - sub cat_endmarker { my $self = shift; --- 171,174 ---- *************** *** 322,332 **** } - =item C<match> - - Matches current terminal symbol with terminal character, - and loads up the next lookahead character - - =cut - sub match { my $self = shift; --- 177,180 ---- *************** *** 344,353 **** } - =item C<lookahead> - - Returns value of current lookahead - - =cut - sub lookahead { my $self = shift; --- 192,195 ---- *************** *** 355,364 **** } - =item C<nexttoken> - - Sets next token as lookahead - - =cut - sub nexttoken { my $self = shift; --- 197,200 ---- *************** *** 370,379 **** } - =item C<R> - - R -> O - - =cut - sub R { my $self = shift; --- 206,209 ---- *************** *** 387,396 **** } - =item C<P> - - P -> OP' - - =cut - sub P { my $self = shift; --- 217,220 ---- *************** *** 405,414 **** } - =item C<P_prime> - - P' -> '&'O | epsilon - - =cut - sub P_prime { my $self = shift; --- 229,232 ---- *************** *** 437,446 **** } - =item C<O> - - O -> CO' - - =cut - sub O { my $self = shift; --- 255,258 ---- *************** *** 455,464 **** } - =item C<O_prime> - - O' -> '|'CO' | epsilon - - =cut - sub O_prime { my $self = shift; --- 267,270 ---- *************** *** 487,496 **** } - =item C<C> - - C -> SC' - - =cut - sub C { my $self = shift; --- 293,296 ---- *************** *** 505,514 **** } - =item C<C_prime> - - C' -> .SC' | epsilon - - =cut - sub C_prime { my $self = shift; --- 305,308 ---- *************** *** 536,545 **** } - =item C<S> - - S -> LS' - - =cut - sub S { my $self = shift; --- 330,333 ---- *************** *** 554,563 **** } - =item C<S_prime> - - S' -> *S' | epsilon - - =cut - sub S_prime { my $self = shift; --- 342,345 ---- *************** *** 575,584 **** } - =item C<L> - - L -> a | b | c |..| 0 | 1 | 2 |..| (R) - - =cut - sub L { my $self = shift; --- 357,360 ---- *************** *** 611,620 **** } - =item C<get_next_pos> - - Returns the next position, used in creating leaf nodes for terminal symbols (minus null string) - - =cut - sub get_next_pos { my $self = shift; --- 387,390 ---- *************** *** 622,631 **** } - =item C<get_curr_pos> - - Returns the current count of terminal symbols (minus null string) - - =cut - sub get_curr_pos { my $self = shift; --- 392,395 ---- *************** *** 633,642 **** } - =item C<set_parse_tree> - - Set parse tree - - =cut - sub set_parse_tree { my $self = shift; --- 397,400 ---- *************** *** 645,654 **** } - =item C<get_parse_tree> - - Return parse tree - - =cut - sub get_parse_tree { my $self = shift; --- 403,406 ---- *************** *** 656,665 **** } - =item C<get_terminals> - - Returns array of terminal symbols - - =cut - sub get_terminals { my $self = shift; --- 408,411 ---- *************** *** 667,676 **** } - =item C<is_terminal> - - Checks to see if given character is a terminal symbol - - =cut - sub is_terminal { my $self = shift; --- 413,416 ---- *************** *** 678,687 **** } - =item C<is_member> - - General subroutine used to test if an element is already in an array - - =cut - sub is_member { my $self = shift; --- 418,421 ---- *************** *** 705,714 **** } - =item C<get_symbols> - - Returns array of all symbols used in current regex - - =cut - sub get_symbols { my $self = shift; --- 439,442 ---- *************** *** 716,725 **** } - =item C<trace_on> - - Turns on tracing - allows to trace the recursive descent parsing - - =cut - sub trace_on { my $self = shift; --- 444,447 ---- *************** *** 728,737 **** } - =item C<trace_off> - - Turns tracing off - - =cut - sub trace_off { my $self = shift; --- 450,453 ---- *************** *** 740,749 **** } - =item C<trace> - - Returns value of _TRACE - - =cut - sub trace { my $self = shift; --- 456,459 ---- *************** *** 751,760 **** } - =item C<toggle_cat_state> - - Toggles cat state instead of cat'ing a '.' to everything - - =cut - sub toggle_cat_state { my $self = shift; --- 461,464 ---- *************** *** 763,772 **** } - =item C<get_cat_state> - - Returns $self->{_CAT_STATE} (1|0) - - =cut - sub get_cat_state { my $self = shift; --- 467,470 ---- *************** *** 774,783 **** } - =item C<set_error> - - Increments error count for regex parsing - - =cut - sub set_error { my $self = shift; --- 472,475 ---- *************** *** 785,794 **** } - =item C<get_error> - - Returns error count - - =cut - sub get_error { my $self = shift; --- 477,480 ---- *************** *** 796,805 **** } - =item C<set_done> - - Sets done flag - - =cut - sub set_done { my $self = shift; --- 482,485 ---- *************** *** 807,816 **** } - =item C<done> - - Returns if done or not - - =cut - sub done { my $self = shift; --- 487,490 ---- *************** *** 818,829 **** } - =item C<DESTROY> - - Called automatically when object is destroyed either explicitly - or automatically when references go to 0 or when the main program - is finished - - =cut - sub DESTROY { return; --- 492,495 ---- *************** *** 832,836 **** 1; ! =back =head1 AUTHOR --- 498,562 ---- 1; ! __END__ ! ! =head1 NAME ! ! PRE - A regular expression base class ! ! =head1 SYNOPSIS ! ! use PRE; ! ! =head1 DESCRIPTION ! ! This module implements a parallel regular expression ! parser, and supports the conversion of a PRE to ! a parallel finite automata. A homegrown recursive ! descent parser is used to build the parse tree, and the method ! used to convert the parallel regular expression to a PFA is a ! modified Thompson's construction that accounts for the additional ! interleave operator (&). ! ! Recursive Descent-safe Regex Grammar: ! ! R -> P ! ! P -> OP' ! ! P -> '&' OP' | epsilon ! ! O -> CO' ! ! O' -> '|' CO' | epsilon ! ! C -> SC' ! ! C' -> .SC' | epsilon ! ! S -> LS' ! ! S' -> *S' | epsilon ! ! L -> a | b | c |..| 0 | 1 | 2 |..| (R) | epsilon ! ! Terminal symbols: a,b,c,..,z,0,1,2,..,9,|,*,(,) ! ! NOTE: Concatenation operator, '.', is not a terminal symbol ! and should not be included in the regex ! ! FAQ: ! Q: Does this support Perl regular expressions? ! A: No, just the regular expression using the terminal symbols ! listed above. ! ! B<Valid terminal characters include:> ! ! I<a b c d e f g h i j k l m n o p q r s t u v w x y z> ! ! I<A B C D E F G H I J K L M N O P Q R S T U V W X Y Z> ! ! I<0 1 2 3 4 5 6 7 8 9 + - = ? [ ] { } . ~ ^ @ % $> ! ! I<: ; < >> =head1 AUTHOR Index: RE.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/RE.pm,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** RE.pm 24 Feb 2006 21:27:15 -0000 1.3 --- RE.pm 27 Feb 2006 17:42:18 -0000 1.4 *************** *** 1,68 **** # $Revision$ $Date$ $Author$ - =head1 NAME - - RE - A regular expression base class - - =head1 SYNOPSIS - - use RE; - use DFA; - my $re = RE->new(); - $re->set_re('a|b|(hi)*'); - my $dfa = $re->to_dfa(); - print $dfa->info(); # see stuff on DFA - - =head1 DESCRIPTION - - This module implements a regular expression - parser, and supports the conversion of a RE to - a deterministic finite automata. A homegrown recursive - descent parser is used to build the parse tree, and the method - used to conver the regular expression to a DFA uses no intermediate - NFA. - - Recursive Descent-safe Regex Grammar: - - R -> O - - O -> CO' - - O' -> '|' CO' | epsilon - - C -> SC' - - C' -> .SC' | epsilon - - S -> LS' - - S' -> *S' | epsilon - - L -> a | b | c |..| 0 | 1 | 2 |..| (R) | epsilon - - Terminal symbols: a,b,c,..,z,0,1,2,..,9,|,*,(,) - - NOTE: Concatenation operator, '.', is not a terminal symbol - and should not be included in the regex - - FAQ: - Q: Does this support Perl regular expressions? - A: No, just the regular expression using the terminal symbols - listed above. - - B<Valid terminal characters include:> - - I<a b c d e f g h i j k l m n o p q r s t u v w x y z> - - I<A B C D E F G H I J K L M N O P Q R S T U V W X Y Z> - - I<0 1 2 3 4 5 6 7 8 9 + - = ? & [ ] { } . ~ ^ @ % $> - - I<: ; < >> - - B<Methods> - - =cut - package FLAT::FA::RE; --- 1,4 ---- *************** *** 75,86 **** use Data::Dumper; - =over 1 - - =item C<new> - - Create a brand spaking new RE object; does not accept regex here - - =cut - sub new { my $class = shift; --- 11,14 ---- *************** *** 108,118 **** } - =item C<set_epsilon> - - Not really for public consumption, but could be in the future. Defines - how epsilon (i.e., the null string) is represented in the parse tree. - - =cut - sub set_epsilon { my $self = shift; --- 36,39 ---- *************** *** 123,132 **** } - =item C<get_epsilon_symbol> - - Returns the string representation of the null string - - =cut - sub get_epsilon_symbol { my $self = shift; --- 44,47 ---- *************** *** 134,144 **** } - - =item C<set_re> - - Defines a regular expression for RE to parse through - - =cut - sub set_re { my $self = shift; --- 49,52 ---- *************** *** 175,185 **** } - - =item C<get_re> - - Returns the regular expression set by C<set_re> as a string - - =cut - sub get_re { my $self = shift; --- 83,86 ---- *************** *** 187,197 **** } - =item C<set_current> - - Meant for private consumption. Initializes the stack used to store - what part of the regex has yet to be parsed - - =cut - sub set_current { my $self = shift; --- 88,91 ---- *************** *** 202,212 **** } - =item C<reset_current> - - Meant for private consumption. Initializes the stack used to store - what part of the regex has yet to be parsed - - =cut - sub reset_current { my $self = shift; --- 96,99 ---- *************** *** 215,224 **** } - =item C<get_current> - - Returns what is in the _CURRENT_STR stack - - =cut - sub get_current { my $self = shift; --- 102,105 ---- *************** *** 226,247 **** } - =item C<minimize> - - Minimizes the regular expression optimally - - =cut - sub minimize { my $self = shift; - return; } - =item C<shrink> - - Shrinks RE using hueristics to create a 'small enough' equivalent expression - - =cut - sub shrink { my $self = shift; --- 107,115 ---- *************** *** 250,261 **** } - =item C<to_nfa> - - Not implemented, but will create an NFA using Thompson's Method; from there - one could do a NFA->to_dfa, and compare the resulting dfa to the one from - RE->to_dfa. - - =cut - sub to_nfa { my $self = shift; --- 118,121 ---- *************** *** 269,278 **** } - =item C<thompson> - - Guts of RE->to_nfa; uses depth first parse tree traversal - - =cut - sub thompson { my $self = shift; --- 129,132 ---- *************** *** 310,322 **** } ! =item C<to_dfa> ! ! Currently BREAKS on a*(b|cd)m!!!!!!!!!!!!!! ! ! Main driver which is used to convert the regular expression to a DFA; calls ! RE->parse() internally if _PARSE_TREE is !defined, so no need to call before this function. ! ! =cut ! sub to_dfa_BROKEN { my $self = shift; --- 164,168 ---- } ! #Currently BREAKS on a*(b|cd)m!!!!!!!!!!!!!! sub to_dfa_BROKEN { my $self = shift; *************** *** 387,397 **** } - - =item C<get_transitions_on> - - Provides a way to get the transitions using the contents of the _FOLLOW_POS table - - =cut - sub get_transition_on { my $self = shift; --- 233,236 ---- *************** *** 405,415 **** } - =item C<move> - - Called by RE->to_re to get the sub set of new states for each sub set of states during - the sub state construction process of building the DFA - - =cut - sub move { my $self = shift; --- 244,247 ---- *************** *** 436,445 **** } - =item C<firstpos> - - Determines firt positions for all nodes in the a parse tree - - =cut - sub firstpos { my $self = shift; --- 268,271 ---- *************** *** 488,497 **** } - =item C<lastpost> - - Determines the last postition for all nodes in the parse tree - - =cut - sub lastpos { my $self = shift; --- 314,317 ---- *************** *** 540,549 **** } - =item C<followpos> - - Determines the first postition for all nodes in the parse tree - - =cut - sub followpos { my $self = shift; --- 360,363 ---- *************** *** 569,578 **** } - =item C<followpos> - - Returns hash containing follow position table - - =cut - sub get_followpos { my $self = shift; --- 383,386 ---- *************** *** 584,593 **** ################################################################ - =item C<parse> - - Parses regular expressin set by RE->set_re, and stores the parse tree in _PARSE_TREE - - =cut - sub parse { my $self = shift; --- 392,395 ---- *************** *** 601,610 **** } - =item C<cat_endmarker> - - Adds '#', or the end of regex marker to the parse tree; not for public consumption - - =cut - sub cat_endmarker { my $self = shift; --- 403,406 ---- *************** *** 613,623 **** } - =item C<match> - - Matches current terminal symbol with terminal character, - and loads up the next lookahead character - - =cut - sub match { my $self = shift; --- 409,412 ---- *************** *** 635,644 **** } - =item C<lookahead> - - Returns value of current lookahead - - =cut - sub lookahead { my $self = shift; --- 424,427 ---- *************** *** 646,655 **** } - =item C<nexttoken> - - Sets next token as lookahead - - =cut - sub nexttoken { my $self = shift; --- 429,432 ---- *************** *** 661,670 **** } - =item C<R> - - R -> O - - =cut - sub R { my $self = shift; --- 438,441 ---- *************** *** 678,687 **** } - =item C<O> - - O -> CO' - - =cut - sub O { my $self = shift; --- 449,452 ---- *************** *** 696,705 **** } - =item C<O_prime> - - O' -> '|'CO' | epsilon - - =cut - sub O_prime { my $self = shift; --- 461,464 ---- *************** *** 728,737 **** } - =item C<C> - - C -> SC' - - =cut - sub C { my $self = shift; --- 487,490 ---- *************** *** 746,755 **** } - =item C<C_prime> - - C' -> .SC' | epsilon - - =cut - sub C_prime { my $self = shift; --- 499,502 ---- *************** *** 777,786 **** } - =item C<S> - - S -> LS' - - =cut - sub S { my $self = shift; --- 524,527 ---- *************** *** 795,804 **** } - =item C<S_prime> - - S' -> *S' | epsilon - - =cut - sub S_prime { my $self = shift; --- 536,539 ---- *************** *** 816,825 **** } - =item C<L> - - L -> a | b | c |..| 0 | 1 | 2 |..| (R) - - =cut - sub L { my $self = shift; --- 551,554 ---- *************** *** 852,861 **** } - =item C<get_next_pos> - - Returns the next position, used in creating leaf nodes for terminal symbols (minus null string) - - =cut - sub get_next_pos { my $self = shift; --- 581,584 ---- *************** *** 863,872 **** } - =item C<get_curr_pos> - - Returns the current count of terminal symbols (minus null string) - - =cut - sub get_curr_pos { my $self = shift; --- 586,589 ---- *************** *** 874,883 **** } - =item C<set_parse_tree> - - Set parse tree - - =cut - sub set_parse_tree { my $self = shift; --- 591,594 ---- *************** *** 886,895 **** } - =item C<get_parse_tree> - - Return parse tree - - =cut - sub get_parse_tree { my $self = shift; --- 597,600 ---- *************** *** 897,906 **** } - =item C<get_terminals> - - Returns array of terminal symbols - - =cut - sub get_terminals { my $self = shift; --- 602,605 ---- *************** *** 908,917 **** } - =item C<is_terminal> - - Checks to see if given character is a terminal symbol - - =cut - sub is_terminal { my $self = shift; --- 607,610 ---- *************** *** 919,928 **** } - =item C<is_member> - - General subroutine used to test if an element is already in an array - - =cut - sub is_member { my $self = shift; --- 612,615 ---- *************** *** 934,955 **** $ret++; } - # foreach (@_) { - # if (defined($_)) { - # if ($test eq $_) { - # $ret++; - # last; - # } - # } - # } } return $ret; } - =item C<get_symbols> - - Returns array of all symbols used in current regex - - =cut - sub get_symbols { my $self = shift; --- 621,628 ---- *************** *** 957,966 **** } - =item C<trace_on> - - Turns on tracing - allows to trace the recursive descent parsing - - =cut - sub trace_on { my $self = shift; --- 630,633 ---- *************** *** 969,978 **** } - =item C<trace_off> - - Turns tracing off - - =cut - sub trace_off { my $self = shift; --- 636,639 ---- *************** *** 981,990 **** } - =item C<trace> - - Returns value of _TRACE - - =cut - sub trace { my $self = shift; --- 642,645 ---- *************** *** 992,1001 **** } - =item C<toggle_cat_state> - - Toggles cat state instead of cat'ing a '.' to everything - - =cut - sub toggle_cat_state { my $self = shift; --- 647,650 ---- *************** *** 1004,1013 **** } - =item C<get_cat_state> - - Returns $self->{_CAT_STATE} (1|0) - - =cut - sub get_cat_state { my $self = shift; --- 653,656 ---- *************** *** 1015,1024 **** } - =item C<set_error> - - Increments error count for regex parsing - - =cut - sub set_error { my $self = shift; --- 658,661 ---- *************** *** 1026,1035 **** } - =item C<get_error> - - Returns error count - - =cut - sub get_error { my $self = shift; --- 663,666 ---- *************** *** 1037,1046 **** } - =item C<set_done> - - Sets done flag - - =cut - sub set_done { my $self = shift; --- 668,671 ---- *************** *** 1048,1057 **** } - =item C<done> - - Returns if done or not - - =cut - sub done { my $self = shift; --- 673,676 ---- *************** *** 1059,1070 **** } - =item C<DESTROY> - - Called automatically when object is destroyed either explicitly - or automatically when references go to 0 or when the main program - is finished - - =cut - sub DESTROY { return; --- 678,681 ---- *************** *** 1073,1077 **** 1; ! =back =head1 AUTHOR --- 684,748 ---- 1; ! __END__ ! ! =head1 NAME ! ! RE - A regular expression base class ! ! =head1 SYNOPSIS ! ! use RE; ! use DFA; ! my $re = RE->new(); ! $re->set_re('a|b|(hi)*'); ! my $dfa = $re->to_dfa(); ! print $dfa->info(); # see stuff on DFA ! ! =head1 DESCRIPTION ! ! This module implements a regular expression ! parser, and supports the conversion of a RE to ! a deterministic finite automata. A homegrown recursive ! descent parser is used to build the parse tree, and the method ! used to conver the regular expression to a DFA uses no intermediate ! NFA. ! ! Recursive Descent-safe Regex Grammar: ! ! R -> O ! ! O -> CO' ! ! O' -> '|' CO' | epsilon ! ! C -> SC' ! ! C' -> .SC' | epsilon ! ! S -> LS' ! ! S' -> *S' | epsilon ! ! L -> a | b | c |..| 0 | 1 | 2 |..| (R) | epsilon ! ! Terminal symbols: a,b,c,..,z,0,1,2,..,9,|,*,(,) ! ! NOTE: Concatenation operator, '.', is not a terminal symbol ! and should not be included in the regex ! ! FAQ: ! Q: Does this support Perl regular expressions? ! A: No, just the regular expression using the terminal symbols ! listed above. ! ! B<Valid terminal characters include:> ! ! I<a b c d e f g h i j k l m n o p q r s t u v w x y z> ! ! I<A B C D E F G H I J K L M N O P Q R S T U V W X Y Z> ! ! I<0 1 2 3 4 5 6 7 8 9 + - = ? & [ ] { } . ~ ^ @ % $> ! ! I<: ; < >> =head1 AUTHOR |
|
From: <per...@li...> - 2006-02-27 17:42:24
|
Update of /cvsroot/perl-flat/flat4cpan/lib/FLAT In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv31851/lib/FLAT Modified Files: FA.pm Log Message: cleaning up comments Index: FA.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA.pm,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** FA.pm 24 Feb 2006 21:27:15 -0000 1.3 --- FA.pm 27 Feb 2006 17:42:18 -0000 1.4 *************** *** 1,23 **** # $Revision$ $Date$ $Author$ - =head1 NAME - - FA - A finite automata base class - - =head1 SYNOPSIS - - use FA; - - =head1 DESCRIPTION - - This module is a base finite automata - used by NFA and DFA to encompass - common functions. It is probably of no use - other than to organize the DFA and NFA modules. - - B<Methods> - - =cut - package FLAT::FA; --- 1,4 ---- *************** *** 28,39 **** use Data::Dumper; - =over 18 - - =item C<set_start> - - Sets start state, calls FA->add_state - - =cut - sub set_start { my $self = shift; --- 9,12 ---- *************** *** 46,55 **** } - =item C<get_start> - - Returns start state name as string - - =cut - sub get_start { my $self = shift; --- 19,22 ---- *************** *** 57,66 **** } - =item C<is_start> - - Tests is string is the start state - - =cut - sub is_start { my $self = shift; --- 24,27 ---- *************** *** 72,81 **** } - =item C<add_state> - - Adds a state label to the state array if it does not already exist (handles dups) - - =cut - sub add_state { my $self = shift; --- 33,36 ---- *************** *** 88,97 **** } - =item C<get_states> - - Returns the array of all states - - =cut - # Returns array of states sub get_states { --- 43,46 ---- *************** *** 100,116 **** } - =item C<ensure_unique_states> - - Compares the names of the states in $self and the - provided FA, and only renames a state (in $self) - if a name collision is detected; if the disambiguation - string causes a new collision, a random string is created - using crypt() until there is no collision detected - - Usage: - $self->ensure_unique_states($NFA1,'string_to_disambiguate'); - - =cut - sub ensure_unique_states { my $self = shift; --- 49,52 ---- *************** *** 131,141 **** } - =item C<number_states> - - Numbers states 0-# of states; first appends state name with a - random string to avoid conflicts - - =cut - sub number_states { my $self = shift; --- 67,70 ---- *************** *** 157,166 **** } - =item C<append_state_names> - - Appends state names with the specified suffix - - =cut - sub append_state_names { my $self = shift; --- 86,89 ---- *************** *** 177,187 **** } - - =item C<prepend_state_names> - - Prepends state names with the specified prefix - - =cut - sub prepend_state_names { my $self = shift; --- 100,103 ---- *************** *** 198,207 **** } - =item C<is_state> - - Tests if given string is the name of a state - - =cut - # Will test if the string passed to it is the same as a label of any state sub is_state { --- 114,117 ---- *************** *** 210,220 **** } - =item C<add_final> - - Adds a list of state lables to the final states array; handles dups - and ensures state is in set of states $self->{{STATES} - - =cut - # Adds state to final (accepting) state stack sub add_final { --- 120,123 ---- *************** *** 232,241 **** } - =item C<remove_final> - - Removes the given state from $self->{_FINAL_STATES} - - =cut - sub remove_final { my $self = shift; --- 135,138 ---- *************** *** 251,260 **** } - =item C<get_final> - - Returns the array of all final states - - =cut - # Returns array of final states sub get_final { --- 148,151 ---- *************** *** 263,273 **** } - - =item C<is_final> - - Checks to see if given state is in the final state array - - =cut - # Will test if the string passed to it is the same as a label of any state sub is_final { --- 154,157 ---- *************** *** 276,285 **** } - =item C<add_symbol> - - Adds symbol to the symbol array; handles dups - - =cut - # Adds symbol sub add_symbol { --- 160,163 ---- *************** *** 293,302 **** } - =item C<is_symbol> - - Checks to see if given symbol is in the symbol array - - =cut - # Will test if the string passed to it is the same as a label of any symbol sub is_symbol { --- 171,174 ---- *************** *** 305,314 **** } - =item C<get_symbols> - - Returns array of all symbols - - =cut - # Returns array of all symbols sub get_symbols { --- 177,180 ---- *************** *** 317,326 **** } - =item C<get_transition> - - Returns hash of all transitions (symbols and next states) for given state - - =cut - # Returns a hash of all transitions (symbols and next states) for specified state sub get_transition { --- 183,186 ---- *************** *** 331,340 **** } - =item C<get_all_transitions> - - Returns hash of all transitions for all states and symbols - - =cut - sub get_all_transitions { my $self = shift; --- 191,194 ---- *************** *** 342,352 **** } - - =item C<has_transition_on> - - Tests if given state has a transition on given symbol - - =cut - sub has_transition_on { my $self = shift; --- 196,199 ---- *************** *** 360,369 **** } - =item C<has_transitions> - - Tests if given state has a transition on given symbol - - =cut - sub has_transitions { my $self = shift; --- 207,210 ---- *************** *** 376,386 **** } - - =item C<delete_transition> - - Deletes transition given the state and the symbol - - =cut - sub delete_transition { my $self = shift; --- 217,220 ---- *************** *** 393,402 **** } - =item C<to_file> - - Dumps FA to file in the proper input file format - - =cut - sub to_file { my $self = shift; --- 227,230 ---- *************** *** 408,422 **** } - =over 18 - - =item C<compliment> - - Returns compliment of 2 arrays - i.e., the items that they - do not have in common; requires arrays be passed by reference; - example: - my @compliment = $self->compliment(\@set1,\@set2); - - =cut - sub compliment { my $self = shift; --- 236,239 ---- *************** *** 446,455 **** } - =item C<is_member> - - Tests if string is in given array - - =cut - # General subroutine used to test if an element is already in an array sub is_member { --- 263,266 ---- *************** *** 462,483 **** $ret++; } - # foreach (@_) { - # if (defined($_)) { - # if ($test eq $_) { - # $ret++; - # last; - # } - # } - # } } return $ret; } - =item C<DESTROY> - - Called automatically when object is no longer needed - - =cut - sub DESTROY { return; --- 273,280 ---- *************** *** 486,490 **** 1; ! =back =head1 AUTHOR --- 283,302 ---- 1; ! __END__ ! ! =head1 NAME ! ! FA - A finite automata base class ! ! =head1 SYNOPSIS ! ! use FA; ! ! =head1 DESCRIPTION ! ! This module is a base finite automata ! used by NFA and DFA to encompass ! common functions. It is probably of no use ! other than to organize the DFA and NFA modules. =head1 AUTHOR *************** *** 510,518 **** This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. =head1 COPYRIGHT This code is released under the same terms as Perl. - - =cut --- 322,328 ---- This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern ! Mississippi. It then became the basis for my MS research. and thesis. =head1 COPYRIGHT This code is released under the same terms as Perl. |
|
From: <per...@li...> - 2006-02-27 17:42:21
|
Update of /cvsroot/perl-flat/flat4cpan/t In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv31851/t Removed Files: FLAT-FA-INPUT.t Log Message: cleaning up comments --- FLAT-FA-INPUT.t DELETED --- |
|
From: <per...@li...> - 2006-02-27 17:42:21
|
Update of /cvsroot/perl-flat/flat4cpan In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv31851 Modified Files: MANIFEST Log Message: cleaning up comments Index: MANIFEST =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/MANIFEST,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** MANIFEST 24 Feb 2006 21:27:15 -0000 1.5 --- MANIFEST 27 Feb 2006 17:42:17 -0000 1.6 *************** *** 6,10 **** t/FLAT-FA-RE.t t/FLAT-FA-PRE.t - t/FLAT-FA-INPUT.t lib/FLAT/FA.pm lib/FLAT/FA/DFA.pm --- 6,9 ---- |
|
From: <per...@li...> - 2006-02-24 21:37:26
|
Update of /cvsroot/perl-flat/flat4cpan/t In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7967 Modified Files: FLAT-FA-INPUT.t Log Message: added note about what I have planned for this test Index: FLAT-FA-INPUT.t =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/t/FLAT-FA-INPUT.t,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** FLAT-FA-INPUT.t 24 Feb 2006 21:27:15 -0000 1.1 --- FLAT-FA-INPUT.t 24 Feb 2006 21:37:21 -0000 1.2 *************** *** 31,32 **** --- 31,36 ---- #$dfa->load_file('input/dfa.1'); #isa_ok($dfa,'FLAT::FA::DFA'); + + ##It is my intention to not only use existing input files, but + ##also to generate them, test output ability, then make sure + ##I can read them back in properly. |
|
From: <per...@li...> - 2006-02-24 21:27:23
|
Update of /cvsroot/perl-flat/flat4cpan In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3762 Modified Files: MANIFEST Log Message: more tests...input and output files now Index: MANIFEST =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/MANIFEST,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** MANIFEST 24 Feb 2006 00:03:37 -0000 1.4 --- MANIFEST 24 Feb 2006 21:27:15 -0000 1.5 *************** *** 6,9 **** --- 6,10 ---- t/FLAT-FA-RE.t t/FLAT-FA-PRE.t + t/FLAT-FA-INPUT.t lib/FLAT/FA.pm lib/FLAT/FA/DFA.pm |
|
From: <per...@li...> - 2006-02-24 21:27:22
|
Update of /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3762/lib/FLAT/FA Modified Files: DFA.pm PFA.pm PRE.pm RE.pm Log Message: more tests...input and output files now Index: DFA.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/DFA.pm,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** DFA.pm 21 Feb 2006 14:43:40 -0000 1.2 --- DFA.pm 24 Feb 2006 21:27:15 -0000 1.3 *************** *** 37,41 **** my $class = shift; bless { ! _START_STATE => undef, # start states -> plural! _STATES => [], # Set of all states _FINAL_STATES => [], # Set of final states, subset of _STATES --- 37,41 ---- my $class = shift; bless { ! _START_STATE => undef, # start states -> plural! _STATES => [], # Set of all states _FINAL_STATES => [], # Set of final states, subset of _STATES Index: PFA.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/PFA.pm,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** PFA.pm 21 Feb 2006 14:43:40 -0000 1.2 --- PFA.pm 24 Feb 2006 21:27:15 -0000 1.3 *************** *** 1081,1085 **** } # rename nodes as actual numbers ! my $number = 0; foreach ($self->get_nodes()) { $self->rename_node($_,$number); --- 1081,1085 ---- } # rename nodes as actual numbers ! $number = 0; foreach ($self->get_nodes()) { $self->rename_node($_,$number); Index: PRE.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/PRE.pm,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** PRE.pm 21 Feb 2006 14:43:40 -0000 1.2 --- PRE.pm 24 Feb 2006 21:27:15 -0000 1.3 *************** *** 57,61 **** I<A B C D E F G H I J K L M N O P Q R S T U V W X Y Z> ! I<0 1 2 3 4 5 6 7 8 9 + - = , ? [ ] { } . ~ ^ @ % $> I<: ; < >> --- 57,61 ---- I<A B C D E F G H I J K L M N O P Q R S T U V W X Y Z> ! I<0 1 2 3 4 5 6 7 8 9 + - = ? [ ] { } . ~ ^ @ % $> I<: ; < >> *************** *** 100,104 **** _TERMINALS => [qw(a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ! 0 1 2 3 4 5 6 7 8 9 + - = , ? [ ] { } . ~ ^ @ % $ : ; < >)], _TRACE => 0, --- 100,104 ---- _TERMINALS => [qw(a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ! 0 1 2 3 4 5 6 7 8 9 + - = ? [ ] { } . ~ ^ @ % $ : ; < >)], _TRACE => 0, Index: RE.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA/RE.pm,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** RE.pm 21 Feb 2006 14:43:40 -0000 1.2 --- RE.pm 24 Feb 2006 21:27:15 -0000 1.3 *************** *** 57,61 **** I<A B C D E F G H I J K L M N O P Q R S T U V W X Y Z> ! I<0 1 2 3 4 5 6 7 8 9 + - = , ? & [ ] { } . ~ ^ @ % $> I<: ; < >> --- 57,61 ---- I<A B C D E F G H I J K L M N O P Q R S T U V W X Y Z> ! I<0 1 2 3 4 5 6 7 8 9 + - = ? & [ ] { } . ~ ^ @ % $> I<: ; < >> *************** *** 101,105 **** _TERMINALS => [qw(a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ! 0 1 2 3 4 5 6 7 8 9 + - = , ? & [ ] { } . ~ ^ @ % $ : ; < >)], _TRACE => 0, --- 101,105 ---- _TERMINALS => [qw(a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ! 0 1 2 3 4 5 6 7 8 9 + - = ? & [ ] { } . ~ ^ @ % $ : ; < >)], _TRACE => 0, *************** *** 399,403 **** my $symbol = shift; my @ret = undef; ! if (@{$self->{_SYMBOL_POS}}->[$state-1] eq $symbol) { @ret = @{$self->{_FOLLOW_POS}->{$state}}; } --- 399,403 ---- my $symbol = shift; my @ret = undef; ! if (@{$self->{_SYMBOL_POS}}[$state-1] eq $symbol) { @ret = @{$self->{_FOLLOW_POS}->{$state}}; } |
Update of /cvsroot/perl-flat/flat4cpan/t/input In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3762/t/input Added Files: dfa.1 nfa.1 nfa.2 nfa.3 nfa.4 nfa.5 nfa.6 nfa.7 pfa.1 pfa.2 pfa.3 Log Message: more tests...input and output files now --- NEW FILE: pfa.1 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ # PFA 1 START :: 1 # start node(s) FINAL :: 4,6 # end nodes LAMBDA :: lambda # how lambda split/sync is represented EPSILON :: epsilon # how epsilon transition is represented 0: epsilon 1 1: lambda 2,5 2: c 3 3: c 3 d 4 4: c 3 d 4 5: a 5 b 6 6: --- NEW FILE: pfa.2 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ # PFA 2 START :: 1 # start node(s) FINAL :: 5,6 # end nodes LAMBDA :: lambda # how lambda split/sync is represented EPSILON :: epsilon # how epsilon transition is represented 1: a 2 2: lambda 3,4 3: b 5 4: c 6 5: 6: --- NEW FILE: pfa.3 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ # PFA 1 START :: 1,2 # start node(s) FINAL :: 6 # end nodes LAMBDA :: lambda # how lambda split/sync is represented EPSILON :: epsilon # how epsilon transition is represented 1: a 3 2: b 4 3: lambda 5 4: lambda 5 5: c 6 6: --- NEW FILE: dfa.1 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ START :: 0 FINAL :: 2,2_5,2_4_5 0: a 1_3 b 2 1_3: a 2 b 2_4_5 2: c 4 4: b 5 5: c 1 1: b 2_5 2_5: c 1_4 1_4: b 2_5 2_4_5: c 1_4 b 5 --- NEW FILE: nfa.6 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ # NFA 7 START :: 0 # start state FINAL :: 2 # end states EPSILON :: epsilon # how epsilon transition is represented 0: epsilon 3 a 1 1: b 2,5 2: 3: b 4 4: epsilon 2 a 1 --- NEW FILE: nfa.7 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ # # State Transition File # The detection of of an '&' or 'epsilon' flags this FSA as nondetermininstic # Otherwise, it is treated as deterministic # 0: epsilon 1 # nfa detected bc of 'epsilon' a 2 b 3 1: a 2 & 4 # nfa could also be flagged when this '&' is detected 2: b 3 & 4 3: epsilon 4 4: a 0 --- NEW FILE: nfa.4 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ START :: 0 FINAL :: 2 EPSILON :: epsilon 0: epsilon 1,5 1: a 3 2: b 3,4 c 2 3: epsilon 2 b 5 4: epsilon 3 c 2,5 5: epsilon 1,2 c 3 --- NEW FILE: nfa.5 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ # NFA 5 START :: 0 # start state FINAL :: 3,8,9,10,15 # end states EPSILON :: epsilon # how epsilon transition is represented 0: d 1 c 6 s 13 1: o 2 i 4 2: g 3 3: epsilon 9 4: g 5 5: 6: a 7 u 11 7: t 8 8: epsilon 9 9: epsilon 10 10: 11: t 12 12: 13: k 14 i 16 14: y 15 15: epsilon 10 16: t 17 17: 18: --- NEW FILE: nfa.2 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ START :: 0 FINAL :: 5 EPSILON :: epsilon 0: epsilon 1,4 a 1 1: b 2 2: epsilon 3 c 3 3: c 2 d 4 4: epsilon 5 e 5 5: --- NEW FILE: nfa.3 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ START :: 0 FINAL :: 2 EPSILON :: epsilon 0: epsilon 1,3 b 2 1: a 2,4 2: b 5 3: c 2,6 4: epsilon 5 a 2,4 # loops back to itself 5: a 4 b 5 # loops back to itself c 6 6: a 5 c 6 # loops back to itself --- NEW FILE: nfa.1 --- # $Revision: 1.1 $ $Date: 2006/02/24 21:27:16 $ $Author: estrabd $ # NFA 1 START :: 0 # start state FINAL :: 2 # end states EPSILON :: epsilon # how epsilon transition is represented 0: a 1,3 b 2 1: b 2,5 2: c 4 3: a 2 b 4 4: b 5 5: c 1 x 6 6: x 2 |
|
From: <per...@li...> - 2006-02-24 21:27:20
|
Update of /cvsroot/perl-flat/flat4cpan/lib/FLAT In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3762/lib/FLAT Modified Files: FA.pm Log Message: more tests...input and output files now Index: FA.pm =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/lib/FLAT/FA.pm,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** FA.pm 21 Feb 2006 14:43:40 -0000 1.2 --- FA.pm 24 Feb 2006 21:27:15 -0000 1.3 *************** *** 149,153 **** } # rename states as actual numbers ! my $number = 0; foreach ($self->get_states()) { $self->rename_state($_,$number); --- 149,153 ---- } # rename states as actual numbers ! $number = 0; foreach ($self->get_states()) { $self->rename_state($_,$number); |
|
From: <per...@li...> - 2006-02-24 21:27:20
|
Update of /cvsroot/perl-flat/flat4cpan/t In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3762/t Modified Files: FLAT.t Added Files: FLAT-FA-INPUT.t Log Message: more tests...input and output files now Index: FLAT.t =================================================================== RCS file: /cvsroot/perl-flat/flat4cpan/t/FLAT.t,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** FLAT.t 24 Feb 2006 18:28:23 -0000 1.2 --- FLAT.t 24 Feb 2006 21:27:15 -0000 1.3 *************** *** 6,10 **** # change 'tests => 1' to 'tests => last_test_to_print'; ! use Test::More tests => 12; use lib qw(../lib); BEGIN { use_ok('FLAT::FA') }; --- 6,10 ---- # change 'tests => 1' to 'tests => last_test_to_print'; ! use Test::More tests => 16; use lib qw(../lib); BEGIN { use_ok('FLAT::FA') }; *************** *** 26,29 **** isa_ok($pfa,'FLAT::FA::PFA'); my $nfa = $pfa->to_nfa(); my $dfa = $nfa->to_dfa(); ! my $dfa_min = $dfa->minimize(); --- 26,33 ---- isa_ok($pfa,'FLAT::FA::PFA'); my $nfa = $pfa->to_nfa(); + isa_ok($nfa,'FLAT::FA::NFA'); my $dfa = $nfa->to_dfa(); ! isa_ok($dfa,'FLAT::FA::DFA'); ! my @removed = $dfa->minimize(); ! isa_ok($dfa,'FLAT::FA::DFA'); ! ok(($#removed+1) >= 0,'FLAT::FA::DFA->minimize() returns int >= 0'); --- NEW FILE: FLAT-FA-INPUT.t --- # Before `make install' is performed this script should be runnable with # `make test'. After `make install' it should work as `perl FLAT-FA.t' ######################### # change 'tests => 1' to 'tests => last_test_to_print'; use Test::More tests => 16; use lib qw(../lib); BEGIN { use_ok('FLAT::FA') }; BEGIN { use_ok('FLAT::FA::DFA') }; BEGIN { use_ok('FLAT::FA::NFA') }; BEGIN { use_ok('FLAT::FA::PFA') }; BEGIN { use_ok('FLAT::FA::RE') }; BEGIN { use_ok('FLAT::FA::PRE') }; use Cwd; isa_ok(FLAT::FA::DFA->new(),'FLAT::FA::DFA'); isa_ok(FLAT::FA::NFA->new(),'FLAT::FA::NFA'); isa_ok(FLAT::FA::PFA->new(),'FLAT::FA::PFA'); isa_ok(FLAT::FA::RE->new(),'FLAT::FA::RE'); isa_ok(FLAT::FA::PRE->new(),'FLAT::FA::PRE'); # # Tests ability to read input files and generate valid # output # #my $dfa = FLAT::FA::DFA->new(); #isa_ok($dfa,'FLAT::FA::DFA'); #$dfa->load_file('input/dfa.1'); #isa_ok($dfa,'FLAT::FA::DFA'); |
|
From: <per...@li...> - 2006-02-24 20:59:44
|
Update of /cvsroot/perl-flat/flat4cpan/t/input In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv24801/input Log Message: Directory /cvsroot/perl-flat/flat4cpan/t/input added to the repository |
|
From: <per...@li...> - 2006-02-24 18:42:15
|
Update of /cvsroot/perl-flat/blokhead/lib/FLAT In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv27297/lib/FLAT Modified Files: Regex.pm Log Message: - updates to regex ops (especially handling extended [] characters) - added more regex tests - anchoring option to as_perl_regex - "contains" method for regexes (just pass off regex matching to perl ;)) Index: Regex.pm =================================================================== RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/Regex.pm,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** Regex.pm 24 Feb 2006 06:20:25 -0000 1.4 --- Regex.pm 24 Feb 2006 18:42:09 -0000 1.5 *************** *** 37,41 **** sub as_perl_regex { ! "(?:" . $_[0]->op->as_perl_regex(0) . ")"; } --- 37,49 ---- sub as_perl_regex { ! my ($self, %opts) = @_; ! ! my $fmt = $opts{anchored} ? '(?:\A%s\z)' : '(?:%s)'; ! return sprintf $fmt, $self->op->as_perl_regex(0); ! } ! ! sub contains { ! my ($self, $string) = @_; ! $string =~ $self->as_perl_regex(anchored => 1); } *************** *** 138,141 **** --- 146,152 ---- literal square bracket characters is currently not supported. + The expression "" (or any string containing only whitespace) is not a valid + FLAT regex expression. Either C<[]> or C<#> are probably what was intended. + =item $regex-E<gt>as_string *************** *** 145,167 **** 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: --- 156,172 ---- FLAT::Regex->new($string)->as_string ! is identical to $string, especially if $string contains whitespace or ! redundant parentheses. =item $regex-E<gt>as_perl_regex ! =item $regex-E<gt>as_perl_regex(anchored => $bool); ! Returns an equivalent Perl regular expression. If the "anchored" option ! is set to a true value, the regular expression will be anchored with ! C<\A> and C<\z>. The default behavior is to omit the anchors. The Perl regex will not contain capturing parentheses. "Extended" characters ! that are written as "[char]" in FLAT regexes will be written without the square brackets in the corresponding Perl regex. So the following: *************** *** 169,171 **** --- 174,177 ---- will be equal to "(?:foo(?:bar)*)". + =back |
|
From: <per...@li...> - 2006-02-24 18:42:15
|
Update of /cvsroot/perl-flat/blokhead/t In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv27297/t Modified Files: 01-regex.t Log Message: - updates to regex ops (especially handling extended [] characters) - added more regex tests - anchoring option to as_perl_regex - "contains" method for regexes (just pass off regex matching to perl ;)) Index: 01-regex.t =================================================================== RCS file: /cvsroot/perl-flat/blokhead/t/01-regex.t,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** 01-regex.t 12 Nov 2005 23:08:56 -0000 1.3 --- 01-regex.t 24 Feb 2006 18:42:09 -0000 1.4 *************** *** 1,3 **** ! use Test::More 'no_plan'; use FLAT; --- 1,3 ---- ! use Test::More tests => 65; use FLAT; *************** *** 8,32 **** sub regex { FLAT::Regex->new(@_) } ! is( "" . regex( "(((a)bc)def)ghi" ), "abcdefghi", "Collapse parens for concatenation" ); ! is( "" . regex( "(((a)+b+c)+d+e+f)+g+h+i" ), "a+b+c+d+e+f+g+h+i", "Collapse parens for alternation" ); ! is( "" . regex( "(a+(b+(cd)))*" ), ! "(a+b+cd)*", "Parens kept for precedence" ); ! is( "". regex("#"), "#", "Null regex" ); ! is( "". regex("[]"), "[]", "epsilon" ); ! for ( ")ab", "a(bc(d)", "ab)cd(ef", "a+b+", "a++b", "+a", "h**", "a+*" ) { eval { regex($_) }; ok( $@, --- 8,40 ---- sub regex { FLAT::Regex->new(@_) } ! is( regex( "(((a)bc)def)ghi" )->as_string, "abcdefghi", "Collapse parens for concatenation" ); ! is( regex( "(((a)+b+c)+d+e+f)+g+h+i" )->as_string, "a+b+c+d+e+f+g+h+i", "Collapse parens for alternation" ); ! is( regex( "((a+(b+(cd)))*)+e" )->as_string, ! "(a+b+cd)*+e", "Parens kept for precedence" ); ! is( regex("#")->as_string, "#", "Null regex" ); ! is( regex("[]")->as_string, "[]", "epsilon" ); ! is( regex("[#][ ][foo][*][a][1][23]")->as_string, ! "[#][ ][foo][*]a1[23]", ! "special [] characters as string" ); ! ! is( regex(" a\tb\nc \n\t d")->as_string, ! "abcd", ! "whitespace ignored" ); ! ! for ( ")ab", "a(bc(d)", "ab)cd(ef", "a+b+", "a++b", "+a", "h**", "a+*", "" ) { eval { regex($_) }; ok( $@, *************** *** 34,42 **** } - - $reg = regex( "abc+def+ghi*+(a+b)*" ); ! is( "" . $reg, ! "" . $reg->reverse->reverse, "Reversal operation idempotent" ); --- 42,48 ---- } $reg = regex( "abc+def+ghi*+(a+b)*" ); ! is( $reg->as_string, ! $reg->reverse->reverse->as_string, "Reversal operation idempotent" ); *************** *** 45,48 **** --- 51,66 ---- ok( regex("#")->is_empty, "is_empty (atomic)" ); + + ok( ! regex("[#]")->is_empty, + "is_empty (atomic)" ); + + ok( ! regex("[foo]")->is_empty, + "is_empty (atomic)" ); + + ok( ! regex("[]")->is_empty, + "is_empty (atomic)" ); + + ok( ! regex("[ ]")->is_empty, + "is_empty (atomic)" ); ok( regex("a#a")->is_empty, *************** *** 55,58 **** --- 73,79 ---- "is_empty (star)" ); + ok( ! regex("[#]*")->is_empty, + "is_empty (star)" ); + ok( ! regex("#+b")->is_empty, "is_empty (alternation)" ); *************** *** 62,65 **** --- 83,87 ---- + ok( regex("a")->is_finite, "is_finite (atomic)" ); *************** *** 71,74 **** --- 93,99 ---- "is_finite (star)" ); + ok( ! regex("[#]*")->is_finite, + "is_finite (star)" ); + ok( regex("[]*")->is_finite, "is_finite (star)" ); *************** *** 91,92 **** --- 116,138 ---- ok( ! regex("a*a")->is_finite, "is_finite (concatenation)" ); + + #### + + $reg = regex("ab(c|de|f*)(g|[])"); + my $p = $reg->as_perl_regex(anchored => 1); + + for (qw[ abcg abc abdeg abde ab abg abfffg abff ]) { + ok( /$p/, + "as_perl_regex (positives)" ); + + ok( $reg->contains($_), + "contains (positives)" ); + } + + for (qw[ aabcg ac abcdeg abdef abffgg ]) { + ok( ! /$p/, + "as_perl_regex (negatives)" ); + + ok( ! $reg->contains($_), + "contains (negatives)" ); + } |
