Name

Data::NFA - Non deterministic finite state machine from regular expression.

Synopsis

Create a non deterministic finite state machine from a regular expression which can then be converted into a deterministic finite state machine by Data::DFA and used to parse sequences of symbols.

For example, the regular expression:

((a|b)*)**4

produces the following machine:

use Data::NFA qw(:all);
use Data::Table::Text qw(:all);
use Test::More qw(no_plan);

my $N = 4;

my $s = q(zeroOrMore(choice(element("a"), element("b"))));

my $nfa = eval qq(fromExpr(($s)x$N));

ok $nfa->print("((a|b)*)**$N: ") eq nws <<END;
((a|b)*)**4:
Location  F  Transitions  Jumps
     0  1  { a => 1 }   [2, 4, 6, 8, 10, 12, 14, 16]
     1  1  undef        [0, 2, 3, 4, 6, 8, 10, 12, 14, 16]
     2  0  { b => 3 }   undef
     3  1  undef        [0, 2, 4, 6, 8, 10, 12, 14, 16]
     4  1  { a => 5 }   [6, 8, 10, 12, 14, 16]
     5  1  undef        [4, 6, 7, 8, 10, 12, 14, 16]
     6  0  { b => 7 }   undef
     7  1  undef        [4, 6, 8, 10, 12, 14, 16]
     8  1  { a => 9 }   [10, 12, 14, 16]
     9  1  undef        [8, 10, 11, 12, 14, 16]
    10  0  { b => 11 }  undef
    11  1  undef        [8, 10, 12, 14, 16]
    12  1  { a => 13 }  [14, 16]
    13  1  undef        [12, 14, 15, 16]
    14  0  { b => 15 }  undef
    15  1  undef        [12, 14, 16]
    16  1  undef        undef
END

Description

The following sections describe the methods in each functional area of this module. For an alphabetic listing of all methods by name see Index.

Construct regular expression

Construct a regular expression that defines the language to be parsed using the following combining operations which can all be imported:

element($)

One element.

   Parameter  Description
1  $label     Transition label

Example:

my $nfa = fromExpr(element("a"));

ok $nfa->print("Element: a") eq nws <<END;
Element: a
Location  F  Transitions
       0  0  { a => 1 }
       1  1  undef

END

This is a static method and so should be invoked as:

Data::NFA::element

sequence(@)

Sequence of elements.

   Parameter  Description
1  @elements  Elements

Example:

my $nfa = fromExpr(sequence(element("a"), element("b")));

ok $nfa->print("Sequence: ab") eq nws <<END;
Sequence: ab
Location  F  Transitions
       0  0  { a => 1 }
       1  0  { b => 2 }
       2  1  undef
END

This is a static method and so should be invoked as:

Data::NFA::sequence

optional(@)

An optional sequence of element.

   Parameter  Description
1  @element   Elements

Example:

my $nfa = fromExpr(element("a"), optional(element("b")), element("c"));

ok $nfa->print("Optional: ab?c") eq nws <<END;
Optional: ab?c
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [2]
       2  0  { c => 3 }   undef
       3  1  undef        undef
END

my $nfa = fromExpr

(element("a"),

oneOrMore(choice(element("b"), element("c"))),

optional(element("d")),

element("e")

);

ok $nfa->print("a(b|c)+d?e :") eq nws <<END;
a(b|c)+d?e :
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3 .. 6]
       3  0  { c => 4 }   undef
       4  0  undef        [1, 3, 5, 6]
       5  0  { d => 6 }   [6]
       6  0  { e => 7 }   undef
       7  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::optional

zeroOrMore(@)

Zero or more repetitions of a sequence of elements.

   Parameter  Description
1  @element   Elements

Example:

my $nfa = fromExpr(element("a"), zeroOrMore(element("b")), element("c"));

ok $nfa->print("Zero Or More: ab*c") eq nws <<END;
Zero Or More: ab*c
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3]
       3  0  { c => 4 }   undef
       4  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::zeroOrMore

oneOrMore(@)

One or more repetitions of a sequence of elements.

   Parameter  Description
1  @element   Elements

Example:

my $nfa = fromExpr(element("a"), oneOrMore(element("b")), element("c"));

ok $nfa->print("One or More: ab+c") eq nws <<END;
One or More: ab+c
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   undef
       2  0  undef        [1, 3]
       3  0  { c => 4 }   undef
       4  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::oneOrMore

choice(@)

Choice from amongst one or more elements.

   Parameter  Description
