Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
Marpa::PP::Semantics(3User Contributed Perl DocumentatiMarpa::PP::Semantics(3)

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:

       o   The value semantics.	 This is the semantics which produces the
	   value of the	parse tree.

       o   The ranking semantics, which	is used	to rank	ambiguous parse
	   results, but	which can be exploited for its side effects.

   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:

       o   Token Nodes,	which have a constant semantics, initialized when the
	   token is read.

       o   Rule	Nodes, which have a dynamic semantics, based on	action names
	   and actions,	as described below.

       o   Null	Nodes, which have a constant semantics,	initialized when the
	   recognizer is created.

   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:

       o   Determine the action	name.

       o   Resolve the action name to an action.  An action is a Perl closure.

       o   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.

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

       o   A Recognizer	Setup Phase, followed by

       o   the processing of zero or more parse	series.

       While processing	a parse	series,	we have:

       o   A Series Setup Phase, followed by

       o   an optional Ranking Phase, followed by

       o   the processing of zero or more parse	results.

       While processing	a parse	result,	we have:

       o   A Result Setup Phase, followed by

       o   a Tree Traveral Phase.

       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:

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

       o   Resolving an	action based on	the "lhs" property of the rule.

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

       o   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.

RESOLVING ACTION NAMES
       Action names come from these sources:

       o   The "default_action"	named argument of Marpa's grammar.

       o   The "action"	property of Marpa's rules.

       o   The "ranking_action"	property of Marpa's rules.

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

       o   The "lhs" property of Marpa's rules.

   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:

       o   The action name resolves explicitly.

       o   The action name is fully qualified to begin with.

       o   The "actions" named argument	is defined.

       o   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.

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

perl v5.24.1			  2017-07-02	       Marpa::PP::Semantics(3)

NAME | SYNOPSIS | OVERVIEW | NODES | OVERVIEW OF THE SEMANTIC PHASES | THE SEMANTIC PHASES IN DETAIL | FINDING THE ACTION FOR A RULE | RESOLVING ACTION NAMES | THE PER-PARSE VARIABLE | PARSE ORDER | CONTEXT-AWARE STATIC METHODS | INFINITE LOOPS | COPYRIGHT AND LICENSE

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=Marpa::PP::Semantics&sektion=3&manpath=FreeBSD+12.1-RELEASE+and+Ports>

home | help