/ 
Marpa-R2-13.001_000
River stage two • 41 direct dependents • 62 total dependents
/ Marpa::R2::Semantics::Order

NAME

Marpa::R2::Semantics::Order - How the SLIF ranks ambiguous parses

Description

Marpa allows ambiguous parses. While an unambiguous parse can produce at most one parse tree and one parse result, an ambiguous parse will produce a parse series. A parse series is a sequence of parse trees, each of which will have its own parse result.

This document describes ways of controlling the order in which the SLIF recognizer's value() method evaluates the parse trees of an ambiguous parse. It also describes ways to exclude selected parse trees from the parse series.

There are three ways to sort parses.

All these methods are described in more detail below.

Semantic duplicates

Regardless of the parse order chosen, no two parse trees in a parse series will be semantic duplicates. Two parse trees are semantic duplicates if and only if a recursive, top-down evaluation of each applies the same rules in the same order at the same G1 locations. If the semantics are deterministic, parse trees that are semantic duplicates will always produce the same parse result. In other words, from the point of view of a deterministic semantics, parse trees that are semantic duplicates are indistinguishable.

The default parse order

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

Traversal of the parse trees in arbitrary parse order will be always be well-behaved in the sense that no two parse trees will be semantic duplicates, and no unique (semantic non-duplicate) parse tree will be omitted. No other property of arbitrary parse order is guaranteed. For example, the order may change each time the parse series is traversed.

Non-default values of the ranking_method named argument

The default value of Marpa::R2's ranking_method named argument is "none". If the "none" value of Marpa::R2's ranking_method named argument is specified, the default parse order is selected.

Use of non-default values of the ranking_method named argument is somewhat like PEG, in that it ranks rule alternatives at choice points. It has the advantage over PEG of being more powerful, because it can rank the parses of any grammar that Marpa::R2 can parse. It is also safer in the sense that in Marpa::R2 the BNF guides the grammar in the tradiional way. The PEG parse description, while it looks like BNF, is not interpreted as BNF, and often omits parses that a BNF-driven parser like Marpa::R2 recognizes. The lack of safety comes from inability to predict which parses will be omitted --- it is very hard to determine, in general, what grammar a PEG parser is actually parsing. There is much more about the use of Marpa::R2's ranking_method named argument in its own document.

Letting the application sort 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 parse result of every parse tree is a <rank, true_value> duple. The duples can then be sorted by rank. Once the results 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.)

One way for an application to implement ranking is with Marpa's abstract syntax forests. Ranking using ASF's will probably be less efficient than using the recognizer's ranking method, but allows a more general and powerful solution.

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.

Copyright and License

Copyright 2022 Jeffrey Kegler
This file is part of Marpa::R2.  Marpa::R2 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::R2 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::R2.  If not, see
http://www.gnu.org/licenses/.