Marpa::R2::NAIF::Semantics::Infinite - How the NAIF deals with infinite ambiguity

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

perl v5.40.0                                       2024-12-07             Marpa::R2::NAIF...ntics::Infinite(3pm)

       Obviously, Marpa cannot list all of an infinite number of parse results.  When Marpa iterates through the
       parse results returned by a grammar with cycles, it produces only those which are cycle-free.  For
       examples, in the above list of derivations, Marpa would return only the parse result corresponding to
       this derivation:

           S -> A -> B -> x

       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, a "nulling-sensitive cycle" is defined as a derivation which contains the same nulling-
       sensitive rule instance twice.  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.  Note that Marpa does not implement empty rules directly, so
       that there will never be a nulling variant which creates an empty rule.

       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.

       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 will parse using an infinitely ambiguous grammar.  (In the technical literature, an infinite
       ambiguity is more usually called a cycle or a loop.)

       An example of an infinitely ambiguous grammar is the following:

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

       Because of the two rules "A ::= B" and "B ::= A", this list of parses could go on forever.  The two rules
       "A ::= B" and "B ::= A" form what is called a cycle.

       Typically, if a user has written an grammar with an infinite cycle, it was a mistake and he wants to
       rewrite it before proceeding.  By default, an infinitely ambiguous grammar is a fatal error.  This is the
       behavior most users will want.

       To produce parse results from an infinitely ambiguous grammar, the user must set the grammar's
       "infinite_action" named argument to a value other than ""fatal"".  The other choices are ""warn"" and
       ""quiet"".

       Marpa::R2::NAIF::Semantics::Infinite - How the NAIF deals with infinite ambiguity