# 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:

Create the parser:

``````  my \$dfa = fromExpr
("a",
oneOrMore
(choice(qw(b c))),
optional("d"),
"e"
);``````

Recognize sequences of symbols:

``````  ok  \$dfa->parser->accepts(qw(a b e));
ok  \$dfa->parser->accepts(qw(a b c e));
ok !\$dfa->parser->accepts(qw(a d));
ok !\$dfa->parser->accepts(qw(a c d));
ok  \$dfa->parser->accepts(qw(a c d e));``````

Print the transition table:

``````  is_deeply \$dfa->print("a(b|c)+d?e"), <<END;
a(b|c)+d?e
State  Final  Symbol  Target  Final
1      0         a            4
2      1         b            1
3                c            1
4                d            2
5                e            3      1
6      2         e            3      1
7      3      1                      1
8      4         b            1
9                c            1
END``````

Discover why a sequence cannot be recognized:

``````  my \$parser = \$dfa->parser;

eval { \$parser->accept(\$_) } for qw(a b a);

is_deeply \$@, <<END;
Expected one of  : b c d e
But found        : a
END

is_deeply  \$parser->fail,       qq(a);
is_deeply [\$parser->next],     [qw(b c d e)];
is_deeply  \$parser->processed, [qw(a b)];

ok !\$parser->final;``````

To construct and parse regular expressions in the format used by !ELEMENT definitions in DTDs used to validate XML:

``````  is_deeply
parseDtdElement(q(a,  b*,  c))->printAsExpr,
q/element(q(a)), zeroOrMore(element(q(b))), element(q(c))/;``````

# Description

Deterministic finite state parser from regular expression.

Version 20201030.

The following sections describe the methods in each functional area of this module. For an alphabetic listing of all methods by name see Index.

# Construct 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

(element("a"),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

oneOrMore(choice(element("b"), element("c"))),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

optional(element("d")),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

element("e")  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

);
my \$parser = \$dfa->parser;                                                    # New parser

eval { \$parser->accept(\$_) } for qw(a b a);                                   # Try to parse a b a

is_deeply [\$parser->next],     [qw(b c d e)];                                 # Next acceptable symbol
is_deeply  \$parser->processed, [qw(a b)];                                     # Symbols processed

ok !\$parser->final;                                                           # Not in a final state

ok \$dfa->dumpAsJson eq <<END, q(dumpAsJson);                                  # Dump as json
{
"finalStates" : {
"0" : null,
"1" : null,
"2" : null,
"4" : null,
"5" : 1
},
"transitions" : {
"0" : {
"a" : "2"
},
"1" : {
"b" : "1",
"c" : "1",
"d" : "4",
"e" : "5"
},
"2" : {
"b" : "1",
"c" : "1"
},
"4" : {
"e" : "5"
}
}
}
END``````

This is a static method and so should either be imported or invoked as:

``  Data::DFA::element``

## sequence(@elements)

Sequence of elements.

``````     Parameter  Description
1  @elements  Elements``````

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``````

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))),

optional("d"),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

"e"
);
is_deeply ['a'..'e'], [\$dfa->symbols];                                        # List symbols

my \$dfa = fromExpr                                                            # Construct DFA
(element("a"),
oneOrMore(choice(element("b"), element("c"))),

optional(element("d")),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

element("e")
);
my \$parser = \$dfa->parser;                                                    # New parser

eval { \$parser->accept(\$_) } for qw(a b a);                                   # Try to parse a b a

is_deeply [\$parser->next],     [qw(b c d e)];                                 # Next acceptable symbol
is_deeply  \$parser->processed, [qw(a b)];                                     # Symbols processed

ok !\$parser->final;                                                           # Not in a final state

ok \$dfa->dumpAsJson eq <<END, q(dumpAsJson);                                  # Dump as json
{
"finalStates" : {
"0" : null,
"1" : null,
"2" : null,
"4" : null,
"5" : 1
},
"transitions" : {
"0" : {
"a" : "2"
},
"1" : {
"b" : "1",
"c" : "1",
"d" : "4",
"e" : "5"
},
"2" : {
"b" : "1",
"c" : "1"
},
"4" : {
"e" : "5"
}
}
}
END``````

