/ 
Marpa-R2-2.003_002
River stage two • 39 direct dependents • 56 total dependents
/ Marpa::R2::Semantics

NAME

Marpa::R2::Semantics - How Marpa evaluates parses

SYNOPSIS

my $grammar = Marpa::R2::Grammar->new(
    {   start          => 'Expression',
        actions        => 'My_Actions',
        default_action => 'first_arg',
        rules          => [
            { lhs => 'Expression', rhs => [qw/Term/] },
            { lhs => 'Term',       rhs => [qw/Factor/] },
            { lhs => 'Factor',     rhs => [qw/Number/] },
            { lhs => 'Term', rhs => [qw/Term Add Term/], action => 'do_add' },
            {   lhs    => 'Factor',
                rhs    => [qw/Factor Multiply Factor/],
                action => 'do_multiply'
            },
        ],
    }
);
sub My_Actions::do_add {
    my ( undef, $t1, undef, $t2 ) = @_;
    return $t1 + $t2;
}

sub My_Actions::do_multiply {
    my ( undef, $t1, undef, $t2 ) = @_;
    return $t1 * $t2;
}

sub My_Actions::first_arg { shift; return shift; }

my $value_ref = $recce->value;
my $value = $value_ref ? ${$value_ref} : 'No Parse';

OVERVIEW

Marpa's semantics will be familiar to those who have used traditional methods to evaluate parses. A parse is seen as a parse tree. Nodes on the tree are evaluated recursively, bottom-up. Once the values of all its child nodes are known, a parent node is ready to be evaluated. The value of a parse is the value of the top node of the parse tree.

When a Marpa grammar is created, its semantics is specified indirectly, as action names. To produce the values used in the semantics, Marpa must do three things:

  • Determine the action name.

  • Resolve the action name to an action.

  • If the action is a rule evaluation closure, call it to produce the actual result.

An action name and action is also used to create the per-parse-tree variable, as described below.

ACTIONS

Action names resolve to actions. An action can be

  • A Perl closure. When this is associated with a rule, it is called a rule evaluation closure. The closure will be called to produce the value of the action.

  • A constant. The constant is the value of the action.

  • A "whatever" value.

Perl is unable to distinguish reliably between a non-existent value and scalars with an undef value. For safety therefore, the "::undef" reserved action name must be used to specify a constant whose value is a Perl undef.

"WHATEVER" VALUES

A "whatever" value can have any value which is assignable to a Perl scalar. Other than that, a "whatever" value is unspecified. It may be constant, or may vary from instance to instance. If it varies it may do so randomly or according to a pattern. "Whatever" values will usually only be appropriate for cases where the application does not care what the value is.

"Whatever" values are very efficient to implement, and Marpa often defaults to them. The "::whatever" reserved action name can be used to explicitly specify a whatever value.

A "whatever" value may happen to be identical to any other value, and therefore "whatever" values cannot be reliably disinguished from other results. For this reason, whenever a rule has "whatever" semantics, all rules with the same LHS must also have "whatever" semantics. Where this is not the case, Marpa throws an exception.

NODES

Token nodes

For every input token, there is an associated token node. Token nodes are leaf nodes in the parse tree. Tokens always have a token symbol. At lexing time, they can be assigned a token value. If no token value is assigned at lex time, the token value has an "whatever" value. A "whatever" value in one that cannot be relied on. It may, for example, vary from instance to instance, either randomly or according to an arbitrary pattern.

Rule nodes

If a node is not a token node, then it is a rule node. Rule nodes are always associated with a rule. It a rule's action is a rule evaluation closure, it is called at Node Evaluation Time.

The rule evaluation closures's arguments will be a per-parse-tree variable followed, if the rule is not nulled, by the values of its child nodes in lexical order. If the rule is nulled, the child node values will be omitted. A rule evaluation closure action is always called in scalar context.

If the action is a constant, it becomes the value of the rule node. If the action is a rule evaluation closure, its return value becomes the value of the node. If there is no action for a rule node, the rule node has a "whatever" value.

Sequence rule nodes

Some rules are sequence rules. Sequence rule nodes are also rule nodes. Everything said above about rule nodes applies to sequence rule nodes. Specifically, the arguments to the value actions for sequence rules are the per-parse-tree variable followed by the values of the child nodes in lexical order.

