Name

Data::DFA - Deterministic finite state parser from regular expression

Synopsis

Create a deterministic finite state parser to recognize sequences of symbols that match a given regular expression.

To recognize sequences of symbols drawn from 'a'..'e' that match the regular expression: a (b|c)+ d? e:

# Construct a deterministic finite state automaton from the regular expression:

  use Data::DFA qw(:all);
  use Data::Table::Text qw(:all);
  use Test::More qw(no_plan);

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

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

# Print the symbols used and the transitions table:

  is_deeply ['a'..'e'], [$dfa->symbols];

  ok $dfa->print("Dfa for a(b|c)+d?e :") eq nws <<END;
Dfa for a(b|c)+d?e :
    State        Final  Symbol  Target       Final
1   0                   a       1 3          0
2   1 2 3 4 5 6  0      b       1 2 3 4 5 6  0
3                       c       1 3 4 5 6    0
4                       d       6            0
5                       e       7            1
6   1 3          0      b       1 2 3 4 5 6  0
7                       c       1 3 4 5 6    0
8   1 3 4 5 6    0      b       1 2 3 4 5 6  0
9                       c       1 3 4 5 6    0
10                      d       6            0
11                      e       7            1
12  6            0      e       7            1
END

# Create a parser and use it to parse a sequence of symbols

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

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

# Create a parser and use it to parse a sequence of symbols

  my $parser = $dfa->parser;

  eval { $parser->accept($_) } for qw(a b a);
  my $r = $@;
  ok $r =~ m(Already processed: a b);
  ok $r =~ m(Expected one of  : b c d e);
  ok $r =~ m(But found        : a);

  is_deeply [$parser->next],     [qw(b c d e)];
  is_deeply  $parser->processed, [qw(a b)];
  ok !$parser->final;

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

 {my $e = q/element(q(a)), zeroOrMore(choice(element(q(b)), element(q(c)))), element(q(d))/;
  my $d = eval qq/fromExpr($e)/;

  my $E = $d->printAsExpr;
  ok $e eq $E;

  my $R = $d->printAsRe;
  ok $R eq q(a, (b | c)*, d);                                                   # Print as DTD regular expression

  my $D = parseDtdElement($R);                                                  # Parse DTD regular expression
  my $S = $D->printAsExpr;
  ok $e eq $S;
 }

Description

Deterministic finite state parser from regular expression

Version 20191111.

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

Construct regular expression

Construct a regular expression that defines the language to be parsed using the following combining operations:

element($)

One element.

     Parameter  Description
  1  $label     Transition symbol

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (𝗲𝗹𝗲𝗺𝗲𝗻𝘁("a"),
      oneOrMore(choice(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("b"), 𝗲𝗹𝗲𝗺𝗲𝗻𝘁("c"))),
      optional(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("d")),
      𝗲𝗹𝗲𝗺𝗲𝗻𝘁("e")
     );

    ok  $dfa->parser->accepts(qw(a b e));                                         # Accept symbols
    ok !$dfa->parser->accepts(qw(a d));

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

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

  if (0) {
    my $dfa = fromExpr                                                            # Construct DFA
     (𝗲𝗹𝗲𝗺𝗲𝗻𝘁("a"),
      oneOrMore(choice(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("b"), 𝗲𝗹𝗲𝗺𝗲𝗻𝘁("c"))),
      optional(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("d")),
      𝗲𝗹𝗲𝗺𝗲𝗻𝘁("e")
     );
    my $parser = $dfa->parser;                                                    # New parser

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

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

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

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

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

  Data::DFA::element

sequence(@)

Sequence of elements.

     Parameter  Description
  1  @elements  Elements

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (zeroOrMore(𝘀𝗲𝗾𝘂𝗲𝗻𝗰𝗲('a'..'c')),
      except('b'..'d')
     );

    ok  $dfa->parser->accepts(qw(a b c a ));
    ok !$dfa->parser->accepts(qw(a b c a b));
    ok !$dfa->parser->accepts(qw(a b c a c));
    ok !$dfa->parser->accepts(qw(a c c a b c));


    ok $dfa->print(q(Test)) eq <<END;                                             # Print renumbered DFA
  Test
     State  Final  Symbol  Target  Final
  1      0         a            1      1
  2      1      1  b            2
  3      2         c            0
  END
   }

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

  Data::DFA::sequence

optional(@)

An optional sequence of element.

     Parameter  Description
  1  @element   Elements

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      𝗼𝗽𝘁𝗶𝗼𝗻𝗮𝗹(element("d")),
      element("e")
     );

    ok  $dfa->parser->accepts(qw(a b e));                                         # Accept symbols
    ok !$dfa->parser->accepts(qw(a d));

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

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

  if (0) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      𝗼𝗽𝘁𝗶𝗼𝗻𝗮𝗹(element("d")),
      element("e")
     );
    my $parser = $dfa->parser;                                                    # New parser

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

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

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

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

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

  Data::DFA::optional

zeroOrMore(@)

Zero or more repetitions of a sequence of elements.

     Parameter  Description
  1  @element   Elements

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (𝘇𝗲𝗿𝗼𝗢𝗿𝗠𝗼𝗿𝗲(sequence('a'..'c')),
      except('b'..'d')
     );

    ok  $dfa->parser->accepts(qw(a b c a ));
    ok !$dfa->parser->accepts(qw(a b c a b));
    ok !$dfa->parser->accepts(qw(a b c a c));
    ok !$dfa->parser->accepts(qw(a c c a b c));


    ok $dfa->print(q(Test)) eq <<END;                                             # Print renumbered DFA
  Test
     State  Final  Symbol  Target  Final
  1      0         a            1      1
  2      1      1  b            2
  3      2         c            0
  END
   }

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

  Data::DFA::zeroOrMore

oneOrMore(@)

One or more repetitions of a sequence of elements.

     Parameter  Description
  1  @element   Elements

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      𝗼𝗻𝗲𝗢𝗿𝗠𝗼𝗿𝗲(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );

    ok  $dfa->parser->accepts(qw(a b e));                                         # Accept symbols
    ok !$dfa->parser->accepts(qw(a d));

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

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

  if (0) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      𝗼𝗻𝗲𝗢𝗿𝗠𝗼𝗿𝗲(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );
    my $parser = $dfa->parser;                                                    # New parser

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

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

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

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

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

  Data::DFA::oneOrMore

choice(@)

Choice from amongst one or more elements.

     Parameter  Description
  1  @elements  Elements to be chosen from

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(𝗰𝗵𝗼𝗶𝗰𝗲(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );

    ok  $dfa->parser->accepts(qw(a b e));                                         # Accept symbols
    ok !$dfa->parser->accepts(qw(a d));

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

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

  if (0) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(𝗰𝗵𝗼𝗶𝗰𝗲(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );
    my $parser = $dfa->parser;                                                    # New parser

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

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

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

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

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

  Data::DFA::choice

except(@)

Choice from amongst all symbols except the ones mentioned

     Parameter  Description
  1  @elements  Elements to be chosen from

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (zeroOrMore(sequence('a'..'c')),
      𝗲𝘅𝗰𝗲𝗽𝘁('b'..'d')
     );

    ok  $dfa->parser->accepts(qw(a b c a ));
    ok !$dfa->parser->accepts(qw(a b c a b));
    ok !$dfa->parser->accepts(qw(a b c a c));
    ok !$dfa->parser->accepts(qw(a c c a b c));


    ok $dfa->print(q(Test)) eq <<END;                                             # Print renumbered DFA
  Test
     State  Final  Symbol  Target  Final
  1      0         a            1      1
  2      1      1  b            2
  3      2         c            0
  END
   }

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

  Data::DFA::except

fromExpr(@)

Create a DFA parser from a regular @expression.

     Parameter    Description
  1  @expression  Regular expression

Example:

  if (1) {
    my $dfa = 𝗳𝗿𝗼𝗺𝗘𝘅𝗽𝗿                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );

    ok  $dfa->parser->accepts(qw(a b e));                                         # Accept symbols
    ok !$dfa->parser->accepts(qw(a d));

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

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

  if (0) {
    my $dfa = 𝗳𝗿𝗼𝗺𝗘𝘅𝗽𝗿                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );
    my $parser = $dfa->parser;                                                    # New parser

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

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

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

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

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

  Data::DFA::fromExpr

printFinal($)

Print a final state

     Parameter  Description
  1  $final     Final State

print($$)

Print the specified $dfa using the specified $title.

     Parameter  Description
  1  $dfa       DFA
  2  $title     Optional title

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (zeroOrMore(sequence('a'..'c')),
      except('b'..'d')
     );

    ok  $dfa->parser->accepts(qw(a b c a ));
    ok !$dfa->parser->accepts(qw(a b c a b));
    ok !$dfa->parser->accepts(qw(a b c a c));
    ok !$dfa->parser->accepts(qw(a c c a b c));


    ok $dfa->𝗽𝗿𝗶𝗻𝘁(q(Test)) eq <<END;                                             # Print renumbered DFA
  Test
     State  Final  Symbol  Target  Final
  1      0         a            1      1
  2      1      1  b            2
  3      2         c            0
  END
   }

symbols($)

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

     Parameter  Description
  1  $dfa       DFA

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );

    ok  $dfa->parser->accepts(qw(a b e));                                         # Accept 𝘀𝘆𝗺𝗯𝗼𝗹𝘀
    ok !$dfa->parser->accepts(qw(a d));

    is_deeply ['a'..'e'], [$dfa->𝘀𝘆𝗺𝗯𝗼𝗹𝘀];                                        # List 𝘀𝘆𝗺𝗯𝗼𝗹𝘀

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

parser($)

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

     Parameter  Description
  1  $dfa       Deterministic finite state automaton generated from an expression

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );

    ok  $dfa->𝗽𝗮𝗿𝘀𝗲𝗿->accepts(qw(a b e));                                         # Accept symbols
    ok !$dfa->𝗽𝗮𝗿𝘀𝗲𝗿->accepts(qw(a d));

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

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

  if (0) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );
    my $𝗽𝗮𝗿𝘀𝗲𝗿 = $dfa->𝗽𝗮𝗿𝘀𝗲𝗿;                                                    # New 𝗽𝗮𝗿𝘀𝗲𝗿

    eval { $𝗽𝗮𝗿𝘀𝗲𝗿->accept($_) } for qw(a b a);                                   # Try to parse a b a

    is_deeply [$𝗽𝗮𝗿𝘀𝗲𝗿->next],     [qw(b c d e)];                                 # Next acceptable symbol
    is_deeply  $𝗽𝗮𝗿𝘀𝗲𝗿->processed, [qw(a b)];                                     # Symbols processed

    ok !$𝗽𝗮𝗿𝘀𝗲𝗿->final;                                                           # Not in a final state

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

dumpAsJson($)

Create a JSON string representing a $dfa.

     Parameter  Description
  1  $dfa       Deterministic finite state automaton generated from an expression

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );

    ok  $dfa->parser->accepts(qw(a b e));                                         # Accept symbols
    ok !$dfa->parser->accepts(qw(a d));

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

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

printAsExpr($)

Print a $dfa as an expression.

     Parameter  Description
  1  $dfa       DFA

Example:

  if (1)
   {my $e = q/element(q(a)), zeroOrMore(choice(element(q(b)), element(q(c)))), element(q(d))/;
    my $d = eval qq/fromExpr($e)/;
    confess $@ if $@;

    my $E = $d->𝗽𝗿𝗶𝗻𝘁𝗔𝘀𝗘𝘅𝗽𝗿;
    ok $e eq $E;

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

    my $D = parseDtdElement($R);
    my $S = $D->𝗽𝗿𝗶𝗻𝘁𝗔𝘀𝗘𝘅𝗽𝗿;
    ok $e eq $S;
   }

printAsRe($)

Print a $dfa as a regular expression.

     Parameter  Description
  1  $dfa       DFA

