| 1 | #!/usr/bin/perl | ||||||||||||||||||||||||||||||||||
| 2 | #------------------------------------------------------------------------------- | ||||||||||||||||||||||||||||||||||
| 3 | # Non deterministic finite state machine from regular expression. | ||||||||||||||||||||||||||||||||||
| 4 | # Philip R Brenan at gmail dot com, Appa Apps Ltd Inc., 2018 | ||||||||||||||||||||||||||||||||||
| 5 | #------------------------------------------------------------------------------- | ||||||||||||||||||||||||||||||||||
| 6 | # podDocumentation | ||||||||||||||||||||||||||||||||||
| 7 | package Data::NFA; | ||||||||||||||||||||||||||||||||||
| 8 | 1 | our $VERSION = 20201031; | |||||||||||||||||||||||||||||||||
| 9 | 1 | require v5.26; | |||||||||||||||||||||||||||||||||
| 10 | 1 | ▶ | use warnings FATAL => qw(all); | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 11 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 12 | 1 | ▶ | use Carp qw(confess); | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 13 | 1 | ▶ | use Data::Dump qw(dump); | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 14 | 1 | ▶ | use Data::Table::Text qw(:all); | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 15 | 1 | ▶ | use utf8; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 16 | |||||||||||||||||||||||||||||||||||
| 17 | # NFA : bless {state=>{symbol=>state}, jumps=>{state=>1}, final=>defined if final, return=>state to return to} | ||||||||||||||||||||||||||||||||||
| 18 | # Jumps are instead of a transition not after a transition | ||||||||||||||||||||||||||||||||||
| 19 | |||||||||||||||||||||||||||||||||||
| 20 | 1 | my $logFile = q(/home/phil/z/z/z/zzz.txt); # Log printed results if developing | |||||||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||||||||
| 22 | 101 | ▶ | sub Element {q(element)} # Element of a regular expression. | ||||||||||||||||||||||||||||||||
|
Subroutine
Element: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||||||||
| 23 | 43 | ▶ | sub Sequence {q(sequence)} # Sequence of regular expressions. | ||||||||||||||||||||||||||||||||
|
Subroutine
Sequence: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||||||||
| 24 | 37 | ▶ | sub Optional {q(optional)} # Optional regular expression. | ||||||||||||||||||||||||||||||||
|
Subroutine
Optional: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||||||||
| 25 | 41 | ▶ | sub ZeroOrMore{q(zeroOrMore)} # Zero or more instances of a regular expression. | ||||||||||||||||||||||||||||||||
|
Subroutine
ZeroOrMore: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||||||||
| 26 | 24 | ▶ | sub OneOrMore {q(oneOrMore)} # One or more instances of a regular expression. | ||||||||||||||||||||||||||||||||
|
Subroutine
OneOrMore: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||||||||
| 27 | 35 | ▶ | sub Choice {q(choice)} # Choice between regular expressions. | ||||||||||||||||||||||||||||||||
|
Subroutine
Choice: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||||||||
| 28 | 4 | ▶ | sub Except {q(except)} # Choice between any symbols mentioned so far minus the ones listed. | ||||||||||||||||||||||||||||||||
|
Subroutine
Except: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||||||||
| 30 | #D1 Construct regular expression # Construct a regular expression that defines the language to be parsed using the following combining operations which can all be imported: | ||||||||||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||||||||
| 32 | sub element($) #S One element. An element can also be represented by a string or number | ||||||||||||||||||||||||||||||||||
| 33 | 7 | ▶ | {my ($label) = @_; # Transition symbol | ||||||||||||||||||||||||||||||||
|
Subroutine
element: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 34 | 7 | [Element, @_] | |||||||||||||||||||||||||||||||||
| 35 | } | ||||||||||||||||||||||||||||||||||
| 36 | |||||||||||||||||||||||||||||||||||
| 37 | sub sequence(@) #S Sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 38 | 4 | ▶ | {my (@elements) = @_; # Elements | ||||||||||||||||||||||||||||||||
|
Subroutine
sequence: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 39 | 4 | [Sequence, @elements] | |||||||||||||||||||||||||||||||||
| 40 | } | ||||||||||||||||||||||||||||||||||
| 41 | |||||||||||||||||||||||||||||||||||
| 42 | sub optional(@) #S An optional sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 43 | 2 | ▶ | {my (@element) = @_; # Elements | ||||||||||||||||||||||||||||||||
|
Subroutine
optional: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 44 | 2 | [Optional, @element] | |||||||||||||||||||||||||||||||||
| 45 | } | ||||||||||||||||||||||||||||||||||
| 46 | |||||||||||||||||||||||||||||||||||
| 47 | sub zeroOrMore(@) #S Zero or more repetitions of a sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 48 | 8 | ▶ | {my (@element) = @_; # Elements | ||||||||||||||||||||||||||||||||
|
Subroutine
zeroOrMore: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 49 | 8 | [ZeroOrMore, @element] | |||||||||||||||||||||||||||||||||
| 50 | } | ||||||||||||||||||||||||||||||||||
| 51 | |||||||||||||||||||||||||||||||||||
| 52 | sub oneOrMore(@) #S One or more repetitions of a sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 53 | 2 | ▶ | {my (@element) = @_; # Elements | ||||||||||||||||||||||||||||||||
|
Subroutine
oneOrMore: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 54 | 2 | [OneOrMore, @element] | |||||||||||||||||||||||||||||||||
| 55 | } | ||||||||||||||||||||||||||||||||||
| 56 | |||||||||||||||||||||||||||||||||||
| 57 | sub choice(@) #S Choice from amongst one or more elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 58 | 15 | ▶ | {my (@elements) = @_; # Elements to be chosen from | ||||||||||||||||||||||||||||||||
|
Subroutine
choice: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 59 | 15 | [Choice, @elements] | |||||||||||||||||||||||||||||||||
| 60 | } | ||||||||||||||||||||||||||||||||||
| 61 | |||||||||||||||||||||||||||||||||||
| 62 | sub except(@) #S Choice from amongst all symbols except the ones mentioned | ||||||||||||||||||||||||||||||||||
| 63 | 2 | ▶ | {my (@elements) = @_; # Elements not to be chosen from | ||||||||||||||||||||||||||||||||
|
Subroutine
except: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 64 | 2 | [Except, @elements] | |||||||||||||||||||||||||||||||||
| 65 | } | ||||||||||||||||||||||||||||||||||
| 66 | |||||||||||||||||||||||||||||||||||
| 67 | #D1 Non deterministic finite state machine # Create a non deterministic finite state machine to represent a regular expression. | ||||||||||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||||||||
| 69 | sub newNfa(%) #P Create a new NFA | ||||||||||||||||||||||||||||||||||
| 70 | 0 | ▶ | {my (%options) = @_; # Options | ||||||||||||||||||||||||||||||||
|
Subroutine
newNfa: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 71 | 0 | bless {}, q(Data::NFA); | |||||||||||||||||||||||||||||||||
| 72 | } | ||||||||||||||||||||||||||||||||||
| 73 | |||||||||||||||||||||||||||||||||||
| 74 | sub newNfaState(%) #P Create a new NFA state. | ||||||||||||||||||||||||||||||||||
| 75 | 221 | ▶ | {my (%options) = @_; # Options | ||||||||||||||||||||||||||||||||
|
Subroutine
newNfaState: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 76 | |||||||||||||||||||||||||||||||||||
| 77 | 221 | my $r = genHash(q(Data::NFA::State), # NFA State | |||||||||||||||||||||||||||||||||
| 78 | transitions => undef, # {symbol => state} : transitions from this state consuming one input symbol | ||||||||||||||||||||||||||||||||||
| 79 | jumps => undef, # {to => 1} : jumps from this state not consuming any input symbols | ||||||||||||||||||||||||||||||||||
| 80 | final => undef, # Whether this state is final | ||||||||||||||||||||||||||||||||||
| 81 | ); | ||||||||||||||||||||||||||||||||||
| 82 | |||||||||||||||||||||||||||||||||||
| 83 | 221 | %$r = (%$r, %options); | |||||||||||||||||||||||||||||||||
| 84 | |||||||||||||||||||||||||||||||||||
| 85 | 221 | $r | |||||||||||||||||||||||||||||||||
| 86 | } | ||||||||||||||||||||||||||||||||||
| 87 | |||||||||||||||||||||||||||||||||||
| 88 | sub addNewState(%) #P Create a new NFA state and add it to an NFA created with L<newNfa>. | ||||||||||||||||||||||||||||||||||
| 89 | 0 | ▶ | {my ($nfa) = @_; # Nfa | ||||||||||||||||||||||||||||||||
|
Subroutine
addNewState: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 90 | 0 | my $n = keys %$nfa; | |||||||||||||||||||||||||||||||||
| 91 | 0 | $$nfa{$n} = newNfaState; | |||||||||||||||||||||||||||||||||
| 92 | } | ||||||||||||||||||||||||||||||||||
| 93 | |||||||||||||||||||||||||||||||||||
| 94 | sub fromExpr2($$$) #P Create an NFA from a regular expression. | ||||||||||||||||||||||||||||||||||
| 95 | 104 | ▶ | {my ($states, $expr, $symbols) = @_; # States, regular expression constructed from L<element|/element> L<sequence|/sequence> L<optional|/optional> L<zeroOrMore|/zeroOrMore> L<oneOrMore|/oneOrMore> L<choice|/choice>, set of symbols used by the NFA. | ||||||||||||||||||||||||||||||||
|
Subroutine
fromExpr2: called CC=23 SCAR=31.4
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 96 | 104 | ▶ | $states //= {}; | ||||||||||||||||||||||||||||||||
|
Condition50%1/2
$states //= {}
MC/DC0%0/1
$states //= {}
$states
Truth table50%1/2
A
A= $states
| |||||||||||||||||||||||||||||||||||
| 97 | 104 | ▶ | my $next = sub{scalar keys %$states}; # Next state name | ||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 98 | 0 | ▶ | my $last = sub{&$next - 1}; # Last state created | ||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=1.2
| |||||||||||||||||||||||||||||||||||
| 99 | |||||||||||||||||||||||||||||||||||
| 100 | my $save = sub # Save as a new state | ||||||||||||||||||||||||||||||||||
| 101 | 201 | ▶ | {my ($transitions, $jumps, $final) = @_; # Transitions, jumps, final | ||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 102 | 201 | my $s = $states->{&$next} = newNfaState | |||||||||||||||||||||||||||||||||
| 103 | (transitions=>$transitions, jumps=>$jumps, final=>$final); | ||||||||||||||||||||||||||||||||||
| 104 | 201 | $s; | |||||||||||||||||||||||||||||||||
| 105 | 104 | }; | |||||||||||||||||||||||||||||||||
| 106 | |||||||||||||||||||||||||||||||||||
| 107 | my $jump = sub # Add jumps | ||||||||||||||||||||||||||||||||||
| 108 | 53 | ▶ | {my ($from, @to) = @_; | ||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
| |||||||||||||||||||||||||||||||||||
| 109 | 53 | my $state = $states->{$from}; | |||||||||||||||||||||||||||||||||
| 110 | 53 | $state->jumps->{$_}++ for @to | |||||||||||||||||||||||||||||||||
| 111 | 104 | }; | |||||||||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||||||||
| 113 | 104 | my $start = &$next + 1; # Start state | |||||||||||||||||||||||||||||||||
| 114 | 104 | &$save(undef, {$start=>1}); # Offset the start of each expression by one cell to allow zeroOrMore, oneOrMore to jump back to their beginning without jumping back to the start of a containing choice | |||||||||||||||||||||||||||||||||
| 115 | |||||||||||||||||||||||||||||||||||
| 116 | 104 | ▶ | if (!ref($expr)) # Element not wrapped with element() | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 117 | 55 | {&$save({$expr=>$start+1}, undef); | |||||||||||||||||||||||||||||||||
| 118 | } | ||||||||||||||||||||||||||||||||||
| 119 | else | ||||||||||||||||||||||||||||||||||
| 120 | 49 | {my ($structure) = @$expr; | |||||||||||||||||||||||||||||||||
| 121 | 49 | ▶ | if ($structure eq Element) # Element | ||||||||||||||||||||||||||||||||
|
Branch: 7 branches
| |||||||||||||||||||||||||||||||||||
| 122 | 10 | {my (undef, $element) = @$expr; | |||||||||||||||||||||||||||||||||
| 123 | 10 | &$save({$element=>$start+1}, undef); | |||||||||||||||||||||||||||||||||
| 124 | } | ||||||||||||||||||||||||||||||||||
| 125 | elsif ($structure eq Sequence) # Sequence of elements | ||||||||||||||||||||||||||||||||||
| 126 | 4 | {my (undef, @elements) = @$expr; | |||||||||||||||||||||||||||||||||
| 127 | 4 | $states->fromExpr2($_, $symbols) for @elements; | |||||||||||||||||||||||||||||||||
| 128 | } | ||||||||||||||||||||||||||||||||||
| 129 | elsif ($structure eq Optional) # Optional element | ||||||||||||||||||||||||||||||||||
| 130 | 2 | {my (undef, @elements) = @$expr; | |||||||||||||||||||||||||||||||||
| 131 | 2 | $states->fromExpr2($_, $symbols) for @elements; | |||||||||||||||||||||||||||||||||
| 132 | 2 | &$jump($start, &$next); # Optional so we have the option of jumping over it | |||||||||||||||||||||||||||||||||
| 133 | } | ||||||||||||||||||||||||||||||||||
| 134 | elsif ($structure eq ZeroOrMore) # Zero or more | ||||||||||||||||||||||||||||||||||
| 135 | 11 | {my (undef, @elements) = @$expr; | |||||||||||||||||||||||||||||||||
| 136 | 11 | $states->fromExpr2($_, $symbols) for @elements; | |||||||||||||||||||||||||||||||||
| 137 | 11 | &$jump($start, &$next+1); # Optional so we have the option of jumping over it | |||||||||||||||||||||||||||||||||
| 138 | 11 | &$save(undef, {$start=>1}); # Repeated so we have the option of redoing it | |||||||||||||||||||||||||||||||||
| 139 | } | ||||||||||||||||||||||||||||||||||
| 140 | elsif ($structure eq OneOrMore) # One or more | ||||||||||||||||||||||||||||||||||
| 141 | 2 | {my (undef, @elements) = @$expr; | |||||||||||||||||||||||||||||||||
| 142 | 2 | $states->fromExpr2($_, $symbols) for @elements; | |||||||||||||||||||||||||||||||||
| 143 | 2 | my $N = &$next; | |||||||||||||||||||||||||||||||||
| 144 | 2 | &$save(); # Create new empty state | |||||||||||||||||||||||||||||||||
| 145 | 2 | &$jump($N, $start, $N+1); # Do it again or move on | |||||||||||||||||||||||||||||||||
| 146 | } | ||||||||||||||||||||||||||||||||||
| 147 | elsif ($structure eq Choice) # Choice | ||||||||||||||||||||||||||||||||||
| 148 | 18 | {my (undef, @elements) = @$expr; | |||||||||||||||||||||||||||||||||
| 149 | 18 | my @fix; | |||||||||||||||||||||||||||||||||
| 150 | 18 | for my $i(keys @elements) # Each element index | |||||||||||||||||||||||||||||||||
| 151 | 35 | {my $element = $elements[$i]; # Each element separate by a gap so we can not jump in then jump out | |||||||||||||||||||||||||||||||||
| 152 | 35 | ▶ | if ($i) | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 153 | 17 | {&$jump($start, &$next) | |||||||||||||||||||||||||||||||||
| 154 | } | ||||||||||||||||||||||||||||||||||
| 155 | 35 | $states->fromExpr2($element, $symbols); # Choice | |||||||||||||||||||||||||||||||||
| 156 | 35 | ▶ | if ($i < $#elements) | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 157 | 17 | {push @fix, &$next; | |||||||||||||||||||||||||||||||||
| 158 | 17 | &$save(); # Fixed later to jump over subsequent choices | |||||||||||||||||||||||||||||||||
| 159 | } | ||||||||||||||||||||||||||||||||||
| 160 | } | ||||||||||||||||||||||||||||||||||
| 161 | 18 | my $N = &$next; # Fix intermediates | |||||||||||||||||||||||||||||||||
| 162 | 18 | &$jump($_, $N) for @fix; | |||||||||||||||||||||||||||||||||
| 163 | } | ||||||||||||||||||||||||||||||||||
| 164 | elsif ($structure eq Except) # Except | ||||||||||||||||||||||||||||||||||
| 165 | 2 | {my (undef, @exclude) = @$expr; | |||||||||||||||||||||||||||||||||
| 166 | 2 | ▶ | my %exclude = map{(ref $_ ? $$_[1] : $_)=>1} @exclude; # Names of elements to exclude | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 167 | 2 | my @fix; | |||||||||||||||||||||||||||||||||
| 168 | 2 | my @elements = grep {!$exclude{$_}} | |||||||||||||||||||||||||||||||||
| 169 | sort keys %$symbols; # Each element not excluded | ||||||||||||||||||||||||||||||||||
| 170 | 2 | for my $i(keys @elements) # Each element index | |||||||||||||||||||||||||||||||||
| 171 | 4 | {my $element = $elements[$i]; # Each element separate by a gap so we can not jump in then jump out | |||||||||||||||||||||||||||||||||
| 172 | 4 | ▶ | &$jump($start, &$next) if $i; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 173 | 4 | $states->fromExpr2(element($element), $symbols); # Choice of not excluded symbols | |||||||||||||||||||||||||||||||||
| 174 | 4 | ▶ | if ($i < $#elements) | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 175 | 2 | {push @fix, &$next; | |||||||||||||||||||||||||||||||||
| 176 | 2 | &$save(); # Fixed later to jump over subsequent choices | |||||||||||||||||||||||||||||||||
| 177 | } | ||||||||||||||||||||||||||||||||||
| 178 | } | ||||||||||||||||||||||||||||||||||
| 179 | 2 | my $N = &$next; # Fix intermediates | |||||||||||||||||||||||||||||||||
| 180 | # &$save(); | ||||||||||||||||||||||||||||||||||
| 181 | 2 | &$jump($_, $N) for @fix; | |||||||||||||||||||||||||||||||||
| 182 | } | ||||||||||||||||||||||||||||||||||
| 183 | else # Unknown request | ||||||||||||||||||||||||||||||||||
| 184 | 0 | {confess "Unknown structuring operation: $structure"; | |||||||||||||||||||||||||||||||||
| 185 | } | ||||||||||||||||||||||||||||||||||
| 186 | } | ||||||||||||||||||||||||||||||||||
| 187 | 104 | $states | |||||||||||||||||||||||||||||||||
| 188 | } # fromExpr2 | ||||||||||||||||||||||||||||||||||
| 189 | |||||||||||||||||||||||||||||||||||
| 190 | sub propagateFinalState($) #P Mark the B<$states> that can reach the final state with a jump as final. | ||||||||||||||||||||||||||||||||||
| 191 | 20 | ▶ | {my ($states) = @_; # States | ||||||||||||||||||||||||||||||||
|
Subroutine
propagateFinalState: called CC=7 SCAR=19.5
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 192 | 20 | my %checked; | |||||||||||||||||||||||||||||||||
| 193 | 20 | for(;;) | |||||||||||||||||||||||||||||||||
| 194 | 29 | {my $changes = 0; | |||||||||||||||||||||||||||||||||
| 195 | 29 | for my $state(values %$states) # Each state | |||||||||||||||||||||||||||||||||
| 196 | 349 | ▶ | {if (!defined $state->final) # Current state is not a final state | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 197 | 282 | ▶ | {if (defined $state->jumps) | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 198 | 282 | {for my $jumpName(sort keys $state->jumps->%*) # Each jump | |||||||||||||||||||||||||||||||||
| 199 | 533 | {my $jump = $$states{$jumpName}; | |||||||||||||||||||||||||||||||||
| 200 | 533 | ▶ | if (defined(my $final = $jump->final)) # Target state is final | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 201 | 38 | {++$changes; | |||||||||||||||||||||||||||||||||
| 202 | 38 | $state->final = $final; # Mark state as final | |||||||||||||||||||||||||||||||||
| 203 | 38 | last; | |||||||||||||||||||||||||||||||||
| 204 | } | ||||||||||||||||||||||||||||||||||
| 205 | } | ||||||||||||||||||||||||||||||||||
| 206 | } | ||||||||||||||||||||||||||||||||||
| 207 | } | ||||||||||||||||||||||||||||||||||
| 208 | } | ||||||||||||||||||||||||||||||||||
| 209 | 29 | ▶ | last unless $changes; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 210 | } | ||||||||||||||||||||||||||||||||||
| 211 | } # propagateFinalState | ||||||||||||||||||||||||||||||||||
| 212 | |||||||||||||||||||||||||||||||||||
| 213 | sub statesReachableViaJumps($$) #P Find the names of all the B<$states> that can be reached from a specified B<$stateName> via jumps alone. | ||||||||||||||||||||||||||||||||||
| 214 | 401 | ▶ | {my ($states, $StateName) = @_; # States, name of start state | ||||||||||||||||||||||||||||||||
|
Subroutine
statesReachableViaJumps: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 215 | 401 | my %reachable; | |||||||||||||||||||||||||||||||||
| 216 | 401 | my @check = ($StateName); | |||||||||||||||||||||||||||||||||
| 217 | 401 | my %checked; | |||||||||||||||||||||||||||||||||
| 218 | |||||||||||||||||||||||||||||||||||
| 219 | 401 | ▶ | while(@check) # Reachable from the start state by a single transition after zero or more jumps | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 220 | 2571 | {my $stateName = pop @check; | |||||||||||||||||||||||||||||||||
| 221 | 2571 | ▶ | next if $checked{$stateName}++; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 222 | 1587 | ▶ | confess "No such state: $stateName" unless my $state = $$states{$stateName}; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 223 | 1587 | for my $s(sort keys $state->jumps->%*) # States that can be reached via jumps | |||||||||||||||||||||||||||||||||
| 224 | 2170 | {$reachable{$s}++; # New state to check | |||||||||||||||||||||||||||||||||
| 225 | 2170 | push @check, $s; | |||||||||||||||||||||||||||||||||
| 226 | } | ||||||||||||||||||||||||||||||||||
| 227 | } | ||||||||||||||||||||||||||||||||||
| 228 | |||||||||||||||||||||||||||||||||||
| 229 | 401 | [sort keys %reachable] | |||||||||||||||||||||||||||||||||
| 230 | } # statesReachableViaJumps | ||||||||||||||||||||||||||||||||||
| 231 | |||||||||||||||||||||||||||||||||||
| 232 | sub removeEmptyFields($) #P Remove empty fields from the B<states> representing an NFA. | ||||||||||||||||||||||||||||||||||
| 233 | 20 | ▶ | {my ($states) = @_; # States | ||||||||||||||||||||||||||||||||
|
Subroutine
removeEmptyFields: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 234 | 20 | for my $state(values %$states) # Remove empty fields | |||||||||||||||||||||||||||||||||
| 235 | 221 | {for(qw(jumps transitions)) | |||||||||||||||||||||||||||||||||
| 236 | 442 | ▶ | {delete $$state{$_} unless keys $$state{$_}->%*; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 237 | } | ||||||||||||||||||||||||||||||||||
| 238 | 221 | ▶ | delete $$state{final} unless defined $$state{final}; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 239 | } | ||||||||||||||||||||||||||||||||||
| 240 | } # removeEmptyFields | ||||||||||||||||||||||||||||||||||
| 241 | |||||||||||||||||||||||||||||||||||
| 242 | sub fromExpr(@) #S Create an NFA from a regular B<@expression>. | ||||||||||||||||||||||||||||||||||
| 243 | 20 | ▶ | {my (@expression) = @_; # Regular expressions | ||||||||||||||||||||||||||||||||
|
Subroutine
fromExpr: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 244 | 20 | my $states = bless {}; | |||||||||||||||||||||||||||||||||
| 245 | 20 | my %symbols; # Symbols named in expression | |||||||||||||||||||||||||||||||||
| 246 | my $symbols; $symbols = sub # Locate symbols | ||||||||||||||||||||||||||||||||||
| 247 | 62 | ▶ | {my ($expr) = @_; | ||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=5 SCAR=16.1
| |||||||||||||||||||||||||||||||||||
| 248 | 62 | ▶ | if (ref $expr) | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 249 | 45 | ▶ | {$symbols{$$expr[1]}++ if $$expr[0] eq Element; # Add symbol enclosed in element | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 250 | 45 | my ($type, @elements) = @$expr; | |||||||||||||||||||||||||||||||||
| 251 | 45 | for(@elements) | |||||||||||||||||||||||||||||||||
| 252 | 68 | ▶ | {ref $_ ? $symbols->($_) : $symbols{$_}++; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 253 | } | ||||||||||||||||||||||||||||||||||
| 254 | } | ||||||||||||||||||||||||||||||||||
| 255 | else # Process sub expressions | ||||||||||||||||||||||||||||||||||
| 256 | 17 | {$symbols{$expr}++; # Add symbol not enclosed in element() | |||||||||||||||||||||||||||||||||
| 257 | } | ||||||||||||||||||||||||||||||||||
| 258 | 20 | }; | |||||||||||||||||||||||||||||||||
| 259 | 20 | $symbols->($_) for @expression; # Locate all symbols | |||||||||||||||||||||||||||||||||
| 260 | |||||||||||||||||||||||||||||||||||
| 261 | 20 | $states->fromExpr2($_, \%symbols) for @expression; # Create state transitions | |||||||||||||||||||||||||||||||||
| 262 | 20 | $states->{keys %$states} = newNfaState(final=>1); # End state | |||||||||||||||||||||||||||||||||
| 263 | |||||||||||||||||||||||||||||||||||
| 264 | 20 | for my $state(sort keys %$states) # Collapse multiple jumps | |||||||||||||||||||||||||||||||||
| 265 | {$$states{$state}->jumps = | ||||||||||||||||||||||||||||||||||
| 266 | 221 | {map {$_=>1} @{statesReachableViaJumps($states, $state)}}; | |||||||||||||||||||||||||||||||||
| 267 | } | ||||||||||||||||||||||||||||||||||
| 268 | |||||||||||||||||||||||||||||||||||
| 269 | 20 | $states->propagateFinalState; # Propagate final states | |||||||||||||||||||||||||||||||||
| 270 | |||||||||||||||||||||||||||||||||||
| 271 | 20 | $states->removeEmptyFields; # Remove any empty fields | |||||||||||||||||||||||||||||||||
| 272 | |||||||||||||||||||||||||||||||||||
| 273 | 20 | $states | |||||||||||||||||||||||||||||||||
| 274 | } # fromExpr | ||||||||||||||||||||||||||||||||||
| 275 | |||||||||||||||||||||||||||||||||||
| 276 | sub printFinalState($) #P Print the final field of the specified B<$state>. | ||||||||||||||||||||||||||||||||||
| 277 | 233 | ▶ | {my ($state) = @_; # State | ||||||||||||||||||||||||||||||||
|
Subroutine
printFinalState: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 278 | 233 | ▶ | defined($state->final) ? 1 : q(); | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 279 | } | ||||||||||||||||||||||||||||||||||
| 280 | |||||||||||||||||||||||||||||||||||
| 281 | sub printWithJumps($;$) #P Print the current B<$states> of an NFA with jumps using the specvified B<$title>. | ||||||||||||||||||||||||||||||||||
| 282 | 21 | ▶ | {my ($states, $title) = @_; # States, optional title | ||||||||||||||||||||||||||||||||
|
Subroutine
printWithJumps: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 283 | 21 | my @o; | |||||||||||||||||||||||||||||||||
| 284 | 21 | push @o, [qw(Location F Transitions Jumps)]; | |||||||||||||||||||||||||||||||||
| 285 | 21 | for(sort{$a <=> $b} keys %$states) | |||||||||||||||||||||||||||||||||
| 286 | 233 | {my $d = $states->{$_}; | |||||||||||||||||||||||||||||||||
| 287 | 233 | my @j = sort {$a <=> $b} keys %{$d->jumps}; | |||||||||||||||||||||||||||||||||
| 288 | 233 | my $f = printFinalState($d); | |||||||||||||||||||||||||||||||||
| 289 | 233 | ▶ | push @o, [sprintf("%4d", $_), $f, | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 290 | dump($d->transitions), | ||||||||||||||||||||||||||||||||||
| 291 | dump(@j ? [@j] : undef)]; | ||||||||||||||||||||||||||||||||||
| 292 | } | ||||||||||||||||||||||||||||||||||
| 293 | 21 | my $t = formatTableBasic([@o]); | |||||||||||||||||||||||||||||||||
| 294 | 21 | ▶ | $title ? "$title\n$t" : $t | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 295 | } | ||||||||||||||||||||||||||||||||||
| 296 | |||||||||||||||||||||||||||||||||||
| 297 | sub printWithOutJumps($$) #P Print the current B<$states> of an NFA without jumps using the specified B<$title>. | ||||||||||||||||||||||||||||||||||
| 298 | 0 | ▶ | {my ($states, $title) = @_; # States, title. | ||||||||||||||||||||||||||||||||
|
Subroutine
printWithOutJumps: not called CC=2 SCAR=17.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 299 | 0 | my @o; | |||||||||||||||||||||||||||||||||
| 300 | 0 | push @o, [qw(Location F Transitions)]; | |||||||||||||||||||||||||||||||||
| 301 | 0 | for(sort{$a <=> $b} keys %$states) | |||||||||||||||||||||||||||||||||
| 302 | 0 | {my $d = $states->{$_}; | |||||||||||||||||||||||||||||||||
| 303 | 0 | my $f = printFinalState($d); | |||||||||||||||||||||||||||||||||
| 304 | 0 | push @o, [sprintf("%4d", $_), $f, | |||||||||||||||||||||||||||||||||
| 305 | dump($d->transitions)]; | ||||||||||||||||||||||||||||||||||
| 306 | } | ||||||||||||||||||||||||||||||||||
| 307 | 0 | "$title\n". formatTableBasic([@o]); | |||||||||||||||||||||||||||||||||
| 308 | } | ||||||||||||||||||||||||||||||||||
| 309 | |||||||||||||||||||||||||||||||||||
| 310 | sub print($$) # Print the current B<$states> of the non deterministic finite state automaton using the specified B<$title>. If it is non deterministic, the non deterministic jumps will be shown as well as the transitions table. If deterministic, only the transitions table will be shown. | ||||||||||||||||||||||||||||||||||
| 311 | 21 | ▶ | {my ($states, $title) = @_; # States, title | ||||||||||||||||||||||||||||||||
|
Subroutine
print: called CC=5 SCAR=16.2
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 312 | 21 | my $j = 0; # Number of non deterministic jumps encountered | |||||||||||||||||||||||||||||||||
| 313 | 21 | for(sort{$a <=> $b} keys %$states) | |||||||||||||||||||||||||||||||||
| 314 | 233 | {my $d = $states->{$_}; | |||||||||||||||||||||||||||||||||
| 315 | 233 | my @j = sort keys %{$d->jumps}; | |||||||||||||||||||||||||||||||||
| 316 | 233 | ▶ | ++$j if @j > 0; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 317 | } | ||||||||||||||||||||||||||||||||||
| 318 | |||||||||||||||||||||||||||||||||||
| 319 | 21 | ▶ | my $r = $j ? &printWithJumps(@_) : &printWithOutJumps(@_); # Print | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 320 | |||||||||||||||||||||||||||||||||||
| 321 | 21 | ▶ | owf($logFile, $r) if -e $logFile; # Log the result if requested | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 322 | 21 | $r # Return the result | |||||||||||||||||||||||||||||||||
| 323 | } | ||||||||||||||||||||||||||||||||||
| 324 | |||||||||||||||||||||||||||||||||||
| 325 | sub symbols($) # Return an array of all the transition symbols. | ||||||||||||||||||||||||||||||||||
| 326 | 2 | ▶ | {my ($states) = @_; # States | ||||||||||||||||||||||||||||||||
|
Subroutine
symbols: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 327 | 2 | my %s; | |||||||||||||||||||||||||||||||||
| 328 | 2 | for my $d(values %$states) | |||||||||||||||||||||||||||||||||
| 329 | 28 | ▶ | {if ($d->transitions) | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 330 | 7 | {$s{$_}++ for sort keys $d->transitions->%*; | |||||||||||||||||||||||||||||||||
| 331 | } | ||||||||||||||||||||||||||||||||||
| 332 | } | ||||||||||||||||||||||||||||||||||
| 333 | 2 | sort keys %s | |||||||||||||||||||||||||||||||||
| 334 | } | ||||||||||||||||||||||||||||||||||
| 335 | |||||||||||||||||||||||||||||||||||
| 336 | sub isFinal($$) # Whether, in the B<$states> specifying an NFA the named state B<$state> is a final state. | ||||||||||||||||||||||||||||||||||
| 337 | 2 | ▶ | {my ($states, $state) = @_; # States, name of state to test | ||||||||||||||||||||||||||||||||
|
Subroutine
isFinal: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 338 | 2 | my $f = $$states{$state}->final; | |||||||||||||||||||||||||||||||||
| 339 | 2 | ▶ | my $F = defined($f) ? $f : undef; # Defined yields "" for false which is not what we want | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 340 | 2 | $F | |||||||||||||||||||||||||||||||||
| 341 | } | ||||||||||||||||||||||||||||||||||
| 342 | |||||||||||||||||||||||||||||||||||
| 343 | sub statesReachableViaSymbol($$$$) #P Find the names of all the states that can be reached from a specified state via a specified symbol and all the jumps available. | ||||||||||||||||||||||||||||||||||
| 344 | 457 | ▶ | {my ($states, $StateName, $symbol, $cache) = @_; # States, name of start state, symbol to reach on, a hash to be used as a cache | ||||||||||||||||||||||||||||||||
|
Subroutine
statesReachableViaSymbol: called CC=8 SCAR=20.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 345 | 457 | my %reachable; | |||||||||||||||||||||||||||||||||
| 346 | 457 | my @check = ($StateName); | |||||||||||||||||||||||||||||||||
| 347 | 457 | my %checked; | |||||||||||||||||||||||||||||||||
| 348 | |||||||||||||||||||||||||||||||||||
| 349 | 457 | ▶ | while(@check) # Reachable from the start state by a single transition after zero or more jumps | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 350 | 2241 | {my $stateName = pop @check; | |||||||||||||||||||||||||||||||||
| 351 | 2241 | ▶ | next if $checked{$stateName}++; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 352 | 1367 | ▶ | confess "No such state: $stateName" unless my $state = $$states{$stateName}; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 353 | |||||||||||||||||||||||||||||||||||
| 354 | 1367 | ▶ | if ($state->transitions) | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 355 | 575 | ▶ | {if (my $t = $state->transitions->{$symbol}) # Transition on the symbol | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 356 | 178 | {$reachable{$t}++; | |||||||||||||||||||||||||||||||||
| 357 | $reachable{$_}++ | ||||||||||||||||||||||||||||||||||
| 358 | 178 | ▶ | for @{$$cache{$t} //= statesReachableViaJumps($states, $t)}; # Cache results of this expensive call | ||||||||||||||||||||||||||||||||
|
Condition33%1/3
$cache->{$t} //= &statesReachableViaJumps($states, $t)
MC/DC0%0/2
$cache->{$t} //= &statesReachableViaJumps($states, $t)
$cache->{$t}
&statesReachableViaJumps($states, $t)
Truth table33%1/3
A //= B
A= $cache->{$t}B= &statesReachableViaJumps($states, $t)
| |||||||||||||||||||||||||||||||||||
| 359 | } | ||||||||||||||||||||||||||||||||||
| 360 | } | ||||||||||||||||||||||||||||||||||
| 361 | 1367 | push @check, sort keys $state->jumps->%*; # Make a jump and try again | |||||||||||||||||||||||||||||||||
| 362 | } | ||||||||||||||||||||||||||||||||||
| 363 | |||||||||||||||||||||||||||||||||||
| 364 | 457 | [sort keys %reachable] | |||||||||||||||||||||||||||||||||
| 365 | } # statesReachableViaSymbol | ||||||||||||||||||||||||||||||||||
| 366 | |||||||||||||||||||||||||||||||||||
| 367 | sub allTransitions($) # Return all transitions in the NFA specified by B<$states> as {stateName}{symbol} = [reachable states]. | ||||||||||||||||||||||||||||||||||
| 368 | 1 | ▶ | {my ($states) = @_; # States | ||||||||||||||||||||||||||||||||
|
Subroutine
allTransitions: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 369 | 1 | my $symbols = [$states->symbols]; # Symbols in nfa | |||||||||||||||||||||||||||||||||
| 370 | 1 | my $cache = {}; # Cache results | |||||||||||||||||||||||||||||||||
| 371 | |||||||||||||||||||||||||||||||||||
| 372 | 1 | my $nfaSymbolTransitions; | |||||||||||||||||||||||||||||||||
| 373 | 1 | for my $StateName(sort keys %$states) # Each NFA state | |||||||||||||||||||||||||||||||||
| 374 | 12 | {my $target = $$nfaSymbolTransitions{$StateName} = {}; | |||||||||||||||||||||||||||||||||
| 375 | 12 | for my $symbol(@$symbols) # Each NFA symbol | |||||||||||||||||||||||||||||||||
| 376 | {my $statesReachableViaSymbol = sub #P Find the names of all the states that can be reached from a specified state via a specified symbol and all the jumps available. | ||||||||||||||||||||||||||||||||||
| 377 | 12 | ▶ | {my %reachable; | ||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=8 SCAR=20.9
| |||||||||||||||||||||||||||||||||||
| 378 | 12 | my @check = ($StateName); | |||||||||||||||||||||||||||||||||
| 379 | 12 | my %checked; | |||||||||||||||||||||||||||||||||
| 380 | |||||||||||||||||||||||||||||||||||
| 381 | 12 | ▶ | while(@check) # Reachable from the start state by a single transition after zero or more jumps | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 382 | 131 | {my $stateName = pop @check; | |||||||||||||||||||||||||||||||||
| 383 | 131 | ▶ | next if $checked{$stateName}++; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 384 | 57 | my $state = $$states{$stateName}; | |||||||||||||||||||||||||||||||||
| 385 | 57 | ▶ | confess "No such state: $stateName" unless $state; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 386 | 57 | my $transitions = $state->transitions; | |||||||||||||||||||||||||||||||||
| 387 | |||||||||||||||||||||||||||||||||||
| 388 | 57 | ▶ | if (defined(my $to = $$transitions{$symbol})) # Transition on the symbol | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 389 | 15 | {$reachable{$to}++; | |||||||||||||||||||||||||||||||||
| 390 | $reachable{$_}++ | ||||||||||||||||||||||||||||||||||
| 391 | 15 | ▶ | for @{$$cache{$to} //= statesReachableViaJumps($states, $to)}; # Cache results of this expensive call | ||||||||||||||||||||||||||||||||
|
Condition66%2/3
$cache->{$to} //= &statesReachableViaJumps($states, $to)
MC/DC0%0/2
$cache->{$to} //= &statesReachableViaJumps($states, $to)
$cache->{$to}
&statesReachableViaJumps($states, $to)
Truth table66%2/3
A //= B
A= $cache->{$to}B= &statesReachableViaJumps($states, $to)
| |||||||||||||||||||||||||||||||||||
| 392 | } | ||||||||||||||||||||||||||||||||||
| 393 | 57 | ▶ | if (my $jumps = $state->jumps) | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 394 | 57 | {push @check, sort keys %$jumps; # Make a jump and try again | |||||||||||||||||||||||||||||||||
| 395 | } | ||||||||||||||||||||||||||||||||||
| 396 | } | ||||||||||||||||||||||||||||||||||
| 397 | |||||||||||||||||||||||||||||||||||
| 398 | 12 | [sort keys %reachable] # List of reachable states | |||||||||||||||||||||||||||||||||
| 399 | 12 | }; # statesReachableViaSymbol | |||||||||||||||||||||||||||||||||
| 400 | |||||||||||||||||||||||||||||||||||
| 401 | 12 | $$target{$symbol} = &$statesReachableViaSymbol; # States in the NFA reachable on the symbol | |||||||||||||||||||||||||||||||||
| 402 | } | ||||||||||||||||||||||||||||||||||
| 403 | } | ||||||||||||||||||||||||||||||||||
| 404 | |||||||||||||||||||||||||||||||||||
| 405 | $nfaSymbolTransitions | ||||||||||||||||||||||||||||||||||
| 406 | 1 | } # allTransitions | |||||||||||||||||||||||||||||||||
| 407 | |||||||||||||||||||||||||||||||||||
| 408 | sub parse2($$@) #P Parse an array of symbols | ||||||||||||||||||||||||||||||||||
| 409 | 561 | ▶ | {my ($states, $stateName, @symbols) = @_; # States, current state, remaining symbols | ||||||||||||||||||||||||||||||||
|
Subroutine
parse2: called CC=6 SCAR=17.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 410 | |||||||||||||||||||||||||||||||||||
| 411 | 561 | ▶ | if (defined(my $final = $$states{$stateName}->final)) # Return success if we are in a final state with no more symbols to parse | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 412 | 120 | ▶ | {return 1 unless @symbols; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 413 | } | ||||||||||||||||||||||||||||||||||
| 414 | |||||||||||||||||||||||||||||||||||
| 415 | 521 | ▶ | return 0 unless @symbols; # No more symbols but not in a final state | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 416 | |||||||||||||||||||||||||||||||||||
| 417 | 457 | my ($symbol, @remainder) = @symbols; # Current symbol to parse | |||||||||||||||||||||||||||||||||
| 418 | 457 | my $reachable = statesReachableViaSymbol($states, $stateName, $symbol, {}); # States reachable from the current state via the current symbol | |||||||||||||||||||||||||||||||||
| 419 | |||||||||||||||||||||||||||||||||||
| 420 | 457 | for my $nextState(@$reachable) # Each state reachable from the current state | |||||||||||||||||||||||||||||||||
| 421 | 464 | {my $result = &parse2($states, $nextState, @remainder); # Try each reachable state | |||||||||||||||||||||||||||||||||
| 422 | 464 | ▶ | return $result if $result; # Propagate success if a solution was found | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 423 | } | ||||||||||||||||||||||||||||||||||
| 424 | |||||||||||||||||||||||||||||||||||
| 425 | undef # No path to a final state found | ||||||||||||||||||||||||||||||||||
| 426 | 368 | } | |||||||||||||||||||||||||||||||||
| 427 | |||||||||||||||||||||||||||||||||||
| 428 | sub parse($@) # Parse, using the NFA specified by B<$states>, the list of symbols in L<@symbols>. | ||||||||||||||||||||||||||||||||||
| 429 | 97 | ▶ | {my ($states, @symbols) = @_; # States, array of symbols | ||||||||||||||||||||||||||||||||
|
Subroutine
parse: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 430 | |||||||||||||||||||||||||||||||||||
| 431 | 97 | parse2($states, 0, @symbols); | |||||||||||||||||||||||||||||||||
| 432 | } | ||||||||||||||||||||||||||||||||||
| 433 | |||||||||||||||||||||||||||||||||||
| 434 | #D0 | ||||||||||||||||||||||||||||||||||
| 435 | #------------------------------------------------------------------------------- | ||||||||||||||||||||||||||||||||||
| 436 | # Export | ||||||||||||||||||||||||||||||||||
| 437 | #------------------------------------------------------------------------------- | ||||||||||||||||||||||||||||||||||
| 438 | |||||||||||||||||||||||||||||||||||
| 439 | 1 | ▶ | use Exporter qw(import); | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 440 | |||||||||||||||||||||||||||||||||||
| 441 | 1 | ▶ | use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS); | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 442 | |||||||||||||||||||||||||||||||||||
| 443 | 1 | @ISA = qw(Exporter); | |||||||||||||||||||||||||||||||||
| 444 | 1 | @EXPORT_OK = qw( | |||||||||||||||||||||||||||||||||
| 445 | choice | ||||||||||||||||||||||||||||||||||
| 446 | element | ||||||||||||||||||||||||||||||||||
| 447 | except | ||||||||||||||||||||||||||||||||||
| 448 | oneOrMore optional | ||||||||||||||||||||||||||||||||||
| 449 | sequence | ||||||||||||||||||||||||||||||||||
| 450 | zeroOrMore | ||||||||||||||||||||||||||||||||||
| 451 | ); | ||||||||||||||||||||||||||||||||||
| 452 | 1 | %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]); | |||||||||||||||||||||||||||||||||
| 453 | |||||||||||||||||||||||||||||||||||
| 454 | # podDocumentation | ||||||||||||||||||||||||||||||||||
| 455 | |||||||||||||||||||||||||||||||||||
| 456 | =pod | ||||||||||||||||||||||||||||||||||
| 457 | |||||||||||||||||||||||||||||||||||
| 458 | =encoding utf-8 | ||||||||||||||||||||||||||||||||||
| 459 | |||||||||||||||||||||||||||||||||||
| 460 | =head1 Name | ||||||||||||||||||||||||||||||||||
| 461 | |||||||||||||||||||||||||||||||||||
| 462 | Data::NFA - Non deterministic finite state machine from regular expression. | ||||||||||||||||||||||||||||||||||
| 463 | |||||||||||||||||||||||||||||||||||
| 464 | =head1 Synopsis | ||||||||||||||||||||||||||||||||||
| 465 | |||||||||||||||||||||||||||||||||||
| 466 | Create a non deterministic finite state machine from a regular expression which | ||||||||||||||||||||||||||||||||||
| 467 | can then be converted into a deterministic finite state machine by L<Data::DFA> | ||||||||||||||||||||||||||||||||||
| 468 | and used to parse sequences of symbols. | ||||||||||||||||||||||||||||||||||
| 469 | |||||||||||||||||||||||||||||||||||
| 470 | For example, the regular expression: | ||||||||||||||||||||||||||||||||||
| 471 | |||||||||||||||||||||||||||||||||||
| 472 | ((a|b)*)**4 | ||||||||||||||||||||||||||||||||||
| 473 | |||||||||||||||||||||||||||||||||||
| 474 | produces the following machine: | ||||||||||||||||||||||||||||||||||
| 475 | |||||||||||||||||||||||||||||||||||
| 476 | use Data::NFA qw(:all); | ||||||||||||||||||||||||||||||||||
| 477 | use Data::Table::Text qw(:all); | ||||||||||||||||||||||||||||||||||
| 478 | use Test::More qw(no_plan); | ||||||||||||||||||||||||||||||||||
| 479 | |||||||||||||||||||||||||||||||||||
| 480 | my $N = 4; | ||||||||||||||||||||||||||||||||||
| 481 | |||||||||||||||||||||||||||||||||||
| 482 | my $s = q(zeroOrMore(choice(element("a"), element("b")))); | ||||||||||||||||||||||||||||||||||
| 483 | |||||||||||||||||||||||||||||||||||
| 484 | my $nfa = eval qq(fromExpr(($s)x$N)); | ||||||||||||||||||||||||||||||||||
| 485 | |||||||||||||||||||||||||||||||||||
| 486 | ok $nfa->printNws("((a|b)*)**$N: ") eq nws <<END; | ||||||||||||||||||||||||||||||||||
| 487 | ((a|b)*)**4: | ||||||||||||||||||||||||||||||||||
| 488 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 489 | 0 1 { a => 1 } [2, 4, 6, 8, 10, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 490 | 1 1 undef [0, 2, 3, 4, 6, 8, 10, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 491 | 2 0 { b => 3 } undef | ||||||||||||||||||||||||||||||||||
| 492 | 3 1 undef [0, 2, 4, 6, 8, 10, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 493 | 4 1 { a => 5 } [6, 8, 10, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 494 | 5 1 undef [4, 6, 7, 8, 10, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 495 | 6 0 { b => 7 } undef | ||||||||||||||||||||||||||||||||||
| 496 | 7 1 undef [4, 6, 8, 10, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 497 | 8 1 { a => 9 } [10, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 498 | 9 1 undef [8, 10, 11, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 499 | 10 0 { b => 11 } undef | ||||||||||||||||||||||||||||||||||
| 500 | 11 1 undef [8, 10, 12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 501 | 12 1 { a => 13 } [14, 16] | ||||||||||||||||||||||||||||||||||
| 502 | 13 1 undef [12, 14, 15, 16] | ||||||||||||||||||||||||||||||||||
| 503 | 14 0 { b => 15 } undef | ||||||||||||||||||||||||||||||||||
| 504 | 15 1 undef [12, 14, 16] | ||||||||||||||||||||||||||||||||||
| 505 | 16 1 undef undef | ||||||||||||||||||||||||||||||||||
| 506 | END | ||||||||||||||||||||||||||||||||||
| 507 | |||||||||||||||||||||||||||||||||||
| 508 | =head1 Description | ||||||||||||||||||||||||||||||||||
| 509 | |||||||||||||||||||||||||||||||||||
| 510 | Non deterministic finite state machine from regular expression. | ||||||||||||||||||||||||||||||||||
| 511 | |||||||||||||||||||||||||||||||||||
| 512 | |||||||||||||||||||||||||||||||||||
| 513 | Version 20200621. | ||||||||||||||||||||||||||||||||||
| 514 | |||||||||||||||||||||||||||||||||||
| 515 | |||||||||||||||||||||||||||||||||||
| 516 | The following sections describe the methods in each functional area of this | ||||||||||||||||||||||||||||||||||
| 517 | module. For an alphabetic listing of all methods by name see L<Index|/Index>. | ||||||||||||||||||||||||||||||||||
| 518 | |||||||||||||||||||||||||||||||||||
| 519 | |||||||||||||||||||||||||||||||||||
| 520 | |||||||||||||||||||||||||||||||||||
| 521 | =head1 Construct regular expression | ||||||||||||||||||||||||||||||||||
| 522 | |||||||||||||||||||||||||||||||||||
| 523 | Construct a regular expression that defines the language to be parsed using the following combining operations which can all be imported: | ||||||||||||||||||||||||||||||||||
| 524 | |||||||||||||||||||||||||||||||||||
| 525 | =head2 element($label) | ||||||||||||||||||||||||||||||||||
| 526 | |||||||||||||||||||||||||||||||||||
| 527 | One element. An element can also be represented by a string or number | ||||||||||||||||||||||||||||||||||
| 528 | |||||||||||||||||||||||||||||||||||
| 529 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 530 | 1 $label Transition symbol | ||||||||||||||||||||||||||||||||||
| 531 | |||||||||||||||||||||||||||||||||||
| 532 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 533 | |||||||||||||||||||||||||||||||||||
| 534 | |||||||||||||||||||||||||||||||||||
| 535 | my $nfa = fromExpr(𝗲𝗹𝗲𝗺𝗲𝗻𝘁("a")); | ||||||||||||||||||||||||||||||||||
| 536 | ok $nfa->print("Element: a") eq <<END; | ||||||||||||||||||||||||||||||||||
| 537 | Element: a | ||||||||||||||||||||||||||||||||||
| 538 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 539 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 540 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 541 | 2 1 undef undef\ | ||||||||||||||||||||||||||||||||||
| 542 | END | ||||||||||||||||||||||||||||||||||
| 543 | ok $nfa->isFinal(2); | ||||||||||||||||||||||||||||||||||
| 544 | ok !$nfa->isFinal(0); | ||||||||||||||||||||||||||||||||||
| 545 | ok $nfa->parse(qw(a)); | ||||||||||||||||||||||||||||||||||
| 546 | ok !$nfa->parse(qw(a b)); | ||||||||||||||||||||||||||||||||||
| 547 | ok !$nfa->parse(qw(b)); | ||||||||||||||||||||||||||||||||||
| 548 | ok !$nfa->parse(qw(b a)); | ||||||||||||||||||||||||||||||||||
| 549 | |||||||||||||||||||||||||||||||||||
| 550 | |||||||||||||||||||||||||||||||||||
| 551 | This is a static method and so should either be imported or invoked as: | ||||||||||||||||||||||||||||||||||
| 552 | |||||||||||||||||||||||||||||||||||
| 553 | Data::NFA::element | ||||||||||||||||||||||||||||||||||
| 554 | |||||||||||||||||||||||||||||||||||
| 555 | |||||||||||||||||||||||||||||||||||
| 556 | =head2 sequence(@elements) | ||||||||||||||||||||||||||||||||||
| 557 | |||||||||||||||||||||||||||||||||||
| 558 | Sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 559 | |||||||||||||||||||||||||||||||||||
| 560 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 561 | 1 @elements Elements | ||||||||||||||||||||||||||||||||||
| 562 | |||||||||||||||||||||||||||||||||||
| 563 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 564 | |||||||||||||||||||||||||||||||||||
| 565 | |||||||||||||||||||||||||||||||||||
| 566 | my $nfa = fromExpr(qw(a b)); | ||||||||||||||||||||||||||||||||||
| 567 | is_deeply $nfa->print("ab"), <<END; | ||||||||||||||||||||||||||||||||||
| 568 | ab | ||||||||||||||||||||||||||||||||||
| 569 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 570 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 571 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 572 | 2 undef [3] | ||||||||||||||||||||||||||||||||||
| 573 | 3 { b => 4 } undef | ||||||||||||||||||||||||||||||||||
| 574 | 4 1 undef undef | ||||||||||||||||||||||||||||||||||
| 575 | END | ||||||||||||||||||||||||||||||||||
| 576 | ok !$nfa->parse(qw()); | ||||||||||||||||||||||||||||||||||
| 577 | ok $nfa->parse(qw(a b)); | ||||||||||||||||||||||||||||||||||
| 578 | ok !$nfa->parse(qw(b a)); | ||||||||||||||||||||||||||||||||||
| 579 | ok !$nfa->parse(qw(a)); | ||||||||||||||||||||||||||||||||||
| 580 | ok !$nfa->parse(qw(b)); | ||||||||||||||||||||||||||||||||||
| 581 | |||||||||||||||||||||||||||||||||||
| 582 | |||||||||||||||||||||||||||||||||||
| 583 | This is a static method and so should either be imported or invoked as: | ||||||||||||||||||||||||||||||||||
| 584 | |||||||||||||||||||||||||||||||||||
| 585 | Data::NFA::sequence | ||||||||||||||||||||||||||||||||||
| 586 | |||||||||||||||||||||||||||||||||||
| 587 | |||||||||||||||||||||||||||||||||||
| 588 | =head2 optional(@element) | ||||||||||||||||||||||||||||||||||
| 589 | |||||||||||||||||||||||||||||||||||
| 590 | An optional sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 591 | |||||||||||||||||||||||||||||||||||
| 592 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 593 | 1 @element Elements | ||||||||||||||||||||||||||||||||||
| 594 | |||||||||||||||||||||||||||||||||||
| 595 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 596 | |||||||||||||||||||||||||||||||||||
| 597 | |||||||||||||||||||||||||||||||||||
| 598 | my $nfa = fromExpr("a", 𝗼𝗽𝘁𝗶𝗼𝗻𝗮𝗹("b"), "c"); | ||||||||||||||||||||||||||||||||||
| 599 | is_deeply $nfa->print("ab?c"), <<END; | ||||||||||||||||||||||||||||||||||
| 600 | ab?c | ||||||||||||||||||||||||||||||||||
| 601 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 602 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 603 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 604 | 2 undef [3 .. 6] | ||||||||||||||||||||||||||||||||||
| 605 | 3 undef [4, 5, 6] | ||||||||||||||||||||||||||||||||||
| 606 | 4 { b => 5 } undef | ||||||||||||||||||||||||||||||||||
| 607 | 5 undef [6] | ||||||||||||||||||||||||||||||||||
| 608 | 6 { c => 7 } undef | ||||||||||||||||||||||||||||||||||
| 609 | 7 1 undef undef | ||||||||||||||||||||||||||||||||||
| 610 | END | ||||||||||||||||||||||||||||||||||
| 611 | ok !$nfa->parse(qw(a)); | ||||||||||||||||||||||||||||||||||
| 612 | ok $nfa->parse(qw(a b c)); | ||||||||||||||||||||||||||||||||||
| 613 | ok $nfa->parse(qw(a c)); | ||||||||||||||||||||||||||||||||||
| 614 | ok !$nfa->parse(qw(a c b)); | ||||||||||||||||||||||||||||||||||
| 615 | |||||||||||||||||||||||||||||||||||
| 616 | |||||||||||||||||||||||||||||||||||
| 617 | This is a static method and so should either be imported or invoked as: | ||||||||||||||||||||||||||||||||||
| 618 | |||||||||||||||||||||||||||||||||||
| 619 | Data::NFA::optional | ||||||||||||||||||||||||||||||||||
| 620 | |||||||||||||||||||||||||||||||||||
| 621 | |||||||||||||||||||||||||||||||||||
| 622 | =head2 zeroOrMore(@element) | ||||||||||||||||||||||||||||||||||
| 623 | |||||||||||||||||||||||||||||||||||
| 624 | Zero or more repetitions of a sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 625 | |||||||||||||||||||||||||||||||||||
| 626 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 627 | 1 @element Elements | ||||||||||||||||||||||||||||||||||
| 628 | |||||||||||||||||||||||||||||||||||
| 629 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 630 | |||||||||||||||||||||||||||||||||||
| 631 | |||||||||||||||||||||||||||||||||||
| 632 | my $nfa = fromExpr("a", 𝘇𝗲𝗿𝗼𝗢𝗿𝗠𝗼𝗿𝗲("b"), "c"); | ||||||||||||||||||||||||||||||||||
| 633 | is_deeply $nfa->print("ab*c"), <<END; | ||||||||||||||||||||||||||||||||||
| 634 | ab*c | ||||||||||||||||||||||||||||||||||
| 635 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 636 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 637 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 638 | 2 undef [3, 4, 6, 7] | ||||||||||||||||||||||||||||||||||
| 639 | 3 undef [4, 6, 7] | ||||||||||||||||||||||||||||||||||
| 640 | 4 { b => 5 } undef | ||||||||||||||||||||||||||||||||||
| 641 | 5 undef [3, 4, 6, 7] | ||||||||||||||||||||||||||||||||||
| 642 | 6 undef [7] | ||||||||||||||||||||||||||||||||||
| 643 | 7 { c => 8 } undef | ||||||||||||||||||||||||||||||||||
| 644 | 8 1 undef undef | ||||||||||||||||||||||||||||||||||
| 645 | END | ||||||||||||||||||||||||||||||||||
| 646 | ok $nfa->parse(qw(a c)); | ||||||||||||||||||||||||||||||||||
| 647 | ok $nfa->parse(qw(a b c)); | ||||||||||||||||||||||||||||||||||
| 648 | ok $nfa->parse(qw(a b b c)); | ||||||||||||||||||||||||||||||||||
| 649 | ok !$nfa->parse(qw(a b b d)); | ||||||||||||||||||||||||||||||||||
| 650 | |||||||||||||||||||||||||||||||||||
| 651 | my $nfa = fromExpr("a", | ||||||||||||||||||||||||||||||||||
| 652 | 𝘇𝗲𝗿𝗼𝗢𝗿𝗠𝗼𝗿𝗲(choice("a", | ||||||||||||||||||||||||||||||||||
| 653 | "a")), | ||||||||||||||||||||||||||||||||||
| 654 | "a"); | ||||||||||||||||||||||||||||||||||
| 655 | is_deeply $nfa->print("(a(a|a)*a"), <<END; | ||||||||||||||||||||||||||||||||||
| 656 | (a(a|a)*a | ||||||||||||||||||||||||||||||||||
| 657 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 658 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 659 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 660 | 2 undef [3, 4, 5, 7, 8, 10, 11] | ||||||||||||||||||||||||||||||||||
| 661 | 3 undef [4, 5, 7, 8, 10, 11] | ||||||||||||||||||||||||||||||||||
| 662 | 4 undef [5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 663 | 5 { a => 6 } undef | ||||||||||||||||||||||||||||||||||
| 664 | 6 undef [3, 4, 5, 7 .. 11] | ||||||||||||||||||||||||||||||||||
| 665 | 7 undef [8] | ||||||||||||||||||||||||||||||||||
| 666 | 8 { a => 9 } undef | ||||||||||||||||||||||||||||||||||
| 667 | 9 undef [3, 4, 5, 7, 8, 10, 11] | ||||||||||||||||||||||||||||||||||
| 668 | 10 undef [11] | ||||||||||||||||||||||||||||||||||
| 669 | 11 { a => 12 } undef | ||||||||||||||||||||||||||||||||||
| 670 | 12 1 undef undef | ||||||||||||||||||||||||||||||||||
| 671 | END | ||||||||||||||||||||||||||||||||||
| 672 | |||||||||||||||||||||||||||||||||||
| 673 | ok !$nfa->parse(qw(a)); | ||||||||||||||||||||||||||||||||||
| 674 | ok $nfa->parse(qw(a a)); | ||||||||||||||||||||||||||||||||||
| 675 | ok $nfa->parse(qw(a a a)); | ||||||||||||||||||||||||||||||||||
| 676 | ok !$nfa->parse(qw(a b a)); | ||||||||||||||||||||||||||||||||||
| 677 | |||||||||||||||||||||||||||||||||||
| 678 | |||||||||||||||||||||||||||||||||||
| 679 | This is a static method and so should either be imported or invoked as: | ||||||||||||||||||||||||||||||||||
| 680 | |||||||||||||||||||||||||||||||||||
| 681 | Data::NFA::zeroOrMore | ||||||||||||||||||||||||||||||||||
| 682 | |||||||||||||||||||||||||||||||||||
| 683 | |||||||||||||||||||||||||||||||||||
| 684 | =head2 oneOrMore(@element) | ||||||||||||||||||||||||||||||||||
| 685 | |||||||||||||||||||||||||||||||||||
| 686 | One or more repetitions of a sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 687 | |||||||||||||||||||||||||||||||||||
| 688 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 689 | 1 @element Elements | ||||||||||||||||||||||||||||||||||
| 690 | |||||||||||||||||||||||||||||||||||
| 691 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 692 | |||||||||||||||||||||||||||||||||||
| 693 | |||||||||||||||||||||||||||||||||||
| 694 | my $nfa = fromExpr("a", 𝗼𝗻𝗲𝗢𝗿𝗠𝗼𝗿𝗲("b"), "c"); | ||||||||||||||||||||||||||||||||||
| 695 | |||||||||||||||||||||||||||||||||||
| 696 | is_deeply $nfa->print("One or More: ab+c"), <<END; | ||||||||||||||||||||||||||||||||||
| 697 | One or More: ab+c | ||||||||||||||||||||||||||||||||||
| 698 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 699 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 700 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 701 | 2 undef [3, 4] | ||||||||||||||||||||||||||||||||||
| 702 | 3 undef [4] | ||||||||||||||||||||||||||||||||||
| 703 | 4 { b => 5 } undef | ||||||||||||||||||||||||||||||||||
| 704 | 5 undef [3, 4, 6, 7] | ||||||||||||||||||||||||||||||||||
| 705 | 6 undef [7] | ||||||||||||||||||||||||||||||||||
| 706 | 7 { c => 8 } undef | ||||||||||||||||||||||||||||||||||
| 707 | 8 1 undef undef | ||||||||||||||||||||||||||||||||||
| 708 | END | ||||||||||||||||||||||||||||||||||
| 709 | |||||||||||||||||||||||||||||||||||
| 710 | ok !$nfa->parse(qw(a c)); | ||||||||||||||||||||||||||||||||||
| 711 | ok $nfa->parse(qw(a b c)); | ||||||||||||||||||||||||||||||||||
| 712 | ok $nfa->parse(qw(a b b c)); | ||||||||||||||||||||||||||||||||||
| 713 | ok !$nfa->parse(qw(a b b d)); | ||||||||||||||||||||||||||||||||||
| 714 | |||||||||||||||||||||||||||||||||||
| 715 | |||||||||||||||||||||||||||||||||||
| 716 | This is a static method and so should either be imported or invoked as: | ||||||||||||||||||||||||||||||||||
| 717 | |||||||||||||||||||||||||||||||||||
| 718 | Data::NFA::oneOrMore | ||||||||||||||||||||||||||||||||||
| 719 | |||||||||||||||||||||||||||||||||||
| 720 | |||||||||||||||||||||||||||||||||||
| 721 | =head2 choice(@elements) | ||||||||||||||||||||||||||||||||||
| 722 | |||||||||||||||||||||||||||||||||||
| 723 | Choice from amongst one or more elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 724 | |||||||||||||||||||||||||||||||||||
| 725 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 726 | 1 @elements Elements to be chosen from | ||||||||||||||||||||||||||||||||||
| 727 | |||||||||||||||||||||||||||||||||||
| 728 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 729 | |||||||||||||||||||||||||||||||||||
| 730 | |||||||||||||||||||||||||||||||||||
| 731 | my $nfa = fromExpr("a", | ||||||||||||||||||||||||||||||||||
| 732 | 𝗰𝗵𝗼𝗶𝗰𝗲(qw(b c)), | ||||||||||||||||||||||||||||||||||
| 733 | "d"); | ||||||||||||||||||||||||||||||||||
| 734 | is_deeply $nfa->print("(a(b|c)d"), <<END; | ||||||||||||||||||||||||||||||||||
| 735 | (a(b|c)d | ||||||||||||||||||||||||||||||||||
| 736 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 737 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 738 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 739 | 2 undef [3, 4, 6, 7] | ||||||||||||||||||||||||||||||||||
| 740 | 3 undef [4, 6, 7] | ||||||||||||||||||||||||||||||||||
| 741 | 4 { b => 5 } undef | ||||||||||||||||||||||||||||||||||
| 742 | 5 undef [8, 9] | ||||||||||||||||||||||||||||||||||
| 743 | 6 undef [7] | ||||||||||||||||||||||||||||||||||
| 744 | 7 { c => 8 } undef | ||||||||||||||||||||||||||||||||||
| 745 | 8 undef [9] | ||||||||||||||||||||||||||||||||||
| 746 | 9 { d => 10 } undef | ||||||||||||||||||||||||||||||||||
| 747 | 10 1 undef undef | ||||||||||||||||||||||||||||||||||
| 748 | END | ||||||||||||||||||||||||||||||||||
| 749 | |||||||||||||||||||||||||||||||||||
| 750 | ok $nfa->parse(qw(a b d)); | ||||||||||||||||||||||||||||||||||
| 751 | ok $nfa->parse(qw(a c d)); | ||||||||||||||||||||||||||||||||||
| 752 | ok !$nfa->parse(qw(a b c d)); | ||||||||||||||||||||||||||||||||||
| 753 | |||||||||||||||||||||||||||||||||||
| 754 | |||||||||||||||||||||||||||||||||||
| 755 | This is a static method and so should either be imported or invoked as: | ||||||||||||||||||||||||||||||||||
| 756 | |||||||||||||||||||||||||||||||||||
| 757 | Data::NFA::choice | ||||||||||||||||||||||||||||||||||
| 758 | |||||||||||||||||||||||||||||||||||
| 759 | |||||||||||||||||||||||||||||||||||
| 760 | =head2 except(@elements) | ||||||||||||||||||||||||||||||||||
| 761 | |||||||||||||||||||||||||||||||||||
| 762 | Choice from amongst all symbols except the ones mentioned | ||||||||||||||||||||||||||||||||||
| 763 | |||||||||||||||||||||||||||||||||||
| 764 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 765 | 1 @elements Elements not to be chosen from | ||||||||||||||||||||||||||||||||||
| 766 | |||||||||||||||||||||||||||||||||||
| 767 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 768 | |||||||||||||||||||||||||||||||||||
| 769 | |||||||||||||||||||||||||||||||||||
| 770 | my $nfa = fromExpr(choice(qw(a b c)), 𝗲𝘅𝗰𝗲𝗽𝘁(qw(c x)), choice(qw(a b c))); | ||||||||||||||||||||||||||||||||||
| 771 | |||||||||||||||||||||||||||||||||||
| 772 | is_deeply $nfa->print("(a|b|c)(c!x)(a|b|c)"), <<END; | ||||||||||||||||||||||||||||||||||
| 773 | (a|b|c)(c!x)(a|b|c) | ||||||||||||||||||||||||||||||||||
| 774 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 775 | 0 undef [1, 2, 4, 5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 776 | 1 undef [2, 4, 5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 777 | 2 { a => 3 } undef | ||||||||||||||||||||||||||||||||||
| 778 | 3 undef [9, 10, 11, 13, 14] | ||||||||||||||||||||||||||||||||||
| 779 | 4 undef [5] | ||||||||||||||||||||||||||||||||||
| 780 | 5 { b => 6 } undef | ||||||||||||||||||||||||||||||||||
| 781 | 6 undef [9, 10, 11, 13, 14] | ||||||||||||||||||||||||||||||||||
| 782 | 7 undef [8] | ||||||||||||||||||||||||||||||||||
| 783 | 8 { c => 9 } undef | ||||||||||||||||||||||||||||||||||
| 784 | 9 undef [10, 11, 13, 14] | ||||||||||||||||||||||||||||||||||
| 785 | 10 undef [11, 13, 14] | ||||||||||||||||||||||||||||||||||
| 786 | 11 { a => 12 } undef | ||||||||||||||||||||||||||||||||||
| 787 | 12 undef [15, 16, 17, 19, 20, 22, 23] | ||||||||||||||||||||||||||||||||||
| 788 | 13 undef [14] | ||||||||||||||||||||||||||||||||||
| 789 | 14 { b => 15 } undef | ||||||||||||||||||||||||||||||||||
| 790 | 15 undef [16, 17, 19, 20, 22, 23] | ||||||||||||||||||||||||||||||||||
| 791 | 16 undef [17, 19, 20, 22, 23] | ||||||||||||||||||||||||||||||||||
| 792 | 17 { a => 18 } undef | ||||||||||||||||||||||||||||||||||
| 793 | 18 1 undef [24] | ||||||||||||||||||||||||||||||||||
| 794 | 19 undef [20] | ||||||||||||||||||||||||||||||||||
| 795 | 20 { b => 21 } undef | ||||||||||||||||||||||||||||||||||
| 796 | 21 1 undef [24] | ||||||||||||||||||||||||||||||||||
| 797 | 22 undef [23] | ||||||||||||||||||||||||||||||||||
| 798 | 23 { c => 24 } undef | ||||||||||||||||||||||||||||||||||
| 799 | 24 1 undef undef | ||||||||||||||||||||||||||||||||||
| 800 | END | ||||||||||||||||||||||||||||||||||
| 801 | |||||||||||||||||||||||||||||||||||
| 802 | ok !$nfa->parse(qw(a a)); | ||||||||||||||||||||||||||||||||||
| 803 | ok $nfa->parse(qw(a a a)); | ||||||||||||||||||||||||||||||||||
| 804 | ok !$nfa->parse(qw(a c a)); | ||||||||||||||||||||||||||||||||||
| 805 | |||||||||||||||||||||||||||||||||||
| 806 | |||||||||||||||||||||||||||||||||||
| 807 | This is a static method and so should either be imported or invoked as: | ||||||||||||||||||||||||||||||||||
| 808 | |||||||||||||||||||||||||||||||||||
| 809 | Data::NFA::except | ||||||||||||||||||||||||||||||||||
| 810 | |||||||||||||||||||||||||||||||||||
| 811 | |||||||||||||||||||||||||||||||||||
| 812 | =head1 Non deterministic finite state machine | ||||||||||||||||||||||||||||||||||
| 813 | |||||||||||||||||||||||||||||||||||
| 814 | Create a non deterministic finite state machine to represent a regular expression. | ||||||||||||||||||||||||||||||||||
| 815 | |||||||||||||||||||||||||||||||||||
| 816 | =head2 fromExpr(@expression) | ||||||||||||||||||||||||||||||||||
| 817 | |||||||||||||||||||||||||||||||||||
| 818 | Create an NFA from a regular B<@expression>. | ||||||||||||||||||||||||||||||||||
| 819 | |||||||||||||||||||||||||||||||||||
| 820 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 821 | 1 @expression Regular expressions | ||||||||||||||||||||||||||||||||||
| 822 | |||||||||||||||||||||||||||||||||||
| 823 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 824 | |||||||||||||||||||||||||||||||||||
| 825 | |||||||||||||||||||||||||||||||||||
| 826 | my $nfa = 𝗳𝗿𝗼𝗺𝗘𝘅𝗽𝗿 | ||||||||||||||||||||||||||||||||||
| 827 | ("a", | ||||||||||||||||||||||||||||||||||
| 828 | oneOrMore(choice(qw(b c))), | ||||||||||||||||||||||||||||||||||
| 829 | optional("d"), | ||||||||||||||||||||||||||||||||||
| 830 | element("e") | ||||||||||||||||||||||||||||||||||
| 831 | ); | ||||||||||||||||||||||||||||||||||
| 832 | |||||||||||||||||||||||||||||||||||
| 833 | is_deeply $nfa->print("a(b|c)+d?e"), <<END; | ||||||||||||||||||||||||||||||||||
| 834 | a(b|c)+d?e | ||||||||||||||||||||||||||||||||||
| 835 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 836 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 837 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 838 | 2 undef [3, 4, 5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 839 | 3 undef [4, 5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 840 | 4 undef [5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 841 | 5 { b => 6 } undef | ||||||||||||||||||||||||||||||||||
| 842 | 6 undef [3, 4, 5, 7 .. 14] | ||||||||||||||||||||||||||||||||||
| 843 | 7 undef [8] | ||||||||||||||||||||||||||||||||||
| 844 | 8 { c => 9 } undef | ||||||||||||||||||||||||||||||||||
| 845 | 9 undef [3, 4, 5, 7, 8, 10 .. 14] | ||||||||||||||||||||||||||||||||||
| 846 | 10 undef [11 .. 14] | ||||||||||||||||||||||||||||||||||
| 847 | 11 undef [12, 13, 14] | ||||||||||||||||||||||||||||||||||
| 848 | 12 { d => 13 } undef | ||||||||||||||||||||||||||||||||||
| 849 | 13 undef [14] | ||||||||||||||||||||||||||||||||||
| 850 | 14 { e => 15 } undef | ||||||||||||||||||||||||||||||||||
| 851 | 15 1 undef undef | ||||||||||||||||||||||||||||||||||
| 852 | END | ||||||||||||||||||||||||||||||||||
| 853 | |||||||||||||||||||||||||||||||||||
| 854 | is_deeply ['a'..'e'], [$nfa->symbols]; | ||||||||||||||||||||||||||||||||||
| 855 | |||||||||||||||||||||||||||||||||||
| 856 | ok !$nfa->parse(qw(a e)); | ||||||||||||||||||||||||||||||||||
| 857 | ok !$nfa->parse(qw(a d e)); | ||||||||||||||||||||||||||||||||||
| 858 | ok $nfa->parse(qw(a b c e)); | ||||||||||||||||||||||||||||||||||
| 859 | ok $nfa->parse(qw(a b c d e)); | ||||||||||||||||||||||||||||||||||
| 860 | |||||||||||||||||||||||||||||||||||
| 861 | |||||||||||||||||||||||||||||||||||
| 862 | This is a static method and so should either be imported or invoked as: | ||||||||||||||||||||||||||||||||||
| 863 | |||||||||||||||||||||||||||||||||||
| 864 | Data::NFA::fromExpr | ||||||||||||||||||||||||||||||||||
| 865 | |||||||||||||||||||||||||||||||||||
| 866 | |||||||||||||||||||||||||||||||||||
| 867 | =head2 print($states, $title) | ||||||||||||||||||||||||||||||||||
| 868 | |||||||||||||||||||||||||||||||||||
| 869 | Print the current B<$states> of the non deterministic finite state automaton using the specified B<$title>. If it is non deterministic, the non deterministic jumps will be shown as well as the transitions table. If deterministic, only the transitions table will be shown. | ||||||||||||||||||||||||||||||||||
| 870 | |||||||||||||||||||||||||||||||||||
| 871 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 872 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 873 | 2 $title Title | ||||||||||||||||||||||||||||||||||
| 874 | |||||||||||||||||||||||||||||||||||
| 875 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 876 | |||||||||||||||||||||||||||||||||||
| 877 | |||||||||||||||||||||||||||||||||||
| 878 | my $nfa = fromExpr | ||||||||||||||||||||||||||||||||||
| 879 | ("a", | ||||||||||||||||||||||||||||||||||
| 880 | oneOrMore(choice(qw(b c))), | ||||||||||||||||||||||||||||||||||
| 881 | optional("d"), | ||||||||||||||||||||||||||||||||||
| 882 | element("e") | ||||||||||||||||||||||||||||||||||
| 883 | ); | ||||||||||||||||||||||||||||||||||
| 884 | |||||||||||||||||||||||||||||||||||
| 885 | is_deeply $nfa->𝗽𝗿𝗶𝗻𝘁("a(b|c)+d?e"), <<END; | ||||||||||||||||||||||||||||||||||
| 886 | a(b|c)+d?e | ||||||||||||||||||||||||||||||||||
| 887 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 888 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 889 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 890 | 2 undef [3, 4, 5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 891 | 3 undef [4, 5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 892 | 4 undef [5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 893 | 5 { b => 6 } undef | ||||||||||||||||||||||||||||||||||
| 894 | 6 undef [3, 4, 5, 7 .. 14] | ||||||||||||||||||||||||||||||||||
| 895 | 7 undef [8] | ||||||||||||||||||||||||||||||||||
| 896 | 8 { c => 9 } undef | ||||||||||||||||||||||||||||||||||
| 897 | 9 undef [3, 4, 5, 7, 8, 10 .. 14] | ||||||||||||||||||||||||||||||||||
| 898 | 10 undef [11 .. 14] | ||||||||||||||||||||||||||||||||||
| 899 | 11 undef [12, 13, 14] | ||||||||||||||||||||||||||||||||||
| 900 | 12 { d => 13 } undef | ||||||||||||||||||||||||||||||||||
| 901 | 13 undef [14] | ||||||||||||||||||||||||||||||||||
| 902 | 14 { e => 15 } undef | ||||||||||||||||||||||||||||||||||
| 903 | 15 1 undef undef | ||||||||||||||||||||||||||||||||||
| 904 | END | ||||||||||||||||||||||||||||||||||
| 905 | |||||||||||||||||||||||||||||||||||
| 906 | is_deeply ['a'..'e'], [$nfa->symbols]; | ||||||||||||||||||||||||||||||||||
| 907 | |||||||||||||||||||||||||||||||||||
| 908 | ok !$nfa->parse(qw(a e)); | ||||||||||||||||||||||||||||||||||
| 909 | ok !$nfa->parse(qw(a d e)); | ||||||||||||||||||||||||||||||||||
| 910 | ok $nfa->parse(qw(a b c e)); | ||||||||||||||||||||||||||||||||||
| 911 | ok $nfa->parse(qw(a b c d e)); | ||||||||||||||||||||||||||||||||||
| 912 | |||||||||||||||||||||||||||||||||||
| 913 | |||||||||||||||||||||||||||||||||||
| 914 | =head2 symbols($states) | ||||||||||||||||||||||||||||||||||
| 915 | |||||||||||||||||||||||||||||||||||
| 916 | Return an array of all the transition symbols. | ||||||||||||||||||||||||||||||||||
| 917 | |||||||||||||||||||||||||||||||||||
| 918 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 919 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 920 | |||||||||||||||||||||||||||||||||||
| 921 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 922 | |||||||||||||||||||||||||||||||||||
| 923 | |||||||||||||||||||||||||||||||||||
| 924 | my $nfa = fromExpr | ||||||||||||||||||||||||||||||||||
| 925 | ("a", | ||||||||||||||||||||||||||||||||||
| 926 | oneOrMore(choice(qw(b c))), | ||||||||||||||||||||||||||||||||||
| 927 | optional("d"), | ||||||||||||||||||||||||||||||||||
| 928 | element("e") | ||||||||||||||||||||||||||||||||||
| 929 | ); | ||||||||||||||||||||||||||||||||||
| 930 | |||||||||||||||||||||||||||||||||||
| 931 | is_deeply $nfa->print("a(b|c)+d?e"), <<END; | ||||||||||||||||||||||||||||||||||
| 932 | a(b|c)+d?e | ||||||||||||||||||||||||||||||||||
| 933 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 934 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 935 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 936 | 2 undef [3, 4, 5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 937 | 3 undef [4, 5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 938 | 4 undef [5, 7, 8] | ||||||||||||||||||||||||||||||||||
| 939 | 5 { b => 6 } undef | ||||||||||||||||||||||||||||||||||
| 940 | 6 undef [3, 4, 5, 7 .. 14] | ||||||||||||||||||||||||||||||||||
| 941 | 7 undef [8] | ||||||||||||||||||||||||||||||||||
| 942 | 8 { c => 9 } undef | ||||||||||||||||||||||||||||||||||
| 943 | 9 undef [3, 4, 5, 7, 8, 10 .. 14] | ||||||||||||||||||||||||||||||||||
| 944 | 10 undef [11 .. 14] | ||||||||||||||||||||||||||||||||||
| 945 | 11 undef [12, 13, 14] | ||||||||||||||||||||||||||||||||||
| 946 | 12 { d => 13 } undef | ||||||||||||||||||||||||||||||||||
| 947 | 13 undef [14] | ||||||||||||||||||||||||||||||||||
| 948 | 14 { e => 15 } undef | ||||||||||||||||||||||||||||||||||
| 949 | 15 1 undef undef | ||||||||||||||||||||||||||||||||||
| 950 | END | ||||||||||||||||||||||||||||||||||
| 951 | |||||||||||||||||||||||||||||||||||
| 952 | is_deeply ['a'..'e'], [$nfa->𝘀𝘆𝗺𝗯𝗼𝗹𝘀]; | ||||||||||||||||||||||||||||||||||
| 953 | |||||||||||||||||||||||||||||||||||
| 954 | ok !$nfa->parse(qw(a e)); | ||||||||||||||||||||||||||||||||||
| 955 | ok !$nfa->parse(qw(a d e)); | ||||||||||||||||||||||||||||||||||
| 956 | ok $nfa->parse(qw(a b c e)); | ||||||||||||||||||||||||||||||||||
| 957 | ok $nfa->parse(qw(a b c d e)); | ||||||||||||||||||||||||||||||||||
| 958 | |||||||||||||||||||||||||||||||||||
| 959 | |||||||||||||||||||||||||||||||||||
| 960 | =head2 isFinal($states, $state) | ||||||||||||||||||||||||||||||||||
| 961 | |||||||||||||||||||||||||||||||||||
| 962 | Whether, in the B<$states> specifying an NFA the named state B<$state> is a final state. | ||||||||||||||||||||||||||||||||||
| 963 | |||||||||||||||||||||||||||||||||||
| 964 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 965 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 966 | 2 $state Name of state to test | ||||||||||||||||||||||||||||||||||
| 967 | |||||||||||||||||||||||||||||||||||
| 968 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 969 | |||||||||||||||||||||||||||||||||||
| 970 | |||||||||||||||||||||||||||||||||||
| 971 | my $nfa = fromExpr(element("a")); | ||||||||||||||||||||||||||||||||||
| 972 | ok $nfa->print("Element: a") eq <<END; | ||||||||||||||||||||||||||||||||||
| 973 | Element: a | ||||||||||||||||||||||||||||||||||
| 974 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 975 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 976 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 977 | 2 1 undef undef\ | ||||||||||||||||||||||||||||||||||
| 978 | END | ||||||||||||||||||||||||||||||||||
| 979 | ok $nfa->𝗶𝘀𝗙𝗶𝗻𝗮𝗹(2); | ||||||||||||||||||||||||||||||||||
| 980 | ok !$nfa->𝗶𝘀𝗙𝗶𝗻𝗮𝗹(0); | ||||||||||||||||||||||||||||||||||
| 981 | ok $nfa->parse(qw(a)); | ||||||||||||||||||||||||||||||||||
| 982 | ok !$nfa->parse(qw(a b)); | ||||||||||||||||||||||||||||||||||
| 983 | ok !$nfa->parse(qw(b)); | ||||||||||||||||||||||||||||||||||
| 984 | ok !$nfa->parse(qw(b a)); | ||||||||||||||||||||||||||||||||||
| 985 | |||||||||||||||||||||||||||||||||||
| 986 | |||||||||||||||||||||||||||||||||||
| 987 | =head2 allTransitions($states) | ||||||||||||||||||||||||||||||||||
| 988 | |||||||||||||||||||||||||||||||||||
| 989 | Return all transitions in the NFA specified by B<$states> as {stateName}{symbol} = [reachable states]. | ||||||||||||||||||||||||||||||||||
| 990 | |||||||||||||||||||||||||||||||||||
| 991 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 992 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 993 | |||||||||||||||||||||||||||||||||||
| 994 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 995 | |||||||||||||||||||||||||||||||||||
| 996 | |||||||||||||||||||||||||||||||||||
| 997 | my $s = q(zeroOrMore(choice("a"))); | ||||||||||||||||||||||||||||||||||
| 998 | |||||||||||||||||||||||||||||||||||
| 999 | my $nfa = eval qq(fromExpr(sequence($s,$s))); | ||||||||||||||||||||||||||||||||||
| 1000 | |||||||||||||||||||||||||||||||||||
| 1001 | is_deeply $nfa->print("a*"), <<END; | ||||||||||||||||||||||||||||||||||
| 1002 | a* | ||||||||||||||||||||||||||||||||||
| 1003 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 1004 | 0 1 undef [1 .. 4, 6 .. 9, 11] | ||||||||||||||||||||||||||||||||||
| 1005 | 1 1 undef [2, 3, 4, 6 .. 9, 11] | ||||||||||||||||||||||||||||||||||
| 1006 | 2 1 undef [3, 4, 6 .. 9, 11] | ||||||||||||||||||||||||||||||||||
| 1007 | 3 undef [4] | ||||||||||||||||||||||||||||||||||
| 1008 | 4 { a => 5 } undef | ||||||||||||||||||||||||||||||||||
| 1009 | 5 1 undef [2, 3, 4, 6 .. 9, 11] | ||||||||||||||||||||||||||||||||||
| 1010 | 6 1 undef [7, 8, 9, 11] | ||||||||||||||||||||||||||||||||||
| 1011 | 7 1 undef [8, 9, 11] | ||||||||||||||||||||||||||||||||||
| 1012 | 8 undef [9] | ||||||||||||||||||||||||||||||||||
| 1013 | 9 { a => 10 } undef | ||||||||||||||||||||||||||||||||||
| 1014 | 10 1 undef [7, 8, 9, 11] | ||||||||||||||||||||||||||||||||||
| 1015 | 11 1 undef undef | ||||||||||||||||||||||||||||||||||
| 1016 | END | ||||||||||||||||||||||||||||||||||
| 1017 | |||||||||||||||||||||||||||||||||||
| 1018 | ok $nfa->parse(qw()); | ||||||||||||||||||||||||||||||||||
| 1019 | ok $nfa->parse(qw(a)); | ||||||||||||||||||||||||||||||||||
| 1020 | ok !$nfa->parse(qw(b)); | ||||||||||||||||||||||||||||||||||
| 1021 | ok $nfa->parse(qw(a a)); | ||||||||||||||||||||||||||||||||||
| 1022 | ok !$nfa->parse(qw(b b)); | ||||||||||||||||||||||||||||||||||
| 1023 | ok !$nfa->parse(qw(a b)); | ||||||||||||||||||||||||||||||||||
| 1024 | ok !$nfa->parse(qw(b a)); | ||||||||||||||||||||||||||||||||||
| 1025 | ok !$nfa->parse(qw(c)); | ||||||||||||||||||||||||||||||||||
| 1026 | |||||||||||||||||||||||||||||||||||
| 1027 | is_deeply $nfa->𝗮𝗹𝗹𝗧𝗿𝗮𝗻𝘀𝗶𝘁𝗶𝗼𝗻𝘀, { | ||||||||||||||||||||||||||||||||||
| 1028 | "0" => { a => [10, 11, 2 .. 9] }, | ||||||||||||||||||||||||||||||||||
| 1029 | "1" => { a => [10, 11, 2 .. 9] }, | ||||||||||||||||||||||||||||||||||
| 1030 | "2" => { a => [10, 11, 2 .. 9] }, | ||||||||||||||||||||||||||||||||||
| 1031 | "3" => { a => [11, 2 .. 9] }, | ||||||||||||||||||||||||||||||||||
| 1032 | "4" => { a => [11, 2 .. 9] }, | ||||||||||||||||||||||||||||||||||
| 1033 | "5" => { a => [10, 11, 2 .. 9] }, | ||||||||||||||||||||||||||||||||||
| 1034 | "6" => { a => [10, 11, 7, 8, 9] }, | ||||||||||||||||||||||||||||||||||
| 1035 | "7" => { a => [10, 11, 7, 8, 9] }, | ||||||||||||||||||||||||||||||||||
| 1036 | "8" => { a => [10, 11, 7, 8, 9] }, | ||||||||||||||||||||||||||||||||||
| 1037 | "9" => { a => [10, 11, 7, 8, 9] }, | ||||||||||||||||||||||||||||||||||
| 1038 | "10" => { a => [10, 11, 7, 8, 9] }, | ||||||||||||||||||||||||||||||||||
| 1039 | "11" => { a => [] }, | ||||||||||||||||||||||||||||||||||
| 1040 | }; | ||||||||||||||||||||||||||||||||||
| 1041 | |||||||||||||||||||||||||||||||||||
| 1042 | is_deeply $nfa->print("a*a* 2"), <<END; | ||||||||||||||||||||||||||||||||||
| 1043 | a*a* 2 | ||||||||||||||||||||||||||||||||||
| 1044 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 1045 | 0 1 undef [1 .. 4, 6 .. 9, 11] | ||||||||||||||||||||||||||||||||||
| 1046 | 1 1 undef [2, 3, 4, 6 .. 9, 11] | ||||||||||||||||||||||||||||||||||
| 1047 | 2 1 undef [3, 4, 6 .. 9, 11] | ||||||||||||||||||||||||||||||||||
| 1048 | 3 undef [4] | ||||||||||||||||||||||||||||||||||
| 1049 | 4 { a => 5 } undef | ||||||||||||||||||||||||||||||||||
| 1050 | 5 1 undef [2, 3, 4, 6 .. 9, 11] | ||||||||||||||||||||||||||||||||||
| 1051 | 6 1 undef [7, 8, 9, 11] | ||||||||||||||||||||||||||||||||||
| 1052 | 7 1 undef [8, 9, 11] | ||||||||||||||||||||||||||||||||||
| 1053 | 8 undef [9] | ||||||||||||||||||||||||||||||||||
| 1054 | 9 { a => 10 } undef | ||||||||||||||||||||||||||||||||||
| 1055 | 10 1 undef [7, 8, 9, 11] | ||||||||||||||||||||||||||||||||||
| 1056 | 11 1 undef undef | ||||||||||||||||||||||||||||||||||
| 1057 | END | ||||||||||||||||||||||||||||||||||
| 1058 | |||||||||||||||||||||||||||||||||||
| 1059 | |||||||||||||||||||||||||||||||||||
| 1060 | =head2 parse($states, @symbols) | ||||||||||||||||||||||||||||||||||
| 1061 | |||||||||||||||||||||||||||||||||||
| 1062 | Parse, using the NFA specified by B<$states>, the list of symbols in L<@symbols>. | ||||||||||||||||||||||||||||||||||
| 1063 | |||||||||||||||||||||||||||||||||||
| 1064 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1065 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1066 | 2 @symbols Array of symbols | ||||||||||||||||||||||||||||||||||
| 1067 | |||||||||||||||||||||||||||||||||||
| 1068 | B<Example:> | ||||||||||||||||||||||||||||||||||
| 1069 | |||||||||||||||||||||||||||||||||||
| 1070 | |||||||||||||||||||||||||||||||||||
| 1071 | my $nfa = fromExpr(element("a")); | ||||||||||||||||||||||||||||||||||
| 1072 | ok $nfa->print("Element: a") eq <<END; | ||||||||||||||||||||||||||||||||||
| 1073 | Element: a | ||||||||||||||||||||||||||||||||||
| 1074 | Location F Transitions Jumps | ||||||||||||||||||||||||||||||||||
| 1075 | 0 undef [1] | ||||||||||||||||||||||||||||||||||
| 1076 | 1 { a => 2 } undef | ||||||||||||||||||||||||||||||||||
| 1077 | 2 1 undef undef\ | ||||||||||||||||||||||||||||||||||
| 1078 | END | ||||||||||||||||||||||||||||||||||
| 1079 | ok $nfa->isFinal(2); | ||||||||||||||||||||||||||||||||||
| 1080 | ok !$nfa->isFinal(0); | ||||||||||||||||||||||||||||||||||
| 1081 | ok $nfa->𝗽𝗮𝗿𝘀𝗲(qw(a)); | ||||||||||||||||||||||||||||||||||
| 1082 | ok !$nfa->𝗽𝗮𝗿𝘀𝗲(qw(a b)); | ||||||||||||||||||||||||||||||||||
| 1083 | ok !$nfa->𝗽𝗮𝗿𝘀𝗲(qw(b)); | ||||||||||||||||||||||||||||||||||
| 1084 | ok !$nfa->𝗽𝗮𝗿𝘀𝗲(qw(b a)); | ||||||||||||||||||||||||||||||||||
| 1085 | |||||||||||||||||||||||||||||||||||
| 1086 | |||||||||||||||||||||||||||||||||||
| 1087 | |||||||||||||||||||||||||||||||||||
| 1088 | =head2 Data::NFA::State Definition | ||||||||||||||||||||||||||||||||||
| 1089 | |||||||||||||||||||||||||||||||||||
| 1090 | |||||||||||||||||||||||||||||||||||
| 1091 | NFA State | ||||||||||||||||||||||||||||||||||
| 1092 | |||||||||||||||||||||||||||||||||||
| 1093 | |||||||||||||||||||||||||||||||||||
| 1094 | |||||||||||||||||||||||||||||||||||
| 1095 | |||||||||||||||||||||||||||||||||||
| 1096 | =head3 Output fields | ||||||||||||||||||||||||||||||||||
| 1097 | |||||||||||||||||||||||||||||||||||
| 1098 | |||||||||||||||||||||||||||||||||||
| 1099 | B<final> - Whether this state is final | ||||||||||||||||||||||||||||||||||
| 1100 | |||||||||||||||||||||||||||||||||||
| 1101 | B<jumps> - {to => 1} : jumps from this state not consuming any input symbols | ||||||||||||||||||||||||||||||||||
| 1102 | |||||||||||||||||||||||||||||||||||
| 1103 | B<transitions> - {symbol => state} : transitions from this state consuming one input symbol | ||||||||||||||||||||||||||||||||||
| 1104 | |||||||||||||||||||||||||||||||||||
| 1105 | |||||||||||||||||||||||||||||||||||
| 1106 | |||||||||||||||||||||||||||||||||||
| 1107 | =head1 Private Methods | ||||||||||||||||||||||||||||||||||
| 1108 | |||||||||||||||||||||||||||||||||||
| 1109 | =head2 newNfa(%options) | ||||||||||||||||||||||||||||||||||
| 1110 | |||||||||||||||||||||||||||||||||||
| 1111 | Create a new NFA | ||||||||||||||||||||||||||||||||||
| 1112 | |||||||||||||||||||||||||||||||||||
| 1113 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1114 | 1 %options Options | ||||||||||||||||||||||||||||||||||
| 1115 | |||||||||||||||||||||||||||||||||||
| 1116 | =head2 newNfaState(%options) | ||||||||||||||||||||||||||||||||||
| 1117 | |||||||||||||||||||||||||||||||||||
| 1118 | Create a new NFA state. | ||||||||||||||||||||||||||||||||||
| 1119 | |||||||||||||||||||||||||||||||||||
| 1120 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1121 | 1 %options Options | ||||||||||||||||||||||||||||||||||
| 1122 | |||||||||||||||||||||||||||||||||||
| 1123 | =head2 addNewState($nfa) | ||||||||||||||||||||||||||||||||||
| 1124 | |||||||||||||||||||||||||||||||||||
| 1125 | Create a new NFA state and add it to an NFA created with L<newNfa>. | ||||||||||||||||||||||||||||||||||
| 1126 | |||||||||||||||||||||||||||||||||||
| 1127 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1128 | 1 $nfa Nfa | ||||||||||||||||||||||||||||||||||
| 1129 | |||||||||||||||||||||||||||||||||||
| 1130 | =head2 fromExpr2($states, $expr, $symbols) | ||||||||||||||||||||||||||||||||||
| 1131 | |||||||||||||||||||||||||||||||||||
| 1132 | Create an NFA from a regular expression. | ||||||||||||||||||||||||||||||||||
| 1133 | |||||||||||||||||||||||||||||||||||
| 1134 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1135 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1136 | 2 $expr Regular expression constructed from L<element|/element> L<sequence|/sequence> L<optional|/optional> L<zeroOrMore|/zeroOrMore> L<oneOrMore|/oneOrMore> L<choice|/choice> | ||||||||||||||||||||||||||||||||||
| 1137 | 3 $symbols Set of symbols used by the NFA. | ||||||||||||||||||||||||||||||||||
| 1138 | |||||||||||||||||||||||||||||||||||
| 1139 | =head2 propagateFinalState($states) | ||||||||||||||||||||||||||||||||||
| 1140 | |||||||||||||||||||||||||||||||||||
| 1141 | Mark the B<$states> that can reach the final state with a jump as final. | ||||||||||||||||||||||||||||||||||
| 1142 | |||||||||||||||||||||||||||||||||||
| 1143 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1144 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1145 | |||||||||||||||||||||||||||||||||||
| 1146 | =head2 statesReachableViaJumps($states, $StateName) | ||||||||||||||||||||||||||||||||||
| 1147 | |||||||||||||||||||||||||||||||||||
| 1148 | Find the names of all the B<$states> that can be reached from a specified B<$stateName> via jumps alone. | ||||||||||||||||||||||||||||||||||
| 1149 | |||||||||||||||||||||||||||||||||||
| 1150 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1151 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1152 | 2 $StateName Name of start state | ||||||||||||||||||||||||||||||||||
| 1153 | |||||||||||||||||||||||||||||||||||
| 1154 | =head2 removeEmptyFields($states) | ||||||||||||||||||||||||||||||||||
| 1155 | |||||||||||||||||||||||||||||||||||
| 1156 | Remove empty fields from the B<states> representing an NFA. | ||||||||||||||||||||||||||||||||||
| 1157 | |||||||||||||||||||||||||||||||||||
| 1158 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1159 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1160 | |||||||||||||||||||||||||||||||||||
| 1161 | =head2 printFinalState($state) | ||||||||||||||||||||||||||||||||||
| 1162 | |||||||||||||||||||||||||||||||||||
| 1163 | Print the final field of the specified B<$state>. | ||||||||||||||||||||||||||||||||||
| 1164 | |||||||||||||||||||||||||||||||||||
| 1165 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1166 | 1 $state State | ||||||||||||||||||||||||||||||||||
| 1167 | |||||||||||||||||||||||||||||||||||
| 1168 | =head2 printWithJumps($states, $title) | ||||||||||||||||||||||||||||||||||
| 1169 | |||||||||||||||||||||||||||||||||||
| 1170 | Print the current B<$states> of an NFA with jumps using the specvified B<$title>. | ||||||||||||||||||||||||||||||||||
| 1171 | |||||||||||||||||||||||||||||||||||
| 1172 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1173 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1174 | 2 $title Optional title | ||||||||||||||||||||||||||||||||||
| 1175 | |||||||||||||||||||||||||||||||||||
| 1176 | =head2 printWithOutJumps($states, $title) | ||||||||||||||||||||||||||||||||||
| 1177 | |||||||||||||||||||||||||||||||||||
| 1178 | Print the current B<$states> of an NFA without jumps using the specified B<$title>. | ||||||||||||||||||||||||||||||||||
| 1179 | |||||||||||||||||||||||||||||||||||
| 1180 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1181 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1182 | 2 $title Title. | ||||||||||||||||||||||||||||||||||
| 1183 | |||||||||||||||||||||||||||||||||||
| 1184 | =head2 statesReachableViaSymbol($states, $StateName, $symbol, $cache) | ||||||||||||||||||||||||||||||||||
| 1185 | |||||||||||||||||||||||||||||||||||
| 1186 | Find the names of all the states that can be reached from a specified state via a specified symbol and all the jumps available. | ||||||||||||||||||||||||||||||||||
| 1187 | |||||||||||||||||||||||||||||||||||
| 1188 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1189 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1190 | 2 $StateName Name of start state | ||||||||||||||||||||||||||||||||||
| 1191 | 3 $symbol Symbol to reach on | ||||||||||||||||||||||||||||||||||
| 1192 | 4 $cache A hash to be used as a cache | ||||||||||||||||||||||||||||||||||
| 1193 | |||||||||||||||||||||||||||||||||||
| 1194 | =head2 parse2($states, $stateName, @symbols) | ||||||||||||||||||||||||||||||||||
| 1195 | |||||||||||||||||||||||||||||||||||
| 1196 | Parse an array of symbols | ||||||||||||||||||||||||||||||||||
| 1197 | |||||||||||||||||||||||||||||||||||
| 1198 | Parameter Description | ||||||||||||||||||||||||||||||||||
| 1199 | 1 $states States | ||||||||||||||||||||||||||||||||||
| 1200 | 2 $stateName Current state | ||||||||||||||||||||||||||||||||||
| 1201 | 3 @symbols Remaining symbols | ||||||||||||||||||||||||||||||||||
| 1202 | |||||||||||||||||||||||||||||||||||
| 1203 | |||||||||||||||||||||||||||||||||||
| 1204 | =head1 Index | ||||||||||||||||||||||||||||||||||
| 1205 | |||||||||||||||||||||||||||||||||||
| 1206 | |||||||||||||||||||||||||||||||||||
| 1207 | 1 L<addNewState|/addNewState> - Create a new NFA state and add it to an NFA created with L<newNfa>. | ||||||||||||||||||||||||||||||||||
| 1208 | |||||||||||||||||||||||||||||||||||
| 1209 | 2 L<allTransitions|/allTransitions> - Return all transitions in the NFA specified by B<$states> as {stateName}{symbol} = [reachable states]. | ||||||||||||||||||||||||||||||||||
| 1210 | |||||||||||||||||||||||||||||||||||
| 1211 | 3 L<choice|/choice> - Choice from amongst one or more elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 1212 | |||||||||||||||||||||||||||||||||||
| 1213 | 4 L<element|/element> - One element. | ||||||||||||||||||||||||||||||||||
| 1214 | |||||||||||||||||||||||||||||||||||
| 1215 | 5 L<except|/except> - Choice from amongst all symbols except the ones mentioned | ||||||||||||||||||||||||||||||||||
| 1216 | |||||||||||||||||||||||||||||||||||
| 1217 | 6 L<fromExpr|/fromExpr> - Create an NFA from a regular B<@expression>. | ||||||||||||||||||||||||||||||||||
| 1218 | |||||||||||||||||||||||||||||||||||
| 1219 | 7 L<fromExpr2|/fromExpr2> - Create an NFA from a regular expression. | ||||||||||||||||||||||||||||||||||
| 1220 | |||||||||||||||||||||||||||||||||||
| 1221 | 8 L<isFinal|/isFinal> - Whether, in the B<$states> specifying an NFA the named state B<$state> is a final state. | ||||||||||||||||||||||||||||||||||
| 1222 | |||||||||||||||||||||||||||||||||||
| 1223 | 9 L<newNfa|/newNfa> - Create a new NFA | ||||||||||||||||||||||||||||||||||
| 1224 | |||||||||||||||||||||||||||||||||||
| 1225 | 10 L<newNfaState|/newNfaState> - Create a new NFA state. | ||||||||||||||||||||||||||||||||||
| 1226 | |||||||||||||||||||||||||||||||||||
| 1227 | 11 L<oneOrMore|/oneOrMore> - One or more repetitions of a sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 1228 | |||||||||||||||||||||||||||||||||||
| 1229 | 12 L<optional|/optional> - An optional sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 1230 | |||||||||||||||||||||||||||||||||||
| 1231 | 13 L<parse|/parse> - Parse, using the NFA specified by B<$states>, the list of symbols in L<@symbols>. | ||||||||||||||||||||||||||||||||||
| 1232 | |||||||||||||||||||||||||||||||||||
| 1233 | 14 L<parse2|/parse2> - Parse an array of symbols | ||||||||||||||||||||||||||||||||||
| 1234 | |||||||||||||||||||||||||||||||||||
| 1235 | 15 L<print|/print> - Print the current B<$states> of the non deterministic finite state automaton using the specified B<$title>. | ||||||||||||||||||||||||||||||||||
| 1236 | |||||||||||||||||||||||||||||||||||
| 1237 | 16 L<printFinalState|/printFinalState> - Print the final field of the specified B<$state>. | ||||||||||||||||||||||||||||||||||
| 1238 | |||||||||||||||||||||||||||||||||||
| 1239 | 17 L<printWithJumps|/printWithJumps> - Print the current B<$states> of an NFA with jumps using the specvified B<$title>. | ||||||||||||||||||||||||||||||||||
| 1240 | |||||||||||||||||||||||||||||||||||
| 1241 | 18 L<printWithOutJumps|/printWithOutJumps> - Print the current B<$states> of an NFA without jumps using the specified B<$title>. | ||||||||||||||||||||||||||||||||||
| 1242 | |||||||||||||||||||||||||||||||||||
| 1243 | 19 L<propagateFinalState|/propagateFinalState> - Mark the B<$states> that can reach the final state with a jump as final. | ||||||||||||||||||||||||||||||||||
| 1244 | |||||||||||||||||||||||||||||||||||
| 1245 | 20 L<removeEmptyFields|/removeEmptyFields> - Remove empty fields from the B<states> representing an NFA. | ||||||||||||||||||||||||||||||||||
| 1246 | |||||||||||||||||||||||||||||||||||
| 1247 | 21 L<sequence|/sequence> - Sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 1248 | |||||||||||||||||||||||||||||||||||
| 1249 | 22 L<statesReachableViaJumps|/statesReachableViaJumps> - Find the names of all the B<$states> that can be reached from a specified B<$stateName> via jumps alone. | ||||||||||||||||||||||||||||||||||
| 1250 | |||||||||||||||||||||||||||||||||||
| 1251 | 23 L<statesReachableViaSymbol|/statesReachableViaSymbol> - Find the names of all the states that can be reached from a specified state via a specified symbol and all the jumps available. | ||||||||||||||||||||||||||||||||||
| 1252 | |||||||||||||||||||||||||||||||||||
| 1253 | 24 L<symbols|/symbols> - Return an array of all the transition symbols. | ||||||||||||||||||||||||||||||||||
| 1254 | |||||||||||||||||||||||||||||||||||
| 1255 | 25 L<zeroOrMore|/zeroOrMore> - Zero or more repetitions of a sequence of elements and/or symbols. | ||||||||||||||||||||||||||||||||||
| 1256 | |||||||||||||||||||||||||||||||||||
| 1257 | =head1 Installation | ||||||||||||||||||||||||||||||||||
| 1258 | |||||||||||||||||||||||||||||||||||
| 1259 | This module is written in 100% Pure Perl and, thus, it is easy to read, | ||||||||||||||||||||||||||||||||||
| 1260 | comprehend, use, modify and install via B<cpan>: | ||||||||||||||||||||||||||||||||||
| 1261 | |||||||||||||||||||||||||||||||||||
| 1262 | sudo cpan install Data::NFA | ||||||||||||||||||||||||||||||||||
| 1263 | |||||||||||||||||||||||||||||||||||
| 1264 | =head1 Author | ||||||||||||||||||||||||||||||||||
| 1265 | |||||||||||||||||||||||||||||||||||
| 1266 | L<philiprbrenan@gmail.com|mailto:philiprbrenan@gmail.com> | ||||||||||||||||||||||||||||||||||
| 1267 | |||||||||||||||||||||||||||||||||||
| 1268 | L<http://www.appaapps.com|http://www.appaapps.com> | ||||||||||||||||||||||||||||||||||
| 1269 | |||||||||||||||||||||||||||||||||||
| 1270 | =head1 Copyright | ||||||||||||||||||||||||||||||||||
| 1271 | |||||||||||||||||||||||||||||||||||
| 1272 | Copyright (c) 2016-2019 Philip R Brenan. | ||||||||||||||||||||||||||||||||||
| 1273 | |||||||||||||||||||||||||||||||||||
| 1274 | This module is free software. It may be used, redistributed and/or modified | ||||||||||||||||||||||||||||||||||
| 1275 | under the same terms as Perl itself. | ||||||||||||||||||||||||||||||||||
| 1276 | |||||||||||||||||||||||||||||||||||
| 1277 | =cut | ||||||||||||||||||||||||||||||||||
| 1278 | |||||||||||||||||||||||||||||||||||
| 1279 | |||||||||||||||||||||||||||||||||||
| 1280 | |||||||||||||||||||||||||||||||||||
| 1281 | # Tests and documentation | ||||||||||||||||||||||||||||||||||
| 1282 | |||||||||||||||||||||||||||||||||||
| 1283 | sub test | ||||||||||||||||||||||||||||||||||
| 1284 | 1 | ▶ | {my $p = __PACKAGE__; | ||||||||||||||||||||||||||||||||
|
Subroutine
test: called CC=5 SCAR=16.2
Pod
undocumented
| |||||||||||||||||||||||||||||||||||
| 1285 | 1 | binmode($_, ":utf8") for *STDOUT, *STDERR; | |||||||||||||||||||||||||||||||||
| 1286 | 1 | ▶ | return if eval "eof(${p}::DATA)"; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 1287 | 1 | my $s = eval "join('', <${p}::DATA>)"; | |||||||||||||||||||||||||||||||||
| 1288 | 1 | ▶ | $@ and die $@; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 1289 | 1 | ▶ | eval $s; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
Subroutine
BEGIN: called CC=1 SCAR=0.0
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 1290 | 1 | ▶ | $@ and die $@; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 1291 | 1 | 1 | |||||||||||||||||||||||||||||||||
| 1292 | } | ||||||||||||||||||||||||||||||||||
| 1293 | |||||||||||||||||||||||||||||||||||
| 1294 | 1 | ▶ | test unless caller; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 1295 | |||||||||||||||||||||||||||||||||||
| 1296 | 1 | 1; | |||||||||||||||||||||||||||||||||
| 1297 | # podDocumentation | ||||||||||||||||||||||||||||||||||
| 1298 | __DATA__ | ||||||||||||||||||||||||||||||||||