Name

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

Synopsis

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

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

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

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

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

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

# Print the symbols used and the transitions table:

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

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

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

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

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

  say STDERR $@;                                                                # Error message
#   Already processed: a b
#   Expected one of  : b c d e
#   But was given    : a

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

Description

Deterministic finite state parser from regular expression

Version "20190329".

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

Construct regular expression

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

element($)

One element.

     Parameter  Description
  1  $label     Transition 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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

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

  Data::DFA::element

sequence(@)

Sequence of elements.

     Parameter  Description
  1  @elements  Elements

Example:

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

    ok  $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a));                 # Accept symbols
    ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g));                 # Fail to accept symbols

    my $parser = $dfa->parser;
    $parser->accept(qw(a b c d e f g a b c d e f g a));
    ok $parser->final;


    ok $dfa->print(q(Test)) eq <<END if compressDfa;                              # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok $dfa->print(q(Test)) eq <<END unless compressDfa;                          # Print uncompressed DFA
  Test
      State        Final  Symbol  Target       Final
   1            0         a       1 13 9           1
   2                      b       11 13            1
   3                      c                13      1
   4  0 10 12 7 8      0  a       1 13 9           1
   5                      b       11 13            1
   6                      c                13      1
   7  1 13 9           1  b                 2      0
   8            2      0  c                 3      0
   9            3      0  d                 4      0
  10            4      0  e                 5      0
  11            5      0  f                 6      0
  12            6      0  g       0 10 12 7 8      0
  END

    ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa;                # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok 1 if compressDfa;
   }

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

  Data::DFA::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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

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

  Data::DFA::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'..'g')),
      except('d'..'g')
     );

    ok  $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a));                 # Accept symbols
    ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g));                 # Fail to accept symbols

    my $parser = $dfa->parser;
    $parser->accept(qw(a b c d e f g a b c d e f g a));
    ok $parser->final;


    ok $dfa->print(q(Test)) eq <<END if compressDfa;                              # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok $dfa->print(q(Test)) eq <<END unless compressDfa;                          # Print uncompressed DFA
  Test
      State        Final  Symbol  Target       Final
   1            0         a       1 13 9           1
   2                      b       11 13            1
   3                      c                13      1
   4  0 10 12 7 8      0  a       1 13 9           1
   5                      b       11 13            1
   6                      c                13      1
   7  1 13 9           1  b                 2      0
   8            2      0  c                 3      0
   9            3      0  d                 4      0
  10            4      0  e                 5      0
  11            5      0  f                 6      0
  12            6      0  g       0 10 12 7 8      0
  END

    ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa;                # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok 1 if compressDfa;
   }

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

  Data::DFA::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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

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

  Data::DFA::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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

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

  Data::DFA::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'..'g')),
      𝗲𝘅𝗰𝗲𝗽𝘁('d'..'g')
     );

    ok  $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a));                 # Accept symbols
    ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g));                 # Fail to accept symbols

    my $parser = $dfa->parser;
    $parser->accept(qw(a b c d e f g a b c d e f g a));
    ok $parser->final;


    ok $dfa->print(q(Test)) eq <<END if compressDfa;                              # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok $dfa->print(q(Test)) eq <<END unless compressDfa;                          # Print uncompressed DFA
  Test
      State        Final  Symbol  Target       Final
   1            0         a       1 13 9           1
   2                      b       11 13            1
   3                      c                13      1
   4  0 10 12 7 8      0  a       1 13 9           1
   5                      b       11 13            1
   6                      c                13      1
   7  1 13 9           1  b                 2      0
   8            2      0  c                 3      0
   9            3      0  d                 4      0
  10            4      0  e                 5      0
  11            5      0  f                 6      0
  12            6      0  g       0 10 12 7 8      0
  END

    ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa;                # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok 1 if compressDfa;
   }

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

  Data::DFA::except

fromExpr(@)

Create a DFA from a regular expression.

     Parameter  Description
  1  @expr      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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

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

  Data::DFA::fromExpr

compress($)

Compress DFA by renaming states and deleting no longer needed NFA states

     Parameter  Description
  1  $dfa       DFA

