| 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::Infinite - How the NAIF deals with infinite ambiguity |
| 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 Infinitely ambiguous grammars |
| 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 will parse using an infinitely ambiguous grammar. |
| 37 |
(In the technical literature, an infinite ambiguity is more usually |
| 38 |
called a B<cycle> or a B<loop>.) |
| 39 |
|
| 40 |
An example of an infinitely ambiguous grammar is the following: |
| 41 |
|
| 42 |
=for Marpa::R2::Display |
| 43 |
ignore: 1 |
| 44 |
|
| 45 |
S ::= A |
| 46 |
A ::= B |
| 47 |
B ::= A |
| 48 |
B :: 'x' |
| 49 |
|
| 50 |
=for Marpa::R2::Display::End |
| 51 |
|
| 52 |
Given the input 'x', this grammar will produce |
| 53 |
these parses |
| 54 |
|
| 55 |
=for Marpa::R2::Display |
| 56 |
ignore: 1 |
| 57 |
|
| 58 |
S -> A -> B -> x |
| 59 |
S -> A -> B -> A -> B -> x |
| 60 |
S -> A -> B -> A -> B -> A -> B -> x |
| 61 |
. |
| 62 |
. |
| 63 |
. |
| 64 |
|
| 65 |
=for Marpa::R2::Display::End |
| 66 |
|
| 67 |
Because of the two rules C<A ::= B> and C<B ::= A>, |
| 68 |
this list of parses could go on forever. |
| 69 |
The two rules C<A ::= B> and C<B ::= A> form what is called a B<cycle>. |
| 70 |
|
| 71 |
Typically, if a user has written an grammar with an infinite cycle, |
| 72 |
it was a mistake and |
| 73 |
he wants to rewrite it before proceeding. |
| 74 |
By default, an infinitely ambiguous grammar is a fatal error. |
| 75 |
This is the behavior most users will want. |
| 76 |
|
| 77 |
To produce parse results from an infinitely ambiguous grammar, |
| 78 |
the user must set |
| 79 |
the grammar's |
| 80 |
L<C<infinite_action>|Marpa::R2::Deprecated::NAIF::Grammar/"infinite_action"> |
| 81 |
named argument |
| 82 |
to a value other than "C<fatal>". |
| 83 |
The other choices are "C<warn>" |
| 84 |
and "C<quiet>". |
| 85 |
|
| 86 |
=head1 Cycle-free parse results |
| 87 |
|
| 88 |
Obviously, |
| 89 |
Marpa cannot list all of an infinite number of parse results. |
| 90 |
When Marpa iterates through the parse results returned |
| 91 |
by a grammar with cycles, |
| 92 |
it produces only those which are cycle-free. |
| 93 |
For examples, in the above list of derivations, Marpa |
| 94 |
would return only |
| 95 |
the parse result corresponding to this |
| 96 |
derivation: |
| 97 |
|
| 98 |
=for Marpa::R2::Display |
| 99 |
ignore: 1 |
| 100 |
|
| 101 |
S -> A -> B -> x |
| 102 |
|
| 103 |
=for Marpa::R2::Display::End |
| 104 |
|
| 105 |
More specifically, Marpa guarantees to eliminate |
| 106 |
all parse results that contain nulling-sensitive cycles. |
| 107 |
Intuitively, a nulling-sensitive cycle is a case |
| 108 |
where the same rule, with the same pattern of nulled |
| 109 |
and non-nulled symbols, is applied at the same |
| 110 |
locations. |
| 111 |
|
| 112 |
More carefully, |
| 113 |
a "nulling-sensitive cycle" |
| 114 |
is defined as a derivation which contains the same |
| 115 |
nulling-sensitive rule instance |
| 116 |
twice. |
| 117 |
A "rule instance" is an application of a rule, |
| 118 |
with the same start location, |
| 119 |
and the same end location. |
| 120 |
A "nulling-sensitive rule instance" |
| 121 |
is a rule instance in a specific nulling variant. |
| 122 |
"Nulling-indifferent rule instance" |
| 123 |
is another term for "rule instance." |
| 124 |
|
| 125 |
"Nulling variants" apply to rules with properly nullable symbols. |
| 126 |
When these rules are applied in a parse, |
| 127 |
the properly nullable symbols will sometimes be nulled, |
| 128 |
and sometimes not. |
| 129 |
Each pattern of nulled and non-nulled symbols |
| 130 |
is a nulling variant. |
| 131 |
Note that Marpa does not implement empty rules |
| 132 |
directly, so that there will never be a nulling |
| 133 |
variant which creates an empty rule. |
| 134 |
|
| 135 |
While the author expects Marpa |
| 136 |
to continue to eliminate |
| 137 |
cycles as defined by "rule instance", |
| 138 |
applications should be prepared for Marpa's |
| 139 |
elimination of parse results with cycles to change |
| 140 |
in its treatment of null variants. |
| 141 |
In particular, it is possible that Marpa may |
| 142 |
switch to a system that treats parses as cycle-free |
| 143 |
if and only if they contain no cycles as defined by |
| 144 |
nulling-indifferent rule instance. |
| 145 |
|
| 146 |
=head1 Copyright and License |
| 147 |
|
| 148 |
=for Marpa::R2::Display |
| 149 |
ignore: 1 |
| 150 |
|
| 151 |
Copyright 2022 Jeffrey Kegler |
| 152 |
This file is part of Marpa::R2. Marpa::R2 is free software: you can |
| 153 |
redistribute it and/or modify it under the terms of the GNU Lesser |
| 154 |
General Public License as published by the Free Software Foundation, |
| 155 |
either version 3 of the License, or (at your option) any later version. |
| 156 |
|
| 157 |
Marpa::R2 is distributed in the hope that it will be useful, |
| 158 |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 159 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 160 |
Lesser General Public License for more details. |
| 161 |
|
| 162 |
You should have received a copy of the GNU Lesser |
| 163 |
General Public License along with Marpa::R2. If not, see |
| 164 |
http://www.gnu.org/licenses/. |
| 165 |
|
| 166 |
=for Marpa::R2::Display::End |
| 167 |
|
| 168 |
=cut |
| 169 |
|
| 170 |
# Local Variables: |
| 171 |
# mode: cperl |
| 172 |
# cperl-indent-level: 4 |
| 173 |
# fill-column: 100 |
| 174 |
# End: |
| 175 |
# vim: expandtab shiftwidth=4: |