blib/lib/Params/Validate/Strict/BNF.pm

filter: Statementstmt 100% 69 / 69 Branchbran 96.1% 25 / 26 Conditioncond 100% 6 / 6 MC/DCmcdc 100% 4 / 4 Subroutinesub 100% 10 / 10 Podpod 100% 1 / 1 totaltotal 99.1% 115 / 116 CC 20 SCAR 16.2
CC
20
Cov
99%
bnf_to_matcher
8.0
_rule_to_regex
7.0
_parse_rhs
4.0
CRAP 5.1
« blib/lib/Params/Validate/Strict.pm ↑ Summary
1 package Params::Validate::Strict::BNF;
2  
3 6 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 6 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 6 ▶use Carp ();
Subroutine BEGIN: called CC=1 SCAR=0.0
6 6 ▶use Exporter qw(import);
Subroutine BEGIN: called CC=1 SCAR=0.0
7 6 ▶use Params::Validate::Strict qw(validate_strict);
Subroutine BEGIN: called CC=1 SCAR=0.0
8  
9 6 our $VERSION = '0.43';
10 6 our @EXPORT_OK = qw(bnf_to_matcher);
11  
12 6 my %_cache;
13  
14 =head1 NAME
15  
16 Params::Validate::Strict::BNF - compile a BNF grammar to a string matcher
17  
18 =head1 SYNOPSIS
19  
20 use Params::Validate::Strict::BNF qw(bnf_to_matcher);
21  
22 my $matcher = bnf_to_matcher([
23 '<greeting> ::= "hello" | "hi"',
24 ]);
25 $matcher->('hello'); # 1
26 $matcher->('bye'); # 0
27  
28 =head1 DESCRIPTION
29  
30 Converts an arrayref of BNF grammar lines into a closure that tests whether
31 a string is a member of the language defined by that grammar.
32  
33 Used internally by L<Params::Validate::Strict> when a schema rule includes a
34 C<bnf> key. Results are cached by grammar content, so repeated calls with
35 the same grammar pay no compilation cost after the first call.
36  
37 =head1 GRAMMAR FORMAT
38  
39 Each element of the arrayref is either a rule definition or a continuation line.
40  
41 =head2 Rule definition
42  
43 '<rule-name> ::= <alternatives>'
44  
45 The left-hand side is a non-terminal name enclosed in angle brackets.
46 The right-hand side is one or more alternatives separated by C<|>.
47  
48 =head2 Continuation lines
49  
50 A line that contains no C<::=> is appended (with a space) to the preceding
51 rule's right-hand side. This lets long rules span multiple array elements:
52  
53 '<telephone-number> ::= <country-code-opt> <area-code> <separator-opt>',
54 '<central-office-code> <separator-opt> <station-code>',
55  
56 =head2 Terminals
57  
58 Literal text is enclosed in double quotes. An empty terminal C<""> matches
59 the empty string (makes a production optional):
60  
61 '<sep> ::= "" | "-" | " "'
62  
63 Backslash escapes inside terminals (e.g. C<"\"">) are passed through to the
64 compiled regex via C<quotemeta>, so no special treatment is needed for regex
65 metacharacters.
66  
67 =head2 Non-terminals
68  
69 References to other rules are enclosed in angle brackets: C<< <rule-name> >>.
70 Recursive rules are not supported and will raise an exception.
71  
72 =head2 Start rule
73  
74 The first rule defined in the grammar is the start rule. A value must match
75 the language generated by that rule (anchored C<^...$>) to be accepted.
76  
77 =head1 FUNCTIONS
78  
79 =head2 bnf_to_matcher( \@grammar_lines )
80  
81 =head3 Purpose
82  
83 Compiles a BNF grammar into a reusable string-membership predicate.
84 Parses the grammar lines into production rules, builds a compiled regular
85 expression, and returns a closure that tests whether a given string belongs
86 to the language. Results are cached by grammar content so repeated calls with
87 identical grammar lines pay the compilation cost only once.
88  
89 =head3 Arguments
90  
91 =head4 grammar_lines (required)
92  
93 An arrayref of one or more BNF grammar lines. Each line is either a rule
94 definition (C<< '<name> ::= <rhs>' >>) or a continuation line (no C<::=>,
95 appended to the preceding rule with a space). Terminals are double-quoted;
96 non-terminals use angle brackets; alternatives are separated by C<|>.
97  
98 =head3 Returns
99  
100 A code reference C<sub ($str) -> 0|1> that returns C<1> if C<$str> is defined
101 and matches the start rule, C<0> otherwise (including when C<$str> is undef).
102  
103 =head3 Side Effects
104  
105 The compiled matcher is stored in a module-level cache keyed by grammar
106 content and is never freed. Grammars are expected to be defined once at
107 program start-up and reused across many calls.
108  
109 =head3 Usage Example
110  
111 use Params::Validate::Strict::BNF qw(bnf_to_matcher);
112  
113 my $is_colour = bnf_to_matcher([
114 '<colour> ::= "red" | "green" | "blue"',
115 ]);
116  
117 $is_colour->('red'); # 1
118 $is_colour->('purple'); # 0
119 $is_colour->(undef); # 0
120  
121 =head3 API SPECIFICATION
122  
123 =head4 Input
124  
125 grammar_lines => {
126 type => 'arrayref',
127 min => 1,
128 }
129  
130 =head4 Output
131  
132 { type => 'coderef' }
133  
134 The returned coderef has the signature C<sub ($str) -> 0|1>.
135  
136 =head3 FORMAL SPECIFICATION
137  
138 bnf_to_matcher : seq STRING -> (STRING U {undef}) -> B
139  
140 Let G = <N, T, P, S> be the grammar derived from grammar_lines, where
141 N -- set of non-terminals (angle-bracket names)
142 T -- set of terminals (double-quoted literals)
143 P -- set of productions in N x (N U T)*
144 S -- start symbol (first defined non-terminal)
145  
146 L(G) = { w in T* | S =>* w } (language generated by G)
147  
148 bnf_to_matcher(lines) =def= lambda s.
149 if s is undef then 0
150 else if s in L(G) then 1
151 else 0
152  
153 Pre-conditions:
154 lines /= empty
155 for all n in N referenced in P: n is defined in P (no dangling non-terminals)
156 no cycle in the non-terminal reference graph (no left recursion / loops)
157  
158 Post-conditions:
159 result is a coderef
160 for all s: result(s) = 1 iff s in L(G)
161 result(undef) = 0
162  
163 Raises an exception if:
164  
165 =over 4
166  
167 =item * the argument is not an arrayref
168  
169 =item * the grammar contains no rule definitions
170  
171 =item * a non-terminal reference is not defined elsewhere in the grammar
172  
173 =item * a recursive rule is detected
174  
175 =back
176  
177 =cut
178  
179 81 ▶sub bnf_to_matcher {
Subroutine bnf_to_matcher: called CC=8 SCAR=20.8
Pod documented
180 81 my ($grammar_lines) = @_;
181  
182 81 validate_strict({
183 input => { grammar_lines => $grammar_lines },
184 schema => {
185 grammar_lines => {
186 type => 'arrayref',
187 min => 1,
188 },
189 },
190 });
191  
192 73 my $cache_key = join("\0", @$grammar_lines);
193 73 ▶ return $_cache{$cache_key} if exists $_cache{$cache_key};
Branch: 1 branch
BranchTrueFalseTotal
if exists $_cache{$cache_key} 24 49 73
194  
195 49 my (%rules, @rule_order);
196 49 my ($current_rule, $current_rhs);
197  
198 107 ▶ my $flush = sub {
Subroutine __ANON__: called CC=2 SCAR=6.9
199 107 ▶ return unless defined $current_rule;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $current_rule 49 58 107
200 58 $rules{$current_rule} = _parse_rhs($current_rhs);
201 49 };
202  
203 49 for my $line (@$grammar_lines) {
204 69 ▶ if($line =~ /^\s*(<[^>]+>)\s*::=\s*(.*)$/) {
Branch: 2 branches
BranchTrueFalseTotal
if ($line =~ /^\s*(<[^>]+>)\s*::=\s*(.*)$/) { } 58 11 69
elsif (defined $current_rule and $line =~ /\S/) { } 6 9 15
205 58 $flush->();
206 58 $current_rule = $1;
207 58 ▶ push @rule_order, $current_rule unless exists $rules{$current_rule};
Branch: 1 branch
BranchTrueFalseTotal
unless exists $rules{$current_rule} 58 0 58
208 58 $current_rhs = $2;
209 ▶ } elsif(defined $current_rule && $line =~ /\S/) {
Condition100%3/3
defined $current_rule and $line =~ /\S/
!ll&&!rl&&r
416
MC/DC100%2/2
defined $current_rule and $line =~ /\S/
defined $current_rule $line =~ /\S/
Truth table100%3/3
A and B
A= defined $current_ruleB= $line =~ /\S/
ABresult
0X0
100
111
210 6 $current_rhs .= " $line";
211 }
212 }
213 49 $flush->();
214  
215 49 ▶ Carp::croak 'bnf_to_matcher: no rules found in grammar' unless @rule_order;
Branch: 1 branch
BranchTrueFalseTotal
unless @rule_order 4 45 49
216  
217 45 my $start = $rule_order[0];
218 45 my $regex_str = _rule_to_regex($start, \%rules, {});
219 37 my $re = qr/^(?:$regex_str)$/s;
220  
221 37 ▶ my $matcher = sub { defined($_[0]) && $_[0] =~ $re ? 1 : 0 };
Subroutine __ANON__: called CC=3 SCAR=11.0
Branch: 1 branch
BranchTrueFalseTotal
defined $_[0] && $_[0] =~ /$re/s ? : 35 31 66
Condition100%3/3
defined $_[0] and $_[0] =~ /$re/s
!ll&&!rl&&r
32835
MC/DC100%2/2
defined $_[0] and $_[0] =~ /$re/s
defined $_[0] $_[0] =~ /$re/s
Truth table100%3/3
A and B
A= defined $_[0]B= $_[0] =~ /$re/s
ABresult
0X0
100
111
222 37 $_cache{$cache_key} = $matcher;
223 37 return $matcher;
224 }
225  
226 68 ▶sub _parse_rhs {
Subroutine _parse_rhs: called CC=4 SCAR=13.9
227 68 my $rhs = $_[0];
228 68 my @alternatives;
229  
230 68 for my $alt (split /\s*\|\s*/, $rhs) {
231 111 my @tokens;
232 111 ▶ while($alt =~ /("(?:[^"\\]|\\.)*"|<[^>]+>)/g) {
Branch: 1 branch
BranchTrueFalseTotal
if ($alt =~ /("(?:[^"\\]|\\.)*"|<[^>]+>)/g) 140 111 251
233 140 my $tok = $1;
234 140 ▶ if($tok =~ /^"(.*)"$/s) {
Branch: 1 branch
BranchTrueFalseTotal
if ($tok =~ /^"(.*)"$/s) { } 106 34 140
235 106 push @tokens, { type => 'terminal', value => $1 };
236 } else {
237 34 push @tokens, { type => 'nonterminal', name => $tok };
238 }
239 }
240 111 push @alternatives, \@tokens;
241 }
242 68 return \@alternatives;
243 }
244  
245 89 ▶sub _rule_to_regex {
Subroutine _rule_to_regex: called CC=7 SCAR=19.5
246 89 my ($rule_name, $rules, $seen) = @_;
247 Carp::croak "bnf_to_matcher: undefined rule '$rule_name' referenced in grammar"
248 89 ▶ unless exists $rules->{$rule_name};
Branch: 1 branch
BranchTrueFalseTotal
unless exists $rules->{$rule_name} 5 84 89
249 Carp::croak "bnf_to_matcher: recursive rule '$rule_name' is not supported"
250 84 ▶ if $seen->{$rule_name};
Branch: 1 branch
BranchTrueFalseTotal
if $seen->{$rule_name} 5 79 84
251  
252 79 local $seen->{$rule_name} = 1;
253  
254 79 my @alt_regexes;
255 79 for my $alt (@{ $rules->{$rule_name} }) {
256 209 my $alt_re = '';
257 209 for my $tok (@$alt) {
258 234 ▶ if($tok->{type} eq 'terminal') {
Branch: 1 branch
BranchTrueFalseTotal
if ($tok->{'type'} eq 'terminal') { } 199 35 234
259 199 $alt_re .= quotemeta($tok->{value});
260 } else {
261 35 $alt_re .= _rule_to_regex($tok->{name}, $rules, $seen);
262 }
263 }
264 200 push @alt_regexes, $alt_re;
265 }
266  
267 70 ▶ return @alt_regexes == 1
Branch: 1 branch
BranchTrueFalseTotal
@alt_regexes == 1 ? : 46 24 70
268 ? $alt_regexes[0]
269 : '(?:' . join('|', @alt_regexes) . ')';
270 }
271  
272 6 1;
273  
274 __END__
« blib/lib/Params/Validate/Strict.pm ↑ Summary