Example:

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

    ok  $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a));                 # Accept symbols
    ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g));                 # Fail to accept symbols

    my $parser = $dfa->parser;
    $parser->accept(qw(a b c d e f g a b c d e f g a));
    ok $parser->final;


    ok $dfa->print(q(Test)) eq <<END if compressDfa;                              # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok $dfa->print(q(Test)) eq <<END unless compressDfa;                          # Print uncompressed DFA
  Test
      State        Final  Symbol  Target       Final
   1            0         a       1 13 9           1
   2                      b       11 13            1
   3                      c                13      1
   4  0 10 12 7 8      0  a       1 13 9           1
   5                      b       11 13            1
   6                      c                13      1
   7  1 13 9           1  b                 2      0
   8            2      0  c                 3      0
   9            3      0  d                 4      0
  10            4      0  e                 5      0
  11            5      0  f                 6      0
  12            6      0  g       0 10 12 7 8      0
  END

    ok $dfa->𝗰𝗼𝗺𝗽𝗿𝗲𝘀𝘀->print(q(Test)) eq <<END unless compressDfa;                # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok 1 if compressDfa;
   }

print($$$)

Print DFA to a string and optionally to STDERR or STDOUT

     Parameter  Description
  1  $dfa       DFA
  2  $title     Title
  3  $print     1 - STDOUT or 2 - STDERR

Example:

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

    ok  $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a));                 # Accept symbols
    ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g));                 # Fail to accept symbols

    my $parser = $dfa->parser;
    $parser->accept(qw(a b c d e f g a b c d e f g a));
    ok $parser->final;


    ok $dfa->𝗽𝗿𝗶𝗻𝘁(q(Test)) eq <<END if compressDfa;                              # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok $dfa->𝗽𝗿𝗶𝗻𝘁(q(Test)) eq <<END unless compressDfa;                          # Print uncompressed DFA
  Test
      State        Final  Symbol  Target       Final
   1            0         a       1 13 9           1
   2                      b       11 13            1
   3                      c                13      1
   4  0 10 12 7 8      0  a       1 13 9           1
   5                      b       11 13            1
   6                      c                13      1
   7  1 13 9           1  b                 2      0
   8            2      0  c                 3      0
   9            3      0  d                 4      0
  10            4      0  e                 5      0
  11            5      0  f                 6      0
  12            6      0  g       0 10 12 7 8      0
  END

    ok $dfa->compress->𝗽𝗿𝗶𝗻𝘁(q(Test)) eq <<END unless compressDfa;                # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok 1 if compressDfa;
   }

symbols($)

Return an array of all the symbols accepted by the DFA

     Parameter  Description
  1  $dfa       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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

parser($)

Create a parser from a deterministic finite state automaton constructed from a regular expression.

     Parameter  Description
  1  $dfa       Deterministic finite state automaton generated from an 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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

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

  Data::DFA::parser

dumpAsJson($)

Create a JSON representation {transitions=>{symbol=>state}, finalStates=>{state=>1}}

     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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

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

  Data::DFA::dumpAsJson

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 automaton

Example:

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

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

    ok  $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a));                 # Accept symbols
    ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g));                 # Fail to accept symbols

    my $parser = $dfa->parser;
    $parser->accept(qw(a b c d e f g a b c d e f g a));
    ok $parser->final;


    ok $dfa->print(q(Test)) eq <<END if compressDfa;                              # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok $dfa->print(q(Test)) eq <<END unless compressDfa;                          # Print uncompressed DFA
  Test
      State        Final  Symbol  Target       Final
   1            0         a       1 13 9           1
   2                      b       11 13            1
   3                      c                13      1
   4  0 10 12 7 8      0  a       1 13 9           1
   5                      b       11 13            1
   6                      c                13      1
   7  1 13 9           1  b                 2      0
   8            2      0  c                 3      0
   9            3      0  d                 4      0
  10            4      0  e                 5      0
  11            5      0  f                 6      0
  12            6      0  g       0 10 12 7 8      0
  END

    ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa;                # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok 1 if compressDfa;
   }

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

Returns whether we are currently in a final state or not

     Parameter  Description
  1  $parser    DFA Parser

