.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{
.    if \nF \{
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Marpa::R2::NAIF::Semantics::Null 3pm"
.TH Marpa::R2::NAIF::Semantics::Null 3pm "2015-03-06" "perl v5.20.2" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Marpa::R2::NAIF::Semantics::Null \- How the NAIF evaluates null rules and symbols
.SH "Overview"
.IX Header "Overview"
This document deals with Marpa's low-level \s-1NAIF\s0 interface.
If you are new to Marpa,
or are not sure which interface you are interested in,
or do not know what the Named Argment InterFace (\s-1NAIF\s0) is,
you probably want to look instead at
the document on semantics for the \s-1SLIF\s0
interface.
.PP
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 \fBvisible\fR.
.PP
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 \fBnull parse\fR.
.PP
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.
.SH "Description"
.IX Header "Description"
.SS "Null values come from rules"
.IX Subsection "Null values come from rules"
All null values for symbols come from rules with that symbol
on their \s-1LHS.\s0
For a symbol to be nulled, it must be on the \s-1LHS\s0 of at least one
nullable rule.
The action of one of these nullable rules will be the action for
the nulled symbol.
.PP
If the action is a constant, then that constant is the value
of the nulled symbol.
If the action is a rule evaluation closure,
then that closure is called with no child arguments,
and the closure's result is the value of the nulled symbol.
.PP
It may be that more than one nullable rule has that symbol on
its \s-1LHS,\s0 and and that
these rules have different action names.
In that case, the action for the empty rule with that \s-1LHS\s0
is the one which
applies.
It is a fatal error if the nullable rules for a \s-1LHS\s0 symbol
have different action names, and there is no empty rule for that \s-1LHS\s0
symbol.
A simple way to fix this problem is create such an empty rule.
.SS "Null subtrees"
.IX Subsection "Null subtrees"
A null subtree is a subtree all of whose symbols and rules are nulled.
Marpa prunes
all null subtrees back to their topmost nulled symbol.
.PP
The \*(L"lost\*(R" semantics of the non-topmost symbols and rules
of null subtrees is 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.
.PP
Since nulled symbols and rules correspond to zero-length strings,
so we are literally dealing here with
the \*(L"semantics of nothing\*(R".
In theory the semantics of nothing can be arbitrarily complex.
In practice it should be possible to keep them simple.
.SH "Example"
.IX Header "Example"
As already stated,
Marpa prunes every null subtree back to its topmost
null symbol.
Here is an example:
.PP
.Vb 4
\&    sub do_L {
\&        shift;
\&        return \*(AqL(\*(Aq . ( join q{;}, map { $_ // \*(Aq[ERROR!]\*(Aq } @_ ) . \*(Aq)\*(Aq;
\&    }
\&
\&    sub do_R {
\&        return \*(AqR(): I will never be called\*(Aq;
\&    }
\&
\&    sub do_S {
\&        shift;
\&        return \*(AqS(\*(Aq . ( join q{;}, map { $_ // \*(Aq[ERROR!]\*(Aq } @_ ) . \*(Aq)\*(Aq;
\&    }
\&
\&    sub do_X { return \*(AqX(\*(Aq . $_[1] . \*(Aq)\*(Aq; }
\&    sub do_Y { return \*(AqY(\*(Aq . $_[1] . \*(Aq)\*(Aq; }
\&
\&    ## no critic (Variables::ProhibitPackageVars)
\&    our $null_A = \*(Aqnull A\*(Aq;
\&    our $null_B = \*(Aqnull B\*(Aq;
\&    our $null_L = \*(Aqnull L\*(Aq;
\&    our $null_R = \*(Aqnull R\*(Aq;
\&    our $null_X = \*(Aqnull X\*(Aq;
\&    our $null_Y = \*(Aqnull Y\*(Aq;
\&    ## use critic
\&
\&    my $grammar = Marpa::R2::Grammar\->new(
\&        {   start   => \*(AqS\*(Aq,
\&            actions => \*(Aqmain\*(Aq,
\&            rules   => [
\&                [ \*(AqS\*(Aq, [qw/L R/],   \*(Aqdo_S\*(Aq ],
\&                [ \*(AqL\*(Aq, [qw/A B X/], \*(Aqdo_L\*(Aq ],
\&                [ \*(AqL\*(Aq, [], \*(Aqnull_L\*(Aq ],
\&                [ \*(AqR\*(Aq, [qw/A B Y/], \*(Aqdo_R\*(Aq ],
\&                [ \*(AqR\*(Aq, [], \*(Aqnull_R\*(Aq ],
\&                [ \*(AqA\*(Aq, [], \*(Aqnull_A\*(Aq ],
\&                [ \*(AqB\*(Aq, [], \*(Aqnull_B\*(Aq ],
\&                [ \*(AqX\*(Aq, [], \*(Aqnull_X\*(Aq ],
\&                [ \*(AqX\*(Aq, [qw/x/], \*(Aqdo_X\*(Aq ],
\&                [ \*(AqY\*(Aq, [], \*(Aqnull_Y\*(Aq ],
\&                [ \*(AqY\*(Aq, [qw/y/], \*(Aqdo_Y\*(Aq ],
\&            ],
\&        }
\&    );
\&
\&    $grammar\->precompute();
\&
\&    my $recce = Marpa::R2::Recognizer\->new( { grammar => $grammar } );
\&
\&    $recce\->read( \*(Aqx\*(Aq, \*(Aqx\*(Aq );
.Ve
.PP
If we write the unpruned parse tree
in pre-order, depth-first, indenting children
below their parents, we get something like this:
.PP
.Vb 9
\&        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 \*(Aqx\*(Aq
\&             2: Nulled Rule, Rule R := A B Y
\&                 2.1: Nulled Symbol A
\&                 2.2: Nulled Symbol B
\&                 2.3: Nulled Symbol Y
.Ve
.PP
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 \s-1LHS\s0 of the rule numbered 2.
.PP
The pruned tree looks like this
.PP
.Vb 6
\&        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 \*(Aqx\*(Aq
\&             2: LHS of Nulled Rule, Symbol R
.Ve
.PP
Here is the output:
.PP
.Vb 1
\&    S(L(null A;null B;X(x));null R)
.Ve
.PP
In the output we see
.IP "\(bu" 4
The null value for symbol 1.1: "\f(CW\*(C`null A\*(C'\fR".
This comes from the empty rule for \f(CW\*(C`A\*(C'\fR.
.IP "\(bu" 4
The null value for symbol 1.2: "\f(CW\*(C`null B\*(C'\fR".
This comes from the empty rule for \f(CW\*(C`B\*(C'\fR.
.IP "\(bu" 4
The token value for symbol 1.3: "\f(CW\*(C`x\*(C'\fR".
.IP "\(bu" 4
An application of the semantic Perl closure for the rule
\&\f(CW\*(C`L := A B X\*(C'\fR.
.IP "\(bu" 4
The null value for rule 2: "\f(CW\*(C`null R\*(C'\fR".
This comes from the empty rule for \f(CW\*(C`R\*(C'\fR.
.IP "\(bu" 4
An application of the semantic Perl closure for the rule
\&\f(CW\*(C`S := L R\*(C'\fR
.PP
We \fBdo not\fR see any output
for symbols
2.1 (\f(CW\*(C`A\*(C'\fR),
2.2 (\f(CW\*(C`B\*(C'\fR),
or 2.3 (\f(CW\*(C`Y\*(C'\fR)
because they were not topmost
in the pruned subtree.
We \fBdo not\fR see an application of the rule evaluation closure for rule \f(CW\*(C`R := A B Y\*(C'\fR,
because there is an empty rule for \f(CW\*(C`R\*(C'\fR, and that takes priority.
.SH "Copyright and License"
.IX Header "Copyright and License"
.Vb 5
\&  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/.
.Ve