This is a static method and so should either be imported or invoked as:

``  Data::DFA::optional``

## zeroOrMore(@element)

Zero or more repetitions of a sequence of elements.

``````     Parameter  Description
1  @element   Elements``````

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``````

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",

oneOrMore(choice(qw(b c))),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

optional("d"),
"e"
);
is_deeply ['a'..'e'], [\$dfa->symbols];                                        # List symbols

my \$dfa = fromExpr                                                            # Construct DFA
(element("a"),

oneOrMore(choice(element("b"), element("c"))),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

optional(element("d")),
element("e")
);
my \$parser = \$dfa->parser;                                                    # New parser

eval { \$parser->accept(\$_) } for qw(a b a);                                   # Try to parse a b a

is_deeply [\$parser->next],     [qw(b c d e)];                                 # Next acceptable symbol
is_deeply  \$parser->processed, [qw(a b)];                                     # Symbols processed

ok !\$parser->final;                                                           # Not in a final state

ok \$dfa->dumpAsJson eq <<END, q(dumpAsJson);                                  # Dump as json
{
"finalStates" : {
"0" : null,
"1" : null,
"2" : null,
"4" : null,
"5" : 1
},
"transitions" : {
"0" : {
"a" : "2"
},
"1" : {
"b" : "1",
"c" : "1",
"d" : "4",
"e" : "5"
},
"2" : {
"b" : "1",
"c" : "1"
},
"4" : {
"e" : "5"
}
}
}
END``````

This is a static method and so should either be imported or invoked as:

``  Data::DFA::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(choice(qw(b c))),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

optional("d"),
"e"
);
is_deeply ['a'..'e'], [\$dfa->symbols];                                        # List symbols

my \$dfa = fromExpr                                                            # Construct DFA
(element("a"),

oneOrMore(choice(element("b"), element("c"))),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

optional(element("d")),
element("e")
);
my \$parser = \$dfa->parser;                                                    # New parser

eval { \$parser->accept(\$_) } for qw(a b a);                                   # Try to parse a b a

is_deeply [\$parser->next],     [qw(b c d e)];                                 # Next acceptable symbol
is_deeply  \$parser->processed, [qw(a b)];                                     # Symbols processed

ok !\$parser->final;                                                           # Not in a final state

ok \$dfa->dumpAsJson eq <<END, q(dumpAsJson);                                  # Dump as json
{
"finalStates" : {
"0" : null,
"1" : null,
"2" : null,
"4" : null,
"5" : 1
},
"transitions" : {
"0" : {
"a" : "2"
},
"1" : {
"b" : "1",
"c" : "1",
"d" : "4",
"e" : "5"
},
"2" : {
"b" : "1",
"c" : "1"
},
"4" : {
"e" : "5"
}
}
}
END``````

This is a static method and so should either be imported or invoked as:

``  Data::DFA::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')),

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::except``

## fromExpr(@expression)

Create a DFA parser from a regular @expression.

``````     Parameter    Description
1  @expression  Regular 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 \$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``

## univalent(\$dfa)

Check that the DFA is univalent: a univalent DFA has a mapping from symbols to states. Returns a hash showing the mapping from symbols to states if the DFA is univalent, else returns undfef.

``````     Parameter  Description
1  \$dfa       Dfa to check``````

# Print

Pritn the Dfa in various ways.

## 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->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``````

## 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->symbols];                                        # List symbols  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲``````

## parser(\$dfa, \$observer)

Create a parser from a \$dfa constructed from a regular expression.

``````     Parameter  Description
1  \$dfa       Deterministic finite state automaton
2  \$observer  Optional observer``````

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``````

## 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->printAsExpr;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

ok \$e eq \$E;

my \$R = \$d->printAsRe;
ok \$R eq q(a (b | c)* d);

my \$D = parseDtdElement(q(a, (b | c)*, d));

my \$S = \$D->printAsExpr;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

ok \$e eq \$S;
}``````

## 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->printAsRe;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

ok \$R eq q(a (b | c)* d);

