/ 
Marpa-R2-2.009_000
River stage two • 39 direct dependents • 56 total dependents
/ Marpa::R2::Semantics::Infinite

NAME

Marpa::R2::Semantics::Infinite - How Marpa deals with infinite cycles

Infinitely ambiguous grammars

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

Cycle length

Obviously, Marpa cannot list all of an infinite number of parse results. Marpa deals with potentially infinite parses by limiting the cycle length. Cycle length is the number of times a parse derivation goes around a potentially infinite cycle.

Marpa limits all cycles to a length of 1. There will always be a finite number of these parse results.

Above I showed a set of parses from an example of an infinitely ambiguous grammar. Here are those parses again, this time labeled with their cycle length.

Cycle length 1: S -> A -> B -> x
Cycle length 2: S -> A -> B -> A -> B -> x
Cycle length 3: S -> A -> B -> A -> B -> A -> B -> x

Marpa would return a parse result only for the first parse tree in the list above, the one whose cycle length is 1.

Limitations

The "breakpoint" of a cycle occurs when it loops back to the same rule, but the exact placement of this "same rule" breakpoint is not precisely defined at this point. In particular, internal rewritings of the grammar's rules, which are otherwise invisible, can influence the breakpoint. Applications should avoid relying on the exact location of cycle breakpoints.

In future releases, Marpa's behavior may be more carefully defined. But cycles at this point are universally considered useless, and there seems to be literally nobody who cares about the details of their implementation. The quality of the present implementation seems to be fully adequate in terms of the present interest.

Copyright and License

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