re-dfa-pm

Description

This is a study project for regular expression implementation.
Only the most basic regular expression syntax is supported, i.e.,
the closure (*) operator, the alternation (|) operator, and the
concatenation operator.

Installation

make -f meta.mk
perl Makefile.PL
make

Usage:

• As an NFA generator:

  perl -Ilib script/re2nfa.pl '(a|b)(aa|bb)(a|b)'

  It will generate one image file, NFA.png:

  http://agentzh.org/misc/re/NFA.png

• As a DFA generator:

  perl -Ilib script/re2dfa.pl '(a|b)(aa|bb)(a|b)'

  It will generate two image files, DFA.png and DFA.min.png, showing the DFA automata and the minimized DFA automata:

  http://agentzh.org/misc/re/DFA.png

  http://agentzh.org/misc/re/DFA.min.png

• As a regular expression compiler:

  perl -Ilib script/re2pl.pl '(a|b)(aa|bb)(a|b)'

  will generate a Perl subroutine's source code to implement the corresponding minized DFA automata:

  http://agentzh.org/misc/re/sample.pl

  On the other hand, we can also compile regular expressions down to C code:

  perl -Ilib script/re2c.pl '(a|b)(aa|bb)(a|b)'

  The generated C code can be seen here:

  http://agentzh.org/misc/re/sample.c

• As a regular expression parser:

  perl -Ilib script/re2xml.pl '(a|b)(aa|bb)(a|b)'

  It will output the XML representation for the parsed regular expression's AST (Abstract Syntax Tree) structure:

  http://agentzh.org/misc/re/sample.xml

• As a regular expression interpreter:

  perl -Ilib script/evalre.pl -c '(a|b)(aa|bb)(a|b)' "abbbf"

  This command will run the regular expression against the text "abbbf" using the C backend (specified by the -c option). It will output

  match: 'abbb'

  The evalre.pl script uses the Inline::C Perl module to run the C code generated by the regular expression compiler with the C backend.

  Also, it's possible to use the Perl backend to run the regular expression, by specifying the -p option:

  perl -Ilib script/evalre.pl -p '(a|b)(aa|bb)(a|b)' "abbbf"