Example:

  if (1)
   {my $e = q/element(q(a)), zeroOrMore(choice(element(q(b)), element(q(c)))), element(q(d))/;
    my $d = eval qq/fromExpr($e)/;
    confess $@ if $@;

    my $E = $d->printAsExpr;
    ok $e eq $E;

    my $R = $d->𝗽𝗿𝗶𝗻𝘁𝗔𝘀𝗥𝗲;
    ok $R eq q(((a, (b | c)*, d)));

    my $D = parseDtdElement($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 expression

Example:

  if (1)
   {my $e = q/element(q(a)), zeroOrMore(choice(element(q(b)), element(q(c)))), element(q(d))/;
    my $d = eval qq/fromExpr($e)/;
    confess $@ if $@;

    my $E = $d->printAsExpr;
    ok $e eq $E;

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

    my $D = 𝗽𝗮𝗿𝘀𝗲𝗗𝘁𝗱𝗘𝗹𝗲𝗺𝗲𝗻𝘁($R);
    my $S = $D->printAsExpr;
    ok $e eq $S;
   }

Parser methods

Use the DFA to parse a sequence of symbols

Data::DFA::Parser::accept($$)

Using the specified $parser, accept the next symbol drawn from the symbol set if possible by moving to a new state otherwise confessing with a helpful message that such a move is not possible.

     Parameter  Description
  1  $parser    DFA Parser
  2  $symbol    Next symbol to be processed by the finite state automaton

Example:

  if (0) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );
    my $parser = $dfa->parser;                                                    # New parser

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

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

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

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

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (zeroOrMore(sequence('a'..'c')),
      except('b'..'d')
     );

    ok  $dfa->parser->accepts(qw(a b c a ));
    ok !$dfa->parser->accepts(qw(a b c a b));
    ok !$dfa->parser->accepts(qw(a b c a c));
    ok !$dfa->parser->accepts(qw(a c c a b c));


    ok $dfa->print(q(Test)) eq <<END;                                             # Print renumbered DFA
  Test
     State  Final  Symbol  Target  Final
  1      0         a            1      1
  2      1      1  b            2
  3      2         c            0
  END
   }

Data::DFA::Parser::final($)

Returns whether the specified $parser is in a final state or not.

     Parameter  Description
  1  $parser    DFA Parser

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (zeroOrMore(sequence('a'..'c')),
      except('b'..'d')
     );

    ok  $dfa->parser->accepts(qw(a b c a ));
    ok !$dfa->parser->accepts(qw(a b c a b));
    ok !$dfa->parser->accepts(qw(a b c a c));
    ok !$dfa->parser->accepts(qw(a c c a b c));


    ok $dfa->print(q(Test)) eq <<END;                                             # Print renumbered DFA
  Test
     State  Final  Symbol  Target  Final
  1      0         a            1      1
  2      1      1  b            2
  3      2         c            0
  END
   }

Data::DFA::Parser::next($)

Returns an array of symbols that would be accepted in the current state by the specified $parser.

     Parameter  Description
  1  $parser    DFA Parser

Example:

  if (0) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );
    my $parser = $dfa->parser;                                                    # New parser

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

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

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

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

Data::DFA::Parser::accepts($@)

