File Coverage

blib/lib/FLAT.pm
Criterion Covered Total %
statement 28 40 70.0
branch 2 2 100.0
condition 0 3 0.0
subroutine 10 16 62.5
pod 8 8 100.0
total 48 69 69.5


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