NAME¶
Marpa::R2::NAIF::Semantics::Order - How the NAIF ranks ambiguous parses
Description¶
This document deals with Marpa's low-level NAIF interface. If you are new to
Marpa, or are not sure which interface you are interested in, or do not know
what the Named Argment InterFace (NAIF) is, you probably want to look instead
at the document on semantics for the SLIF interface.
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 NAIF
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.
Almost all of what is said in this document also applies to the SLIF
recognizer's "value" method. Certain named arguments which control
the parse order are present in the NAIF, but are not present in the SLIF, and
this accounts for the differences between the two.
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. 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.
Default parse order¶
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 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.
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 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" 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.
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.
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¶
A parse series is kept in a structure called a
parse bocage. The parse
bocage is a tree-like structure, whose root node is the common root of all the
parse trees of the parse series. In an unambiguous parse, there will be only
one parse tree, and the parse bocage will be equivalent to that parse tree. In
an ambiguous parse, there will be
choice points in the parse bocage. At
the choice points, there will be two or more
alternatives -- choices
which result in different parse trees.
When ranking, the logic traverses the parse bocage, looking for choice points.
From the point of view of the individual parse trees, this traversal will be
top-down and left-to-right. At the choice points, the 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 2014 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/.