Jeffrey Kegler > Marpa-PP-0.014000 > Marpa::PP::Semantics

Download:
Marpa-PP-0.014000.tar.gz

Annotate this POD

CPAN RT

Open  0
View/Report Bugs
Source  

NAME ^

Marpa::PP::Semantics - How Marpa Evaluates Parses

SYNOPSIS ^

    my $grammar = Marpa::PP::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 is of two kinds:

Value Semantics

Marpa's value 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.

Marpa's semantics operate on the application's original rules and symbols. The internals of the parser are hidden from the semantics. Nodes in Marpa's virtual parse trees are of three kinds:

Action Names and Actions

When a Marpa grammar is created, much of its value semantics and ranking semantics is specified indirectly, as action names. Marpa does not allow semantics to be specified directly as Perl closures until the evaluation phase. This approach to semantics follows Perl 6. I discovered the wisdom of having an additonal layer of abstraction the hard way.

To implement its semantics of action names and actions, Marpa must do three things:

The action names and actions used to produce the node value are called value action names and value actions. The action names and actions used to rank nodes are called ranking action names and ranking actions.

An action name and action is also used to create the per-parse variable, as described below. The per-parse variable is a special case, but it is intended to be used as part of the value semantics.

NODES ^

Token Nodes

For every input token, there is an associated token node. In the default model of input, every token will become a leaf node 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 defaults to a Perl undef.

Rule Nodes

Nodes which are ancestors of token nodes are called rule nodes. Rule nodes are always associated with a rule. The value of a rule node is computed at Node Evaluation Time. Applications can specify, on a per-rule basis, Perl closures to evaluate rule nodes. The Perl closures which produce the value of rule nodes are called value actions.

A value action's arguments will be a per-parse variable followed by the values of its child nodes in lexical order. The return value of a value action becomes the value of the node. A value action is always evaluated in scalar context. If there is no value action for a rule node, the value of the rule node is a Perl undef.

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 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 value action of a sequence rule node must be a Perl closure 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 Perl 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 node which derives the zero-length, or empty string. By default, the value of a null node is a Perl undef. This is adequate for many applications, but Marpa allows other values to be specified for null nodes. In fact, Marpa allows allows an arbitrarily complex null semantics. Readers interested in null nodes with values other than undef, or who simply would like to read a more detailed account of how Marpa's null semantics works, should turn to 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.

Evaluations, Parse Results and Parse Series

When the semantics are applied to a parse, it produces a value called a parse result. Because Marpa allows ambiguous parsing, each parse can have zero or more parse results. A parse series is the series of zero or more parse results for a single evaluation. 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 recognizer, we have

While processing a parse series, we have:

While processing a parse result, we have:

Within the Tree Traversal Phase, from the point of view of each rule node, we have Node Evaluation Time.

THE SEMANTIC PHASES IN DETAIL ^

Recognizer Setup Phase

In the Recognizer Setup Phase, the null values of the symbols are determined. The null values of symbols never change -- they are in effect properties of the grammar.

Exactly one Recognizer Setup Phase occurs for every recognizer. For every Marpa Recognizer object, the Recognizer Setup Phase occurs before any Series Setup Phase.

Series Setup Phase

During the Series Setup Phase all value action names are resolved to Perl closures -- the value actions. The value actions are never called in the Series Setup Phase. Value actions are called in the Tree Traversal Phase.

Exactly one Series Setup Phase occurs for each parse series. A Series Setup Phase occurs in the first call of the recognizer's value method of each parse series.

Ranking Phase

In the Ranking Phase, all ranking action names are resolved to Perl closures (ranking actions), and those ranking actions are called. The entire ranking semantics is carried out in the Ranking Phase. The Ranking Phase is the only phase in which ranking action names are resolved and the only phase in which ranking actions are called.

Ranking Phases do not occur if recognizer's ranking_method is "none", which is the default. If the recognizer's ranking method is set to a value other than "none", a Ranking Phase occurs during the first call of the recognizer's value method for each parse series.

Result Setup Phase

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

In every parse series, all the Result Setup Phases occur after the Series Setup Phase. In every parse series which has a Ranking Phase, all the Result Setup Phases occur after the Ranking Phase. For each parse result, the Result Setup Phase occurs before its Tree Traversal Phase.

Tree Traversal Phase

During the Tree Traversal Phase, the semantic Perl closures are called. For each parse result, there is exactly one Tree Traversal Phase, which follows the Result Setup Phase.

During parse tree traversal, Node Evaluation Time occurs for every node in the parse. Tree Traversal Phases occur during calls of the recognizer's value method.

Node Evaluation Time

Node Evaluation Time is not really a separate phase. Node Evaluation Time is the Tree Traversal Phase, seen from the point of view of the individual nodes of the parse tree. If a node has a semantic Perl closure, it is called at Node Evaluation Time.

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:

Resolution of action names is described below. If the action property or the default_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:

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 four things must be the case:

In all but one circumstance, failure to resolve an action name is thrown as an exception. Marpa is more lenient when a rule attempts to use the lhs rule property as an action name. That is the one case in which Marpa will look at other alternatives.

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

Generally it is a good practice to keep the semantic Perl closures in their own namespace. But if, for example, the user wants to leave the semantic closures in the main namespace, she can specify "main" as the value of the actions named argument.

THE PER-PARSE VARIABLE ^

In the Result Setup Phase, Marpa creates a per-parse variable. This becomes the first argument of the semantic Perl closures for the rule nodes. If the grammar's action_object named argument is not defined, the per-parse 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 variable can be used for data which does not conveniently fit this model.

The lifetime of the per-parse variable extends into the Tree Traversal Phase. During the Tree Traversal Phase, Marpa's internals never alter the per-parse 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 Result Setup Phase. The return value of the action object constructor becomes the per-parse 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 Perl closure referred to by the value of 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.

CONTEXT-AWARE STATIC METHODS ^

    sub rank_null_a {
        return \( ( $MyTest::MAXIMAL ? -1 : 1 )
            * 10**( 3 - Marpa::PP::token_location() ) );
    }

Ranking Perl closures have available a set of context-aware static methods. A ranking action can use these methods to learn about the context in which it is called. As of this writing, the context-aware static methods are available for the ranking actions only. This may change in the future.

Marpa::PP::location

Returns the location of the origin (or start) of the rule.

Marpa::PP::token_location

Returns the location of the token. Intended for use in callbacks associated with empty rules and nulling symbols.

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 varies among Marpa implementations. If an infinite loop is given a null semantics, which is the default, the location of the break will not matter.

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::PP.  Marpa::PP 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::PP 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::PP.  If not, see
  http://www.gnu.org/licenses/.
syntax highlighting: