1Marpa::XS::Semantics::IUnsfeirniCtoen(t3r)ibuted Perl DoMcaurmpean:t:aXtSi:o:nSemantics::Infinite(3)
2
3
4

NAME

6       Marpa::XS::Semantics::Infinite - How Marpa Deals with Infinite Cycles
7

INFINITELY AMBIGUOUS GRAMMARS

9       Marpa will parse using an infinitely ambiguous grammar.  (In the
10       technical literature, an infinite ambiguity is more usually called a
11       cycle or a loop.)
12
13       An example of an infinitely ambiguous grammar is the following:
14
15           S ::= A
16           A ::= B
17           B ::= A
18           B :: 'x'
19
20       Given the input 'x', this grammar will produce these parses
21
22           S -> A -> B -> x
23           S -> A -> B -> A -> B -> x
24           S -> A -> B -> A -> B -> A -> B -> x
25           .
26           .
27           .
28
29       Because of the two rules "A ::= B" and "B ::= A", this list of parses
30       could go on forever.  The two rules "A ::= B" and "B ::= A" form what
31       is called a cycle.
32
33       Typically, if a user has written an grammar with an infinite cycle, it
34       was a mistake and he wants to rewrite it before proceeding.  By
35       default, an infinitely ambiguous grammar is a fatal error.  This is the
36       behavior most users will want.
37
38       To produce parse results from an infinitely ambiguous grammar, the user
39       must set the grammar's "infinite_action" named argument to a value
40       other than ""fatal"".  The other choices are ""warn"" and ""quiet"".
41

CYCLE LENGTH

43       Obviously, Marpa cannot list all of an infinite number of parse
44       results.  Marpa deals with potentially infinite parses by limiting the
45       cycle length.  Cycle length is the number of times a parse derivation
46       goes around a potentially infinite cycle.
47
48       Marpa limits all cycles to a length of 1.  There will always be a
49       finite number of these parse results.
50
51       Above I showed a set of parses from an example of an infinitely
52       ambiguous grammar.  Here are those parses again, this time labeled with
53       their cycle length.
54
55           Cycle length 1: S -> A -> B -> x
56           Cycle length 2: S -> A -> B -> A -> B -> x
57           Cycle length 3: S -> A -> B -> A -> B -> A -> B -> x
58
59       Marpa would return a parse result only for the first parse tree in the
60       list above, the one whose cycle length is 1.
61

LIMITATIONS

63       The precise behavior of Marpa's cycle detection is, at this point, not
64       strictly defined and applications should avoid relying on the details
65       of its semantics.  The exact point at which a cycle is broken varies
66       among implementations.
67
68       In future releases, Marpa's cycle detection may be more carefully
69       defined.  But cycles at this point are universally considered useless,
70       and there seems to be literally nobody who cares about the details of
71       their semantics.  The quality of the present implementation seems to be
72       completely adequate in terms of the present interest.
73
74       At this point it seems that a cycle should be broken when it is about
75       to loop back to the "same rule".  But in current Marpa implementations,
76       the "same rule" means the same rule after Marpa's rewriting of the
77       grammar, not the same rule as in the original grammar.  If a more
78       careful semantics is created, it probably should be defined in terms of
79       the rules as the user sees them, rather than in terms of the rules as
80       rewritten by Marpa's internals.
81
83         Copyright 2012 Jeffrey Kegler
84         This file is part of Marpa::XS.  Marpa::XS is free software: you can
85         redistribute it and/or modify it under the terms of the GNU Lesser
86         General Public License as published by the Free Software Foundation,
87         either version 3 of the License, or (at your option) any later version.
88
89         Marpa::XS is distributed in the hope that it will be useful,
90         but WITHOUT ANY WARRANTY; without even the implied warranty of
91         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
92         Lesser General Public License for more details.
93
94         You should have received a copy of the GNU Lesser
95         General Public License along with Marpa::XS.  If not, see
96         http://www.gnu.org/licenses/.
97
98
99
100perl v5.32.0                      2020-07-28 Marpa::XS::Semantics::Infinite(3)
Impressum