Confirm that the specified $parser accepts an array representing a sequence of symbols.

     Parameter  Description
  1  $parser    DFA Parser
  2  @symbols   Array of symbols

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );

    ok  $dfa->parser->accepts(qw(a b e));                                         # Accept symbols
    ok !$dfa->parser->accepts(qw(a d));

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

    ok $dfa->print("Dfa for a(b|c)+d?e :") eq <<END;                              # Print renumberDfaed DFA
  Dfa for a(b|c)+d?e :
     State  Final  Symbol  Target  Final
  1      0         a            2
  2      1         b            1
  3                c            1
  4                d            3
  5                e            4      1
  6      2         b            1
  7                c            1
  8      3         e            4      1
  9      4      1
  END
   }

  if (0) {
    my $dfa = fromExpr                                                            # Construct DFA
     (element("a"),
      oneOrMore(choice(element("b"), element("c"))),
      optional(element("d")),
      element("e")
     );
    my $parser = $dfa->parser;                                                    # New parser

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

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

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

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

Data::DFA Definition

DFA State

Output fields

final - Whether this state is g

nfaStates - Hash whose keys are the NFA states that contributed to this super state

pump - Pumping lemmas for this state

sequence - Sequence of states to final state minus pumped states

state - Name of the state - the join of the NFA keys

transitions - Transitions from this state

Data::DFA::State Definition

DFA State

Output fields

final - Whether this state is g

nfaStates - Hash whose keys are the NFA states that contributed to this super state

pump - Pumping lemmas for this state

sequence - Sequence of states to final state minus pumped states

state - Name of the state - the join of the NFA keys

transitions - Transitions from this state

Private Methods

newDFA()

Create a new DFA.

newState(%)

Create a new DFA state with the specified options.

     Parameter  Description
  1  %options   DFA state as hash

fromNfa($)

Create a DFA parser from an NFA.

     Parameter  Description
  1  $nfa       Nfa

finalState($$)

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($$$$$)

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($$$)

Create super states from existing superstate.

     Parameter        Description
  1  $dfa             DFA
  2  $SuperStateName  Start state in DFA
  3  $nfa             NFA we are tracking

transitionOnSymbol($$$)

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($)

Renumber the states in the specified $dfa.

     Parameter  Description
  1  $dfa       DFA

Example:

  if (1) {
    my $dfa = fromExpr                                                            # Construct DFA
     (zeroOrMore(sequence('a'..'c')),
      except('b'..'d')
     );

    ok  $dfa->parser->accepts(qw(a b c a ));
    ok !$dfa->parser->accepts(qw(a b c a b));
    ok !$dfa->parser->accepts(qw(a b c a c));
    ok !$dfa->parser->accepts(qw(a c c a b c));


    ok $dfa->print(q(Test)) eq <<END;                                             # Print renumbered DFA
  Test
     State  Final  Symbol  Target  Final
  1      0         a            1      1
  2      1      1  b            2
  3      2         c            0
  END
   }

removeDuplicatedStates($)

Remove duplicated states in a $dfa.

     Parameter  Description
  1  $dfa       Deterministic finite state automaton generated from an expression

removeUnreachableStates($)

Remove unreachable states in a $dfa.

     Parameter  Description
  1  $dfa       Deterministic finite state automaton generated from an expression

printAsExpr2($%)

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

     Parameter  Description
  1  $dfa       Dfa
  2  %options   Options.

Index

1 choice - Choice from amongst one or more elements.

2 Data::DFA::Parser::accept - Using the specified $parser, accept the next symbol drawn from the symbol set if possible by moving to a new state otherwise confessing with a helpful message that such a move is not possible.

3 Data::DFA::Parser::accepts - Confirm that the specified $parser accepts an array representing a sequence of symbols.

4 Data::DFA::Parser::final - Returns whether the specified $parser is in a final state or not.

5 Data::DFA::Parser::next - Returns an array of symbols that would be accepted in the current state by the specified $parser.

6 dumpAsJson - Create a JSON string representing a $dfa.

7 element - One element.

8 except - Choice from amongst all symbols except the ones mentioned

9 finalState - Check whether, in the specified $nfa, any of the states named in the hash reference $reach are final.

10 fromExpr - Create a DFA parser from a regular @expression.

11 fromNfa - Create a DFA parser from an NFA.

12 newDFA - Create a new DFA.

13 newState - Create a new DFA state with the specified options.

14 oneOrMore - One or more repetitions of a sequence of elements.

15 optional - An optional sequence of element.

16 parseDtdElement - Convert the Dtd Element definition in $stringto a DFA,

17 parser - Create a parser from a $dfa constructed from a regular expression.

18 print - Print the specified $dfa using the specified $title.

19 printAsExpr - Print a $dfa as an expression.

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

21 printAsRe - Print a $dfa as a regular expression.

22 printFinal - Print a final state

23 removeDuplicatedStates - Remove duplicated states in a $dfa.

24 removeUnreachableStates - Remove unreachable states in a $dfa.

25 renumberDfa - Renumber the states in the specified $dfa.

26 sequence - Sequence of elements.

27 superState - Create super states from existing superstate.

28 superStates - Create super states from existing superstate.

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

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

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

Installation

This module is written in 100% Pure Perl and, thus, it is easy to read, comprehend, use, modify and install via cpan:

  sudo cpan install Data::DFA

Author

philiprbrenan@gmail.com

http://www.appaapps.com

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.