NAME
Marpa::R2::Semantics::Order - How Marpa 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 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.
Duplicate parses are eliminated
When evaluating the parse trees in a parse series, Marpa never evaluates the same parse tree twice. What this means probably matches the programmer intuition of what it should mean.
Capturing intuition behind the phrase "same parse tree" in a careful definition, and implementing it in Marpa, was far from trivial. The more careful definition which occupies the rest of this section may interest some readers.
Marpa considers two parse trees to be the same if they are semantic equivalents. Two parse trees are semantic equivalents if and only if a recursive, top-down evaluation of each applies the same rules in the same order at the same earleme locations. This definition implies that, given any deterministic semantics, two parse trees which are semantic equivalents will always produce the same parse result -- hence the term. When the Marpa documentation refers to duplicate parses, it will mean that the two are semantic equivalents, unless otherwise stated.
In this document, the term arbitrary parse order is used to mean an arbitrary choice among the strict total orders of the equivalence classes that contain the semantically equivalent parse trees. This set of equivalence classes is finite.
Traversal of the parse trees in arbitrary parse order will be always be well-behaved in the sense that no parse tree will be omitted in it, except that no two parse trees will be semantic duplicates. However, no other property of it is guaranteed. For example, the order may change each time the parse series is traversed.
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.
Ranking methods
Marpa grammar objects have a ranking_method named argument, whose value can be the name of a ranking method, or "none", indicating that the default ranking method is to be used.
The rule ranking method
The rule method ranks alternative parses according to their rules. Every rule has a rule rank. A rule's rank can be specified using the the rank named argument for that rule. Rule ranks must be integers. If no rule rank is specified, the rule rank is 0. When being ranked, parse trees are traversed top-down, left-to-right.
The high_rule_only ranking method
The high_rule_only ranking method is similar to the rule ranking method, except that, at every choice point, it discards all of the choices which have a rank lower than that of the highest ranked alternative.
In carrying out the ranking, the choice points of the parse trees are visited in top-down, left-to-right order. Since the high_rule_only ranking method eliminates some parse trees, it can reduce or eliminate the ambiguity of a parse, but it does not necessarily do either. This is because, at each choice point among the parse trees, it is possible that several of the choices, or all of them, will have the same rank as the highest ranked alternative.
Rule ranking
When ranking, the logic descends the parse trees top-down and left-to-right. Places where there is more than one alternative are called choice points. Alternatives are ranked (in the rule ranking method) or selected (in the high_rule_only ranking method), by comparing them as follows:
Different ranks: If the two alternatives have different rule ranks, they must also have different rules. The alternative with the higher rule rank will rank high.
Same Rule: If the two alternatives have the same rule, they rank as described under "Null variant ranking".
Same rank, different rules: Two different rules can have the same rank. If the two alternatives are for different rules, but the two rules have the same rank, the relative order of the two alternatives is arbitrary.
Null variant ranking
Some rules have a RHS which contains proper nullables: symbols which may be nulled, but which are not nulling symbols. (Nulling symbols are symbols which are always nulled.)
When a rule contains proper nullables, each application of that rule to a section of input creates a nulling variant -- that rule with a specific pattern of null and non-null symbols. In many cases, this creates an ambiguity -- different nulling variants could apply to the same substring of input. In ambiguous parsings of this kind, some applications may want to rank nulling variants that start with non-null symbols higher. Other applications may want to do the opposite -- to rank nulling variants that start with null symbols higher.
The null_ranking named argument for rules specifies which nulling variants are ranked high or low. Ranking of nulling variants is done left-to-right, with the null preference as indicated by the null_ranking named argument. Specifically, if the null_ranking is "low", then the closer a nulling variant places its visible (non-null) symbols to the start of the rule, the higher it ranks. low null ranking is the default. If the null_ranking is "high", then the closer a nulling variant places its null symbols to the start of the rule, the higher it ranks.
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 parse result of every parse tree 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.
Copyright and License
Copyright 2012 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/.