The difference (and it is a big one) is that in an ordinary rule, the right hand side is fixed in length, and that length is known when you are writing the code for the value action. In a sequence rule, the number of right hand side symbols is not known until node evaluation time. The rule evaluation closure of a sequence rule must be capable of dealing with a variable number of arguments.

Sequence semantics work best when every child node in the sequence has the same semantics. When that is not the case, writing the sequence using ordinary non-sequence rules should be considered as an alternative.

By default, if a sequence rule has separators, the separators are thrown away before the value action is called. This means that separators do not appear in the @_ array of the rule evaluation closure which is the value action. If the value of the keep rule property is a Perl true value, separators are kept, and do appear in the value action's @_ array.

Null nodes

A null node is a special case of a rule node, one where the rule derives the zero-length, or empty string. When the rule node is a null node, the rule evaluation closure will be called with no child value arguments.

When a node is nulled, it must be as a result of a nullable rule, and the action name and action are those associated with that rule. An ambiguity can arise if there is more than one nullable rule with the same LHS, but a different action name. In that case the action name for the null nodes is that of the empty rule.

The remaining case is that of a set of nullable rules with the same LHS, where 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. To fix the issue, the user can add an empty rule. For more details, see the document on null semantics.

OVERVIEW OF THE SEMANTIC PHASES

Most applications will find that the order in which Marpa executes its semantics "just works". This section describes that order in detail. These details can matter in some applications, for example, those which exploit side effects.

Parse trees, parse results and parse series

When the semantics are applied to a parse tree, it produces a value called a parse result. Because Marpa allows ambiguous parsing, each parse can produce a parse series -- a series of zero or more parse trees, each with its own parse result. The first call to the the recognizer's value method after the recognizer is created is the start of the first parse series. The first parse series continues until there is a call to the the reset_evaluation method or until the recognizer is destroyed. Usually, an application is only interested in a single parse series.

When the reset_evaluation method is called for a recognizer, it begins a new parse series. The new parse series continues until there is another call to the the reset_evaluation method, or until the recognizer is destroyed.

Summary of the phases

While processing a parse series, we have:

  • A Series Setup Phase, which occurs during the first call of the recognizer's value method for that series. It is followed by

  • the processing of zero or more parse trees.

While processing a parse tree, we have:

  • A Tree Setup Phase, which occurs during the call of the recognizer's value method for that parse tree. It is followed by

  • a Tree Traveral Phase.

Node Evaluation Time is the Tree Traversal Phase, as seen from the point of view of each rule node. It is not a separate phase.

THE PHASES IN DETAIL

Series Setup Phase

During the Series Setup Phase all value action names are resolved to value actions -- constants or rule evaluation closures. The rule evaluation closures are never called in the Series Setup Phase. They will be called later, in the Tree Traversal Phase. Also, during the Series Setup Phase, the logic which ranks parse trees is executed.

Tree Setup Phase

In the Tree Setup Phase, the per-parse-tree variable is created. If a constructor was found for the action_object, it is run at this point, and the per-parse-tree variable is its return value. Exactly one Tree Setup Phase occurs for each parse tree.

Tree Traversal Phase

During the Tree Traversal Phase, the rule evaluation closures are called. Node Evaluation Time is the Tree Traversal Phase, as seen from the point of view of the individual nodes of the parse tree.

FINDING THE ACTION FOR A RULE

Marpa finds the action for each rule based on rule and symbol properties and on the grammar named arguments. Specifically, Marpa attempts the following, in order:

  • Resolving an action based on the action property of the rule, if one is defined.

  • Resolving an action based on the lhs property of the rule.

  • If the rule is empty, and the default_empty_action named argument of the grammar is defined, resolving an action based on that named argument.

  • Resolving an action based on the default_action named argument of the grammar, if one is defined.

  • Defaulting to a "whatever" value.

Resolution of action names is described below. If the action property the default_action named argument, or the default_empty_action named argument is defined, but does not resolve successfully, Marpa throws an exception. Marpa prefers to "fast fail" in these cases, because they often indicate a mistake in writing the application.

RESOLVING ACTION NAMES

Action names come from these sources:

  • The default_action named argument of Marpa's grammar.

  • The default_empty_action named argument of Marpa's grammar.

  • The action property of Marpa's rules.

  • The new constructor in the package specified by the action_object named argument of the Marpa grammar.

  • The lhs property of Marpa's rules.

Reserved action names

