| 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: |