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 20191111.
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($)
One element.
Parameter Description
1 $label Transition symbolExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("a"),
oneOrMore(choice(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("b"), 𝗲𝗹𝗲𝗺𝗲𝗻𝘁("c"))),
optional(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("d")),
𝗲𝗹𝗲𝗺𝗲𝗻𝘁("e")
);
ok $dfa->parser->accepts(qw(a b e)); # Accept symbols
ok !$dfa->parser->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}
if (0) {
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 be invoked as:
Data::DFA::elementsequence(@)
Sequence of elements.
Parameter Description
1 @elements ElementsExample:
if (1) {
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 be invoked as:
Data::DFA::sequenceoptional(@)
An optional sequence of element.
Parameter Description
1 @element ElementsExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(element("a"),
oneOrMore(choice(element("b"), element("c"))),
𝗼𝗽𝘁𝗶𝗼𝗻𝗮𝗹(element("d")),
element("e")
);
ok $dfa->parser->accepts(qw(a b e)); # Accept symbols
ok !$dfa->parser->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}
if (0) {
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 be invoked as:
Data::DFA::optionalzeroOrMore(@)
Zero or more repetitions of a sequence of elements.
Parameter Description
1 @element ElementsExample:
if (1) {
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 be invoked as:
Data::DFA::zeroOrMoreoneOrMore(@)
One or more repetitions of a sequence of elements.
Parameter Description
1 @element ElementsExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(element("a"),
𝗼𝗻𝗲𝗢𝗿𝗠𝗼𝗿𝗲(choice(element("b"), element("c"))),
optional(element("d")),
element("e")
);
ok $dfa->parser->accepts(qw(a b e)); # Accept symbols
ok !$dfa->parser->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}
if (0) {
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 be invoked as:
Data::DFA::oneOrMorechoice(@)
Choice from amongst one or more elements.
Parameter Description
1 @elements Elements to be chosen fromExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(element("a"),
oneOrMore(𝗰𝗵𝗼𝗶𝗰𝗲(element("b"), element("c"))),
optional(element("d")),
element("e")
);
ok $dfa->parser->accepts(qw(a b e)); # Accept symbols
ok !$dfa->parser->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}
if (0) {
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 be invoked as:
Data::DFA::choiceexcept(@)
Choice from amongst all symbols except the ones mentioned
Parameter Description
1 @elements Elements to be chosen fromExample:
if (1) {
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 be invoked as:
Data::DFA::exceptfromExpr(@)
Create a DFA parser from a regular @expression.
Parameter Description
1 @expression Regular expressionExample:
if (1) {
my $dfa = 𝗳𝗿𝗼𝗺𝗘𝘅𝗽𝗿 # Construct DFA
(element("a"),
oneOrMore(choice(element("b"), element("c"))),
optional(element("d")),
element("e")
);
ok $dfa->parser->accepts(qw(a b e)); # Accept symbols
ok !$dfa->parser->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}
if (0) {
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 be invoked as:
Data::DFA::fromExprprintFinal($)
Print a final state
Parameter Description
1 $final Final Stateprint($$)
Print the specified $dfa using the specified $title.
Parameter Description
1 $dfa DFA
2 $title Optional titleExample:
if (1) {
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($)
Return an array of all the symbols accepted by a $dfa.
Parameter Description
1 $dfa DFAExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(element("a"),
oneOrMore(choice(element("b"), element("c"))),
optional(element("d")),
element("e")
);
ok $dfa->parser->accepts(qw(a b e)); # Accept 𝘀𝘆𝗺𝗯𝗼𝗹𝘀
ok !$dfa->parser->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->𝘀𝘆𝗺𝗯𝗼𝗹𝘀]; # List 𝘀𝘆𝗺𝗯𝗼𝗹𝘀
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}parser($)
Create a parser from a $dfa constructed from a regular expression.
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expressionExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(element("a"),
oneOrMore(choice(element("b"), element("c"))),
optional(element("d")),
element("e")
);
ok $dfa->𝗽𝗮𝗿𝘀𝗲𝗿->accepts(qw(a b e)); # Accept symbols
ok !$dfa->𝗽𝗮𝗿𝘀𝗲𝗿->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}
if (0) {
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($)
Create a JSON string representing a $dfa.
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expressionExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(element("a"),
oneOrMore(choice(element("b"), element("c"))),
optional(element("d")),
element("e")
);
ok $dfa->parser->accepts(qw(a b e)); # Accept symbols
ok !$dfa->parser->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}printAsExpr($)
Print a $dfa as an expression.
Parameter Description
1 $dfa DFAExample:
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($R);
my $S = $D->𝗽𝗿𝗶𝗻𝘁𝗔𝘀𝗘𝘅𝗽𝗿;
ok $e eq $S;
}printAsRe($)
Print a $dfa as a regular expression.
Parameter Description
1 $dfa DFAExample:
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($R);
my $S = $D->printAsExpr;
ok $e eq $S;
}parseDtdElement($)
Convert the Dtd Element definition in $stringto a DFA,
Parameter Description
1 $string String representation of DTD element expressionExample:
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 = 𝗽𝗮𝗿𝘀𝗲𝗗𝘁𝗱𝗘𝗹𝗲𝗺𝗲𝗻𝘁($R);
my $S = $D->printAsExpr;
ok $e eq $S;
}Parser methods
Use the DFA to parse a sequence of symbols
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.
Parameter Description
1 $parser DFA Parser
2 $symbol Next symbol to be processed by the finite state automatonExample:
if (0) {
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
}
if (1) {
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($)
Returns whether the specified $parser is in a final state or not.
Parameter Description
1 $parser DFA ParserExample:
if (1) {
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($)
Returns an array of symbols that would be accepted in the current state by the specified $parser.
Parameter Description
1 $parser DFA ParserExample:
if (0) {
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($@)
Confirm that the specified $parser accepts an array representing a sequence of symbols.
Parameter Description
1 $parser DFA Parser
2 @symbols Array of symbolsExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(element("a"),
oneOrMore(choice(element("b"), element("c"))),
optional(element("d")),
element("e")
);
ok $dfa->parser->accepts(qw(a b e)); # Accept symbols
ok !$dfa->parser->accepts(qw(a d));
is_deeply ['a'..'e'], [$dfa->symbols]; # List symbols
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END; # Print renumberDfaed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2
2 1 b 1
3 c 1
4 d 3
5 e 4 1
6 2 b 1
7 c 1
8 3 e 4 1
9 4 1
END
}
if (0) {
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 g
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 g
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(%)
Create a new DFA state with the specified options.
Parameter Description
1 %options DFA state as hashfromNfa($)
Create a DFA parser from an NFA.
Parameter Description
1 $nfa NfafinalState($$)
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 NFAsuperState($$$$$)
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 symbolsuperStates($$$)
Create super states from existing superstate.
Parameter Description
1 $dfa DFA
2 $SuperStateName Start state in DFA
3 $nfa NFA we are trackingtransitionOnSymbol($$$)
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 SymbolrenumberDfa($)
Renumber the states in the specified $dfa.
Parameter Description
1 $dfa DFAExample:
if (1) {
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
}removeDuplicatedStates($)
Remove duplicated states in a $dfa.
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expressionremoveUnreachableStates($)
Remove unreachable states in a $dfa.
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expressionprintAsExpr2($%)
Print a DFA $dfa_ in an expression form determined by the specified %options.
Parameter Description
1 $dfa Dfa
2 %options Options.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 newDFA - Create a new DFA.
13 newState - Create a new DFA state with the specified options.
14 oneOrMore - One or more repetitions of a sequence of elements.
15 optional - An optional sequence of element.
16 parseDtdElement - Convert the Dtd Element definition in $stringto a DFA,
17 parser - Create a parser from a $dfa constructed from a regular expression.
18 print - Print the specified $dfa using the specified $title.
19 printAsExpr - Print a $dfa as an expression.
20 printAsExpr2 - Print a DFA $dfa_ in an expression form determined by the specified %options.
21 printAsRe - Print a $dfa as a regular expression.
22 printFinal - Print a final state
23 removeDuplicatedStates - Remove duplicated states in a $dfa.
24 removeUnreachableStates - Remove unreachable states in a $dfa.
25 renumberDfa - Renumber the states in the specified $dfa.
26 sequence - Sequence of elements.
27 superState - Create super states from existing superstate.
28 superStates - Create super states from existing superstate.
29 symbols - Return an array of all the symbols accepted by a $dfa.
30 transitionOnSymbol - The super state reached by transition on a symbol from a specified state.
31 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::DFAAuthor
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.