NAME

RE - A regular expression base class

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

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.

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 + - = ? & [ ] { } . ~ ^ @ % $

: ; < >

AUTHOR

Brett D. Estrade - <estrabd AT mailcan DOT com>

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.

BUGS

Not saying it is bug free, just saying I haven't hit any yet :)

AVAILABILITY

Anonymous CVS Checkout at http://www.brettsbsd.net/cgi-bin/viewcvs.cgi/

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.

COPYRIGHT

This code is released under the same terms as Perl.