Debian Codegraph @

pod/Deprecated/NAIF/Semantics/Infinite.pod

raw
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: