1Marpa::XS::Semantics::NUuslelr(3C)ontributed Perl DocumeMnatraptai:o:nXS::Semantics::Null(3)
2
3
4

NAME

6       Marpa::XS::Semantics::Null - How Marpa Evaluates Null Rules and Symbols
7

DESCRIPTION

9   Null values
10       A null node is a node which derives the zero-length, or empty string.
11       This means that a null node cannot be the ancestor of any token nodes.
12       In Marpa, null nodes are always leaf nodes.
13
14       Null nodes are of two kinds.  A nulling symbol node corresponds to a
15       nulling symbol.  A nulled rule node represents a nulled rule.
16
17       For every null node there is a null node symbol, which is used to the
18       determine the value of the null node.  For a nulled rule node, the null
19       node symbol is the nulled rule's left hand side symbol.  For a nulling
20       symbol node, the null node symbol is the nulling symbol.
21
22       The value of a null node is the null value of the null node symbol.
23       The null value of a symbol comes from that symbol's "null_value"
24       property, if one is defined.  Otherwise, the null value of the symbol
25       comes from the grammar's default null value, as defined by the
26       grammar's "default_null_value" named argument.  If neither the symbol
27       "null_value" property or the grammar's "default_null_value" named
28       argument is defined, a symbol's null value is a Perl "undef".
29
30   Null subtrees
31       A null subtree is a subtree all of whose nodes are null.  Marpa prunes
32       all null subtrees back to their topmost null node.  This means that all
33       null nodes that remain in Marpa's virtual parse tree will be leaf
34       nodes.
35
36       The "lost" semantics of the non-root nodes of null subtrees are usually
37       not missed.  Null subtrees cannot contain token nodes, so no token
38       nodes are lost when null subtrees are pruned.  As bushy as a null
39       subtree might be, all of its nodes are null nodes.
40
41       All null nodes correspond to zero-length strings, so we are literally
42       dealing here with the "semantics of nothing".  In theory the semantics
43       of nothing can be arbitrarily complex.  In practice it should be
44       possible to keep them simple.
45
46       If any application ever actually needs it, Marpa could implement a
47       complex, and even dynamic, "semantics of nothing".
48
49   Null sequence nodes
50       Rule nodes for sequences were mentioned above.  Sequence nodes can also
51       be null nodes.  This happens with sequence rules which have a "min"
52       rule property of 0.  Such a sequence rule can contain any number of
53       sequence items, including zero items.  When a sequence contains zero
54       items, it must derive the zero-length string, and its node is a null
55       node.
56
57       Sequence null nodes obey the rules for null nodes.  Their value is that
58       of a symbol -- the left hand side symbol of the nulled sequence rule.
59
60       When the node for a nullable sequence rule is a null node, its
61       semantics comes from the null value for its left hand side symbol.
62       When the node for a nullable sequence rule is not a null node, then it
63       is a rule node and its semantics come from the rule.  It's up to the
64       application to ensure that the null value of the LHS symbol, when seen
65       in the same contexts as the values returned by the semantic Perl
66       closure for the sequence rule, "makes sense".
67
68       If necessary, an application can make sure that the LHS symbol of the
69       sequence rule is not used for a conflicting purpose elsewhere.  This
70       dedicated symbol can then be given whatever semantics are necessary.
71
72       The rules for nodes in null subtrees apply with equal force to nodes
73       for sequence rules.  In a nulled subtree, the only node whose semantics
74       matters is the root node of that subtree.  If a zero-length sequence is
75       in a nulled subtree, and that zero-length sequence is not the root node
76       of that subtree, then its semantics will be completely ignored.
77

EXAMPLE

