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.
To recognize sequences of symbols drawn from 'a'..'e' that match the regular expression: a (b|c)+ d? e:
# 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 = fromExpr
(element("a"),
oneOrMore(choice(element("b"), element("c"))),
optional(element("d")),
element("e")
);
ok $dfa->parser->accepts(qw(a b e));
ok !$dfa->parser->accepts(qw(a d));
# 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 :
State Final Symbol Target Final
1 0 a 1 3 0
2 1 2 3 4 5 6 0 b 1 2 3 4 5 6 0
3 c 1 3 4 5 6 0
4 d 6 0
5 e 7 1
6 1 3 0 b 1 2 3 4 5 6 0
7 c 1 3 4 5 6 0
8 1 3 4 5 6 0 b 1 2 3 4 5 6 0
9 c 1 3 4 5 6 0
10 d 6 0
11 e 7 1
12 6 0 e 7 1
END
# Create a parser and use it to parse a sequence of symbols
my $parser = $dfa->parser; # New parser
eval { $parser->accept($_) } for qw(a b a); # Try to parse a b a
# Create a parser and use it to parse a sequence of symbols
my $parser = $dfa->parser;
eval { $parser->accept($_) } for qw(a b a);
my $r = $@;
ok $r =~ m(Already processed: a b);
ok $r =~ m(Expected one of : b c d e);
ok $r =~ m(But found : 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:
{my $e = q/element(q(a)), zeroOrMore(choice(element(q(b)), element(q(c)))), element(q(d))/;
my $d = eval qq/fromExpr($e)/;
my $E = $d->printAsExpr;
ok $e eq $E;
my $R = $d->printAsRe;
ok $R eq q(a, (b | c)*, d); # Print as DTD regular expression
my $D = parseDtdElement($R); # Parse DTD regular expression
my $S = $D->printAsExpr;
ok $e eq $S;
}
Description
Deterministic finite state parser from regular expression
Version 20200621.
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:
element($label)
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
(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("a"),
oneOrMore(choice(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("b"), 𝗲𝗹𝗲𝗺𝗲𝗻𝘁("c"))),
optional(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("d")),
𝗲𝗹𝗲𝗺𝗲𝗻𝘁("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(@elements)
Sequence of elements.
Parameter Description
1 @elements Elements
Example:
my $dfa = fromExpr # Construct DFA
(zeroOrMore(𝘀𝗲𝗾𝘂𝗲𝗻𝗰𝗲('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
This is a static method and so should either be imported or invoked as:
Data::DFA::sequence
optional(@element)
An optional sequence of element.
Parameter Description
1 @element Elements
Example:
my $dfa = fromExpr # Construct DFA
("a",
oneOrMore(choice(qw(b c))),
𝗼𝗽𝘁𝗶𝗼𝗻𝗮𝗹("d"),
"e"
);
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
my $dfa = fromExpr # Construct DFA
(element("a"),
oneOrMore(choice(element("b"), element("c"))),
𝗼𝗽𝘁𝗶𝗼𝗻𝗮𝗹(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::optional
zeroOrMore(@element)
Zero or more repetitions of a sequence of elements.
Parameter Description
1 @element Elements
Example:
my $dfa = fromExpr # Construct DFA
(𝘇𝗲𝗿𝗼𝗢𝗿𝗠𝗼𝗿𝗲(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
This is a static method and so should either be imported or invoked as:
Data::DFA::zeroOrMore
oneOrMore(@element)
One or more repetitions of a sequence of elements.
Parameter Description
1 @element Elements
Example:
my $dfa = fromExpr # Construct DFA
("a",
𝗼𝗻𝗲𝗢𝗿𝗠𝗼𝗿𝗲(choice(qw(b c))),
optional("d"),
"e"
);
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
my $dfa = fromExpr # Construct DFA
(element("a"),
𝗼𝗻𝗲𝗢𝗿𝗠𝗼𝗿𝗲(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::oneOrMore
choice(@elements)
Choice from amongst one or more elements.
Parameter Description
1 @elements Elements to be chosen from
Example:
my $dfa = fromExpr # Construct DFA
("a",
oneOrMore(𝗰𝗵𝗼𝗶𝗰𝗲(qw(b c))),
optional("d"),
"e"
);
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
my $dfa = fromExpr # Construct DFA
(element("a"),
oneOrMore(𝗰𝗵𝗼𝗶𝗰𝗲(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::choice
except(@elements)
Choice from amongst all symbols except the ones mentioned
Parameter Description
1 @elements Elements to be chosen from
Example:
my $dfa = fromExpr # Construct DFA
(zeroOrMore(sequence('a'..'c')),
𝗲𝘅𝗰𝗲𝗽𝘁('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
This is a static method and so should either be imported or invoked as:
Data::DFA::except
fromExpr(@expression)
Create a DFA parser from a regular @expression.
Parameter Description
1 @expression Regular expression
Example:
my $dfa = 𝗳𝗿𝗼𝗺𝗘𝘅𝗽𝗿 # Construct DFA
("a",
oneOrMore(choice(qw(b c))),
optional("d"),
"e"
);
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
my $dfa = 𝗳𝗿𝗼𝗺𝗘𝘅𝗽𝗿 # 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::fromExpr
print($dfa, $title)
Print the specified $dfa using the specified $title.
Parameter Description
1 $dfa DFA
2 $title Optional title
Example:
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->𝗽𝗿𝗶𝗻𝘁(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
symbols($dfa)
Return an array of all the symbols accepted by a $dfa.
Parameter Description
1 $dfa DFA
Example:
my $dfa = fromExpr # Construct DFA
("a",
oneOrMore(choice(qw(b c))),
optional("d"),
"e"
);
is_deeply ['a'..'e'], [$dfa->𝘀𝘆𝗺𝗯𝗼𝗹𝘀]; # List 𝘀𝘆𝗺𝗯𝗼𝗹𝘀
parser($dfa)
Create a parser from a $dfa constructed from a regular expression.
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expression
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 $𝗽𝗮𝗿𝘀𝗲𝗿 = $dfa->𝗽𝗮𝗿𝘀𝗲𝗿; # New 𝗽𝗮𝗿𝘀𝗲𝗿
eval { $𝗽𝗮𝗿𝘀𝗲𝗿->accept($_) } for qw(a b a); # Try to parse a b a
is_deeply [$𝗽𝗮𝗿𝘀𝗲𝗿->next], [qw(b c d e)]; # Next acceptable symbol
is_deeply $𝗽𝗮𝗿𝘀𝗲𝗿->processed, [qw(a b)]; # Symbols processed
ok !$𝗽𝗮𝗿𝘀𝗲𝗿->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
dumpAsJson($dfa)
Create a JSON string representing a $dfa.
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expression
Example:
my $dfa = fromExpr # Construct DFA
("a",
oneOrMore(choice(qw(b c))),
optional("d"),
"e"
);
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
printAsExpr($dfa)
Print a $dfa as an expression.
Parameter Description
1 $dfa DFA
Example:
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->𝗽𝗿𝗶𝗻𝘁𝗔𝘀𝗘𝘅𝗽𝗿;
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->𝗽𝗿𝗶𝗻𝘁𝗔𝘀𝗘𝘅𝗽𝗿;
ok $e eq $S;
}
printAsRe($dfa)
Print a $dfa as a regular expression.
Parameter Description
1 $dfa DFA
Example:
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->𝗽𝗿𝗶𝗻𝘁𝗔𝘀𝗥𝗲;
ok $R eq q(a (b | c)* d);
my $D = parseDtdElement(q(a, (b | c)*, d));
my $S = $D->printAsExpr;
ok $e eq $S;
}
parseDtdElement($string)
Convert the Dtd Element definition in $string to a DFA.
Parameter Description
1 $string String representation of DTD element expression
Example:
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 = 𝗽𝗮𝗿𝘀𝗲𝗗𝘁𝗱𝗘𝗹𝗲𝗺𝗲𝗻𝘁(q(a, (b | c)*, d));
my $S = $D->printAsExpr;
ok $e eq $S;
}
Paths
Find paths in a DFA.
shortPaths($dfa)
Find a set of paths that reach every state in the DFA with each path terminating in a final state.
Parameter Description
1 $dfa DFA
Example:
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 𝘀𝗵𝗼𝗿𝘁𝗣𝗮𝘁𝗵𝘀 ($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"]};
}
longPaths($dfa)
Find a set of paths that traverse each transition in the DFA with each path terminating in a final state.
Parameter Description
1 $dfa DFA
Example:
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 𝗹𝗼𝗻𝗴𝗣𝗮𝘁𝗵𝘀($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"]};
}
loops($dfa)
Find the non repeating loops from each state.
Parameter Description
1 $dfa DFA
Example:
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));
is_deeply $d->𝗹𝗼𝗼𝗽𝘀, {
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;
}
Parser methods
Use the DFA to parse a sequence of symbols
Data::DFA::Parser::accept($parser, $symbol)
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
Example:
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
Data::DFA::Parser::final($parser)
Returns whether the specified $parser is in a final state or not.
Parameter Description
1 $parser DFA Parser
Example:
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::Parser::next($parser)
Returns an array of symbols that would be accepted in the current state by the specified $parser.
Parameter Description
1 $parser DFA Parser
Example:
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::Parser::accepts($parser, @symbols)
Confirm that the specified $parser accepts an array representing a sequence of symbols.
Parameter Description
1 $parser DFA Parser
2 @symbols Array of symbols
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
Data::DFA Definition
DFA State
Output fields
final - Whether this state is final
nfaStates - Hash whose keys are the NFA states that contributed to this super state
pump - Pumping lemmas for this state
sequence - Sequence of states to final state minus pumped states
state - Name of the state - the join of the NFA keys
transitions - Transitions from this state
Data::DFA::State Definition
DFA State
Output fields
final - Whether this state is final
nfaStates - Hash whose keys are the NFA states that contributed to this super state
pump - Pumping lemmas for this state
sequence - Sequence of states to final state minus pumped states
state - Name of the state - the join of the NFA keys
transitions - Transitions from this state
Private Methods
newDFA()
Create a new DFA.
newState(%options)
Create a new DFA state with the specified options.
Parameter Description
1 %options DFA state as hash
fromNfa($nfa)
Create a DFA parser from an NFA.
Parameter Description
1 $nfa Nfa
finalState($nfa, $reach)
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
superState($dfa, $superStateName, $nfa, $symbols, $nfaSymbolTransitions)
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
superStates($dfa, $SuperStateName, $nfa)
Create super states from existing superstate.
Parameter Description
1 $dfa DFA
2 $SuperStateName Start state in DFA
3 $nfa NFA we are tracking
transitionOnSymbol($dfa, $superStateName, $symbol)
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
renumberDfa($dfa, $initialStateName)
Renumber the states in the specified $dfa.
Parameter Description
1 $dfa DFA
2 $initialStateName Initial super state name
Example:
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
printFinal($final)
Print a final state
Parameter Description
1 $final Final State
removeDuplicatedStates($dfa)
Remove duplicated states in a $dfa.
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expression
removeUnreachableStates($dfa)
Remove unreachable states in a $dfa.
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expression
printAsExpr2($dfa, %options)
Print a DFA $dfa_ in an expression form determined by the specified %options.
Parameter Description
1 $dfa Dfa
2 %options Options.
subArray($A, $B)
Whether the second array is contained within the first
Parameter Description
1 $A Exterior array
2 $B Interior array
removeLongerPathsThatContainShorterPaths($paths)
Remove longer paths that contain shorter paths
Parameter Description
1 $paths Paths
Index
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 Dtd Element definition in $string to a DFA.
19 parser - Create a parser from a $dfa constructed from a regular expression.
20 print - Print the specified $dfa using the specified $title.
21 printAsExpr - Print a $dfa as an expression.
22 printAsExpr2 - Print a DFA $dfa_ in an expression form determined by the specified %options.
23 printAsRe - Print a $dfa as a regular expression.
24 printFinal - Print a final state
25 removeDuplicatedStates - Remove duplicated states in a $dfa.
26 removeLongerPathsThatContainShorterPaths - Remove longer paths that contain shorter paths
27 removeUnreachableStates - Remove unreachable states in a $dfa.
28 renumberDfa - Renumber the states in the specified $dfa.
29 sequence - Sequence of elements.
30 shortPaths - Find a set of paths that reach every state in the DFA with each path terminating in a final state.
31 subArray - Whether the second array is contained within the first
32 superState - Create super states from existing superstate.
33 superStates - Create super states from existing superstate.
34 symbols - Return an array of all the symbols accepted by a $dfa.
35 transitionOnSymbol - The super state reached by transition on a symbol from a specified state. 36 zeroOrMore - Zero or more repetitions of a sequence of elements.
Installation
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
Author
Copyright
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.