1Marpa::XS::Semantics::OUrsdeerr(C3o)ntributed Perl DocumMeanrtpaat:i:oXnS::Semantics::Order(3)
2
6 Marpa::XS::Semantics::Order - How Marpa ranks ambiguous parses
7
9 Marpa allows ambiguous parses. While an unambiguous parse can produce
10 at most one parse tree and one parse result, an ambiguous parse will
11 produce a parse series. A parse series is a sequence of parse trees,
12 each of which will have its own parse result.
13 This document describes ways of controlling the order in which the
15 recognizer's "value" method evaluates the parse trees of an ambiguous
16 parse. It also describes ways to exclude selected parse trees from the
17 parse series.
18 Duplicate parses are eliminated
20 When evaluating the parse trees in a parse series, Marpa never
21 evaluates the same parse tree twice. Marpa considers two parse trees
22 to be the same if they are semantic duplicates.
23 Two parse trees are semantic duplicates if and only if a recursive,
25 top-down evaluation of each applies the same rules in the same order at
26 the same earleme locations. This definition implies that, given any
27 deterministic semantics, two parse trees which are semantic duplicates
28 will always produce the same parse result -- hence the term "semantic
29 duplicates". When the Marpa documentation refers to duplicate parses,
30 it will mean semantic duplicates unless otherwise stated.
31 Default parse order
33 By calling the recognizer's "value" method repeatedly, Marpa can
34 produce all the parse results in the current parse series. The default
35 is for the parse results to be returned in an arbitrary order. This
36 corresponds to the ""none"" value of the recognizer's "ranking_method"
37 named argument.
38 Arbitrary parse order
40 When this document calls a behavior "arbitrary" it means that an
41 application must not rely on that behavior being repeated. An
42 arbitrary behavior is allowed to change from version to version of the
43 software, from run to run of the application, and even from call to
44 call of the methods.
45 "Arbitrary parse order", in particular, means that the particular order
47 in which parse trees are evaluated may not be repeated. But an
48 application can expect, even when the order of evaluation of the parse
49 trees is arbitrary, that all appropriate parse trees will be included
50 in the parse series, and that none of the parse trees in the parse
51 series will be the semantic duplicate of any other tree.
52 Ranking methods
54 Marpa grammar objects have a "ranking_method" named argument, whose
55 value can be the name of a ranking method, or ""none"", indicating that
56 the default ranking method is to be used.
57 The "rule" ranking method
59 The rule method ranks alternative parses according to their rules.
60 Every rule has a rule rank. A rule's rank can be specified using the
61 the "rank" named argument for that rule. Rule ranks must be integers.
62 If no rule rank is specified, the rule rank is 0. When being ranked,
63 parse trees are traversed top-down, left-to-right.
64 The "high_rule_only" ranking method
66 The "high_rule_only" ranking method is similar to the "rule" ranking
67 method, except that, at every choice point, it discards all of the
68 choices which have a rank lower than that of the highest ranked
69 alternative.
70 In carrying out the ranking, the choice points of the parse trees are
72 visited in top-down, left-to-right order. Since the "high_rule_only"
73 ranking method eliminates some parse trees, it can reduce or eliminate
74 the ambiguity of a parse, but it does not necessarily do either. This
75 is because, at each choice point among the parse trees, it is possible
76 that several of the choices, or all of them, will have the same rank as
77 the highest ranked alternative.
78 Null ranking
80 Some rules have a RHS which contains proper nullables: symbols which
81 may be nulled, but which are not nulling symbols. (Nulling symbols are
82 symbols which are always nulled.)
83 When a rule contains proper nullables, each application of that rule to
85 a section of input creates a nulling variant -- that rule with a
86 specific pattern of null and non-null symbols. In many cases, this
87 creates an ambiguity -- different nulling variants could apply to the
88 same substring of input. In ambiguous parsings of this kind, some
89 applications may want to rank nulling variants that start with non-null
90 symbols higher. Other applications may want to do the opposite -- to
91 rank nulling variants that start with null symbols higher.
92 The "null_ranking" named argument for rules specifies which nulling
94 variants are ranked high or low. Ranking of nulling variants is done
95 left-to-right, with the null preference as indicated by the
96 "null_ranking" named argument. Specifically, if the "null_ranking" is
97 ""low"", then the closer a nulling variant places its non-null symbols
98 to the start of the rule, the higher it ranks. If the "null_ranking"
99 is ""high"", then the closer a nulling variant places its null symbols
100 to the start of the rule, the higher it ranks.
101 A rule is null ranked if and only if its "null_ranking" is defined.
103 Note that this definition means that a rule can be considered null
104 ranked even if it does not have any nullable symbols. A rule which is
105 not null ranked is called non-null-ranked.
106 Null ranking, in the current implementation, is targeted at situations
108 where the alternatives are different applications of a single rule. In
109 situations where the choice is between two different rules, an
110 application which cares about the order will typically want to override
111 the null ranking using rule ranks. A more detailed description of the
112 rule comparison logic can be found below.
113 By default, "null_ranking" is undefined, which means the order of the
115 null variants is arbitrary. This is fine for most applications.
116 Details of ranking
118 When ranking, the logic descends the parse trees top-down and left-to-
119 right. Places where there is more than one alternative are called
120 choice points. Alternatives are ranked (in the "rule" ranking method)
121 or selected (in the "high_rule_only" ranking method), by comparing them
122 as follows:
123 · If two alternatives are for the same rule, and that the rule is
125 null ranked, they rank as described under "Null ranking".
126 · If the two alternatives have the same rule, and that rule is non-
128 null-ranked, the alternatives have equal rank.
129 · If the two alternatives have different rules, and the two rules
131 have different rule ranks, the alternative with the higher rule
132 rank ranks high.
133 · The remaining cases deal with the comparison of alternatives which
135 have different rules, when both rules have the same rule rank.
136 · If the rule for one alternative is null ranked, while the rule
138 for the other is non-null-ranked, the alternative with the non-
139 null-ranked rule ranks high.
140 · If both rules are non-null-ranked, the two alternatives have
142 equal rank.
143 · If both rules are null-ranked, their ranking is arbitrary --
145 either one may rank high, or they may have equal rank.
146 A general approach to sorting parses
148 The most general way to sort Marpa parses is for the application to
149 take control. The application can set up the Marpa semantic actions so
150 that the parse result of every parse tree is a "<rank, true_value>"
151 duple. The duples can then be sorted by "rank". Once the resuls are
152 sorted, the "rank" element of the duple can be discarded. (Those
153 familiar with the Schwartzian transform may note a resemblance. In
154 Perl, duples can be implemented as references to arrays of 2 elements.)
155 The user needs to be careful. In theory, ambiguity can cause an
157 exponential explosion in the number of results. In practice, ambiguity
158 tends to get out of hand very easily. Producing and sorting all the
159 parses can take a very long time.
160 The "constant" ranking method is no longer supported
162 The "constant" ranking method is no longer implemented. An initial
163 attempt to find the ideal compromise between flexibility and
164 efficiency, the "constant" ranking method proved too ambitious, and had
165 several drawbacks. First, its overhead was high in comparison to the
166 flexibility it offered. Second, it was not intuitive. Even when the
167 "constant" ranking method was powerful enough to solve a problem, it
168 was not always obvious how to actually use it. Finally, its
169 implementation was extremely complex.
170 The new "rule" ranking method is far more efficient, vastly more
172 intuitive, and far easier to implement and maintain. But the new
173 "rule" ranking method is also very flexible -- it passes the test suite
174 which was written for the "constant" ranking method.
175
177 Copyright 2012 Jeffrey Kegler
178 This file is part of Marpa::XS. Marpa::XS is free software: you can
179 redistribute it and/or modify it under the terms of the GNU Lesser
180 General Public License as published by the Free Software Foundation,
181 either version 3 of the License, or (at your option) any later version.
182 Marpa::XS is distributed in the hope that it will be useful,
184 but WITHOUT ANY WARRANTY; without even the implied warranty of
185 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
186 Lesser General Public License for more details.
187 You should have received a copy of the GNU Lesser
189 General Public License along with Marpa::XS. If not, see
190 http://www.gnu.org/licenses/.
191perl v5.28.1 2019-02-02 Marpa::XS::Semantics::Order(3)