Marpa:...::Order(3pm)

✨ NAME ✨

Marpa::R2::NAIF::Semantics::Order — how the NAIF ranks ambiguous parses 💖

okay so this is the Marpa:...::Order(3pm) page, and yes bestie it lives in the User Contributed Perl Documentation, and yes it is exactly as niche and as iconic as it sounds. it's all about parse order. let's get into it 🫶

---

💅 Description 💅

Real talk first: this document is about Marpa's low-level NAIF interface. So if you're brand new to Marpa, or you're not even sure which interface you actually want, or you straight-up do not know what the Named Argment InterFace (NAIF) is — no worries, it happens to everyone — you probably want to go read the document on semantics for the SLIF interface instead. this one is not your starter pack 💀

So. Marpa allows ambiguous parses. That's the whole vibe. While an unambiguous parse can produce at most one parse tree and one parse result, an ambiguous parse will produce a parse series. And what's a parse series, you ask? It's a sequence of parse trees, and every single one of those trees gets its own parse result. every. one. 👑

This document is about controlling the order in which the NAIF recognizer's value method evaluates the parse trees of an ambiguous parse. And it's also about the ways you can exclude selected parse trees from the parse series entirely. like, bye, not invited to the function 🙈

Almost everything said here also applies to the SLIF recognizer's value method. Almost! Because certain named arguments that control parse order exist in the NAIF but are not present in the SLIF — and that's literally what accounts for the differences between the two. iykyk ✨

🌸 Duplicate parses are eliminated 🌸

When Marpa is evaluating the parse trees in a parse series, it never evaluates the same parse tree twice. Periodt. And what that means is probably exactly what your programmer intuition is telling you it means. 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. And this definition implies something very cute: given any deterministic semantics, two parse trees that are semantic equivalents will always produce the same parse result — hence the term, bestie, the name is doing exactly what it says on the tin. So whenever the Marpa documentation says "duplicate parses", it means the two are semantic equivalents, unless it says otherwise. 💖

🦋 Default parse order 🦋

In this document, the term arbitrary parse order means an arbitrary choice among the strict total orders of the equivalence classes that contain the semantically equivalent parse trees. And good news: this set of equivalence classes is finite. 🎀

Traversal of the parse trees in arbitrary parse order will 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.

And that's it. That is the whole guarantee. No other property of arbitrary parse order is guaranteed. For example, the order may change each time the parse series is traversed. it's giving chaos, honestly 💀

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. And that corresponds to the "none" value of the recognizer's ranking_method named argument. ✨

👑 Ranking methods 👑

Marpa recognizer objects have a ranking_method named argument, and its value can be the name of a ranking method, or "none" — which means the default ranking method is to be used. simple as that. 💅

🌈 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 rank named argument for that rule. Rule ranks must be integers. And if no rule rank is specified, the rule rank is 0. default queen behavior 👑

💜 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. ruthless. we love that for us.

Now, because "high_rule_only" eliminates some parse trees, it can reduce or eliminate the ambiguity of a parse — but it does not necessarily do either. Why? Because at each choice point among the parse trees, it's possible that several of the choices, or all of them, will have the same rank as the highest ranked alternative. so like. it tried its best 🫶

🧚 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 — and at those choice points there will be two or more alternatives, i.e. choices which result in different parse trees. the drama ✨

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 like this:

• 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. yeah. it's just like that sometimes 💀

🍓 Null variant ranking 🍓

Some rules have a RHS which contains proper nullables: symbols which may be nulled, but which are not nulling symbols. (And just so we're clear, nulling symbols are symbols which are always nulled. always always.)

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. And in many cases, this creates an ambiguity, because 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 the exact opposite — to rank nulling variants that start with null symbols higher. both are valid, pick your fighter 💅

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. And "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 results are sorted, the "rank" element of the duple can be discarded. (And if you're familiar with the Schwartzian transform, you may note a resemblance. In Perl, duples can be implemented as references to arrays of 2 elements. iykyk 🧚)

⚠️ 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. be safe out there bestie 😭

---

📜 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/.

---

and that's the whole page, bestie 🫶 this one shipped with perl v5.34.0 and it's dated 2022-02-06 — iconic, timeless, no notes. go forth and rank your ambiguous parses responsibly 💖✨