79       In Marpa, a null node must be leaf node.  Because Marpa prunes every
80       null subtree back to its topmost null node, none of the non-root nodes
81       in a null subtree are represented in Marpa's virtual parse tree.
82       Here's an example:
83
84           sub L {
85               shift;
86               return 'L(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
87           }
88
89           sub R {
90               shift;
91               return 'R(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
92           }
93
94           sub S {
95               shift;
96               return 'S(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
97           }
98
99           my $grammar = Marpa::XS::Grammar->new(
100               {   start   => 'S',
101                   actions => 'main',
102                   rules   => [
103                       [ 'S', [qw/L R/] ],
104                       [ 'L', [qw/A B X/] ],
105                       [ 'L', [] ],
106                       [ 'R', [qw/A B Y/] ],
107                       [ 'R', [] ],
108                       [ 'A', [] ],
109                       [ 'B', [] ],
110                       [ 'X', [] ],
111                       [ 'Y', [] ],
112                   ],
113                   symbols        => {
114                       L => { null_value => 'null L' },
115                       R => { null_value => 'null R' },
116                       A => { null_value => 'null A' },
117                       B => { null_value => 'null B' },
118                       X => { null_value => 'null X', terminal => 1 },
119                       Y => { null_value => 'null Y', terminal => 1 },
120                   },
121               }
122           );
123
124           $grammar->precompute();
125
126           my $recce = Marpa::XS::Recognizer->new( { grammar => $grammar } );
127
128           $recce->read( 'X', 'x' );
129
130       If we write the unpruned parse tree one node per line in pre-order,
131       depth-first, indenting children below their parents, we get something
132       like this:
133
134               0: Rule Node, Rule: S := L R
135                    1: Rule Node, Rule L := A B X
136                        1.1: Null Node, Symbol A
137                        1.2: Null Node, Symbol B
138                        1.3: Token Node, Token value is 'x'
139                    2: Rule Node, Rule R := A B Y
140                        2.1: Null Node, Symbol A
141                        2.2: Null Node, Symbol B
142                        2.3: Null Node, Symbol Y
143
144       In this example, six nodes are nulled.  Four of them are in a single
145       subtree: 2, 2.1, 2.2 and 2.3.  Marpa prunes every null subtree back to
146       its null root node, which in this case is the node numbered 2.
147
148       The pruned tree looks like this
149
150               0: Rule Node, Rule: S := L R
151                    1: Rule Node, Rule L := A B X
152                        1.1: Null Node, Symbol A
153                        1.2: Null Node, Symbol B
154                        1.3: Token Node, Token value is 'x'
155                    2: Null Node, Symbol R
156
157       Here is the output:
158
159           S(L(null A;null B;x);null R)
160
161       In the output we see
162
163       ·   The null value for node 1.1: ""null A"".
164
165       ·   The null value for node 1.2: ""null B"".
166
167       ·   The token value for node 1.3: ""x"".
168
169       ·   An application of the semantic Perl closure for node 1.
170
171       ·   The null value for node 2: ""null R"".
172
173       ·   An application of the semantic Perl closure for rule node 0.
174
175       We do not see any output for nodes 2.1, 2.2, or 2.3 because they were
176       non-root nodes in the pruned subtree.  We do see the null value for
177       node 2, because after pruning it is a leaf node.  We do not see an
178       application of the semantic Perl closure for node 2, because after
179       pruning, node 2 is not a rule node.
180

ADVANCED

182       In rare cases, your application may call for null values with a complex
183       semantics.
184
185   Implementing a complex but constant null semantics
186       If an application's semantics of nothing, while complex, remains
187       constant, you can handle it by setting every nullable symbol's
188       "null_value" property to the value which your semantics produces when
189       that nullable symbol is the root symbol of a null subtree.
190
191   Implementing a complex and dynamic null semantics
192       If the values of an application's null values are not constants, Marpa
193       can still calculate them.  Here is the most general method:
194
195       ·   Determine which of the application's nullable symbols have a
196           dynamic semantics.  Call these the dynamic nullables.
197
198       ·   Let the "null_value" property of every dynamic nullable be a hash
199           key.
200
201       ·   For every rule with a dynamic nullable on its right hand side,
202           write the rule's semantic Perl closure so that it looks up that
203           hash key in a hash whose values are Perl closures.
204
205       ·   The Perl closure can then use an arbitrarily complex semantics for
206           calculating the value of the dynamic nullable.
207
209         Copyright 2012 Jeffrey Kegler
210         This file is part of Marpa::XS.  Marpa::XS is free software: you can
211         redistribute it and/or modify it under the terms of the GNU Lesser
212         General Public License as published by the Free Software Foundation,
213         either version 3 of the License, or (at your option) any later version.
214
215         Marpa::XS is distributed in the hope that it will be useful,
216         but WITHOUT ANY WARRANTY; without even the implied warranty of
217         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
218         Lesser General Public License for more details.
219
220         You should have received a copy of the GNU Lesser
221         General Public License along with Marpa::XS.  If not, see
222         http://www.gnu.org/licenses/.
223
224
225
226perl v5.30.1                      2020-01-30     Marpa::XS::Semantics::Null(3)
Impressum