<commit_before># Copyright 2013 <NAME>
# 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 - How the SLIF evaluates parses

=head1 Synopsis

=for Marpa::R2::Display
name: SLIF full synopsis
normalize-whitespace: 1

    use Marpa::R2;

    my $grammar = Marpa::R2::Scanless::G->new(
        {   bless_package => 'My_Nodes',
            source        => \(<<'END_OF_SOURCE'),
    :default ::= action => [values] bless => ::lhs
    lexeme default = action => [start,length,value] bless => ::name

    :start ::= Script
    Script ::= Expression+ separator => comma
    comma ~ [,]
    Expression ::=
        Number bless => primary
        | '(' Expression ')' bless => paren assoc => group
       || Expression '**' Expression bless => exponentiate assoc => right
       || Expression '*' Expression bless => multiply
        | Expression '/' Expression bless => divide
       || Expression '+' Expression bless => add
        | Expression '-' Expression bless => subtract

    Number ~ [\d]+
    :discard ~ whitespace
    whitespace ~ [\s]+
    # allow comments
    :discard ~ <hash comment>
    <hash comment> ~ <terminated hash comment> | <unterminated
       final hash comment>
    <terminated hash comment> ~ '#' <hash comment body> <vertical space char>
    <unterminated final hash comment> ~ '#' <hash comment body>
    <hash comment body> ~ <hash comment char>*
    <vertical space char> ~ [\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
    <hash comment char> ~ [^\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
    END_OF_SOURCE
        }
    );


    my $recce = Marpa::R2::Scanless::R->new( { grammar => $grammar } );

    my $input = '42*2+7/3, 42*(2+7)/3, 2**7-3, 2**(7-3)';
    $recce->read(\$input);
    my $value_ref = $recce->value();
    die "No parse was found\n" if not defined $value_ref;

    # Result will be something like "86.33... 126 125 16"
    # depending on the floating point precision
    my $result = ${$value_ref}->doit();

    package My_Nodes;

    sub My_Nodes::primary::doit { return $_[0]->[0]->doit() }
    sub My_Nodes::Number::doit  { return $_[0]->[2] }
    sub My_Nodes::paren::doit   { my ($self) = @_; $self->[1]->doit() }

    sub My_Nodes::add::doit {
        my ($self) = @_;
        $self->[0]->doit() + $self->[2]->doit();
    }

    sub My_Nodes::subtract::doit {
        my ($self) = @_;
        $self->[0]->doit() - $self->[2]->doit();
    }

    sub My_Nodes::multiply::doit {
        my ($self) = @_;
        $self->[0]->doit() * $self->[2]->doit();
    }

    sub My_Nodes::divide::doit {
        my ($self) = @_;
        $self->[0]->doit() / $self->[2]->doit();
    }

    sub My_Nodes::exponentiate::doit {
        my ($self) = @_;
        $self->[0]->doit()**$self->[2]->doit();
    }

    sub My_Nodes::Script::doit {
        my ($self) = @_;
        return join q{ }, map { $_->doit() } @{$self};
    }

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

=head1 About this document

This document describes the semantics for
Marpa's primary interface, the SLIF.

=head1 What is semantics?

A parser is an algorithm
that takes a string of symbols (tokens or characters) and finds a structure
in it.
Traditionally, that structure is a tree.

Rarely is an application interested only in the tree.
Usually the idea is that the string "means" something:
the idea is that the string has a B<semantics>.
Traditionally and most often, the tree
is as an intermediate step in producing a value,
a value which represents the "meaning" or "semantics" of the string.

"Evaluating" a tree means finding its semantics.
The rest of this document describes Marpa's methods for evaluating trees.
Those of you who have dealt with other traditional parsers, such as yacc and bison,
will find Marpa's approach familiar.

=head1 Nodes

In a parse tree, nodes are points where the tree branches or terminates.
Tree terminations are also called terminals or "leaves".

Every rule instance in a Marpa parse is reprsented by a branch point (or "node")
in the tree.
The topmost node of a tree is its "root node".
(Trees are easiest to draw upside down, so traditionally in programming,
the top of a tree is its root.)

A node, or branch point, "branches" into zero or more "child nodes".
The node just above a child node,
the one from which the child node branches out,
is called its parent node.

If the node is for a BNF rule,
the parent node is the LHS of the rule,
and the child nodes are the RHS of the rule.
If the node is for a quantified rule,
the parent node is the LHS of the quantified rule,
and the child nodes are the items of the quantifed sequence of symbol on the
right hand side.
If the node is for a lexeme,
the node represents the lexeme's symbol
and there will be no child nodes.

A parent node can have zero or more children.
Rules with zero children are nulled rules,
and are "leaf nodes".
Leaf nodes are also called B<terminals>.
In Marpa's parse trees, every terminal is either
a lexeme or a nulled rule.

In Marpa,
evaluation only takes place within the structural (G1) subgrammar,
and the descriptions of the behaviors of rules and lexemes below
applies only to the G1 subgrammar.
G0 rules and terminal symbols do not become nodes
in the parse tree,
and are never evaluated.

=head1 The order of node evaluation

The nodes of a Marpa parse tree are
evaluated recursively, left-to-right and bottom-up.
This means that,
when a parent node is evaluated,
the values of all child nodes are known
and available for use by the semantics.
The final value of a parse is the value of the top node
of the parse tree.

=head1  Parse trees and parse series

Because Marpa allows ambiguous parsing,
each parse can produce a B<parse series> --
a series of zero or more parse trees,
each with its own parse result.
The first call to the
L<the SLIF recognizer's C<value()>
method|Marpa::R2::Scanless::Recognizer/"value()">
after the recognizer is created is the
start of the first parse series,
and Parse Series Setup Phase takes place
at this point.

The first parse series continues until there is
a call to the
L<the C<series_restart()>
method|Marpa::R2::Scanless::R/"series_restart()">
or until the recognizer is destroyed.
Almost always, an application is only interested in one
parse series.

The C<series_restart()> method starts a new parse series.
The Parse Series Setup Phase for that parse series will take
place during
the SLIF recognizer first C<value()> method called
after the 
C<series_restart()>.

The Parse Series Setup Phase
is one of several phases in which the semantics are executed.
Applications will find that the order in which
these phases occurs "just works".
But the details can matter.
Applications whose behavior might depend on these details
include those which make unusual use of side effects in the semantics;
and those which alter their symbol tables at runtime.
A full description of phases of Marpa'a semantic processing
are in
L<a separate
document|Marpa::R2::Semantics::Phases>.

=head1 Nulled subtrees

A nulled subtree is a subtree of the parse tree formed by a nulled node and its direct and
indirect child nodes.
(All these child nodes will also be nulled nodes.)
Before evaluation,
Marpa prunes all nulled subtrees back to their topmost nulled
node.
Of all the ways of dealing with nulled subtrees, this is the
simplest and
Marpa's users have found it a natural approach.
More detail on the semantics of nulled symbols and subtrees
can be found in
L<a separate document|Marpa::R2::Semantics::Null>.

=head1 Actions and how Marpa finds them

What the SLIF does at each node is called that node's B<action>.
Actions can be explicit or implicit.
An explicit action is one that is specified by the application,
in one of the ways
to be described below.
A node's implicit action is the one it performs if it has no
explicit action.

=head2 Lexeme actions

The implicit action for a lexeme is to return
its literal value in the input stream, as a string.
An explicit default action name for lexemes may be set using the
L<the lexeme default statement|Marpa::R2::Scanless::DSL/"Lexeme default statement">.

=head2 Rule actions

The implicit action for a rule is to return a Perl C<undef>.
An explicit action for a rule can be specified using
L<the C<action> adverb|Marpa::R2::Scanless::DSL/"action">
for the rule or, in the case of a prioritized rule, for the RHS alternative.
A default explicit action for rules can be specified with a
L<default pseudo-rule|Marpa::R2::Scanless::DSL/"Default pseudo-rules">.

=head2 Nulled symbol actions

As mentioned, nulled subtrees are pruned back to their topmost symbol.
Lexemes are never nulled, so a nulled symbol is always the LHS of a rule,
and the action is determined from the rule,
as L<just described|/"Rule actions">.

A complication arises if the symbol appears on the LHS of more than one
nullable rule.  Because the symbol is nulled, the input is no help in determining
which rule to use.  The rule whose semantics are used for a nulled symbol
is determined as follows:

=over 4

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

=item * If one of the nullable rules is a empty rule (a rule with zero RHS symbols),
then the empty rule's semantics are used.

=item * 
In the remaining case,
two or more of the rules have different action names,
but none of the rules in the set is an empty rule.
When this happens, Marpa throws an exception.
One easy way
to fix the issue,
to add an empty rule with the intended semantics.

=back

In determining whether the semantics of two nullable rules
are "the same",
blessing is taken into account.
Two rules are considered to have different semantics if
they are blessed differently.
For more details,
see L<the document on
null semantics|Marpa::R2::Semantics::Null>.

=head1 Blessings

Part of a rule or lexeme's action may be a blessing.
A blessing is the name of a Perl package.
If the action is not a rule evaluation closure, the value
of the action will be blessed into that package.
In the case of a rule evaluation closure,
the argument containing its child values will be blessed
into that package.

Only Perl objects pointed to by references can be blessed,
and it is a fatal error to try to use a blessing with an inappropriate
action.
When an action or action name cannot be blessed, its description
in this document
will indicate that.

Implicitly, an action is not blessed.
Explicity blessings are made using 
the C<bless> adverb.
The C<bless> adverb is allowed

=over 4

=item * for alternatives of prioritized G1 rules;

=item * for quantified G1 rules;

=item * for lexemes;

=item * for the default lexeme statement;

=item * and for the default pseudo-rule.

=back

A G0 rule cannot have a C<bless> adverb.

The value of a C<bless> adverb is called a B<blessing>.
If the blessing is a Perl word
(a string of alphanumerics or underscores),
the name of the class will be formed by prepending
the value of L<the C<bless_package>
named argument|Marpa::R2::Scanless::G/"bless_package">, followed
by a double colon ("C<::>").

If the blessing begins with a double colon ("C<::>"), it is a
reserved blessing.
The reserved blessings are as follows:

=over 4

=item C<::undef>

The rule or lexeme will not be blessed.
By default, both
rules and lexemes are not blessed.

=item C<::lhs>

A blessing of C<::lhs> causes the result to be blessed into
a class whose name is based on the LHS of the rule.
A blessing of C<::lhs> is not allowed for a lexeme.

The class will be the name of the LHS with whitespace
changed to an underscore.
(As a reminder, the whitespace in symbol names will have been normalized,
with leading and trailing whitespace removed,
and all other whitespace sequences changed to a single ASCII space.)
When a C<::lhs> blessing value applies to a rule, it is a fatal
error if the LHS contains anything other than alphanumerics
and whitespace.
In particular, the LHS cannot already contain an underscore ("C<_>").
The C<::lhs> blessing is most useful in a default rule.

=item C<::name>

For a lexeme, the C<::name> reserved blessing
causes it to be blessed into
a class whose name is based on the name of the lexeme.
The C<::name> blessing is not allowed for a rule.

The class is derived from the symbol name in the same way,
and subject to the same restrictions,
as described above for deriving a class name from the LHS
of a rule.
The C<::name> reserved blessing is most useful in
the lexeme default rule.

=back

If any rule or lexeme of a SLIF grammar has
a blessing other than C<::undef>,
a C<bless_package> is required,
and failure to specify one results in
a fatal error.

=head1 Explicit actions

There are four kinds of explicit action name:

=over 4

=item * Array descriptors

=item * Reserved action names

=item * Perl identifiers

=item * Perl names

=back

These are detailed in the sections that follow.

=head1 Array descriptor actions

=for Marpa::R2::Display
name: SLIF DSL synopsis
partial: 1
normalize-whitespace: 1

    lexeme default = action => [start,length,value] bless => ::name

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

If an action is enclosed in square brackets, it is an B<array descriptor>,
and the value of the lexeme or rule will be an array.
Inside the array descriptor should a comma separated list of zero or more array
descriptor items.
The B<array descriptor items> are keywords that describe how the array is to be filled
out.

If the array descriptor is an empty pair of square brackets ("C<[]>"),
then there are zero array descriptor items,
and the value will be an empty array.
Otherwise the "array descriptor item" keywords are interpreted as lists
and those lists are used to fill out the 
array.

=over 4

=item C<length>

The C<length> array descriptor item puts
a single-element list into the array.
That one element will be the length of the rule or lexeme.
Length is in characters.

=item C<start>

The C<length> array descriptor item puts
a single-element list into the array.
That one element will be
the start location of the rule or lexeme into the array.
The start location is an offset in the input string.
The elements of the C<length> and C<start> descriptors are defined
such that the end location
is always start location plus length.

=item C<value>

For a rule,
The C<value> array descriptor item puts
a list of zero or more elements into the array.
The list will contain
the values of
the rule's children, in left-to-right order.

For a lexeme, 
The C<value> array descriptor item puts
a single-element list into the array.
That one element
will be a list
containing a single element,
the token value of the lexeme.

=item C<values>

The C<value> and C<values> array descriptor items are synonyms,
and may be used interchangeably for both rules and lexemes.

=back

=head2 Example

The array descriptor item keywords fill out the array in
the order in which they appear in the the array descriptor.
For example, if we are dealing with a rule,
and the array descriptor is "C<[start,length,value]>",
then the return value is an reference to an array,
whose length will vary, but which will be contain least
two elements.
The first element will be the start location in the
input string of this rule instance,
and the second will be its length.
The remaining elements will be
the values of the rule's RHS children,
in lexical order,
as computed according to the semantics
of those children.
If the rule is nulled, the array will contain only the two elements
indicating start location and length.

=head1 Reserved action names

If the action value begins with a double colon ("C<::>"),
it is a reserved action.
The following are recognized:

=over 4

=item * C<::array>

C<::array> is equivalent to C<[values]>.
This means that, for both lexemes and rules,
the actions C<[values]>, C<[value]> and C<::array>
will do exactly the same thing.

=item * C<::first>

The value of the rule is that of the rule's first child.
If there is no such child, the value is a Perl C<undef>.
It is a fatal error if a 
rule with a C<::first> action
is blessed.
It is also a fatal error to use a C<::first> action
with a lexeme.

=item * C<::undef>

The value of the rule or lexeme is 
a Perl C<undef>.
It is a fatal error if a 
rule with an C<::undef> action
is blessed.

=back

=head1 Perl identifiers as action names

If the action value is a Perl identifier,
it is treated as the name of a Perl variable,
but one which still must be fully qualified by adding a package name.
For this purpose, a Perl identifier is a sequence of one or more alphanumerics
and underscores.
To successfully resolve to actions,
Perl identifiers must be resolved to Perl names,
as L<described below|/"Resolving Perl identifiers to Perl names">.

=head1 Perl names as action names

For this purpose, a Perl name is
is a series of two or more Perl identifiers
separated by double colons ("C<::>").
Note that, by this definition, a Perl name cannot start with a double colon.
Action names starting with double colons
are always treated as a reserved
action names.

Action names which are Perl names by this definition are
treated as they were fully qualified Perl names.
Fully qualified Perl names are resolved to variables in Perl's namespace,
L<as described below|/"Resolving Perl names to Perl variables">.

=head1 The semantics package

To resolve Perl identifiers to Perl names,
a semantics package must be defined.
The semantics package can be defined using the
L<SLIF recognizer's C<semantics_package> named
argument|Marpa::R2::Scanless:R/"semantics_package">,
or it can be taken from the argument to the first C<value()>
call of the parse series.
The C<semantics_package> named argument takes precedence.

If the arguments to the C<value()> method are used to specify
the semantics package, within a parse series they must consistently
specify the same package.
For details see the description of
L<SLIF recognizer's C<value()>
method|Marpa::R2::Scanless:R/"value()">.

If the user wants the Perl variables implementing the semantics
in the C<main> namespace,
she can specify
C<"main">
as the semantics package.
But it is usually good practice to keep
Perl variables intended for use by Marpa's semantics
in their own namespace,
especially if the application is not small.

=head1 Resolving Perl identifiers to Perl names

A Perl identifier is resolved to a Perl name by prepending
the semantic package, followed by a double colon ("C<::>").
For an Perl identifier to resolve successfully
to a Perl name,
a semantics package must be defined.

For example, if the action value
is "C<some_var>", the action value will be regarded as a Perl identifer.
If the semantics package is "C<My_Actions>", Marpa will convert the action
value to "C<My_Actions::some_var>", and hand
it on for processing as a fully qualified Perl name.

=head1 Resolving Perl names to Perl variables

Once Marpa has a fully qualified Perl name, it looks in Perl's symbol tables for
a Perl variable with that name,
either the name of a subroutine, or of a scalar.
It is important to note that for the purposes of Perl's symbol tables,
and therefore for the purposes of Marpa's resolution of Perl names,
references are scalars.

If Marpa finds a Perl subroutine with that fully qualified Perl name,
the action name is resolved to that subroutine,
which then becomes a B<rule evaluation closure>.
If Marpa does not find
a Perl subroutine with that name,
but does find a Perl scalar with that name,
the action name is resolved to that Perl scalar.
(Again, for this purpose a Perl reference is a kind of Perl scalar.)

=head1 Executing rule evaluation closures

A rule evaluation closure action is always called in scalar context,
and its return value will be used as the value of its node.
Arguments to the rule evaluation closure will be as follows:

=over 4

=item *

If the rule is not nulled and is not blessed,
the second and subsequent arguments are the child values in lexical order.

=item *

If the rule is nulled, there will be only one argument:
the, first, per-parse argument.

=item *

If according to the semantics, the rule is blessed and
is not nulled,
the closure will always have exactly two arguments.
The first will be the per-parse argument,
and the second will be a blessed array that contains
the child values in lexical order.
(This grouping of child values into an array
is required in order to allow the blessing to stay in effect.)

=back

Note that in each of these cases,
the first argument of a rule evaluation closure is the per-parse argument.

=head1 Quanitifed rule nodes

Everything just said about rule nodes
applies to nodes for
L<quantified
rules|Marpa::R2::Scanless::DSL/"Quanitifed rules">.
But there is a difference between quantified rules
and others, and it a big one if you are writing a rule
evaluation closure.

In other rules, the right hand side
is fixed in length,
and therefore the number of child nodes is known in advance.
This is not the case with a quantified rule.
The rule evaluation closure
for a quantified rule
must be capable of
dealing with
a variable number of arguments.

=head1 Action context

=for Marpa::R2::Display
name: SLIF action context synopsis
normalize-whitespace: 1

    sub do_S {
        my ($action_object) = @_;
        my $rule_id         = $Marpa::R2::Context::rule;
        my $slg             = $Marpa::R2::Context::slg;
        my ( $lhs, @rhs ) =
            map { $slg->symbol_display_form($_) } $slg->rule_expand($rule_id);
        $action_object->{text} =
              "rule $rule_id: $lhs ::= "
            . ( join q{ }, @rhs ) . "\n"
            . "locations: "
            . ( join q{-}, Marpa::R2::Context::location() ) . "\n";
        return $action_object;
    } ## end sub do_S

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

In addition to the per-parse argument
and their child arguments,
rule evaluation closures also have access
to B<context variables>.

=over

=item * C<$Marpa::R2::Context::grammar> is set to
the grammar being parsed.

=item * C<$Marpa::R2::Context::rule> is the ID of the
current rule.
Given the rule ID, an application can find
its LHS and RHS symbols using
L<the SLIF grammar's C<rule()> method|Marpa::R2::Scanless::G/"rule">.

=item * C<Marpa::R2::Context::location()> returns the start
and end locations of the current rule.

=back

=head1 Bailing out of parse evaluation

=for Marpa::R2::Display
name: SLIF bail synopsis
normalize-whitespace: 1

    my $bail_message = "This is a bail out message!";

    sub do_bail_with_message_if_A {
        my ($action_object, $terminal) = @_;
        Marpa::R2::Context::bail($bail_message) if $terminal eq 'A';
    }

    sub do_bail_with_object_if_A {
        my ($action_object, $terminal) = @_;
        Marpa::R2::Context::bail([$bail_message]) if $terminal eq 'A';
    }

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

=head1 Perl scalars as actions

If a Perl scalar is the action,
it becomes the value of the node, as is.
References are scalars in this context, so that,
for example the value of the node could be a reference to an array.

Another possiiblity is that the Perl scalar action is a reference to code.
What happens in this case is very different from the case where the action
is a rule evaluation closure.
A rule evaluation closure is executed to produce the value of the node.
In contrast, the reference to a subroutine is B<NOT> executed -- it becomes the
value of the node directly.

Assuming no trickery, such as use of Perl's C<local> keyword, takes place,
resolution to a Perl scalar will always resolve to a single, global scalar.
Any modification of this scalar will be seen
by other nodes of the current parse,
and by other parses.
All this suggests that,
as a matter of good practice,
Perl scalar actions be used only as constants.

For example,
assume that actions are in a package named C<My_Actions>,
which contains a hash reference named C<empty_hash>, 

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

        package My_Actions;
        our $empty_hash = {};

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

It can be tempting, in building objects which are hashes,
to start with a left node whose action is C<empty_hash>
and to add contents to it as the object is passed up the evaluation
tree.
But C<$empty_hash> points to a single hash object.
This single hash object will shared by all nodes,
with all nodes seeing each other's changes.
Worse, all Marpa parsers which use the same C<My_Actions>
namespace will share the same hash object.
The correct way to define an
C<empty_hash> action that
initializes an empty hash is as a rule
evaluation closure 
that returns C<{}>.

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

        sub My_Actions::empty_hash { return {}; }

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

=head1 Visibility of Perl object actions

Most application do not manipulate the Perl symbol table at runtime,
and do not make use of Perl's C<local> keyword for declarations.
Applications which use the Perl global namespace in conventional ways,
and which use the same names to point to the same variables
throughout Marpa execution,
can ignore questions about the visibility
of the Perl variables used in actions.

Less conventional applications should be aware that,
for resolution from a Perl name to a Perl variable to take place,
that Perl name must
refer to the intended variable,
and this variable must be visible,
at Parse Series Setup Time.
Parse Series Setup Time occurs during
the first call to a recognizer's L<C<value()>|Marpa::R2::Scanless::R/"value()">
method of the parse series.
More details about Parse Series Setup Time
can be found in
L<the document that describes the processing phases of Marpa's
semantics|Marpa::R2::Semantics::Phases>.

=head1 The per-parse argument

The first argument of every rule evaluation closure is
the B<per-parse> argument.
This is taken from

=over 4

=item * The result of returned by per-parse constructor, if there is one.

=item * Otherwise, the argument to the SLIF recognizer's C<value()> method, if there is one.

=item * If not otherwise specified, the per-parse argument is an empty hash.

=back

The per-parse argument is destroyed once the evaluation of the parse tree is finished.
Between creation and destruction, the per-parse argument is not touched by Marpa's internals --
it is reserved for use by the application.

The primary way of passing data while evaluating a parse tree is purely functional --
results from child nodes are passed up to parent nodes.
Applications can use
the per-parse argument for data which does not conveniently fit the functional model.
Symbol tables are
one common example of data that is best handled outside the functional model.

=head1 The per-parse constructor

The per-parse constructor is the C<new()> method of the semantics package.
If there is no semantics package, or if it has no C<new()> method,
there is no per-parse constructor.

The per-parse constructor is called with one argument.
This argument is the argument of the
the SLIF recognizer's C<value()> method, if one was defined.
Otherwise it is the name of the semantics package.

The result returned by the per-parse constructor becomes the per-parse argument.
The per-parse constructor is called
in the Tree Setup Phase.

=head1 Parse order

If a parse is ambiguous, all parses are returned,
with no duplication.
By default, the order is arbitrary, but
it is also possible to control the order.
Details are in L<the document
on parse order|Marpa::R2::Semantics::Order>.

=head1 Infinite loops

Grammars with infinite loops (cycles)
are generally regarded as useless in practical applications.
Due to lack of interest,
the SLIF does not currently support them,
altougth Libmarpa itself, Marpa's thin interface and the NAIF all do.
Those interested in knowing more can look at L<the
document on the NAIF's support of infinitely ambiguous
grammars|Marpa::R2::NAIF::Semantics::Infinite>.

=head1 Copyright and License

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

  Copyright 2013 <NAME>
  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<commit_msg>Work on semantics documentation: t+<commit_after># Copyright 2013 <NAME>
# 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 - How the SLIF evaluates parses

=head1 Synopsis

=for Marpa::R2::Display
name: SLIF full synopsis
normalize-whitespace: 1

    use Marpa::R2;

    my $grammar = Marpa::R2::Scanless::G->new(
        {   bless_package => 'My_Nodes',
            source        => \(<<'END_OF_SOURCE'),
    :default ::= action => [values] bless => ::lhs
    lexeme default = action => [start,length,value] bless => ::name

    :start ::= Script
    Script ::= Expression+ separator => comma
    comma ~ [,]
    Expression ::=
        Number bless => primary
        | '(' Expression ')' bless => paren assoc => group
       || Expression '**' Expression bless => exponentiate assoc => right
       || Expression '*' Expression bless => multiply
        | Expression '/' Expression bless => divide
       || Expression '+' Expression bless => add
        | Expression '-' Expression bless => subtract

    Number ~ [\d]+
    :discard ~ whitespace
    whitespace ~ [\s]+
    # allow comments
    :discard ~ <hash comment>
    <hash comment> ~ <terminated hash comment> | <unterminated
       final hash comment>
    <terminated hash comment> ~ '#' <hash comment body> <vertical space char>
    <unterminated final hash comment> ~ '#' <hash comment body>
    <hash comment body> ~ <hash comment char>*
    <vertical space char> ~ [\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
    <hash comment char> ~ [^\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
    END_OF_SOURCE
        }
    );


    my $recce = Marpa::R2::Scanless::R->new( { grammar => $grammar } );

    my $input = '42*2+7/3, 42*(2+7)/3, 2**7-3, 2**(7-3)';
    $recce->read(\$input);
    my $value_ref = $recce->value();
    die "No parse was found\n" if not defined $value_ref;

    # Result will be something like "86.33... 126 125 16"
    # depending on the floating point precision
    my $result = ${$value_ref}->doit();

    package My_Nodes;

    sub My_Nodes::primary::doit { return $_[0]->[0]->doit() }
    sub My_Nodes::Number::doit  { return $_[0]->[2] }
    sub My_Nodes::paren::doit   { my ($self) = @_; $self->[1]->doit() }

    sub My_Nodes::add::doit {
        my ($self) = @_;
        $self->[0]->doit() + $self->[2]->doit();
    }

    sub My_Nodes::subtract::doit {
        my ($self) = @_;
        $self->[0]->doit() - $self->[2]->doit();
    }

    sub My_Nodes::multiply::doit {
        my ($self) = @_;
        $self->[0]->doit() * $self->[2]->doit();
    }

    sub My_Nodes::divide::doit {
        my ($self) = @_;
        $self->[0]->doit() / $self->[2]->doit();
    }

    sub My_Nodes::exponentiate::doit {
        my ($self) = @_;
        $self->[0]->doit()**$self->[2]->doit();
    }

    sub My_Nodes::Script::doit {
        my ($self) = @_;
        return join q{ }, map { $_->doit() } @{$self};
    }

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

=head1 About this document

This document describes the semantics for
Marpa's primary interface, the SLIF.

=head1 What is semantics?

A parser is an algorithm
that takes a string of symbols (tokens or characters) and finds a structure
in it.
Traditionally, that structure is a tree.

Rarely is an application interested only in the tree.
Usually the idea is that the string "means" something:
the idea is that the string has a B<semantics>.
Traditionally and most often, the tree
is as an intermediate step in producing a value,
a value which represents the "meaning" or "semantics" of the string.

"Evaluating" a tree means finding its semantics.
The rest of this document describes Marpa's methods for evaluating trees.
Those of you who have dealt with other traditional parsers, such as yacc and bison,
will find Marpa's approach familiar.

=head1 Nodes

In a parse tree, nodes are points where the tree branches or terminates.
Tree terminations are also called terminals or "leaves".

Every rule instance in a Marpa parse is reprsented by a branch point (or "node")
in the tree.
The topmost node of a tree is its "root node".
(Trees are easiest to draw upside down, so traditionally in programming,
the top of a tree is its root.)

A node, or branch point, "branches" into zero or more "child nodes".
The node just above a child node,
the one from which the child node branches out,
is called its parent node.

If the node is for a BNF rule,
the parent node is the LHS of the rule,
and the child nodes are the RHS of the rule.
If the node is for a quantified rule,
the parent node is the LHS of the quantified rule,
and the child nodes are the items of the quantified sequence of symbol on the
right hand side.
If the node is for a lexeme,
the node represents the lexeme's symbol
and there will be no child nodes.

A parent node can have zero or more children.
Rules with zero children are nulled rules,
and are "leaf nodes".
Leaf nodes are also called B<terminals>.
In Marpa's parse trees, every terminal is either
a lexeme or a nulled rule.

In Marpa,
evaluation only takes place within the structural (G1) subgrammar,
and the descriptions of the behaviors of rules and lexemes below
applies only to the G1 subgrammar.
G0 rules and terminal symbols do not become nodes
in the parse tree,
and are never evaluated.

=head1 The order of node evaluation

The nodes of a Marpa parse tree are
evaluated recursively, left-to-right and bottom-up.
This means that,
when a parent node is evaluated,
the values of all child nodes are known
and available for use by the semantics.
The final value of a parse is the value of the top node
of the parse tree.

=head1  Parse trees and parse series

Because Marpa allows ambiguous parsing,
each parse can produce a B<parse series> --
a series of zero or more parse trees,
each with its own parse result.
The first call to the
L<the SLIF recognizer's C<value()>
method|Marpa::R2::Scanless::Recognizer/"value()">
after the recognizer is created is the
start of the first parse series,
and Parse Series Setup Phase takes place
at this point.

The first parse series continues until there is
a call to the
L<the C<series_restart()>
method|Marpa::R2::Scanless::R/"series_restart()">
or until the recognizer is destroyed.
An application is usually interested in only one
parse series.

The C<series_restart()> method starts a new parse series.
The Parse Series Setup Phase for that parse series will take
place during
the next call of the SLIF recognizer's C<value()> method.

The Parse Series Setup Phase
is one of several phases in which the semantics are executed.
Applications will find that the order in which
these phases occurs "just works".
But in some cases the details will matter.
Applications whose behavior might depend on the details
include those which make unusual use of side effects in the semantics;
and those which alter their symbol tables at runtime.
A full description of phases of Marpa'a semantic processing
is in
L<a separate
document|Marpa::R2::Semantics::Phases>.

=head1 Nulled subtrees

A nulled subtree is a subtree of the parse tree formed by a nulled node and its direct and
indirect child nodes.
(All these child nodes will also be nulled nodes.)
Before evaluation,
Marpa prunes all nulled subtrees back to their topmost nulled
node.
Of all the ways of dealing with nulled subtrees, this is the
simplest and
Marpa's users have found it a natural approach.
More detail on the semantics of nulled symbols and subtrees
can be found in
L<a separate document|Marpa::R2::Semantics::Null>.

=head1 Actions and how Marpa finds them

The way in which the SLIF finds the value of a node is called that node's B<action>.
Actions can be explicit or implicit.
An explicit action is one that is explicitly specified by the application,
in one of the ways
to be described below.
A node's implicit action is the one it performs if it has no
explicit action.

=head2 Lexeme actions

The implicit action for a lexeme is to return
its literal value in the input stream, as a string.
An explicit default action name for lexemes may be set using the
L<the lexeme default statement|Marpa::R2::Scanless::DSL/"Lexeme default statement">.

=head2 Rule actions

The implicit action for a rule is to return a Perl C<undef>.
An explicit action for a rule can be specified using
L<the C<action> adverb|Marpa::R2::Scanless::DSL/"action">
for the its RHS alternative.
A default explicit action for rules can be specified with a
L<default pseudo-rule|Marpa::R2::Scanless::DSL/"Default pseudo-rules">.

=head2 Nulled symbol actions

As mentioned, nulled subtrees are pruned back to their topmost symbol.
Lexemes are never nulled, so a nulled symbol is always the LHS of a rule,
and the action is determined from the rule,
as L<just described|/"Rule actions">.

A complication arises if the symbol appears on the LHS of more than one
nullable rule.  Because the symbol is nulled, the input is no help in determining
which rule to use.  The rule whose semantics are used for a nulled symbol
is determined as follows:

=over 4

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

=item * If one of the nullable rules is a empty rule (a rule with zero RHS symbols),
then the empty rule's semantics are used.

=item * 
In the remaining case,
two or more of the rules have different action names,
but none of the rules is an empty rule.
When this happens, Marpa throws an exception.
One easy way
to fix the issue,
to add an empty rule with the intended semantics.

=back

In determining whether the semantics of two nullable rules
are "the same",
the blessing is taken into account.
Two rules are considered to have different semantics if
they are blessed differently.
The SLIF's null semantics are described in more detail
L<in a separate document|Marpa::R2::Semantics::Null>.

=head1 Blessings

Part of a rule or lexeme's action may be a blessing.
A blessing is the name of a Perl package.
If the action is not a rule evaluation closure, the value
of the action will be blessed into that package.
In the case of a rule evaluation closure,
the argument containing its child values will be blessed
into that package.

Only Perl objects pointed to by references can be blessed,
and it is a fatal error to try to use a blessing with an inappropriate
action.
When an action or action name cannot be blessed, its description
in this document
indicates that.

Implicitly, an action is not blessed.
Also, it is a fatal error to bless the implicit action.
Explicit blessings are made using 
the C<bless> adverb.
The C<bless> adverb is allowed

=over 4

=item * for RHS alternatives;

=item * for lexemes;

=item * for the default lexeme statement;

=item * and for the default pseudo-rule.

=back

A G0 rule cannot have a C<bless> adverb.

The value of a C<bless> adverb is called a B<blessing>.
If the blessing is a Perl word
(a string of alphanumerics or underscores),
the name of the class will be formed by prepending
the value of L<the C<bless_package>
named argument|Marpa::R2::Scanless::G/"bless_package">, followed
by a double colon ("C<::>").

If the blessing begins with a double colon ("C<::>"), it is a
reserved blessing.
The reserved blessings are as follows:

=over 4

=item C<::undef>

The rule or lexeme will not be blessed.
For both rules and lexemes,
the implicit blessing is C<::undef>.

=item C<::lhs>

The rule is blessed into
a class whose name is based on the LHS of the rule.
A blessing of C<::lhs> is not allowed for a lexeme.

The class will be the name of the LHS with whitespace
changed to an underscore.
(As a reminder, the whitespace in symbol names will have been normalized,
with leading and trailing whitespace removed,
and all other whitespace sequences changed to a single ASCII space.)
When a C<::lhs> blessing value applies to a rule, it is a fatal
error if the LHS contains anything other than alphanumerics
and whitespace.
In particular, the LHS cannot already contain an underscore ("C<_>").
The C<::lhs> blessing is most useful in a default pseudo-rule.

=item C<::name>

The lexeme
is blessed into
a class whose name is based on the name of the lexeme.
The C<::name> blessing is not allowed for a rule.

The class is derived from the symbol name in the same way,
and subject to the same restrictions,
as described above for deriving a class name from the LHS
of a rule.
The C<::name> reserved blessing is most useful in
the lexeme default statement.

=back

If any rule or lexeme of a SLIF grammar has
a blessing other than C<::undef>,
a C<bless_package> is required,
and failure to specify one results in
a fatal error.

=head1 Explicit actions

There are four kinds of explicit action name:

=over 4

=item * Array descriptors

=item * Reserved action names

=item * Perl identifiers

=item * Perl names

=back

These are detailed in the sections that follow.

=head1 Array descriptor actions

=for Marpa::R2::Display
name: SLIF DSL synopsis
partial: 1
normalize-whitespace: 1

    lexeme default = action => [start,length,value] bless => ::name

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

If an action is enclosed in square brackets, it is an B<array descriptor>,
and the value of the lexeme or rule will be an array.
Inside the array descriptor is a comma separated list of zero or more array item
descriptors.
The B<array item descriptors> are keywords that describe how the array is to be filled
out.

If the array descriptor is an empty pair of square brackets ("C<[]>"),
then there are zero array item descriptors,
and the value will be an empty array.
Otherwise the array item descriptors are interpreted as lists
and those lists are used to fill out the 
array.

=over 4

=item C<length>

The C<length> array item descriptor puts
a single-element list into the array.
That one element will be the length of the rule or lexeme.
Length is in characters.

=item C<start>

The C<start> array item descriptor puts
a single-element list into the array.
That one element will be
the start location of the rule or lexeme into the array.
The start location is an offset in the input string.
The elements of the C<length> and C<start> item descriptors are defined
such that the end location
is always start location plus length.

=item C<value>

For a rule,
the C<value> array item descriptor puts
a list of zero or more elements into the array.
The list will contain
the values of
the rule's children, in left-to-right order.

For a lexeme, 
The C<value> array item descriptor puts
a single-element list into the array.
That one element
will be a list
containing a single element,
the token value of the lexeme.

=item C<values>

The C<value> and C<values> array item descriptors are synonyms,
and may be used interchangeably for both rules and lexemes.

=back

=head2 Example

The array item descriptors fill out the array in
the order in which they appear in the the array descriptor.
For example, if we are dealing with a rule,
and the array descriptor is "C<[start,length,value]>",
then the return value is an reference to an array,
whose length will vary, but which will be contain least
two elements.
The first element will be the start location in the
input string of this rule instance,
and the second will be its length.
The remaining elements will be
the values of the rule's RHS children,
in lexical order.
If the rule is nulled, the array will contain only two elements:
start location and length.

=head1 Reserved action names

If the action value begins with a double colon ("C<::>"),
it is a reserved action.
The following are recognized:

=over 4

=item * C<::array>

C<::array> is equivalent to C<[values]>.
This means that, for both lexemes and rules,
the actions C<[values]>, C<[value]> and C<::array>
will do exactly the same thing.

=item * C<::first>

The value of the rule is that of the rule's first child.
If there is no such child, the value is a Perl C<undef>.
It is a fatal error if a 
rule with a C<::first> action
is blessed.
It is also a fatal error to use a C<::first> action
with a lexeme.

=item * C<::undef>

The value of the rule or lexeme is 
a Perl C<undef>.
It is a fatal error if a 
rule with an C<::undef> action
is blessed.

=back

=head1 Perl identifiers as action names

An action name is considered to be
a Perl identifier, if it is a sequence of one or more alphanumerics
and underscores.
If the action name is a Perl identifier,
it is treated as the name of a Perl variable.
To successfully resolve to actions,
Perl identifiers must be resolved to Perl names,
as L<described below|/"Resolving Perl identifiers to Perl names">.

=head1 Perl names as action names

For this purpose, a Perl name is
is a series of two or more Perl identifiers
separated by double colons ("C<::>").
Note that, by this definition, a Perl name cannot start with a double colon.
Action names starting with double colons
are always treated as a reserved
action names.

Action names which are Perl names by this definition are
treated as they were fully qualified Perl names.
Fully qualified Perl names are resolved to variables in Perl's namespace,
L<as described below|/"Resolving Perl names to Perl variables">.

=head1 The semantics package

To resolve Perl identifiers to Perl names,
a semantics package must be defined.
The semantics package can be defined using the
L<SLIF recognizer's C<semantics_package> named
argument|Marpa::R2::Scanless:R/"semantics_package">,
or it can be taken from the argument to the first C<value()>
call of the parse series.
The C<semantics_package> named argument takes precedence.

If the arguments to the C<value()> method are used to specify
the semantics package, within a parse series they must consistently
specify the same package.
For details, see the description of
L<SLIF recognizer's C<value()>
method|Marpa::R2::Scanless:R/"value()">.

If the user wants the Perl variables implementing the semantics
in the C<main> namespace,
she can specify
C<"main">
as the semantics package.
But it is usually good practice to keep
Perl variables intended for use by Marpa's semantics
in their own namespace,
especially if the application is not small.

=head1 Resolving Perl identifiers to Perl names

A Perl identifier is resolved to a Perl name by prepending
the semantic package, followed by a double colon ("C<::>").
For a Perl identifier to resolve successfully
to a Perl name,
a semantics package must be defined.

For example, if the action name
is "C<some_var>", the action name will be regarded as a Perl identifer.
If the semantics package is "C<My_Actions>", Marpa will convert the action
name to "C<My_Actions::some_var>", and hand
it on for processing as a fully qualified Perl name.

=head1 Resolving Perl names to Perl variables

Once Marpa has a fully qualified Perl name, it looks in Perl's symbol tables for
a Perl variable with that name,
either the name of a subroutine, or of a scalar.
It is important to note that for the purposes of Perl's symbol tables,
and therefore for the purposes of Marpa's resolution of Perl names,
references are scalars.

If Marpa finds a Perl subroutine with that fully qualified Perl name,
the action name is resolved to that subroutine,
which then becomes a B<rule evaluation closure>.
If Marpa does not find
a Perl subroutine with that name,
but does find a Perl scalar with that name,
the action name is resolved to that Perl scalar.
(Again, for this purpose a Perl reference is a kind of Perl scalar.)

=head1 Executing rule evaluation closures

A rule evaluation closure action is always called in scalar context,
and its return value will be used as the value of its node.
Arguments to the rule evaluation closure will be as follows:

=over 4

=item *

If the rule is not nulled and is not blessed,
the second and subsequent arguments are the values of its child nodes, in lexical order.

=item *

If the rule is nulled, there will be only one argument:
the, first, per-parse argument.

=item *

If the rule is blessed, and
is not nulled,
the closure will always have exactly two arguments.
The first will be the per-parse argument,
and the second will be a blessed array that contains
the child values in lexical order.
(The grouping of child values into an array
is required in order to allow the blessing to stay in effect.)

=back

Note that, in every case,
the first argument of a rule evaluation closure is the per-parse argument.

=head1 Quantified rule nodes

Everything just said about rule nodes
applies to nodes for
L<quantified
rules|Marpa::R2::Scanless::DSL/"Quanitified rules">.
But there is a difference between quantified rules
and others, and it a big one if you are writing a rule
evaluation closure.

In other rules, the right hand side
is fixed in length,
and therefore the number of child nodes is known in advance.
This is not the case with a quantified rule.
The rule evaluation closure
for a quantified rule
must be capable of
dealing with
a variable number of child nodes.

=head1 Action context

=for Marpa::R2::Display
name: SLIF action context synopsis
normalize-whitespace: 1

    sub do_S {
        my ($action_object) = @_;
        my $rule_id         = $Marpa::R2::Context::rule;
        my $slg             = $Marpa::R2::Context::slg;
        my ( $lhs, @rhs ) =
            map { $slg->symbol_display_form($_) } $slg->rule_expand($rule_id);
        $action_object->{text} =
              "rule $rule_id: $lhs ::= "
            . ( join q{ }, @rhs ) . "\n"
            . "locations: "
            . ( join q{-}, Marpa::R2::Context::location() ) . "\n";
        return $action_object;
    } ## end sub do_S

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

In addition to the per-parse argument
and their child values,
rule evaluation closures also have access
to B<context variables>.

=over

=item * C<$Marpa::R2::Context::slg> is set to
the SLIF grammar being parsed.

=item * C<$Marpa::R2::Context::rule> is the ID of the
current rule.
Given the rule ID, an application can find
its LHS and RHS symbols using
L<the SLIF grammar's C<rule()> method|Marpa::R2::Scanless::G/"rule">.

=item * C<Marpa::R2::Context::location()> returns the start
and end locations of the current rule.

=back

=head1 Bailing out of parse evaluation

=for Marpa::R2::Display
name: SLIF bail synopsis
normalize-whitespace: 1

    my $bail_message = "This is a bail out message!";

    sub do_bail_with_message_if_A {
        my ($action_object, $terminal) = @_;
        Marpa::R2::Context::bail($bail_message) if $terminal eq 'A';
    }

    sub do_bail_with_object_if_A {
        my ($action_object, $terminal) = @_;
        Marpa::R2::Context::bail([$bail_message]) if $terminal eq 'A';
    }

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

=head1 Perl scalars as actions

If a Perl scalar is the action,
it becomes the value of the node, as is.
References are scalars in this context so that,
for example, the value of the node could be a reference to an array.

Another possiiblity is that the Perl scalar action is a reference to code.
What happens in this case is very different from the case where the action
is a rule evaluation closure.
A rule evaluation closure is executed to produce the value of the node.
In contrast, the reference to a subroutine is B<NOT> executed -- it becomes the
value of the node directly.

Assuming no trickery, such as use of Perl's C<local> keyword, takes place,
resolution to a Perl scalar will always resolve to a single, global scalar.
Any modification of this scalar will be seen
by other nodes of the current parse,
and by other parses.
All this suggests that,
as a matter of good practice,
Perl scalar actions be used only as constants.

For example,
assume that actions are in a package named C<My_Actions>,
which contains a hash reference named C<empty_hash>, 

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

        package My_Actions;
        our $empty_hash = {};

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

It can be tempting, in building objects which are hashes,
to start with a left node whose action is C<empty_hash>
and to add contents to it as the object is passed up the evaluation
tree.
But C<$empty_hash> points to a single hash object.
This single hash object will shared by all nodes,
with all nodes seeing each other's changes.
Worse, all Marpa parsers which use the same C<My_Actions>
namespace will share the same hash object.
The correct way to define an
C<empty_hash> action that
initializes an empty hash is as a rule
evaluation closure 
that returns C<{}>.

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

        sub My_Actions::empty_hash { return {}; }

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

=head1 Visibility of Perl object actions

Most applications do not manipulate the Perl symbol table at runtime,
and do not make use of Perl's C<local> keyword for declarations.
Applications which use the Perl global namespace in conventional ways,
and which use the same names to point to the same variables
throughout Marpa execution,
can ignore questions about the visibility
of the Perl variables used in actions.

Less conventional applications should be aware that,
for resolution from a Perl name to a Perl variable to take place,
that Perl name must
refer to the intended variable,
and this variable must be visible,
at Parse Series Setup Time.
Parse Series Setup Time occurs during
the first call to a recognizer's L<C<value()>|Marpa::R2::Scanless::R/"value()">
method of the parse series.
More details about Parse Series Setup Time
can be found in
L<the document that describes the processing phases of Marpa's
semantics|Marpa::R2::Semantics::Phases>.

=head1 The per-parse argument

The first argument of every rule evaluation closure is
the B<per-parse> argument.
This is taken from

=over 4

=item * The result of returned by per-parse constructor, if there is one.

=item * Otherwise, the argument to the SLIF recognizer's C<value()> method, if there is one.

=item * If not otherwise specified, the per-parse argument is an empty hash.

=back

The per-parse argument is destroyed once the evaluation of the parse tree is finished.
Between creation and destruction, the per-parse argument is not touched by Marpa's internals --
it is reserved for use by the application.

The primary way of passing data while evaluating a parse tree is purely functional --
results from child nodes are passed up to parent nodes.
Applications can use
the per-parse argument for data which does not conveniently fit the functional model.
Symbol tables are
one common example of data that is best handled outside the functional model.

=head1 The per-parse constructor

The per-parse constructor is the C<new()> method of the semantics package.
If there is no semantics package, or if it has no C<new()> method,
there is no per-parse constructor.

The per-parse constructor is called with one argument.
This argument is the argument of the
the SLIF recognizer's C<value()> method, if one was defined.
Otherwise it is the name of the semantics package.

The result returned by the per-parse constructor becomes the per-parse argument.
The per-parse constructor is called
in the Tree Setup Phase.

=head1 Parse order

If a parse is ambiguous, all parses are returned,
with no duplication.
By default, the order is arbitrary, but
it is also possible to control the order.
Details are in L<the document
on parse order|Marpa::R2::Semantics::Order>.

=head1 Infinite loops

Grammars with infinite loops (cycles)
are generally regarded as useless in practical applications.
Due to lack of interest,
the SLIF does not currently support them,
although Libmarpa itself, Marpa's thin interface and the NAIF all do.
Those interested in knowing more can look at L<the
document on the NAIF's support of infinitely ambiguous
grammars|Marpa::R2::NAIF::Semantics::Infinite>.

=head1 Copyright and License

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

  Copyright 2013 <NAME>
  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
{'fraction_non_alphanumeric': 0.07098483935915748, 'fraction_numerical': 0.005954122283216603, 'mean_word_length': 4.053217391304348, 'pattern_counts': {'":': 0, '<': 267, '<?xml version=': 0, '>': 369, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '78505', 'n_tokens_mistral': 16937, 'n_tokens_neox': 16157, 'n_words': 8753}