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
say STDERR $@; # Error message
# Already processed: a b
# Expected one of : b c d e
# But was given : 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 stateDescription
Deterministic finite state parser from regular expression
Version "20190329".
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 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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
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'..'g')),
except('d'..'g')
);
ok $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a)); # Accept symbols
ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g)); # Fail to accept symbols
my $parser = $dfa->parser;
$parser->accept(qw(a b c d e f g a b c d e f g a));
ok $parser->final;
ok $dfa->print(q(Test)) eq <<END if compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok $dfa->print(q(Test)) eq <<END unless compressDfa; # Print uncompressed DFA
Test
State Final Symbol Target Final
1 0 a 1 13 9 1
2 b 11 13 1
3 c 13 1
4 0 10 12 7 8 0 a 1 13 9 1
5 b 11 13 1
6 c 13 1
7 1 13 9 1 b 2 0
8 2 0 c 3 0
9 3 0 d 4 0
10 4 0 e 5 0
11 5 0 f 6 0
12 6 0 g 0 10 12 7 8 0
END
ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok 1 if compressDfa;
}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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
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'..'g')),
except('d'..'g')
);
ok $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a)); # Accept symbols
ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g)); # Fail to accept symbols
my $parser = $dfa->parser;
$parser->accept(qw(a b c d e f g a b c d e f g a));
ok $parser->final;
ok $dfa->print(q(Test)) eq <<END if compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok $dfa->print(q(Test)) eq <<END unless compressDfa; # Print uncompressed DFA
Test
State Final Symbol Target Final
1 0 a 1 13 9 1
2 b 11 13 1
3 c 13 1
4 0 10 12 7 8 0 a 1 13 9 1
5 b 11 13 1
6 c 13 1
7 1 13 9 1 b 2 0
8 2 0 c 3 0
9 3 0 d 4 0
10 4 0 e 5 0
11 5 0 f 6 0
12 6 0 g 0 10 12 7 8 0
END
ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok 1 if compressDfa;
}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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
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'..'g')),
𝗲𝘅𝗰𝗲𝗽𝘁('d'..'g')
);
ok $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a)); # Accept symbols
ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g)); # Fail to accept symbols
my $parser = $dfa->parser;
$parser->accept(qw(a b c d e f g a b c d e f g a));
ok $parser->final;
ok $dfa->print(q(Test)) eq <<END if compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok $dfa->print(q(Test)) eq <<END unless compressDfa; # Print uncompressed DFA
Test
State Final Symbol Target Final
1 0 a 1 13 9 1
2 b 11 13 1
3 c 13 1
4 0 10 12 7 8 0 a 1 13 9 1
5 b 11 13 1
6 c 13 1
7 1 13 9 1 b 2 0
8 2 0 c 3 0
9 3 0 d 4 0
10 4 0 e 5 0
11 5 0 f 6 0
12 6 0 g 0 10 12 7 8 0
END
ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok 1 if compressDfa;
}This is a static method and so should be invoked as:
Data::DFA::exceptfromExpr(@)
Create a DFA from a regular expression.
Parameter Description
1 @expr 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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
END
}This is a static method and so should be invoked as:
Data::DFA::fromExprcompress($)
Compress DFA by renaming states and deleting no longer needed NFA states
Parameter Description
1 $dfa DFAExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(zeroOrMore(sequence('a'..'g')),
except('d'..'g')
);
ok $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a)); # Accept symbols
ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g)); # Fail to accept symbols
my $parser = $dfa->parser;
$parser->accept(qw(a b c d e f g a b c d e f g a));
ok $parser->final;
ok $dfa->print(q(Test)) eq <<END if compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok $dfa->print(q(Test)) eq <<END unless compressDfa; # Print uncompressed DFA
Test
State Final Symbol Target Final
1 0 a 1 13 9 1
2 b 11 13 1
3 c 13 1
4 0 10 12 7 8 0 a 1 13 9 1
5 b 11 13 1
6 c 13 1
7 1 13 9 1 b 2 0
8 2 0 c 3 0
9 3 0 d 4 0
10 4 0 e 5 0
11 5 0 f 6 0
12 6 0 g 0 10 12 7 8 0
END
ok $dfa->𝗰𝗼𝗺𝗽𝗿𝗲𝘀𝘀->print(q(Test)) eq <<END unless compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok 1 if compressDfa;
}print($$$)
Print DFA to a string and optionally to STDERR or STDOUT
Parameter Description
1 $dfa DFA
2 $title Title
3 $print 1 - STDOUT or 2 - STDERRExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(zeroOrMore(sequence('a'..'g')),
except('d'..'g')
);
ok $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a)); # Accept symbols
ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g)); # Fail to accept symbols
my $parser = $dfa->parser;
$parser->accept(qw(a b c d e f g a b c d e f g a));
ok $parser->final;
ok $dfa->𝗽𝗿𝗶𝗻𝘁(q(Test)) eq <<END if compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok $dfa->𝗽𝗿𝗶𝗻𝘁(q(Test)) eq <<END unless compressDfa; # Print uncompressed DFA
Test
State Final Symbol Target Final
1 0 a 1 13 9 1
2 b 11 13 1
3 c 13 1
4 0 10 12 7 8 0 a 1 13 9 1
5 b 11 13 1
6 c 13 1
7 1 13 9 1 b 2 0
8 2 0 c 3 0
9 3 0 d 4 0
10 4 0 e 5 0
11 5 0 f 6 0
12 6 0 g 0 10 12 7 8 0
END
ok $dfa->compress->𝗽𝗿𝗶𝗻𝘁(q(Test)) eq <<END unless compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok 1 if compressDfa;
}symbols($)
Return an array of all the symbols accepted by the 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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}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 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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
END
}This is a static method and so should be invoked as:
Data::DFA::parserdumpAsJson($)
Create a JSON representation {transitions=>{symbol=>state}, finalStates=>{state=>1}}
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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}This is a static method and so should be invoked as:
Data::DFA::dumpAsJsonParser 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 automatonExample:
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
END
}
if (1) {
my $dfa = fromExpr # Construct DFA
(zeroOrMore(sequence('a'..'g')),
except('d'..'g')
);
ok $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a)); # Accept symbols
ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g)); # Fail to accept symbols
my $parser = $dfa->parser;
$parser->accept(qw(a b c d e f g a b c d e f g a));
ok $parser->final;
ok $dfa->print(q(Test)) eq <<END if compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok $dfa->print(q(Test)) eq <<END unless compressDfa; # Print uncompressed DFA
Test
State Final Symbol Target Final
1 0 a 1 13 9 1
2 b 11 13 1
3 c 13 1
4 0 10 12 7 8 0 a 1 13 9 1
5 b 11 13 1
6 c 13 1
7 1 13 9 1 b 2 0
8 2 0 c 3 0
9 3 0 d 4 0
10 4 0 e 5 0
11 5 0 f 6 0
12 6 0 g 0 10 12 7 8 0
END
ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok 1 if compressDfa;
}Data::DFA::Parser::final($)
Returns whether we are currently in a final state or not
Parameter Description
1 $parser DFA ParserExample:
if (1) {
my $dfa = fromExpr # Construct DFA
(zeroOrMore(sequence('a'..'g')),
except('d'..'g')
);
ok $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a)); # Accept symbols
ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g)); # Fail to accept symbols
my $parser = $dfa->parser;
$parser->accept(qw(a b c d e f g a b c d e f g a));
ok $parser->final;
ok $dfa->print(q(Test)) eq <<END if compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok $dfa->print(q(Test)) eq <<END unless compressDfa; # Print uncompressed DFA
Test
State Final Symbol Target Final
1 0 a 1 13 9 1
2 b 11 13 1
3 c 13 1
4 0 10 12 7 8 0 a 1 13 9 1
5 b 11 13 1
6 c 13 1
7 1 13 9 1 b 2 0
8 2 0 c 3 0
9 3 0 d 4 0
10 4 0 e 5 0
11 5 0 f 6 0
12 6 0 g 0 10 12 7 8 0
END
ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 2 1
2 b 3 1
3 c 4 1
4 1 0 a 2 1
5 b 3 1
6 c 4 1
7 2 1 b 5 0
8 5 0 c 6 0
9 6 0 d 7 0
10 7 0 e 8 0
11 8 0 f 9 0
12 9 0 g 1 0
END
ok 1 if compressDfa;
}Data::DFA::Parser::next($)
Returns an array of symbols that would be accepted in the current state
Parameter Description
1 $parser DFA ParserExample:
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
END
}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 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 if compressDfa; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 0 b 1 0
3 c 3 0
4 d 4 0
5 e 5 1
6 2 0 b 1 0
7 c 3 0
8 3 0 b 1 0
9 c 3 0
10 d 4 0
11 e 5 1
12 4 0 e 5 1
END
ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END unless compressDfa; # Print uncompresed DFA
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
}
if (1) { #T 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 dumpAsJson($dfa) eq <<END if compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 0,
"5" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"2" : {
"b" : 1,
"c" : 3
},
"3" : {
"b" : 1,
"c" : 3,
"d" : 4,
"e" : 5
},
"4" : {
"e" : 5
}
}
}
END
ok dumpAsJson($dfa) eq <<END unless compressDfa; # Dump as json
{
"finalStates" : {
"0" : 0,
"1 2 3 4 5 6" : 0,
"1 3" : 0,
"1 3 4 5 6" : 0,
"6" : 0,
"7" : 1
},
"transitions" : {
"0" : {
"a" : "1 3"
},
"1 2 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"1 3" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6"
},
"1 3 4 5 6" : {
"b" : "1 2 3 4 5 6",
"c" : "1 3 4 5 6",
"d" : "6",
"e" : "7"
},
"6" : {
"e" : "7"
}
}
}
END
}Private Methods
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 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 SymbolIndex
1 choice - Choice from amongst one or more elements.
2 compress - Compress DFA by renaming states and deleting no longer needed NFA states
3 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
4 Data::DFA::Parser::accepts - Confirm that a DFA accepts an array representing a sequence of symbols
5 Data::DFA::Parser::final - Returns whether we are currently in a final state or not
6 Data::DFA::Parser::next - Returns an array of symbols that would be accepted in the current state
7 dumpAsJson - Create a JSON representation {transitions=>{symbol=>state}, finalStates=>{state=>1}}
8 element - One element.
9 except - Choice from amongst all symbols except the ones mentioned
10 finalState - Check whether any of the specified states in the NFA are final
11 fromExpr - Create a DFA from a regular expression.
12 oneOrMore - One or more repetitions of a sequence of elements.
13 optional - An optional sequence of element.
14 parser - Create a parser from a deterministic finite state automaton constructed from a regular expression.
15 print - Print DFA to a string and optionally to STDERR or STDOUT
16 sequence - Sequence of elements.
17 superState - Create super states from existing superstate
18 superStates - Create super states from existing superstate
19 symbols - Return an array of all the symbols accepted by the DFA
20 transitionOnSymbol - The super state reached by transition on a symbol from a specified state
21 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-2018 Philip R Brenan.
This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.