Example:

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

    ok  $dfa->parser->accepts(qw(a b c d e f g a b c d e f g a));                 # Accept symbols
    ok !$dfa->parser->accepts(qw(a b c d e f g a b c d e f g g));                 # Fail to accept symbols

    my $parser = $dfa->parser;
    $parser->accept(qw(a b c d e f g a b c d e f g a));
    ok $parser->final;


    ok $dfa->print(q(Test)) eq <<END if compressDfa;                              # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok $dfa->print(q(Test)) eq <<END unless compressDfa;                          # Print uncompressed DFA
  Test
      State        Final  Symbol  Target       Final
   1            0         a       1 13 9           1
   2                      b       11 13            1
   3                      c                13      1
   4  0 10 12 7 8      0  a       1 13 9           1
   5                      b       11 13            1
   6                      c                13      1
   7  1 13 9           1  b                 2      0
   8            2      0  c                 3      0
   9            3      0  d                 4      0
  10            4      0  e                 5      0
  11            5      0  f                 6      0
  12            6      0  g       0 10 12 7 8      0
  END

    ok $dfa->compress->print(q(Test)) eq <<END unless compressDfa;                # Print compressed DFA
  Test
      State  Final  Symbol  Target  Final
   1      0         a            2      1
   2                b            3      1
   3                c            4      1
   4      1      0  a            2      1
   5                b            3      1
   6                c            4      1
   7      2      1  b            5      0
   8      5      0  c            6      0
   9      6      0  d            7      0
  10      7      0  e            8      0
  11      8      0  f            9      0
  12      9      0  g            1      0
  END

    ok 1 if compressDfa;
   }

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

Returns an array of symbols that would be accepted in the current state

     Parameter  Description
  1  $parser    DFA Parser

Example:

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

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

Confirm that a DFA accepts an array representing a sequence of symbols

     Parameter  Description
  1  $parser    DFA Parser
  2  @symbols   Array of 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 if compressDfa;               # Print compressed DFA
  Dfa for a(b|c)+d?e :
      State  Final  Symbol  Target  Final
   1      0         a            2      0
   2      1      0  b            1      0
   3                c            3      0
   4                d            4      0
   5                e            5      1
   6      2      0  b            1      0
   7                c            3      0
   8      3      0  b            1      0
   9                c            3      0
  10                d            4      0
  11                e            5      1
  12      4      0  e            5      1
  END

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

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

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

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

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

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

    ok dumpAsJson($dfa) eq <<END unless compressDfa;                              # Dump as json
  {
     "finalStates" : {
        "0" : 0,
        "1 2 3 4 5 6" : 0,
        "1 3" : 0,
        "1 3 4 5 6" : 0,
        "6" : 0,
        "7" : 1
     },
     "transitions" : {
        "0" : {
           "a" : "1 3"
        },
        "1 2 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "1 3" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6"
        },
        "1 3 4 5 6" : {
           "b" : "1 2 3 4 5 6",
           "c" : "1 3 4 5 6",
           "d" : "6",
           "e" : "7"
        },
        "6" : {
           "e" : "7"
        }
     }
  }
  END
   }

Private Methods

finalState($$)

Check whether any of the specified states in the NFA are final

     Parameter  Description
  1  $nfa       NFA
  2  $reach     Hash of states in the 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

Index

1 choice - Choice from amongst one or more elements.

2 compress - Compress DFA by renaming states and deleting no longer needed NFA states

3 Data::DFA::Parser::accept - Accept the next symbol drawn from the symbol set if possible by moving to a new state otherwise confessing with a helpful message

4 Data::DFA::Parser::accepts - Confirm that a DFA accepts an array representing a sequence of symbols

5 Data::DFA::Parser::final - Returns whether we are currently in a final state or not

6 Data::DFA::Parser::next - Returns an array of symbols that would be accepted in the current state

7 dumpAsJson - Create a JSON representation {transitions=>{symbol=>state}, finalStates=>{state=>1}}

8 element - One element.

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

10 finalState - Check whether any of the specified states in the NFA are final

11 fromExpr - Create a DFA from a regular expression.

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

13 optional - An optional sequence of element.

14 parser - Create a parser from a deterministic finite state automaton constructed from a regular expression.

15 print - Print DFA to a string and optionally to STDERR or STDOUT

16 sequence - Sequence of elements.

17 superState - Create super states from existing superstate

18 superStates - Create super states from existing superstate

19 symbols - Return an array of all the symbols accepted by the DFA

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

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

Installation

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

  sudo cpan install Data::DFA

Author

philiprbrenan@gmail.com

http://www.appaapps.com

Copyright

Copyright (c) 2016-2018 Philip R Brenan.

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