Debian Codegraph @

pod/Deprecated/NAIF/Semantics/Order.pod

raw
1 # Copyright 2022 Jeffrey Kegler
2 # This file is part of Marpa::R2. Marpa::R2 is free software: you can
3 # redistribute it and/or modify it under the terms of the GNU Lesser
4 # General Public License as published by the Free Software Foundation,
5 # either version 3 of the License, or (at your option) any later version.
6 #
7 # Marpa::R2 is distributed in the hope that it will be useful,
8 # but WITHOUT ANY WARRANTY; without even the implied warranty of
9 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
10 # Lesser General Public License for more details.
11 #
12 # You should have received a copy of the GNU Lesser
13 # General Public License along with Marpa::R2. If not, see
14 # http://www.gnu.org/licenses/.
15
16 =head1 NAME
17
18 Marpa::R2::Deprecated::NAIF::Semantics::Order - How the NAIF ranks ambiguous parses
19
20 =head1 THE NAIF INTERFACE IS DEPRECATED
21
22 This document describes the NAIF interface,
23 which is deprecated.
24 PLEASE DO NOT USE IT FOR NEW DEVELOPMENT.
25
26 =head1 Description
27
28 This document deals with Marpa's low-level NAIF interface.
29 If you are new to Marpa,
30 or are not sure which interface you are interested in,
31 or do not know what the Named Argment InterFace (NAIF) is,
32 you probably want to look instead at
33 L<the document on semantics for the SLIF
34 interface|Marpa::R2::Semantics>.
35
36 Marpa allows ambiguous parses.
37 While an unambiguous parse can produce at most one parse tree
38 and one parse result,
39 an ambiguous parse will produce a parse series.
40 A parse series is a sequence of parse trees,
41 each of which will have its own parse result.
42
43 This document describes ways of controlling
44 the order in which
45 the L<NAIF recognizer's C<value> method|Marpa::R2::Deprecated::NAIF::Recognizer/"value()">
46 evaluates the parse
47 trees of an ambiguous parse;
48 It also describes ways to exclude selected parse trees
49 from the parse series.
50
51 Almost all
52 of what is said in this document
53 also applies to the L<SLIF recognizer's C<value> method|Marpa::R2::Scanless::R/"value()">.
54 Certain named arguments which control the parse order are present in the NAIF,
55 but are not present in the SLIF,
56 and this accounts for the differences between the two.
57
58 =head2 Duplicate parses are eliminated
59
60 When evaluating the parse trees in a parse series,
61 Marpa never evaluates the same parse tree twice.
62 What this means probably matches the programmer
63 intuition of what it should mean.
64 Marpa considers two parse trees to be the same if they are
65 B<semantic equivalents>.
66
67 Two parse trees are semantic equivalents if
68 and only if
69 a recursive, top-down evaluation of each
70 applies
71 the same rules
72 in the same order
73 at the same earleme locations.
74 This definition implies that,
75 given any deterministic semantics,
76 two parse trees which are
77 semantic equivalents
78 will always produce the same parse result --
79 hence the term.
80 When the Marpa documentation refers to duplicate
81 parses, it will mean that the two
82 are semantic equivalents, unless otherwise
83 stated.
84
85 =head2 Default parse order
86
87 In this document, the term
88 B<arbitrary parse order>
89 is used to mean an
90 arbitrary choice among
91 the strict total orders of
92 the equivalence classes
93 that contain the semantically equivalent parse trees.
94 This set of equivalence classes is finite.
95
96 Traversal of the parse trees in
97 arbitrary parse order
98 will be always be well-behaved
99 in the sense
100 that no two parse trees will be semantic duplicates,
101 and no unique (semantic non-duplicate)
102 parse tree will be omitted in it,
103 No other property of arbitrary parse order is guaranteed.
104 For example, the order may
105 change each time
106 the parse series is traversed.
107
108 By calling
109 the recognizer's
110 L<C<value>|Marpa::R2::Deprecated::NAIF::Recognizer/"value()">
111 method
112 repeatedly,
113 Marpa can produce all the parse results
114 in the current parse series.
115 The default is for the parse results to be returned
116 in an B<arbitrary parse order>.
117 This corresponds to the "C<none>" value of
118 L<the recognizer's C<ranking_method>|Marpa::R2::Deprecated::NAIF::Recognizer/"ranking_method">
119 named argument.
120
121 =head2 Ranking methods
122
123 Marpa recognizer objects have L<a C<ranking_method> named
124 argument|Marpa::R2::Deprecated::NAIF::Recognizer/"ranking_method">,
125 whose value can be the name of a ranking method,
126 or "C<none>", indicating that the default ranking method is to
127 be used.
128
129 =head2 The C<rule> ranking method
130
131 The rule method ranks alternative parses according to their rules.
132 Every rule has a B<rule rank>.
133 A rule's rank can be specified using the
134 the C<rank> named
135 argument for that rule.
136 Rule ranks must be integers.
137 If no rule rank is specified, the rule rank is 0.
138
139 =head2 The C<high_rule_only> ranking method
140
141 The C<high_rule_only> ranking method is similar to the
142 C<rule> ranking method, except that, at every choice point,
143 it discards all of the choices which
144 have a rank lower than that of the highest ranked alternative.
145
146 Since the C<high_rule_only> ranking method eliminates some
147 parse trees, it can reduce or eliminate the ambiguity of a parse,
148 but it does not necessarily do either.
149 This is because, at each choice point among the parse trees,
150 it is possible that several of the choices,
151 or all of them, will have the same rank
152 as the highest ranked alternative.
153
154 =head2 Rule ranking
155
156 A parse series is kept in a structure called a B<parse bocage>.
157 The parse bocage is a tree-like structure, whose root node
158 is the common root of all the parse trees of the parse series.
159 In an unambiguous parse,
160 there will be only one parse tree,
161 and the parse bocage will be equivalent
162 to that parse tree.
163 In an ambiguous parse,
164 there will be B<choice points> in the parse bocage.
165 At the choice points, there will be two or more
166 B<alternatives> -- choices which
167 result in different parse trees.
168
169 When ranking, the logic traverses the parse bocage,
170 looking for choice points.
171 From the point of view of the individual parse trees,
172 this traversal will be top-down
173 and left-to-right.
174 At the choice points,
175 the alternatives
176 are ranked (in the C<rule> ranking method)
177 or selected
178 (in the C<high_rule_only> ranking method),
179 by comparing them as follows:
180
181 =over
182
183 =item * B<Different ranks>:
184 If the two alternatives have different rule ranks,
185 they must also have different rules.
186 The alternative with the higher rule rank
187 will rank high.
188
189 =item * B<Same Rule>:
190 If the two alternatives have the same rule,
191 they rank as described
192 under L<"Null variant ranking">.
193
194 =item * B<Same rank, different rules>:
195 Two different rules can have the same rank.
196 If the two alternatives are for
197 different rules,
198 but the two rules have the same rank,
199 the relative order of the two alternatives is
200 arbitrary.
201
202 =back
203
204 =head2 Null variant ranking
205
206 Some rules have a RHS which contains
207 B<proper nullables>:
208 symbols
209 which may be nulled, but which are not nulling
210 symbols.
211 (Nulling symbols are symbols which are B<always> nulled.)
212
213 When a rule contains proper nullables, each application
214 of that rule to a section of input creates a B<nulling variant> --
215 that rule with a specific pattern of
216 null and non-null symbols.
217 In many cases, this creates an ambiguity -- different
218 nulling variants could apply to the same substring of input.
219 In ambiguous parsings of this kind,
220 some applications may want to rank nulling variants that start
221 with non-null symbols higher.
222 Other applications may want to do the opposite --
223 to rank nulling variants that start
224 with null symbols higher.
225
226 The
227 L<C<null_ranking> named
228 argument for rules|Marpa::R2::Deprecated::NAIF::Grammar/"null_ranking">
229 specifies which nulling variants are ranked high or low.
230 Ranking of nulling variants is done left-to-right,
231 with the null preference as indicated by the C<null_ranking>
232 named argument.
233 Specifically, if the C<null_ranking> is "C<low>",
234 then the closer a nulling variant
235 places its B<visible> (non-null) symbols to the start of the rule,
236 the higher it ranks.
237 C<low> null ranking is the default.
238 If the C<null_ranking> is "C<high>",
239 then the closer a nulling variant
240 places its B<null> symbols to the start of the rule,
241 the higher it ranks.
242
243 =head2 A general approach to sorting parses
244
245 The most general way to sort Marpa parses is for the application
246 to take control.
247 The application can set up the Marpa semantic actions
248 so that the parse result of every parse tree is a
249 C<< <rank, true_value> >> duple.
250 The duples can then be sorted by C<rank>.
251 Once the resuls are sorted,
252 the C<rank> element of the duple can be discarded.
253 (Those familiar with the Schwartzian transform
254 may note a resemblance.
255 In Perl,
256 duples can be implemented as references to arrays of 2 elements.)
257
258 The user needs to be careful.
259 In theory, ambiguity can cause an exponential explosion in the number of results.
260 In practice, ambiguity tends to get out of hand very easily.
261 Producing and sorting all the parses can take a very
262 long time.
263
264 =head1 Copyright and License
265
266 =for Marpa::R2::Display
267 ignore: 1
268
269 Copyright 2022 Jeffrey Kegler
270 This file is part of Marpa::R2. Marpa::R2 is free software: you can
271 redistribute it and/or modify it under the terms of the GNU Lesser
272 General Public License as published by the Free Software Foundation,
273 either version 3 of the License, or (at your option) any later version.
274
275 Marpa::R2 is distributed in the hope that it will be useful,
276 but WITHOUT ANY WARRANTY; without even the implied warranty of
277 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
278 Lesser General Public License for more details.
279
280 You should have received a copy of the GNU Lesser
281 General Public License along with Marpa::R2. If not, see
282 http://www.gnu.org/licenses/.
283
284 =for Marpa::R2::Display::End
285
286 =cut
287
288 # Local Variables:
289 # mode: cperl
290 # cperl-indent-level: 4
291 # fill-column: 100
292 # End:
293 # vim: expandtab shiftwidth=4: