NAME¶

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

Overview¶

This document deals with Marpa's low-level NAIF 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 (NAIF) is, you probably want to look instead at the document on semantics for the SLIF interface.

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¶

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 $grammar = Marpa::R2::Grammar->new(
        {   start   => 'S',
            actions => 'main',
            rules   => [
                [ 'S', [qw/L R/],   'do_S' ],
                [ 'L', [qw/A B X/], 'do_L' ],
                [ 'L', [], 'null_L' ],
                [ 'R', [qw/A B Y/], 'do_R' ],
                [ 'R', [], 'null_R' ],
                [ 'A', [], 'null_A' ],
                [ 'B', [], 'null_B' ],
                [ 'X', [], 'null_X' ],
                [ 'X', [qw/x/], 'do_X' ],
                [ 'Y', [], 'null_Y' ],
                [ 'Y', [qw/y/], 'do_Y' ],
            ],
        }
    );
    $grammar->precompute();
    my $recce = Marpa::R2::Recognizer->new( { grammar => $grammar } );
    $recce->read( 'x', '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

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 semantic Perl 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 semantic Perl 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/.