/ 
Data-DFA-20180328
River stage one • 1 direct dependent • 1 total dependent
/ Data::DFA

Name

Data::DFA - Deterministic finite state parser from regular expression

Synopsis

Create a deterministic finite state parser to recognize sequences of symbols that match a given regular expression.

For example: to recognize sequences of symbols drawn from 'a'..'e' that match the regular expression: a (b|c)+ d? e proceed as follows:

# Construct a deterministic finite state automaton from the regular expression:

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

my $dfa = dfaFromExpr
 (element("a"),
  oneOrMore(choice(element("b"), element("c"))),
  optional(element("d")),
  element("e")
 );

# Print the symbols used and the transitions table:

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

ok $dfa->print("Dfa for a(b|c)+d?e :") eq nws <<END;
Dfa for a(b|c)+d?e :
Location  F  Transitions
     0  0  { a => 1 }
     1  0  { b => 2, c => 2 }
     2  0  { b => 2, c => 2, d => 6, e => 7 }
     6  0  { e => 7 }
     7  1  undef
END

# Create a parser and parse a sequence of symbols with the returned sub:

my ($parser, $end, $next, $processed) = $dfa->parser;                         # New parser

eval { &$parser($_) } for(qw(a b a));                                         # Try to parse a b a

say STDERR $@;                                                                # Error message
#   Already processed: a b
#   Expected one of  : b c d e
#   But was given    : a

is_deeply [&$next],      [qw(b c d e)];                                       # Next acceptable symbol
is_deeply [&$processed], [qw(a b)];                                           # Symbols processed
ok !&$end;                                                                    # Not at the 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.

Deterministic finite state parser

Create a deterministic finite state automaton to parse sequences of symbols in the language defined by a regular expression.

fromExpr(@)

Create a DFA from a regular expression.

   Parameter  Description
1  @expr      Expression

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

Data::DFA::fromExpr

finalState($$)

Check whether any of the specified states in the NFA are final

   Parameter  Description
1  $nfa       NFA
2  $reach     Hash of states in the NFA

superState($$$)

Create super states from existing superstate

   Parameter        Description
1  $dfa             DFA
2  $superStateName  Start state in DFA
3  $nfa             NFA we are tracking

superStates($$$)

Create super states from existing superstate

   Parameter        Description
1  $dfa             DFA
2  $SuperStateName  Start state in DFA
3  $nfa             NFA we are tracking

transitionOnSymbol($$$)

The super state reached by transition on a symbol from a specified state

   Parameter        Description
1  $dfa             DFA
2  $superStateName  Start state in DFA
3  $symbol          Symbol

print($$$)

Print DFA

   Parameter  Description
1  $dfa       DFA
2  $title     Title
3  $print     1 - STDOUT or 2 - STDERR

parser($)

Create a parser from a deterministic finite state automaton constructed from a regular expression.

   Parameter  Description
1  $dfa       Deterministic finite state automaton generated from an expression

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

Data::DFA::parser

Parser methods

Use the DFA to parse a sequence of symbols

Data::DFA::Parser::accept($$)

Accept the next symbol drawn from the symbol set if possible by moving to a new state otherwise confessing with a helpful message

   Parameter  Description
1  $parser    DFA Parser
2  $symbol    Next symbol to be processed by the finite state automaton

Data::DFA::Parser::final($)

Returns whether we are currently in a final state or not

   Parameter  Description
1  $parser    DFA Parser

Data::DFA::Parser::next($)

Returns an array of symbols that would be accepted in the current state

   Parameter  Description
1  $parser    DFA Parser

Data::DFA::Parser::accepts($@)

Confirm that a DFA accepts an array representing a sequence of symbols

   Parameter  Description
1  $parser    DFA Parser
2  @symbols   Array of symbols

Index

1 Data::DFA::Parser::accept

2 Data::DFA::Parser::accepts

3 Data::DFA::Parser::final

4 Data::DFA::Parser::next

5 finalState

6 fromExpr

7 parser

8 print

9 superState

10 superStates

11 transitionOnSymbol

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

Copyright (c) 2016-2018 Philip R Brenan.

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