blib/lib/Data/NFA.pm

filter: Statementstmt 94.5% 278 / 294 Branchbran 86.2% 88 / 102 Conditioncond 50.0% 4 / 8 MC/DCmcdc 0.0% 0 / 5 Subroutinesub 92.0% 46 / 50 Podpod 75.7% 25 / 33 totaltotal 89.6% 441 / 492 CC 83 SCAR 20.1
CC
83
Cov
92%
fromExpr2
23.1
statesReachableViaSymbol
8.1
__ANON__
8.1
CRAP 7.5
↑ Summary
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 //= {}
l!l
1040
MC/DC0%0/1
$states //= {}
$states
Truth table50%1/2
A
A= $states
Aresult
11
00
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
BranchTrueFalseTotal
if (not ref $expr) { } 55 49 104
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
BranchTrueFalseTotal
if ($structure eq Element()) { } 10 39 49
elsif ($structure eq Sequence()) { } 4 35 39
elsif ($structure eq Optional()) { } 2 33 35
elsif ($structure eq ZeroOrMore()) { } 11 22 33
elsif ($structure eq OneOrMore()) { } 2 20 22
elsif ($structure eq Choice()) { } 18 2 20
elsif ($structure eq Except()) { } 2 0 2
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
BranchTrueFalseTotal
if ($i) 17 18 35
153 17 {&$jump($start, &$next)
154 }
155 35 $states->fromExpr2($element, $symbols); # Choice
156 35 ▶ if ($i < $#elements)
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $#elements) 17 18 35
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
BranchTrueFalseTotal
ref $_ ? : 0 4 4
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
BranchTrueFalseTotal
if $i 2 2 4
173 4 $states->fromExpr2(element($element), $symbols); # Choice of not excluded symbols
174 4 ▶ if ($i < $#elements)
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $#elements) 2 2 4
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
BranchTrueFalseTotal
unless (defined $state->final) 282 67 349
197 282 ▶ {if (defined $state->jumps)
Branch: 1 branch
BranchTrueFalseTotal
if (defined $state->jumps) 282 0 282
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
BranchTrueFalseTotal
if (defined(my $final = $jump->final)) 38 495 533
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
BranchTrueFalseTotal
unless $changes 20 9 29
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
BranchTrueFalseTotal
if (@check) 2571 401 2972
220 2571 {my $stateName = pop @check;
221 2571 ▶ next if $checked{$stateName}++;
Branch: 1 branch
BranchTrueFalseTotal
if $checked{$stateName}++ 984 1587 2571
222 1587 ▶ confess "No such state: $stateName" unless my $state = $$states{$stateName};
Branch: 1 branch
BranchTrueFalseTotal
unless my $state = $states->{$stateName} 0 1587 1587
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
BranchTrueFalseTotal
unless keys %{$$state{$_}} 241 201 442
237 }
238 221 ▶ delete $$state{final} unless defined $$state{final};
Branch: 1 branch
BranchTrueFalseTotal
unless defined $state->{"final"} 163 58 221
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
BranchTrueFalseTotal
if (ref $expr) { } 45 17 62
249 45 ▶ {$symbols{$$expr[1]}++ if $$expr[0] eq Element; # Add symbol enclosed in element
Branch: 1 branch
BranchTrueFalseTotal
if $expr->[0] eq Element() 6 39 45
250 45 my ($type, @elements) = @$expr;
251 45 for(@elements)
252 68 ▶ {ref $_ ? $symbols->($_) : $symbols{$_}++;
Branch: 1 branch
BranchTrueFalseTotal
ref $_ ? : 20 48 68
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
BranchTrueFalseTotal
defined $state->final ? : 66 167 233
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
BranchTrueFalseTotal
@j ? : 145 88 233
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
BranchTrueFalseTotal
$title ? : 21 0 21
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
BranchTrueFalseTotal
if @j > 0 145 88 233
317 }
318  
319 21 ▶ my $r = $j ? &printWithJumps(@_) : &printWithOutJumps(@_); # Print
Branch: 1 branch
BranchTrueFalseTotal
$j ? : 21 0 21
320  
321 21 ▶ owf($logFile, $r) if -e $logFile; # Log the result if requested
Branch: 1 branch
BranchTrueFalseTotal
if -e $logFile 0 21 21
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
BranchTrueFalseTotal
if ($d->transitions) 7 21 28
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
BranchTrueFalseTotal
defined $f ? : 1 1 2
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
BranchTrueFalseTotal
if (@check) 2241 457 2698
350 2241 {my $stateName = pop @check;
351 2241 ▶ next if $checked{$stateName}++;
Branch: 1 branch
BranchTrueFalseTotal
if $checked{$stateName}++ 874 1367 2241
352 1367 ▶ confess "No such state: $stateName" unless my $state = $$states{$stateName};
Branch: 1 branch
BranchTrueFalseTotal
unless my $state = $states->{$stateName} 0 1367 1367
353  
354 1367 ▶ if ($state->transitions)
Branch: 1 branch
BranchTrueFalseTotal
if ($state->transitions) 575 792 1367
355 575 ▶ {if (my $t = $state->transitions->{$symbol}) # Transition on the symbol
Branch: 1 branch
BranchTrueFalseTotal
if (my $t = $state->transitions->{$symbol}) 178 397 575
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)
l!l&&r!l&&!r
01780
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)
ABresult
1X1
011
000
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
BranchTrueFalseTotal
if (@check) 131 12 143
382 131 {my $stateName = pop @check;
383 131 ▶ next if $checked{$stateName}++;
Branch: 1 branch
BranchTrueFalseTotal
if $checked{$stateName}++ 74 57 131
384 57 my $state = $$states{$stateName};
385 57 ▶ confess "No such state: $stateName" unless $state;
Branch: 1 branch
BranchTrueFalseTotal
unless $state 0 57 57
386 57 my $transitions = $state->transitions;
387  
388 57 ▶ if (defined(my $to = $$transitions{$symbol})) # Transition on the symbol
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $to = $transitions->{$symbol})) 15 42 57
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)
l!l&&r!l&&!r
1320
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)
ABresult
1X1
011
000
392 }
393 57 ▶ if (my $jumps = $state->jumps)
Branch: 1 branch
BranchTrueFalseTotal
if (my $jumps = $state->jumps) 57 0 57
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
BranchTrueFalseTotal
if (defined(my $final = $states->{$stateName}->final)) 120 441 561
412 120 ▶ {return 1 unless @symbols;
Branch: 1 branch
BranchTrueFalseTotal
unless @symbols 40 80 120
413 }
414  
415 521 ▶ return 0 unless @symbols; # No more symbols but not in a final state
Branch: 1 branch
BranchTrueFalseTotal
unless @symbols 64 457 521
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
BranchTrueFalseTotal
if $result 89 375 464
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
BranchTrueFalseTotal
if eval "eof(${p}::DATA)" 0 1 1
1287 1 my $s = eval "join('', <${p}::DATA>)";
1288 1 ▶ $@ and die $@;
Branch: 1 branch
BranchTrueFalseTotal
$@ and die $@ 0 1 1
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
BranchTrueFalseTotal
$@ and die $@ 0 1 1
1291 1 1
1292 }
1293  
1294 1 ▶test unless caller;
Branch: 1 branch
BranchTrueFalseTotal
unless caller 0 1 1
1295  
1296 1 1;
1297 # podDocumentation
1298 __DATA__
↑ Summary