Marpa:...finite(3pm)

✨ NAME ✨

Marpa::R2::Deprecated::NAIF::Semantics::Infinite — how the NAIF deals with infinite ambiguity 💫

(that's the whole title, bestie, and it lives in the User Contributed Perl Documentation manual, if you were wondering 💅)

---

🚨 THE NAIF INTERFACE IS DEPRECATED 🚨

Okay so heads up before literally anything else: this doc is about the NAIF interface, and the NAIF interface is deprecated. The original is screaming it in all caps and honestly? Same energy.

PLEASE DO NOT USE IT FOR NEW DEVELOPMENT. 🛑 Not a vibe check you want to fail. New stuff goes elsewhere, periodt.

---

🌀 Infinitely ambiguous grammars

So this document is all about Marpa's low-level NAIF interface. If you're new to Marpa, or you're not sure which interface you even want, or you don't know what the Named Argment InterFace (NAIF) is (yes that's really what it's called, iykyk), then you probably want to go read the document about semantics for the SLIF interface instead. Go, shoo, it's fine 🫶

Now. The tea. ☕

Marpa will parse using an infinitely ambiguous grammar. In the technical literature, an infinite ambiguity is more usually called a cycle or a loop. Same thing, different outfit. ✨

An example of an infinitely ambiguous grammar is this one right here:

S ::= A
A ::= B
B ::= A
B :: 'x'

Given the input 'x', this grammar will produce these parses:

S -> A -> B -> x
S -> A -> B -> A -> B -> x
S -> A -> B -> A -> B -> A -> B -> x
.
.
.

See how the last bit just... keeps going? 😭 Because of the two rules A ::= B and B ::= A, this list of parses could go on forever. Like, genuinely forever. And those two rules A ::= B and B ::= A are what's called a cycle. 🎠

Typically, if a user has written a grammar with an infinite cycle, it was a mistake, and he wants to rewrite it before proceeding. (That's the manpage's wording and honestly it's so real of it.) By default, an infinitely ambiguous grammar is a fatal error. That's the behavior most users will want — lowkey the correct default, no cap. 💀

To produce parse results from an infinitely ambiguous grammar, the user has to set the grammar's named argument infinite_action to a value other than fatal. The other choices are warn and quiet. That's it, those are the three, pick your fighter. 🔥

---

🦋 Cycle-free parse results

Obviously Marpa cannot list all of an infinite number of parse results. Math said no. 🙅 So when Marpa iterates through the parse results returned by a grammar with cycles, it produces only those which are cycle-free.

For example — and this is the manpage's actual example, so watch closely — in the above list of derivations, Marpa would return only the parse result corresponding to this derivation:

S -> A -> B -> x

Just the one. The rest got filtered. Slay. 👑

More specifically, Marpa guarantees to eliminate all parse results that contain nulling-sensitive cycles. Intuitively, a nulling-sensitive cycle is a case where the same rule, with the same pattern of nulled and non-nulled symbols, is applied at the same locations.

More carefully — and now we're being precise, bestie, so pay attention 📝 — a nulling-sensitive cycle is defined as a derivation which contains the same nulling-sensitive rule instance twice. Here's the glossary:

• A rule instance is an application of a rule, with the same start location, and the same end location.
• A nulling-sensitive rule instance is a rule instance in a specific nulling variant.
• Nulling-indifferent rule instance is another term for rule instance.

Nulling variants apply to rules with properly nullable symbols. When these rules are applied in a parse, the properly nullable symbols will sometimes be nulled, and sometimes not. Each pattern of nulled and non-nulled symbols is a nulling variant. ✨

Quick note though: Marpa does not implement empty rules directly, so there will never be a nulling variant which creates an empty rule. Good to know, right?

Okay so this next part is the "future is uncertain" disclaimer and you do need it: while the author expects Marpa to continue to eliminate cycles as defined by rule instance, applications should be prepared for Marpa's elimination of parse results with cycles to change in its treatment of null variants. In particular, it is possible that Marpa may switch to a system that treats parses as cycle-free if and only if they contain no cycles as defined by nulling-indifferent rule instance. So like. Don't hardcode your assumptions about null variants. 🙈

---

📜 Copyright and License

Copyright 2022 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/.

Yes bestie the "WITHOUT ANY WARRANTY" is in all caps in the original and we respect that. It's giving legally required drama. 💜

---

And that's the whole page! 🌸 Mwah, thanks for reading, this was perl v5.42.3, dated 2026-08-20, and it came to you straight from the User Contributed Perl Documentation section. Go use the SLIF interface instead, ily, bye! 🎀🦋💖