1Marpa::XS::Semantics::NUuslelr(3C)ontributed Perl DocumeMnatraptai:o:nXS::Semantics::Null(3)
2
6 Marpa::XS::Semantics::Null - How Marpa Evaluates Null Rules and Symbols
7
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 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 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 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 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 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 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 If any application ever actually needs it, Marpa could implement a
47 complex, and even dynamic, "semantics of nothing".
48 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 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 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 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 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
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 sub L {
85 shift;
86 return 'L(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
87 }
88 sub R {
90 shift;
91 return 'R(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
92 }
93 sub S {
95 shift;
96 return 'S(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
97 }
98 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 $grammar->precompute();
125 my $recce = Marpa::XS::Recognizer->new( { grammar => $grammar } );
127 $recce->read( 'X', 'x' );
129 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 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 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 The pruned tree looks like this
149 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 Here is the output:
158 S(L(null A;null B;x);null R)
160 In the output we see
162 · The null value for node 1.1: ""null A"".
164 · The null value for node 1.2: ""null B"".
166 · The token value for node 1.3: ""x"".
168 · An application of the semantic Perl closure for node 1.
170 · The null value for node 2: ""null R"".
172 · An application of the semantic Perl closure for rule node 0.
174 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
182 In rare cases, your application may call for null values with a complex
183 semantics.
184 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 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 · Determine which of the application's nullable symbols have a
196 dynamic semantics. Call these the dynamic nullables.
197 · Let the "null_value" property of every dynamic nullable be a hash
199 key.
200 · 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 · 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 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 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/.
223perl v5.30.0 2019-07-26 Marpa::XS::Semantics::Null(3)