Debian Codegraph @

pod/Deprecated/NAIF/Semantics/Null.pod

raw
1 # Copyright 2022 Jeffrey Kegler
2 # This file is part of Marpa::R2. Marpa::R2 is free software: you can
3 # redistribute it and/or modify it under the terms of the GNU Lesser
4 # General Public License as published by the Free Software Foundation,
5 # either version 3 of the License, or (at your option) any later version.
6 #
7 # Marpa::R2 is distributed in the hope that it will be useful,
8 # but WITHOUT ANY WARRANTY; without even the implied warranty of
9 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
10 # Lesser General Public License for more details.
11 #
12 # You should have received a copy of the GNU Lesser
13 # General Public License along with Marpa::R2. If not, see
14 # http://www.gnu.org/licenses/.
15
16 =head1 NAME
17
18 Marpa::R2::Deprecated::NAIF::Semantics::Null - How the NAIF evaluates null rules and symbols
19
20 =head1 THE NAIF INTERFACE IS DEPRECATED
21
22 This document describes the NAIF interface,
23 which is deprecated.
24 PLEASE DO NOT USE IT FOR NEW DEVELOPMENT.
25
26 =head1 Overview
27
28 This document deals with Marpa's low-level NAIF interface.
29 If you are new to Marpa,
30 or are not sure which interface you are interested in,
31 or do not know what the Named Argment InterFace (NAIF) is,
32 you probably want to look instead at
33 L<the document on semantics for the SLIF
34 interface|Marpa::R2::Semantics>.
35
36 In Marpa parses, rules and symbols can be nulled --
37 in other words they can derive the zero-length, or null, string.
38 Which symbols can be, or are, nulled, depends on the grammar
39 and the input.
40 When a symbol or rule is not nulled,
41 the symbol is said to be B<visible>.
42
43 Even the start symbol can be nulled,
44 in which case the entire parse derives the null string.
45 A parse in which the start symbol is nulled is
46 called a B<null parse>.
47
48 When evaluating a parse, nulled rules and symbols are
49 assigned values as described
50 L<in the semantics document|Marpa::R2::Deprecated::NAIF::Semantics>.
51 This document provides additional detail on the assignment
52 of values to nulled symbols.
53
54 =head1 Description
55
56 =head2 Null values come from rules
57
58 All null values for symbols come from rules with that symbol
59 on their LHS.
60 For a symbol to be nulled, it must be on the LHS of at least one
61 nullable rule.
62 The action of one of these nullable rules will be the action for
63 the nulled symbol.
64
65 If the action is a constant, then that constant is the value
66 of the nulled symbol.
67 If the action is a rule evaluation closure,
68 then that closure is called with no child arguments,
69 and the closure's result is the value of the nulled symbol.
70
71 It may be that more than one nullable rule has that symbol on
72 its LHS, and and that
73 these rules have different action names.
74 In that case, the action for the empty rule with that LHS
75 is the one which
76 applies.
77 It is a fatal error if the nullable rules for a LHS symbol
78 have different action names, and there is no empty rule for that LHS
79 symbol.
80 A simple way to fix this problem is create such an empty rule.
81
82 =head2 Null subtrees
83
84 A null subtree is a subtree all of whose symbols and rules are nulled.
85 Marpa prunes
86 all null subtrees back to their topmost nulled symbol.
87
88 The "lost" semantics of the non-topmost symbols and rules
89 of null subtrees is usually not missed.
90 Nulled subtrees cannot contain input,
91 and therefore do not contain token symbols.
92 So no token values are lost when
93 nulled subtrees are pruned.
94 As bushy as a null subtree might be,
95 all of its symbols and rules are nulled.
96
97 Since nulled symbols and rules correspond to zero-length strings,
98 so we are literally dealing here with
99 the "semantics of nothing".
100 In theory the semantics of nothing can be arbitrarily complex.
101 In practice it should be possible to keep them simple.
102
103 =head1 Example
104
105 As already stated,
106 Marpa prunes every null subtree back to its topmost
107 null symbol.
108 Here is an example:
109
110 =for Marpa::R2::Display
111 name: Null Value Example
112 perltidy: '-dcsc -sil=0'
113
114 sub do_L {
115 shift;
116 return 'L(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
117 }
118
119 sub do_R {
120 return 'R(): I will never be called';
121 }
122
123 sub do_S {
124 shift;
125 return 'S(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
126 }
127
128 sub do_X { return 'X(' . $_[1] . ')'; }
129 sub do_Y { return 'Y(' . $_[1] . ')'; }
130
131 ## no critic (Variables::ProhibitPackageVars)
132 our $null_A = 'null A';
133 our $null_B = 'null B';
134 our $null_L = 'null L';
135 our $null_R = 'null R';
136 our $null_X = 'null X';
137 our $null_Y = 'null Y';
138 ## use critic
139
140 my $grammar = Marpa::R2::Grammar->new(
141 { start => 'S',
142 actions => 'main',
143 rules => [
144 [ 'S', [qw/L R/], 'do_S' ],
145 [ 'L', [qw/A B X/], 'do_L' ],
146 [ 'L', [], 'null_L' ],
147 [ 'R', [qw/A B Y/], 'do_R' ],
148 [ 'R', [], 'null_R' ],
149 [ 'A', [], 'null_A' ],
150 [ 'B', [], 'null_B' ],
151 [ 'X', [], 'null_X' ],
152 [ 'X', [qw/x/], 'do_X' ],
153 [ 'Y', [], 'null_Y' ],
154 [ 'Y', [qw/y/], 'do_Y' ],
155 ],
156 }
157 );
158
159 $grammar->precompute();
160
161 my $recce = Marpa::R2::Recognizer->new( { grammar => $grammar } );
162
163 $recce->read( 'x', 'x' );
164
165 =for Marpa::R2::Display::End
166
167 If we write the unpruned parse tree
168 in pre-order, depth-first, indenting children
169 below their parents, we get something like this:
170
171 =for Marpa::R2::Display
172 ignore: 1
173
174 0: Visible Rule: S := L R
175 1: Visible Rule L := A B X
176 1.1: Nulled Symbol A
177 1.2: Nulled Symbol B
178 1.3: Token, Value is 'x'
179 2: Nulled Rule, Rule R := A B Y
180 2.1: Nulled Symbol A
181 2.2: Nulled Symbol B
182 2.3: Nulled Symbol Y
183
184 =for Marpa::R2::Display::End
185
186 In this example, five symbols and a rule are nulled.
187 The rule and three of the symbols are in a single subtree: 2, 2.1, 2.2 and 2.3.
188 Marpa prunes every null subtree back to its topmost symbol,
189 which in this case is the LHS of the rule numbered 2.
190
191 The pruned tree looks like this
192
193 =for Marpa::R2::Display
194 ignore: 1
195
196 0: Visible Rule: S := L R
197 1: Visible Rule L := A B X
198 1.1: Nulled Symbol A
199 1.2: Nulled Symbol B
200 1.3: Token, Value is 'x'
201 2: LHS of Nulled Rule, Symbol R
202
203 =for Marpa::R2::Display::End
204
205
206 Here is the output:
207
208 =for Marpa::R2::Display
209 name: Null Value Example Output
210 normalize-whitespace: 1
211
212 S(L(null A;null B;X(x));null R)
213
214 =for Marpa::R2::Display::End
215
216 In the output we see
217
218 =over
219
220 =item * The null value for symbol 1.1: "C<null A>".
221 This comes from the empty rule for C<A>.
222
223 =item * The null value for symbol 1.2: "C<null B>".
224 This comes from the empty rule for C<B>.
225
226 =item * The token value for symbol 1.3: "C<x>".
227
228 =item * An application of the semantic Perl closure for the rule
229 C<L := A B X>.
230
231 =item * The null value for rule 2: "C<null R>".
232 This comes from the empty rule for C<R>.
233
234 =item * An application of the semantic Perl closure for the rule
235 C<S := L R>
236
237 =back
238
239 We B<do not> see any output
240 for symbols
241 2.1 (C<A>),
242 2.2 (C<B>),
243 or 2.3 (C<Y>)
244 because they were not topmost
245 in the pruned subtree.
246 We B<do not> see an application of the rule evaluation closure for rule C<R := A B Y>,
247 because there is an empty rule for C<R>, and that takes priority.
248
249 =head1 Copyright and License
250
251 =for Marpa::R2::Display
252 ignore: 1
253
254 Copyright 2022 Jeffrey Kegler
255 This file is part of Marpa::R2. Marpa::R2 is free software: you can
256 redistribute it and/or modify it under the terms of the GNU Lesser
257 General Public License as published by the Free Software Foundation,
258 either version 3 of the License, or (at your option) any later version.
259
260 Marpa::R2 is distributed in the hope that it will be useful,
261 but WITHOUT ANY WARRANTY; without even the implied warranty of
262 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
263 Lesser General Public License for more details.
264
265 You should have received a copy of the GNU Lesser
266 General Public License along with Marpa::R2. If not, see
267 http://www.gnu.org/licenses/.
268
269 =for Marpa::R2::Display::End
270
271 =cut
272
273 # Local Variables:
274 # mode: cperl
275 # cperl-indent-level: 4
276 # fill-column: 100
277 # End:
278 # vim: expandtab shiftwidth=4: