The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Marpa-PP-0.013_001
2 ++
/ 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 method of sorting parses, called the Constant Ranking Method. The Constant Ranking Method is now severely deprecated. It is unsupported and its documentation has been removed.

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