my \$D = parseDtdElement(q(a, (b | c)*, d));
my \$S = \$D->printAsExpr;
ok \$e eq \$S;
}``````

## parseDtdElementAST(\$string)

Convert the Dtd Element definition in \$string to a parse tree.

``````     Parameter  Description
1  \$string    String representation of DTD element expression``````

Example:

``````  if (1)

{is_deeply unbless(parseDtdElementAST(q(a, (b | c)*, d))),  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

["sequence",
["sequence",
["element", "a"],
["zeroOrMore", ["choice", ["element", "b"], ["element", "c"]]],
],
["element", "d"],
];
}``````

## parseDtdElement(\$string)

Convert the Xml <>DTD> Element definition in the specified \$string to a DFA.

``````     Parameter  Description
1  \$string    DTD element expression string``````

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 = parseDtdElement(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 shortPaths    (\$dfa), { "b c d" => ["b", "c", "d"], "b d" => ["b", "d"] };  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

is_deeply longPaths(\$dfa),
{"a b b c d" => ["a", "b", "b", "c", "d"],
"a b b d"   => ["a", "b", "b", "d"],
"a b c d"   => ["a" .. "d"],
"a b d"     => ["a", "b", "d"],
"b b c d"   => ["b", "b", "c", "d"],
"b b d"     => ["b", "b", "d"],
"b c d"     => ["b", "c", "d"],
"b d"       => ["b", "d"]};
}``````

## 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 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"]};
}``````

## 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));
ok !\$d->parser->accepts(qw(a b c d a));

is_deeply \$d->loops, {  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

1 => [["d", "a", "b", "c"], ["d", "b", "c"], ["d", "c"]],
2 => [["a" .. "d"],         ["b", "c", "d"], ["c", "d"], ["d"]],
3 => [["b", "c", "d", "a"]],
4 => [["c", "d", "a", "b"], ["c", "d", "b"]]};

is_deeply shortPaths(\$d), {"a b c d" => ["a" .. "d"]};
is_deeply longPaths (\$d), { "a b c d" => ["a" .. "d"], "a b c d d" => ["a" .. "d", "d"] };

#say STDERR \$d->printAsExpr;
}``````

# 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 Structures

Data structures used by this package.

## 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::Parser Definition

Parse a sequence of symbols with a DFA

### Output fields

DFA being used

#### fail

Symbol on which we failed

#### observer

Optional sub(\$parser, \$symbol, \$target) to observe transitions.

#### processed

Symbols processed

Current 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 Xml <>DTD> Element definition in the specified \$string to a DFA.

19 parseDtdElementAST - Convert the Dtd Element definition in \$string to a parse tree.

20 parser - Create a parser from a \$dfa constructed from a regular expression.

21 print - Print the specified \$dfa using the specified \$title.

22 printAsExpr - Print a \$dfa as an expression.

23 printAsExpr2 - Print a DFA \$dfa_ in an expression form determined by the specified %options.

24 printAsRe - Print a \$dfa as a regular expression.

25 printFinal - Print a final state

26 removeDuplicatedStates - Remove duplicated states in a \$dfa.

27 removeLongerPathsThatContainShorterPaths - Remove longer paths that contain shorter paths.

28 removeUnreachableStates - Remove unreachable states in a \$dfa.

29 renumberDfa - Renumber the states in the specified \$dfa.

30 sequence - Sequence of elements.

31 shortPaths - Find a set of paths that reach every state in the DFA with each path terminating in a final state.

32 subArray - Whether the second array is contained within the first.

33 superState - Create super states from existing superstate.

34 superStates - Create super states from existing superstate.

35 symbols - Return an array of all the symbols accepted by a \$dfa.

36 transitionOnSymbol - The super state reached by transition on a symbol from a specified state.

37 univalent - Check that the DFA is univalent: a univalent DFA has a mapping from symbols to states.

38 zeroOrMore - Zero or more repetitions of a sequence of elements.

# 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

philiprbrenan@gmail.com

http://www.appaapps.com

Copyright (c) 2016-2019 Philip R Brenan.

This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.