NAME¶
Marpa::R2::Semantics::Null - How the SLIF evaluates null rules and symbols
Overview¶
In Marpa parses, rules and symbols can be nulled -- in other words they can
derive the zero-length, or null, string. Which symbols can be, or are, nulled,
depends on the grammar and the input. When a symbol or rule is not nulled, the
symbol is said to be
visible.
Even the start symbol can be nulled, in which case the entire parse derives the
null string. A parse in which the start symbol is nulled is called a
null
parse.
When evaluating a parse, nulled rules and symbols are assigned values as
described in the semantics document. This document provides additional detail
on the assignment of values to nulled symbols.
Description¶
Null values come from rules¶
Nulled subtrees are pruned back to their topmost symbol. Lexemes are never
nulled, so a nulled symbol is always the LHS of a rule instance, and the
action is determined from the rule alternative.
A complication arises if the symbol appears on the LHS of more than one nullable
rule alternative. Because the symbol is nulled, the input is no help in
determining which rule alternative to use. The rule alternative whose
semantics are used for a nulled symbol is determined as follows:
- •
- If all nullable rule alternatives have the same semantics, that semantics
is used.
- •
- If one of the nullable rule alternatives is empty (that is, has a
zero-length RHS), then the empty alternative's semantics are used.
- •
- In the remaining case, two or more of the rule alternatives have different
action names, but none of the alternatives has a zero-length RHS. When
this happens, Marpa throws an exception. One easy way to fix the issue, is
to add an empty rule with the intended semantics.
In determining whether the semantics of two nullable rule alternatives is
"the same", the blessing is taken into account. Two rule
alternatives are considered to have different semantics if they are blessed
differently.
The "lost" semantics of the non-topmost symbols and rules of null
subtrees are usually not missed. Nulled subtrees cannot contain input, and
therefore do not contain token symbols. So no token values are lost when
nulled subtrees are pruned. As bushy as a null subtree might be, all of its
symbols and rules are nulled.
Since nulled symbols and rules correspond to zero-length strings, so we are
literally dealing here with the "semantics of nothing". In theory
the semantics of nothing can be arbitrarily complex. In practice it should be
possible to keep them simple.
Example¶
As already stated, Marpa prunes every null subtree back to its topmost null
symbol. Here is an example:
sub do_L {
shift;
return 'L(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
}
sub do_R {
return 'R(): I will never be called';
}
sub do_S {
shift;
return 'S(' . ( join q{;}, map { $_ // '[ERROR!]' } @_ ) . ')';
}
sub do_X { return 'X(' . $_[1] . ')'; }
sub do_Y { return 'Y(' . $_[1] . ')'; }
## no critic (Variables::ProhibitPackageVars)
our $null_A = 'null A';
our $null_B = 'null B';
our $null_L = 'null L';
our $null_R = 'null R';
our $null_X = 'null X';
our $null_Y = 'null Y';
## use critic
my $slg = Marpa::R2::Scanless::G->new(
{ source => \<<'END_OF_DSL',
:start ::= S
S ::= L R action => do_S
L ::= A B X action => do_L
L ::= action => null_L
R ::= A B Y action => do_R
R ::= action => null_R
A ::= action => null_A
B ::= action => null_B
X ::= action => null_X
X ::= 'x' action => do_X
Y ::= action => null_Y
Y ::= 'y' action => do_Y
END_OF_DSL
}
);
my $slr = Marpa::R2::Scanless::R->new(
{ grammar => $slg,
semantics_package => 'main',
}
);
$slr->read( \'x' );
If we write the unpruned parse tree in pre-order, depth-first, indenting
children below their parents, we get something like this:
0: Visible Rule: S := L R
1: Visible Rule L := A B X
1.1: Nulled Symbol A
1.2: Nulled Symbol B
1.3: Token, Value is 'x'
2: Nulled Rule, Rule R := A B Y
2.1: Nulled Symbol A
2.2: Nulled Symbol B
2.3: Nulled Symbol Y
In this example, five symbols and a rule are nulled. The rule and three of the
symbols are in a single subtree: 2, 2.1, 2.2 and 2.3. Marpa prunes every null
subtree back to its topmost symbol, which in this case is the LHS of the rule
numbered 2.
The pruned tree looks like this
0: Visible Rule: S := L R
1: Visible Rule L := A B X
1.1: Nulled Symbol A
1.2: Nulled Symbol B
1.3: Token, Value is 'x'
2: LHS of Nulled Rule, Symbol R
Nulled nodes 1.1, 1.2 and 2 were all kept, because they are topmost in their
nulled subtree. All the other nulled nodes were discarded.
Here is the output:
S(L(null A;null B;X(x));null R)
In the output we see
- •
- The null value for symbol 1.1: ""null A"". This comes
from the empty rule for "A".
- •
- The null value for symbol 1.2: ""null B"". This comes
from the empty rule for "B".
- •
- The token value for symbol 1.3: ""x"".
- •
- An application of the rule evaluation closure for the rule "L := A B
X".
- •
- The null value for rule 2: ""null R"". This comes from
the empty rule for "R".
- •
- An application of the rule evaluation closure for the rule "S := L
R"
We
do not see any output for symbols 2.1 ("A"), 2.2
("B"), or 2.3 ("Y") because they were not topmost in the
pruned subtree. We
do not see an application of the rule evaluation
closure for rule "R := A B Y", because there is an empty rule for
"R", and that takes priority.
Copyright and License¶
Copyright 2014 Jeffrey Kegler
This file is part of Marpa::R2. Marpa::R2 is free software: you can
redistribute it and/or modify it under the terms of the GNU Lesser
General Public License as published by the Free Software Foundation,
either version 3 of the License, or (at your option) any later version.
Marpa::R2 is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser
General Public License along with Marpa::R2. If not, see
http://www.gnu.org/licenses/.