If the action name begins with the two characters "::", then it is a reserved action name and must be resolved as such. The current reserved action names are "::whatever" and "::undef". If the reserved action name is not one of those, Marpa throws an exception.

Explicit resolution

The recognizer's closures named argument allows the user to directly control the mapping from action names to actions. The value of the closures named argument is a reference to a hash whose keys are action names and whose hash values are CODE refs.

If an action name is the key of an entry in the closures hash, it resolves to the closure referenced by the value part of that hash entry. Resolution via the closures named argument is called explicit resolution.

When explicit resolution is the only kind of resolution that is wanted, it is best to pick a name that is very unlikely to be the name of a Perl closure. Many of Marpa::HTML's action names are intended for explicit resolution only. In Marpa::HTML those action names begin with an exclamation mark ("!"), and that convention is recommended.

Fully qualified action names

If explicit resolution fails, Marpa transforms the action name into a fully qualified Perl name. An action name that contains a double colon ("::") or a single quote ("'") is considered to be a fully qualified name. Any other action name is considered to be a bare action name.

If the action name to be resolved is already a fully qualified name, it is not further transformed. It will be resolved in the form it was received, or not at all.

For bare action names, Marpa tries to qualify them by adding a package name. If the actions grammar named argument is defined, Marpa uses it as the package name. Otherwise, if the action_object grammar named argument is defined, Marpa uses it as the package name. Once Marpa has fully qualified the action name, Marpa looks for a Perl closure with that name.

Marpa will not attempt to resolve an action name that it cannot fully qualify. This implies that, for an action name to resolve successfully, one of these five things must be the case:

  • The action name is one of the reserved action names.

  • The action name resolves explicitly.

  • The action name is fully qualified to begin with.

  • The actions named argument is defined.

  • The action_object named argument is defined.

Marpa's philosophy is to require that the programmer be specific about action names. This can be an inconvenience, but Marpa prefers this to silently executing unintended code.

It can be good practice to keep the rule evaluation closures in their own namespace. But if, for example, the user wants to leave the rule evaluation closures in the main namespace, she can specify "main" as the value of the actions named argument.

THE PER-PARSE-TREE VARIABLE

In the Tree Setup Phase, Marpa creates a per-parse-tree variable. This becomes the first argument of the rule evaluation closures for the rule nodes. If the grammar's action_object named argument is not defined, the per-parse-tree variable is initialized to an empty hash ref.

Most data for the value actions of the rules will be passed up the parse tree. The actions will see the values of the rule node's child nodes as arguments, and will return their own value to be seen as an argument by their parent node. The per-parse-tree variable can be used for data which does not conveniently fit this model.

The lifetime of the per-parse-tree variable extends into the Tree Traversal Phase. During the Tree Traversal Phase, Marpa's internals never alter the per-parse-tree variable -- it is reserved for use by the application.

Action object constructor

If the grammar's action_object named argument has a defined value, that value is treated as the name of a class. The action object constructor is the new method in the action_object class.

The action object constructor is called in the Tree Setup Phase. The return value of the action object constructor becomes the per-parse-tree variable. It is a fatal error if the grammar's action_object named argument is defined, but does not name a class with a new method.

Resolution of the action object constructor is resolution of the action object constructor name. The action object constructor name is formed by concatenating the literal string "::new" to the value of the action_object named argument.

All standard rules apply when resolving the action object constructor name. In particular, bypass via explicit resolution applies to the action object constructor. If the action object constructor name is a hash key in the evaluator's closures named argument, then the value referred to by that hash entry becomes the action object constructor.

If a grammar has both the action and the action_object named arguments defined, all action names except for the action object constructor will be resolved in the action package or not at all. The action object constructor is always in the action_object class, if it is anywhere.

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 the document on parse order.

INFINITE LOOPS

Marpa allows grammars with infinite loops. These are universally considered useless in practical applications. Marpa supports all the semantics for these that should be necessary and more. Because it can handle infinite loops, Marpa can accurately claim to support every grammar that can be written in BNF.

Marpa applies semantics to infinite loops by breaking the loop at some convenient point, so that an infinite regress is prevented. The exact location at which the loop is broken is subject to change.

More could be done. In particular, a precise definition of where loops are broken would allow applications to depend on the details of the structure of infinite loops. But practical interest in this seems non-existent. For those who want to know more, the details are in a separate document.

COPYRIGHT AND LICENSE

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