1  @elements  Elements to be chosen from

Example:

my $nfa = fromExpr(element("a"),

choice(element("b"), element("c")),

element("d"));

ok $nfa->print("Choice: (a(b|c)d") eq nws <<END;
Choice: (a(b|c)d
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [4]
       3  0  { c => 4 }   undef
       4  0  { d => 5 }   undef
       5  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::choice

Non Deterministic finite state machine

fromExpr(@)

Create an NFA from a regular expression.

   Parameter  Description
1  @expr      Expressions

Example:

my $nfa = fromExpr

(element("a"),

oneOrMore(choice(element("b"), element("c"))),

optional(element("d")),

element("e")

);

ok $nfa->print("a(b|c)+d?e :") eq nws <<END;
a(b|c)+d?e :
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3 .. 6]
       3  0  { c => 4 }   undef
       4  0  undef        [1, 3, 5, 6]
       5  0  { d => 6 }   [6]
       6  0  { e => 7 }   undef
       7  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::fromExpr

print($$$)

Print the current state of the finite automaton. If it is non deterministic, the non deterministic jumps will be shown as well as the transitions table. If deterministic, only the transitions table will be shown.

   Parameter  Description
1  $states    States
2  $title     Title
3  $print     Print to STDERR if 2 or to STDOUT if 1

Example:

my $nfa = fromExpr

(element("a"),

oneOrMore(choice(element("b"), element("c"))),

optional(element("d")),

element("e")

);

ok $nfa->print("a(b|c)+d?e :") eq nws <<END;
a(b|c)+d?e :
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3 .. 6]
       3  0  { c => 4 }   undef
       4  0  undef        [1, 3, 5, 6]
       5  0  { d => 6 }   [6]
       6  0  { e => 7 }   undef
       7  1  undef        undef
END

symbols($)

Return an array of all the transition symbols.

   Parameter  Description
1  $states    States

Example:

my $nfa = fromExpr

(element("a"),

oneOrMore(choice(element("b"), element("c"))),

optional(element("d")),

element("e")

);

ok $nfa->print("a(b|c)+d?e :") eq nws <<END;
a(b|c)+d?e :
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3 .. 6]
       3  0  { c => 4 }   undef
       4  0  undef        [1, 3, 5, 6]
       5  0  { d => 6 }   [6]
       6  0  { e => 7 }   undef
       7  1  undef        undef
END

is_deeply ['a'..'e'], [$nfa->symbols];

Private Methods

fromExpr2($$)

Create an NFA from a regular expression.

   Parameter  Description
1  $states    States
2  $expr      Regular expression constructed from L<element|/element> L<sequence|/sequence> L<optional|/optional> L<zeroOrMore|/zeroOrMore> L<oneOrMore|/oneOrMore> L<choice|/choice>.

propogateFinalState($)

Mark the states that can reach the final state with a jump as final

   Parameter  Description
1  $states    States

statesReachableViaJumps($$)

Find the names of all the states that can be reached from a specified state via jumps alone

   Parameter   Description
1  $states     States
2  $StateName  Name of start state

printWithJumps($$$)

Print the current state of an NFA with jumps.

   Parameter  Description
1  $states    States
2  $title     Title
3  $print     Print to STDERR if 2 or to STDOUT if 1

printWithOutJumps($$$)

Print the current state of an NFA without jumps

   Parameter  Description
1  $states    States
2  $title     Title
3  $print     Print to STDERR if 2 or to STDOUT if 1

Index

1 choice

2 element

7 print

10 propogateFinalState

11 sequence

12 statesReachableViaJumps

13 symbols

14 zeroOrMore

Installation

This module is written in 100% Pure Perl and, thus, it is easy to read, use, modify and install.

Standard Module::Build process for building and installing modules:

perl Build.PL
./Build
./Build test
./Build install

Author

philiprbrenan@gmail.com

http://www.appaapps.com

Copyright

This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.

To install Data::NFA, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Data::NFA

CPAN shell

perl -MCPAN -e shell
install Data::NFA

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

Name

Synopsis

Description

Construct regular expression

element($)

sequence(@)

optional(@)

zeroOrMore(@)

oneOrMore(@)

choice(@)

Non Deterministic finite state machine

fromExpr(@)

print($$$)

symbols($)

Private Methods

fromExpr2($$)

propogateFinalState($)

statesReachableViaJumps($$)

printWithJumps($$$)

printWithOutJumps($$$)

Index

Installation

Author

Copyright

Module Install Instructions