line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package FLAT; |
2
|
|
|
|
|
|
|
|
3
|
6
|
|
|
6
|
|
375344
|
use strict; |
|
6
|
|
|
|
|
43
|
|
|
6
|
|
|
|
|
151
|
|
4
|
6
|
|
|
6
|
|
27
|
use warnings; |
|
6
|
|
|
|
|
10
|
|
|
6
|
|
|
|
|
124
|
|
5
|
6
|
|
|
6
|
|
2400
|
use FLAT::Regex; |
|
6
|
|
|
|
|
19
|
|
|
6
|
|
|
|
|
286
|
|
6
|
6
|
|
|
6
|
|
2558
|
use FLAT::DFA; |
|
6
|
|
|
|
|
19
|
|
|
6
|
|
|
|
|
205
|
|
7
|
6
|
|
|
6
|
|
36
|
use Carp; |
|
6
|
|
|
|
|
12
|
|
|
6
|
|
|
|
|
2208
|
|
8
|
|
|
|
|
|
|
|
9
|
|
|
|
|
|
|
our $VERSION = q{1.0.4}; |
10
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
=head1 NAME |
12
|
|
|
|
|
|
|
|
13
|
|
|
|
|
|
|
FLAT - Formal Language & Automata Toolkit |
14
|
|
|
|
|
|
|
|
15
|
|
|
|
|
|
|
=head2 Name Change Possibility |
16
|
|
|
|
|
|
|
|
17
|
|
|
|
|
|
|
Future releases of this module may very well reflect a name change that is |
18
|
|
|
|
|
|
|
considered to me more I for Perl modules. When this was originally |
19
|
|
|
|
|
|
|
written (2006) as a homework assignment, the original author was not very |
20
|
|
|
|
|
|
|
well versed in the idiomatic aspects of C. Shortly after, a friendly |
21
|
|
|
|
|
|
|
fellow traveller rewrote it. Since then, this module has patiently sat on |
22
|
|
|
|
|
|
|
CPAN waiting for a use. Recently, this use has come in the form of a module |
23
|
|
|
|
|
|
|
for managing sequential consistency in Perl C<&> perl - L. |
24
|
|
|
|
|
|
|
|
25
|
|
|
|
|
|
|
=head1 SYNOPSIS |
26
|
|
|
|
|
|
|
|
27
|
|
|
|
|
|
|
FLAT.pm is the base class of all regular language objects. For more |
28
|
|
|
|
|
|
|
information, see other POD pages. It provides full support for the |
29
|
|
|
|
|
|
|
I operator, which is useful for expressing the regular interleaving |
30
|
|
|
|
|
|
|
of regular languages. |
31
|
|
|
|
|
|
|
|
32
|
|
|
|
|
|
|
=head1 DESCRIPTION |
33
|
|
|
|
|
|
|
|
34
|
|
|
|
|
|
|
This module provides an interface for manipulating the formal language |
35
|
|
|
|
|
|
|
concept of Regular Expressions, which are used to describe Regular |
36
|
|
|
|
|
|
|
Languages, and their equivalent forms of Automata. |
37
|
|
|
|
|
|
|
|
38
|
|
|
|
|
|
|
It's notable that this module supports, in addition to the traditional |
39
|
|
|
|
|
|
|
Regular Expression operators, the C operator (see [1]). This |
40
|
|
|
|
|
|
|
is expressed as an ampersand, C<&>. In addition to this, logical symbols |
41
|
|
|
|
|
|
|
may be multiple characters. This leads to some interesting applications. |
42
|
|
|
|
|
|
|
|
43
|
|
|
|
|
|
|
While the module can do a lot, i.e.: |
44
|
|
|
|
|
|
|
|
45
|
|
|
|
|
|
|
=over 4 |
46
|
|
|
|
|
|
|
|
47
|
|
|
|
|
|
|
=item * parse a regular expression (RE) (of the formal regular language |
48
|
|
|
|
|
|
|
variety) |
49
|
|
|
|
|
|
|
|
50
|
|
|
|
|
|
|
=item * convert a RE to a NFA (and similarly, a I of two regular |
51
|
|
|
|
|
|
|
languages to a I NFA (PFA)) |
52
|
|
|
|
|
|
|
|
53
|
|
|
|
|
|
|
=item * convert a PFA to a NFA (note, PFAs are equivalent to PetriNets |
54
|
|
|
|
|
|
|
(see [2], L) |
55
|
|
|
|
|
|
|
|
56
|
|
|
|
|
|
|
=item * convert a NFA to a DFA |
57
|
|
|
|
|
|
|
|
58
|
|
|
|
|
|
|
=item * convert a DFA to a minimal DFA |
59
|
|
|
|
|
|
|
|
60
|
|
|
|
|
|
|
=item * generate strings that may be accepted by a DFA |
61
|
|
|
|
|
|
|
|
62
|
|
|
|
|
|
|
=back |
63
|
|
|
|
|
|
|
|
64
|
|
|
|
|
|
|
It is still missing some capabilities that one would expect: |
65
|
|
|
|
|
|
|
|
66
|
|
|
|
|
|
|
=over 4 |
67
|
|
|
|
|
|
|
|
68
|
|
|
|
|
|
|
=item * generate equivalent REs from a NFA or DFA |
69
|
|
|
|
|
|
|
|
70
|
|
|
|
|
|
|
=item * provide targeted conversion of PFAs, NFAs, DFAs to their more |
71
|
|
|
|
|
|
|
explicit state forms; this is particularly interested to have in the case |
72
|
|
|
|
|
|
|
of the PFA. |
73
|
|
|
|
|
|
|
|
74
|
|
|
|
|
|
|
=item * provide targeted serialization of PREs (REs with a shuffle) |
75
|
|
|
|
|
|
|
using direct, explicit manuplation of the AST produced by the parser |
76
|
|
|
|
|
|
|
|
77
|
|
|
|
|
|
|
=item * provide other interesting graph-based manipulations that might |
78
|
|
|
|
|
|
|
prove useful, particular when applied to a graph that represents some |
79
|
|
|
|
|
|
|
form of a finite automata (FA) |
80
|
|
|
|
|
|
|
|
81
|
|
|
|
|
|
|
=back |
82
|
|
|
|
|
|
|
|
83
|
|
|
|
|
|
|
In addition to the above deficiencies, application of this toolkit in |
84
|
|
|
|
|
|
|
interesting areas would naturally generate ideas for new and interesting |
85
|
|
|
|
|
|
|
capabilities. |
86
|
|
|
|
|
|
|
|
87
|
|
|
|
|
|
|
=head2 Sequential Consistency and PREs |
88
|
|
|
|
|
|
|
|
89
|
|
|
|
|
|
|
Valid strings accepted by the shuffle of one or more regular languages is |
90
|
|
|
|
|
|
|
necessarily I. This results from the conversions |
91
|
|
|
|
|
|
|
to a DFA that may be traversed inorder to discover valid string paths |
92
|
|
|
|
|
|
|
necessarily obeys the total ordering constraints of each constituent |
93
|
|
|
|
|
|
|
language of the two being shuffled; and the partial ordering that results |
94
|
|
|
|
|
|
|
among valid string accepted by both (see [2] for more on how PetriNets |
95
|
|
|
|
|
|
|
fit in). |
96
|
|
|
|
|
|
|
|
97
|
|
|
|
|
|
|
=head1 USAGE |
98
|
|
|
|
|
|
|
|
99
|
|
|
|
|
|
|
All regular language objects in FLAT implement the following methods. |
100
|
|
|
|
|
|
|
Specific regular language representations (regex, NFA, DFA) may implement |
101
|
|
|
|
|
|
|
additional methods that are outlined in the repsective POD pages. |
102
|
|
|
|
|
|
|
|
103
|
|
|
|
|
|
|
=cut |
104
|
|
|
|
|
|
|
|
105
|
|
|
|
|
|
|
## let subclasses implement a minimal set of closure properties. |
106
|
|
|
|
|
|
|
## they can override these with more efficient versions if they like. |
107
|
|
|
|
|
|
|
|
108
|
|
|
|
|
|
|
sub as_dfa { |
109
|
0
|
|
|
0
|
1
|
0
|
my @params = @_; |
110
|
0
|
|
|
|
|
0
|
return $params[0]->as_nfa->as_dfa; |
111
|
|
|
|
|
|
|
} |
112
|
|
|
|
|
|
|
|
113
|
|
|
|
|
|
|
sub as_min_dfa { |
114
|
0
|
|
|
0
|
1
|
0
|
my @params = @_; |
115
|
0
|
|
|
|
|
0
|
return $params[0]->as_dfa->as_min_dfa; |
116
|
|
|
|
|
|
|
} |
117
|
|
|
|
|
|
|
|
118
|
|
|
|
|
|
|
sub is_infinite { |
119
|
0
|
|
|
0
|
1
|
0
|
my @params = @_; |
120
|
0
|
|
|
|
|
0
|
return !$params[0]->is_finite; |
121
|
|
|
|
|
|
|
} |
122
|
|
|
|
|
|
|
|
123
|
|
|
|
|
|
|
sub star { |
124
|
0
|
|
|
0
|
1
|
0
|
my @params = @_; |
125
|
0
|
|
|
|
|
0
|
return $params[0]->kleene |
126
|
|
|
|
|
|
|
} |
127
|
|
|
|
|
|
|
|
128
|
|
|
|
|
|
|
sub difference { |
129
|
6
|
|
|
6
|
1
|
19
|
my @params = @_; |
130
|
6
|
|
|
|
|
34
|
return $params[0]->intersect($params[1]->complement); |
131
|
|
|
|
|
|
|
} |
132
|
|
|
|
|
|
|
|
133
|
|
|
|
|
|
|
sub symdiff { |
134
|
6
|
|
|
6
|
1
|
11
|
my $self = shift; |
135
|
6
|
100
|
|
|
|
21
|
return $self if not @_; |
136
|
3
|
|
|
|
|
13
|
my $next = shift()->symdiff(@_); |
137
|
3
|
|
|
|
|
15
|
return ($self->difference($next))->union($next->difference($self)); |
138
|
|
|
|
|
|
|
} |
139
|
|
|
|
|
|
|
|
140
|
|
|
|
|
|
|
sub equals { |
141
|
3
|
|
|
3
|
1
|
12
|
my @params = @_; |
142
|
3
|
|
|
|
|
20
|
return $params[0]->symdiff($params[1])->is_empty(); |
143
|
|
|
|
|
|
|
} |
144
|
|
|
|
|
|
|
|
145
|
|
|
|
|
|
|
sub is_subset_of { |
146
|
0
|
|
|
0
|
1
|
|
my @params = @_; |
147
|
0
|
|
|
|
|
|
return $params[0]->difference($params[1])->is_empty; |
148
|
|
|
|
|
|
|
} |
149
|
|
|
|
|
|
|
|
150
|
|
|
|
|
|
|
BEGIN { |
151
|
6
|
|
|
6
|
|
25
|
for my $method ( |
152
|
|
|
|
|
|
|
qw[ as_nfa as_regex union intersect complement concat |
153
|
|
|
|
|
|
|
kleene reverse is_empty is_finite ] |
154
|
|
|
|
|
|
|
) { |
155
|
6
|
|
|
6
|
|
42
|
no strict 'refs'; |
|
6
|
|
|
|
|
10
|
|
|
6
|
|
|
|
|
518
|
|
156
|
|
|
|
|
|
|
*$method = sub { |
157
|
0
|
|
0
|
0
|
|
0
|
my $pkg = ref $_[0] || $_[0]; |
158
|
0
|
|
|
|
|
0
|
carp "$pkg does not (yet) implement $method"; |
159
|
60
|
|
|
|
|
434
|
}; |
160
|
|
|
|
|
|
|
} |
161
|
|
|
|
|
|
|
} |
162
|
|
|
|
|
|
|
|
163
|
|
|
|
|
|
|
1; |
164
|
|
|
|
|
|
|
|
165
|
|
|
|
|
|
|
__END__ |