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.
Defaultparseorder
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 arbitraryparseorder.
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 in it. No other property of arbitrary parse order is guaranteed. For example, the order may
change each time the parse series is traversed.
Choicepoints
When ranking, the logic traverses each node of the parse bocage. In this context, the nodes are also
called "choicepoints". From the point of view of the individual parse trees, the traversal will be top-
down and left-to-right.
Each choicepoint has one or more "choices". Often a choicepoint has only a single choice, in which case
the choicepoint is called "trivial". For two rule instances to be choices of the same choicepoint, they
must end at the same location, and their rules must have the same LHS.
The terms "choicepoint" and "choice" are defined carefully in a separate document. That document also
gives several examples of ranking, which are explained in detail.
Rankingmethods
SLIF recognizer 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"rankingmethod
The rule method ranks alternative parses according to their rule alternatives. Every rule alternative
has a numericrank. A rule's rank can be specified using the the "rank" adverb argument for that RHS
alternative. Rule ranks must be integers. They may be negative. If no numeric rank is specified, the
numeric rank is 0.
The"high_rule_only"rankingmethod
The "high_rule_only" ranking method is similar to the "rule" ranking method, except that, at every
choicepoint, it discards all of the choices which have a rank lower than that of the highest ranked
choice.
The "high_rule_only" ranking method can reduce the ambiguity of a parse, but it does not necessarily do
so. This is because, at each choicepoint 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 choice.
Ruleranking
At each choicepoint, the choices are ranked as follows:
• Differentnumericranks:
If the two parse choices have different numeric ranks, they must also have different rule
alternatives. The parse choice whose rule alternative has the higher numeric rank will rank high.
• Samerulealternative:
If the two parse choices have the same rule alternative, they rank as described under "Null variant
ranking".
• Samenumericrank,differentrulealternatives:
Two different rule alternatives can have the same numeric rank. If the two parse choices are for
rule alternatives that are different, but that have the same numeric rank, the relative order of the
two parse choices is arbitrary.
Rule alternatives may be part of a single rule in the DSL -- for example, a prioritized rule. Lexical
order within a DSL rule makes no difference when ranking rule alternatives. For example, it makes no
difference if two rule alternatives come from the same prioritized rule; or from two different
prioritized rules.
Nullvariantranking
Some rules have a RHS which contains propernullables: symbols which may be nulled, but which are not
nulling symbols. (Nulling symbols are symbols which are always nulled.)
When a rule alternative contains proper nullables, each instance of that rule creates a nullingvariant.
A nullingvariant is a specific pattern of null and non-null symbols in a rule instance's RHS. In many
cases, this creates an ambiguity -- different nulling variants can match the same substring in the 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" adverb for RHS alternatives specifies which nulling variants are ranked high or low.
If the "null-ranking" is ""low"", then the closer a nulling variant places its visible (non-null) symbols
to the start of the rule instance, the higher it ranks. A null ranking of "low" 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 instance, the higher it ranks. In ranking nulling variants with more than one proper nullable,
major-to-minor is left-to-right.
Ageneralapproachtosortingparses
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.)
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.
Install Now
PNG Icons
