Data::DFA - Deterministic finite state parser from regular expression.
Create a deterministic finite state parser to recognize sequences of symbols that match a given regular expression.
To recognize sequences of symbols drawn from 'a'..'e' that match the regular expression: a (b|c)+ d? e:
Create the parser:
my $dfa = fromExpr ("a", oneOrMore (choice(qw(b c))), optional("d"), "e" );
Recognize sequences of symbols:
ok $dfa->parser->accepts(qw(a b e)); ok $dfa->parser->accepts(qw(a b c e)); ok !$dfa->parser->accepts(qw(a d)); ok !$dfa->parser->accepts(qw(a c d)); ok $dfa->parser->accepts(qw(a c d e));
Print the transition table:
is_deeply $dfa->print("a(b|c)+d?e"), <<END; a(b|c)+d?e State Final Symbol Target Final 1 0 a 4 2 1 b 1 3 c 1 4 d 2 5 e 3 1 6 2 e 3 1 7 3 1 1 8 4 b 1 9 c 1 END
Discover why a sequence cannot be recognized:
my $parser = $dfa->parser; eval { $parser->accept($_) } for qw(a b a); is_deeply $@, <<END; Already processed: a b Expected one of : b c d e But found : a END is_deeply $parser->fail, qq(a); is_deeply [$parser->next], [qw(b c d e)]; is_deeply $parser->processed, [qw(a b)]; ok !$parser->final;
To construct and parse regular expressions in the format used by !ELEMENT definitions in DTDs used to validate XML:
is_deeply parseDtdElement(q(a, b*, c))->printAsExpr, q/element(q(a)), zeroOrMore(element(q(b))), element(q(c))/;
Deterministic finite state parser from regular expression.
Version 20201030.
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 a regular expression that defines the language to be parsed using the following combining operations:
One element.
Parameter Description 1 $label Transition symbol
Example:
my $dfa = fromExpr # Construct DFA ("a", oneOrMore(choice(qw(b c))), optional("d"), "e" ); is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols my $dfa = fromExpr # Construct DFA (element("a"), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 oneOrMore(choice(element("b"), element("c"))), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 optional(element("d")), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 element("e") # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ); my $parser = $dfa->parser; # New parser eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a is_deeply [$parser->next], [qw(b c d e)]; # Next acceptable symbol is_deeply $parser->processed, [qw(a b)]; # Symbols processed ok !$parser->final; # Not in a final state ok $dfa->dumpAsJson eq <<END, q(dumpAsJson); # Dump as json { "finalStates" : { "0" : null, "1" : null, "2" : null, "4" : null, "5" : 1 }, "transitions" : { "0" : { "a" : "2" }, "1" : { "b" : "1", "c" : "1", "d" : "4", "e" : "5" }, "2" : { "b" : "1", "c" : "1" }, "4" : { "e" : "5" } } } END
This is a static method and so should either be imported or invoked as:
Data::DFA::element
Sequence of elements.
Parameter Description 1 @elements Elements
my $dfa = fromExpr # Construct DFA (zeroOrMore(sequence('a'..'c')), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 except('b'..'d') ); ok $dfa->parser->accepts(qw(a b c a )); ok !$dfa->parser->accepts(qw(a b c a b)); ok !$dfa->parser->accepts(qw(a b c a c)); ok !$dfa->parser->accepts(qw(a c c a b c)); ok $dfa->print(q(Test)) eq <<END; # Print renumbered DFA Test State Final Symbol Target Final 1 0 a 1 1 2 1 1 b 2 3 2 c 0 END
Data::DFA::sequence
An optional sequence of element.
Parameter Description 1 @element Elements
my $dfa = fromExpr # Construct DFA ("a", oneOrMore(choice(qw(b c))), optional("d"), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 "e" ); is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols my $dfa = fromExpr # Construct DFA (element("a"), oneOrMore(choice(element("b"), element("c"))), optional(element("d")), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 element("e") ); my $parser = $dfa->parser; # New parser eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a is_deeply [$parser->next], [qw(b c d e)]; # Next acceptable symbol is_deeply $parser->processed, [qw(a b)]; # Symbols processed ok !$parser->final; # Not in a final state ok $dfa->dumpAsJson eq <<END, q(dumpAsJson); # Dump as json { "finalStates" : { "0" : null, "1" : null, "2" : null, "4" : null, "5" : 1 }, "transitions" : { "0" : { "a" : "2" }, "1" : { "b" : "1", "c" : "1", "d" : "4", "e" : "5" }, "2" : { "b" : "1", "c" : "1" }, "4" : { "e" : "5" } } } END
Data::DFA::optional
Zero or more repetitions of a sequence of elements.
Data::DFA::zeroOrMore
One or more repetitions of a sequence of elements.
my $dfa = fromExpr # Construct DFA ("a", oneOrMore(choice(qw(b c))), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 optional("d"), "e" ); is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols my $dfa = fromExpr # Construct DFA (element("a"), oneOrMore(choice(element("b"), element("c"))), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 optional(element("d")), element("e") ); my $parser = $dfa->parser; # New parser eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a is_deeply [$parser->next], [qw(b c d e)]; # Next acceptable symbol is_deeply $parser->processed, [qw(a b)]; # Symbols processed ok !$parser->final; # Not in a final state ok $dfa->dumpAsJson eq <<END, q(dumpAsJson); # Dump as json { "finalStates" : { "0" : null, "1" : null, "2" : null, "4" : null, "5" : 1 }, "transitions" : { "0" : { "a" : "2" }, "1" : { "b" : "1", "c" : "1", "d" : "4", "e" : "5" }, "2" : { "b" : "1", "c" : "1" }, "4" : { "e" : "5" } } } END
Data::DFA::oneOrMore
Choice from amongst one or more elements.
Parameter Description 1 @elements Elements to be chosen from
Data::DFA::choice
Choice from amongst all symbols except the ones mentioned
my $dfa = fromExpr # Construct DFA (zeroOrMore(sequence('a'..'c')), except('b'..'d') # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ); ok $dfa->parser->accepts(qw(a b c a )); ok !$dfa->parser->accepts(qw(a b c a b)); ok !$dfa->parser->accepts(qw(a b c a c)); ok !$dfa->parser->accepts(qw(a c c a b c)); ok $dfa->print(q(Test)) eq <<END; # Print renumbered DFA Test State Final Symbol Target Final 1 0 a 1 1 2 1 1 b 2 3 2 c 0 END
Data::DFA::except
Create a DFA parser from a regular @expression.
Parameter Description 1 @expression Regular expression
my $dfa = fromExpr # Construct DFA # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ("a", oneOrMore(choice(qw(b c))), optional("d"), "e" ); is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols my $dfa = fromExpr # Construct DFA # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 (element("a"), oneOrMore(choice(element("b"), element("c"))), optional(element("d")), element("e") ); my $parser = $dfa->parser; # New parser eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a is_deeply [$parser->next], [qw(b c d e)]; # Next acceptable symbol is_deeply $parser->processed, [qw(a b)]; # Symbols processed ok !$parser->final; # Not in a final state ok $dfa->dumpAsJson eq <<END, q(dumpAsJson); # Dump as json { "finalStates" : { "0" : null, "1" : null, "2" : null, "4" : null, "5" : 1 }, "transitions" : { "0" : { "a" : "2" }, "1" : { "b" : "1", "c" : "1", "d" : "4", "e" : "5" }, "2" : { "b" : "1", "c" : "1" }, "4" : { "e" : "5" } } } END
Data::DFA::fromExpr
Check that the DFA is univalent: a univalent DFA has a mapping from symbols to states. Returns a hash showing the mapping from symbols to states if the DFA is univalent, else returns undfef.
Parameter Description 1 $dfa Dfa to check
Pritn the Dfa in various ways.
Print the specified $dfa using the specified $title.
Parameter Description 1 $dfa DFA 2 $title Optional title
my $dfa = fromExpr # Construct DFA (zeroOrMore(sequence('a'..'c')), except('b'..'d') ); ok $dfa->parser->accepts(qw(a b c a )); ok !$dfa->parser->accepts(qw(a b c a b)); ok !$dfa->parser->accepts(qw(a b c a c)); ok !$dfa->parser->accepts(qw(a c c a b c)); ok $dfa->print(q(Test)) eq <<END; # Print renumbered DFA # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 Test State Final Symbol Target Final 1 0 a 1 1 2 1 1 b 2 3 2 c 0 END
Return an array of all the symbols accepted by a $dfa.
Parameter Description 1 $dfa DFA
my $dfa = fromExpr # Construct DFA ("a", oneOrMore(choice(qw(b c))), optional("d"), "e" ); is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
Create a parser from a $dfa constructed from a regular expression.
Parameter Description 1 $dfa Deterministic finite state automaton 2 $observer Optional observer
my $dfa = fromExpr # Construct DFA ("a", oneOrMore(choice(qw(b c))), optional("d"), "e" ); is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols my $dfa = fromExpr # Construct DFA (element("a"), oneOrMore(choice(element("b"), element("c"))), optional(element("d")), element("e") ); my $parser = $dfa->parser; # New parser # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 is_deeply [$parser->next], [qw(b c d e)]; # Next acceptable symbol # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 is_deeply $parser->processed, [qw(a b)]; # Symbols processed # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok !$parser->final; # Not in a final state # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $dfa->dumpAsJson eq <<END, q(dumpAsJson); # Dump as json { "finalStates" : { "0" : null, "1" : null, "2" : null, "4" : null, "5" : 1 }, "transitions" : { "0" : { "a" : "2" }, "1" : { "b" : "1", "c" : "1", "d" : "4", "e" : "5" }, "2" : { "b" : "1", "c" : "1" }, "4" : { "e" : "5" } } } END
Create a JSON string representing a $dfa.
Parameter Description 1 $dfa Deterministic finite state automaton generated from an expression
my $dfa = fromExpr # Construct DFA ("a", oneOrMore(choice(qw(b c))), optional("d"), "e" ); is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
Print a $dfa as an expression.
if (1) {my $e = q/element(q(a)), zeroOrMore(choice(element(q(b)), element(q(c)))), element(q(d))/; my $d = eval qq/fromExpr($e)/; confess $@ if $@; my $E = $d->printAsExpr; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $e eq $E; my $R = $d->printAsRe; ok $R eq q(a (b | c)* d); my $D = parseDtdElement(q(a, (b | c)*, d)); my $S = $D->printAsExpr; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $e eq $S; }
Print a $dfa as a regular expression.
if (1) {my $e = q/element(q(a)), zeroOrMore(choice(element(q(b)), element(q(c)))), element(q(d))/; my $d = eval qq/fromExpr($e)/; confess $@ if $@; my $E = $d->printAsExpr; ok $e eq $E; my $R = $d->printAsRe; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $R eq q(a (b | c)* d); my $D = parseDtdElement(q(a, (b | c)*, d)); my $S = $D->printAsExpr; ok $e eq $S; }
Convert the Dtd Element definition in $string to a parse tree.
Parameter Description 1 $string String representation of DTD element expression
if (1) {is_deeply unbless(parseDtdElementAST(q(a, (b | c)*, d))), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ["sequence", ["sequence", ["element", "a"], ["zeroOrMore", ["choice", ["element", "b"], ["element", "c"]]], ], ["element", "d"], ]; }
Convert the Xml <>DTD> Element definition in the specified $string to a DFA.
Parameter Description 1 $string DTD element expression string
if (1) {my $e = q/element(q(a)), zeroOrMore(choice(element(q(b)), element(q(c)))), element(q(d))/; my $d = eval qq/fromExpr($e)/; confess $@ if $@; my $E = $d->printAsExpr; ok $e eq $E; my $R = $d->printAsRe; ok $R eq q(a (b | c)* d); my $D = parseDtdElement(q(a, (b | c)*, d)); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 my $S = $D->printAsExpr; ok $e eq $S; }
Find paths in a DFA.
Find a set of paths that reach every state in the DFA with each path terminating in a final state.
if (1) {my $dfa = fromExpr (zeroOrMore("a"), oneOrMore("b"), optional("c"), "d" ); ok !$dfa->parser->accepts(qw()); ok !$dfa->parser->accepts(qw(a)); ok !$dfa->parser->accepts(qw(b)); ok !$dfa->parser->accepts(qw(c)); ok !$dfa->parser->accepts(qw(d)); ok $dfa->parser->accepts(qw(b c d)); ok $dfa->parser->accepts(qw(b d)); ok !$dfa->parser->accepts(qw(b a)); ok $dfa->parser->accepts(qw(b b d)); is_deeply shortPaths ($dfa), { "b c d" => ["b", "c", "d"], "b d" => ["b", "d"] }; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 is_deeply longPaths($dfa), {"a b b c d" => ["a", "b", "b", "c", "d"], "a b b d" => ["a", "b", "b", "d"], "a b c d" => ["a" .. "d"], "a b d" => ["a", "b", "d"], "b b c d" => ["b", "b", "c", "d"], "b b d" => ["b", "b", "d"], "b c d" => ["b", "c", "d"], "b d" => ["b", "d"]}; }
Find a set of paths that traverse each transition in the DFA with each path terminating in a final state.
if (1) {my $dfa = fromExpr (zeroOrMore("a"), oneOrMore("b"), optional("c"), "d" ); ok !$dfa->parser->accepts(qw()); ok !$dfa->parser->accepts(qw(a)); ok !$dfa->parser->accepts(qw(b)); ok !$dfa->parser->accepts(qw(c)); ok !$dfa->parser->accepts(qw(d)); ok $dfa->parser->accepts(qw(b c d)); ok $dfa->parser->accepts(qw(b d)); ok !$dfa->parser->accepts(qw(b a)); ok $dfa->parser->accepts(qw(b b d)); is_deeply shortPaths ($dfa), { "b c d" => ["b", "c", "d"], "b d" => ["b", "d"] }; is_deeply longPaths($dfa), # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 {"a b b c d" => ["a", "b", "b", "c", "d"], "a b b d" => ["a", "b", "b", "d"], "a b c d" => ["a" .. "d"], "a b d" => ["a", "b", "d"], "b b c d" => ["b", "b", "c", "d"], "b b d" => ["b", "b", "d"], "b c d" => ["b", "c", "d"], "b d" => ["b", "d"]}; }
Find the non repeating loops from each state.
if (1) {my $d = fromExpr choice oneOrMore "a", oneOrMore "b", oneOrMore "c", oneOrMore "d"; is_deeply $d->print("(a(b(c(d)+)+)+)+"), <<END; (a(b(c(d)+)+)+)+ State Final Symbol Target Final 1 0 a 3 2 1 d 2 1 3 2 1 a 3 4 b 4 5 c 1 6 d 2 1 7 3 b 4 8 4 c 1 END ok !$d->parser->accepts(qw()); ok !$d->parser->accepts(qw(a b c)); ok $d->parser->accepts(qw(a b c d)); ok $d->parser->accepts(qw(a b c d b c d d)); ok !$d->parser->accepts(qw(a b c b d c d d)); ok !$d->parser->accepts(qw(a b c d a)); is_deeply $d->loops, { # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 1 => [["d", "a", "b", "c"], ["d", "b", "c"], ["d", "c"]], 2 => [["a" .. "d"], ["b", "c", "d"], ["c", "d"], ["d"]], 3 => [["b", "c", "d", "a"]], 4 => [["c", "d", "a", "b"], ["c", "d", "b"]]}; is_deeply shortPaths($d), {"a b c d" => ["a" .. "d"]}; is_deeply longPaths ($d), { "a b c d" => ["a" .. "d"], "a b c d d" => ["a" .. "d", "d"] }; #say STDERR $d->printAsExpr; }
Use the DFA to parse a sequence of symbols
Using the specified $parser, accept the next symbol drawn from the symbol set if possible by moving to a new state otherwise confessing with a helpful message that such a move is not possible.
Parameter Description 1 $parser DFA Parser 2 $symbol Next symbol to be processed by the finite state automaton
my $dfa = fromExpr # Construct DFA (element("a"), oneOrMore(choice(element("b"), element("c"))), optional(element("d")), element("e") ); my $parser = $dfa->parser; # New parser eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a is_deeply [$parser->next], [qw(b c d e)]; # Next acceptable symbol is_deeply $parser->processed, [qw(a b)]; # Symbols processed ok !$parser->final; # Not in a final state ok $dfa->dumpAsJson eq <<END, q(dumpAsJson); # Dump as json { "finalStates" : { "0" : null, "1" : null, "2" : null, "4" : null, "5" : 1 }, "transitions" : { "0" : { "a" : "2" }, "1" : { "b" : "1", "c" : "1", "d" : "4", "e" : "5" }, "2" : { "b" : "1", "c" : "1" }, "4" : { "e" : "5" } } } END my $dfa = fromExpr # Construct DFA (zeroOrMore(sequence('a'..'c')), except('b'..'d') ); ok $dfa->parser->accepts(qw(a b c a )); ok !$dfa->parser->accepts(qw(a b c a b)); ok !$dfa->parser->accepts(qw(a b c a c)); ok !$dfa->parser->accepts(qw(a c c a b c)); ok $dfa->print(q(Test)) eq <<END; # Print renumbered DFA Test State Final Symbol Target Final 1 0 a 1 1 2 1 1 b 2 3 2 c 0 END
Returns whether the specified $parser is in a final state or not.
Parameter Description 1 $parser DFA Parser
my $dfa = fromExpr # Construct DFA (zeroOrMore(sequence('a'..'c')), except('b'..'d') ); ok $dfa->parser->accepts(qw(a b c a )); ok !$dfa->parser->accepts(qw(a b c a b)); ok !$dfa->parser->accepts(qw(a b c a c)); ok !$dfa->parser->accepts(qw(a c c a b c)); ok $dfa->print(q(Test)) eq <<END; # Print renumbered DFA Test State Final Symbol Target Final 1 0 a 1 1 2 1 1 b 2 3 2 c 0 END
Returns an array of symbols that would be accepted in the current state by the specified $parser.
my $dfa = fromExpr # Construct DFA (element("a"), oneOrMore(choice(element("b"), element("c"))), optional(element("d")), element("e") ); my $parser = $dfa->parser; # New parser eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a is_deeply [$parser->next], [qw(b c d e)]; # Next acceptable symbol is_deeply $parser->processed, [qw(a b)]; # Symbols processed ok !$parser->final; # Not in a final state ok $dfa->dumpAsJson eq <<END, q(dumpAsJson); # Dump as json { "finalStates" : { "0" : null, "1" : null, "2" : null, "4" : null, "5" : 1 }, "transitions" : { "0" : { "a" : "2" }, "1" : { "b" : "1", "c" : "1", "d" : "4", "e" : "5" }, "2" : { "b" : "1", "c" : "1" }, "4" : { "e" : "5" } } } END
Confirm that the specified $parser accepts an array representing a sequence of symbols.
Parameter Description 1 $parser DFA Parser 2 @symbols Array of symbols
my $dfa = fromExpr # Construct DFA ("a", oneOrMore(choice(qw(b c))), optional("d"), "e" ); is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols my $dfa = fromExpr # Construct DFA (element("a"), oneOrMore(choice(element("b"), element("c"))), optional(element("d")), element("e") ); my $parser = $dfa->parser; # New parser eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a is_deeply [$parser->next], [qw(b c d e)]; # Next acceptable symbol is_deeply $parser->processed, [qw(a b)]; # Symbols processed ok !$parser->final; # Not in a final state ok $dfa->dumpAsJson eq <<END, q(dumpAsJson); # Dump as json { "finalStates" : { "0" : null, "1" : null, "2" : null, "4" : null, "5" : 1 }, "transitions" : { "0" : { "a" : "2" }, "1" : { "b" : "1", "c" : "1", "d" : "4", "e" : "5" }, "2" : { "b" : "1", "c" : "1" }, "4" : { "e" : "5" } } } END
Data structures used by this package.
DFA State
Whether this state is final
Hash whose keys are the NFA states that contributed to this super state
Pumping lemmas for this state
Sequence of states to final state minus pumped states
Name of the state - the join of the NFA keys
Transitions from this state
Parse a sequence of symbols with a DFA
DFA being used
Symbol on which we failed
Optional sub($parser, $symbol, $target) to observe transitions.
Symbols processed
Current state
Create a new DFA.
Create a new DFA state with the specified options.
Parameter Description 1 %options DFA state as hash
Create a DFA parser from an NFA.
Parameter Description 1 $nfa Nfa
Check whether, in the specified $nfa, any of the states named in the hash reference $reach are final. Final states that refer to reduce rules are checked for reduce conflicts.
Parameter Description 1 $nfa NFA 2 $reach Hash of states in the NFA
Create super states from existing superstate.
Parameter Description 1 $dfa DFA 2 $superStateName Start state in DFA 3 $nfa NFA we are converting 4 $symbols Symbols in the NFA we are converting 5 $nfaSymbolTransitions States reachable from each state by symbol
Parameter Description 1 $dfa DFA 2 $SuperStateName Start state in DFA 3 $nfa NFA we are tracking
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
Renumber the states in the specified $dfa.
Parameter Description 1 $dfa DFA 2 $initialStateName Initial super state name
Print a final state
Parameter Description 1 $final Final State
Remove duplicated states in a $dfa.
Remove unreachable states in a $dfa.
Print a DFA $dfa_ in an expression form determined by the specified %options.
Parameter Description 1 $dfa Dfa 2 %options Options.
Whether the second array is contained within the first.
Parameter Description 1 $A Exterior array 2 $B Interior array
Remove longer paths that contain shorter paths.
Parameter Description 1 $paths Paths
1 choice - Choice from amongst one or more elements.
2 Data::DFA::Parser::accept - Using the specified $parser, accept the next symbol drawn from the symbol set if possible by moving to a new state otherwise confessing with a helpful message that such a move is not possible.
3 Data::DFA::Parser::accepts - Confirm that the specified $parser accepts an array representing a sequence of symbols.
4 Data::DFA::Parser::final - Returns whether the specified $parser is in a final state or not.
5 Data::DFA::Parser::next - Returns an array of symbols that would be accepted in the current state by the specified $parser.
6 dumpAsJson - Create a JSON string representing a $dfa.
7 element - One element.
8 except - Choice from amongst all symbols except the ones mentioned
9 finalState - Check whether, in the specified $nfa, any of the states named in the hash reference $reach are final.
10 fromExpr - Create a DFA parser from a regular @expression.
11 fromNfa - Create a DFA parser from an NFA.
12 longPaths - Find a set of paths that traverse each transition in the DFA with each path terminating in a final state.
13 loops - Find the non repeating loops from each state.
14 newDFA - Create a new DFA.
15 newState - Create a new DFA state with the specified options.
16 oneOrMore - One or more repetitions of a sequence of elements.
17 optional - An optional sequence of element.
18 parseDtdElement - Convert the Xml <>DTD> Element definition in the specified $string to a DFA.
19 parseDtdElementAST - Convert the Dtd Element definition in $string to a parse tree.
20 parser - Create a parser from a $dfa constructed from a regular expression.
21 print - Print the specified $dfa using the specified $title.
22 printAsExpr - Print a $dfa as an expression.
23 printAsExpr2 - Print a DFA $dfa_ in an expression form determined by the specified %options.
24 printAsRe - Print a $dfa as a regular expression.
25 printFinal - Print a final state
26 removeDuplicatedStates - Remove duplicated states in a $dfa.
27 removeLongerPathsThatContainShorterPaths - Remove longer paths that contain shorter paths.
28 removeUnreachableStates - Remove unreachable states in a $dfa.
29 renumberDfa - Renumber the states in the specified $dfa.
30 sequence - Sequence of elements.
31 shortPaths - Find a set of paths that reach every state in the DFA with each path terminating in a final state.
32 subArray - Whether the second array is contained within the first.
33 superState - Create super states from existing superstate.
34 superStates - Create super states from existing superstate.
35 symbols - Return an array of all the symbols accepted by a $dfa.
36 transitionOnSymbol - The super state reached by transition on a symbol from a specified state.
37 univalent - Check that the DFA is univalent: a univalent DFA has a mapping from symbols to states.
38 zeroOrMore - Zero or more repetitions of a sequence of elements.
This module is written in 100% Pure Perl and, thus, it is easy to read, comprehend, use, modify and install via cpan:
sudo cpan install Data::DFA
philiprbrenan@gmail.com
http://www.appaapps.com
Copyright (c) 2016-2019 Philip R Brenan.
This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.
To install Data::DFA, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Data::DFA
CPAN shell
perl -MCPAN -e shell install Data::DFA
For more information on module installation, please visit the detailed CPAN module installation guide.