Marpa::PP::Semantics - How Marpa Evaluates Parses
my $grammar = Marpa::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';
Marpa's semantics is of two kinds:
The value semantics. This is the semantics which produces the value of the parse tree.
The ranking semantics, which is used to rank ambiguous parse results, but which can be exploited for its side effects.
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:
Token Nodes, which have a constant semantics, initialized when the token is read.
Rule Nodes, which have a dynamic semantics, based on action names and actions, as described below.
Null Nodes, which have a constant semantics, initialized when the recognizer is created.
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:
Determine the action name.
Resolve the action name to an action. An action is a Perl closure.
Call the Perl closure to produce the actual result.
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.
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.
undef
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.
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.
@_
keep
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.
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.
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.
value
reset_evaluation
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.
While processing a recognizer, we have
A Recognizer Setup Phase, followed by
the processing of zero or more parse series.
While processing a parse series, we have:
A Series Setup Phase, followed by
an optional Ranking Phase, followed by
the processing of zero or more parse results.
While processing a parse result, we have:
A Result Setup Phase, followed by
a Tree Traveral Phase.
Within the Tree Traversal Phase, from the point of view of each rule node, we have Node Evaluation Time.
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.
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.
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.
none
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.
action_object
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.
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 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.
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.
action
Resolving an action based on the lhs property of the rule.
lhs
Resolving an action based on the default_action named argument of the grammar, if one is defined.
default_action
Defaulting to a virtual action which returns a Perl undef.
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.
Action names come from these sources:
The default_action named argument of Marpa's grammar.
The action property of Marpa's rules.
The ranking_action property of Marpa's rules.
ranking_action
The new constructor in the package specified by the action_object named argument of the Marpa grammar.
new
The lhs property of Marpa's rules.
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.
closures
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.
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.
actions
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:
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.
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.
main
"main"
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.
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.
::new
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.
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.
sub rank_null_a { return \( ( $MyTest::MAXIMAL ? -1 : 1 ) * 10**( 3 - Marpa::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.
Returns the location of the origin (or start) of the rule.
Returns the location of the token. Intended for use in callbacks associated with empty rules and nulling symbols.
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 2011 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/.
To install Marpa::PP, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Marpa::PP
CPAN shell
perl -MCPAN -e shell install Marpa::PP
For more information on module installation, please visit the detailed CPAN module installation guide.