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 "20191029".
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; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 4 1
END
}
if (1) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
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; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 1 1
2 b 2 1
3 c 2 1
4 1 1 b 3 0
5 3 c 4 0
6 4 d 5 0
7 5 e 6 0
8 6 f 7 0
9 7 g 0 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 compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 4 1
END
}
if (1) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
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; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 1 1
2 b 2 1
3 c 2 1
4 1 1 b 3 0
5 3 c 4 0
6 4 d 5 0
7 5 e 6 0
8 6 f 7 0
9 7 g 0 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 compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 4 1
END
}
if (1) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
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 compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 4 1
END
}
if (1) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
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; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 1 1
2 b 2 1
3 c 2 1
4 1 1 b 3 0
5 3 c 4 0
6 4 d 5 0
7 5 e 6 0
8 6 f 7 0
9 7 g 0 0
END
}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; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 4 1
END
}
if (1) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
END
}This is a static method and so should be invoked as:
Data::DFA::fromExprcompress($)
Compress the DFA by removing duplicate 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; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 1 1
2 b 2 1
3 c 2 1
4 1 1 b 3 0
5 3 c 4 0
6 4 d 5 0
7 5 e 6 0
8 6 f 7 0
9 7 g 0 0
END
}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; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 1 1
2 b 2 1
3 c 2 1
4 1 1 b 3 0
5 3 c 4 0
6 4 d 5 0
7 5 e 6 0
8 6 f 7 0
9 7 g 0 0
END
}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; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 4 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; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 4 1
END
}
if (1) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
END
}dumpAsJson($)
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; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 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($$)
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) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
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; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 1 1
2 b 2 1
3 c 2 1
4 1 1 b 3 0
5 3 c 4 0
6 4 d 5 0
7 5 e 6 0
8 6 f 7 0
9 7 g 0 0
END
}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; # Print compressed DFA
Test
State Final Symbol Target Final
1 0 a 1 1
2 b 2 1
3 c 2 1
4 1 1 b 3 0
5 3 c 4 0
6 4 d 5 0
7 5 e 6 0
8 6 f 7 0
9 7 g 0 0
END
}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) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
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; # Print compressed DFA
Dfa for a(b|c)+d?e :
State Final Symbol Target Final
1 0 a 2 0
2 1 b 1 0
3 c 1 0
4 d 3 0
5 e 4 1
6 2 b 1 0
7 c 1 0
8 3 e 4 1
END
}
if (1) {
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; # Dump as json
{
"finalStates" : {
"0" : 0,
"1" : 0,
"2" : 0,
"3" : 0,
"4" : 1
},
"transitions" : {
"0" : {
"a" : 2
},
"1" : {
"b" : 1,
"c" : 1,
"d" : 3,
"e" : 4
},
"2" : {
"b" : 1,
"c" : 1
},
"3" : {
"e" : 4
}
}
}
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
return - Return 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
return - Return 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
Parameter Description
1 %options DFA state as hashfromNfa($)
Create a DFA from an NFA.
Parameter Description
1 $nfa NfafinalState($$)
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 SymbolremoveDuplicatedStates($)
Remove duplicated states in a DFA
Parameter Description
1 $dfa Deterministic finite state automaton generated from an expressionprintAsExpr2($%)
Print a DFA $dfa_ in expression form
Parameter Description
1 $dfa Dfa
2 %options OptionsIndex
1 choice - Choice from amongst one or more elements.
2 compress - Compress the DFA by removing duplicate 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 fromNfa - Create a DFA from an NFA.
13 newDFA - Create a new DFA
14 newState - Create a new DFA state
15 oneOrMore - One or more repetitions of a sequence of elements.
16 optional - An optional sequence of element.
17 parseDtdElement - Convert the Dtd Element definition in $stringto a DFA
18 parser - Create a parser from a deterministic finite state automaton constructed from a regular expression.
19 print - Print DFA to a string and optionally to STDERR or STDOUT
20 printAsExpr - Print a $dfa as an expression
21 printAsExpr2 - Print a DFA $dfa_ in expression form
22 printAsRe - Print a $dfa as a regular expression
23 removeDuplicatedStates - Remove duplicated states in a DFA
24 sequence - Sequence of elements.
25 superState - Create super states from existing superstate
26 superStates - Create super states from existing superstate
27 symbols - Return an array of all the symbols accepted by the DFA
28 transitionOnSymbol - The super state reached by transition on a symbol from a specified state
29 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.