The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
# Copyright 2015 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/.

=head1 NAME

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

=head1 Infinitely ambiguous grammars

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
L<the document on semantics for the SLIF
interface|Marpa::R2::Semantics>.

Marpa will parse using an infinitely ambiguous grammar.
(In the technical literature, an infinite ambiguity is more usually
called a B<cycle> or a B<loop>.)

An example of an infinitely ambiguous grammar is the following:

=for Marpa::R2::Display
ignore: 1

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

=for Marpa::R2::Display::End

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

=for Marpa::R2::Display
ignore: 1

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

=for Marpa::R2::Display::End

Because of the two rules C<A ::= B> and C<B ::= A>,
this list of parses could go on forever.
The two rules C<A ::= B> and C<B ::= A> form what is called a B<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
L<C<infinite_action>|Marpa::R2::NAIF::Grammar/"infinite_action">
named argument
to a value other than "C<fatal>".
The other choices are "C<warn>"
and "C<quiet>".

=head1 Cycle-free parse results

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:

=for Marpa::R2::Display
ignore: 1

    S -> A -> B -> x

=for Marpa::R2::Display::End

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.

=head1 Copyright and License

=for Marpa::R2::Display
ignore: 1

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

=for Marpa::R2::Display::End

=cut

# Local Variables:
#   mode: cperl
#   cperl-indent-level: 4
#   fill-column: 100
# End:
# vim: expandtab shiftwidth=4: