RE - A regular expression base class
use FLAT::Legacy::FA::RE; use FLAT::Legacy::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";
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.
Valid terminal characters include:
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 + - = ? & [ ] { } . ~ ^ @ % $
: ; < >
Brett D. Estrade - <estrabd AT mailcan DOT com>
Currently, all states are stored as labels. There is also no integrity checking for consistency among the start, final, and set of all states.
to_dfa is broken, and is now listed as 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.
to_dfa
to_dfa_BROKEN
Perl FLaT Project Website at http://perl-flat.sourceforge.net/pmwiki
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.
This code is released under the same terms as Perl.
To install FLAT::Legacy::FA, copy and paste the appropriate command in to your terminal.
cpanm
cpanm FLAT::Legacy::FA
CPAN shell
perl -MCPAN -e shell install FLAT::Legacy::FA
For more information on module installation, please visit the detailed CPAN module installation guide.