# Copyright 2022 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/.

=head1 NAME

Marpa::R2::Semantics::Null - How the SLIF evaluates null rules and symbols

=head1 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 B<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 B<null parse>.

When evaluating a parse, nulled rules and symbols are
assigned values as described
L<in the semantics document|Marpa::R2::Semantics>.
This document provides additional detail on the assignment
of values to nulled symbols.

=head1 Description

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

=over 4

=item * If all nullable rule alternatives have the same semantics, that semantics is used.

=item * If one of the nullable rule alternatives
is empty (that is, has a zero-length RHS),
then the empty alternative's semantics are used.

=item * 
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.

=back

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.

=head1 Example

As already stated,
Marpa prunes every null subtree back to its topmost
null symbol.
Here is an example:

=for Marpa::R2::Display
name: SLIF null value example
normalize-whitespace: 1

    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' );

=for Marpa::R2::Display::End

If we write the unpruned parse tree
in pre-order, depth-first, indenting children
below their parents, we get something like this:

=for Marpa::R2::Display
ignore: 1

        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

=for Marpa::R2::Display::End

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

=for Marpa::R2::Display
ignore: 1

        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

=for Marpa::R2::Display::End

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:

=for Marpa::R2::Display
name: SLIF null value example output
normalize-whitespace: 1

    S(L(null A;null B;X(x));null R)

=for Marpa::R2::Display::End

In the output we see

=over

=item * The null value for symbol 1.1: "C<null A>".
This comes from the empty rule for C<A>.

=item * The null value for symbol 1.2: "C<null B>".
This comes from the empty rule for C<B>.

=item * The token value for symbol 1.3: "C<x>".

=item * An application of the rule evaluation closure for the rule
C<L := A B X>.

=item * The null value for rule 2: "C<null R>".
This comes from the empty rule for C<R>.

=item * An application of the rule evaluation closure for the rule
C<S := L R>

=back

We B<do not> see any output
for symbols
2.1 (C<A>),
2.2 (C<B>),
or 2.3 (C<Y>)
because they were not topmost
in the pruned subtree.
We B<do not> see an application of the rule evaluation closure for rule C<R := A B Y>,
because there is an empty rule for C<R>, and that takes priority.

=head1 Copyright and License

=for Marpa::R2::Display
ignore: 1

  Copyright 2022 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/.

=for Marpa::R2::Display::End

=cut

# Local Variables:
#   mode: cperl
#   cperl-indent-level: 4
#   fill-column: 100
# End:
# vim: expandtab shiftwidth=4: