/ 
Marpa-PP-0.009_004
/ Marpa::PP::Semantics::Order

NAME

Marpa::PP::Semantics::Order - How Marpa Ranks Ambiguous Parses

DESCRIPTION

This document details the order in which the recognizer's value method returns parse results. The same mechanism allows the selection of parse results. It can also be exploited to do the actual processing of parses, using side effects.

Duplicate Parses are Eliminated

In a single parse series, Marpa will never return the same parse result twice. Marpa regards two parses as being the same if they are semantic duplicates.

Two parses are semantic duplicates if a recursive, top-down evaluation of each applies the same rules in the same order at the same earleme locations. When this is the case, a deterministic semantics will always produce the same value for both parses -- hence the term "semantic duplicate". When the Marpa documentation refers to duplicate parses, it will mean semantic duplicates unless otherwise stated.

Default Parse Order

By calling the recognizer's value method repeatedly, Marpa can produce all the parse results for a given parse. The default is for the parse results to be returned in an arbitrary order. This corresponds to the "none" value of the recognizer's ranking_method named argument.

A General Approach to Sorting Parses

The most general way to sort Marpa parses is for the application to take control. The application can set up the Marpa semantic actions so that the value of every parse result is a <rank, true_value> duple. The duples can then be sorted by rank. Once the resuls are sorted, the rank element of the duple can be discarded. (Those familiar with the Schwartzian transform may note a resemblance. In Perl, duples can be implemented as references to arrays of 2 elements.)

The user needs to be careful. In theory, ambiguity can cause an exponential explosion in the number of results. In practice, ambiguity tends to get out of hand very easily. Producing and sorting all the parses can take a very long time.

The Constant Ranking Method

In the past, Marpa supported a simplified approach to sorting parses, called the Constant Ranking Method. The Constant Ranking Method was intended to be flexible enough to handle many, perhaps even most, practical applications, but simple enough that Marpa is able to optimize it.

The first implementation of the Constant Ranking Method had a semantics which made the rank of a node depend on which of its children were actually used in each parse result. While this is what a user would intuitively expect, it required the the ranks of subtrees to be recalculated dynamically, and partially iterated subtrees to be stored and regrafted into the tree being parsed. The code to do this was very complicated and the efficiency trade-offs arguable. The Constant Ranking Method is currently being simplified. Until its features settle, its documentation has been removed.

COPYRIGHT AND LICENSE

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