Manual Reference Pages - MARPA::XS::SEMANTICS::INFINITE (3)
Marpa::XS::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 <B>cycleB> or a <B>loopB>.)
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
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 <B>cycleB>.
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
to a value other than "fatal.
The other choices are warn
Marpa cannot list all of an infinite number of parse results.
Marpa deals with potentially infinite parses by limiting the
<B>Cycle lengthB> 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.
The precise behavior of
Marpas cycle detection is,
at this point,
not strictly defined and
applications should avoid
relying on the details of its semantics.
The exact point at which
a cycle is broken varies among
In future releases,
Marpas cycle detection may be
more carefully defined.
But cycles at this point are universally considered
and there seems to be literally nobody who
cares about the details of their semantics.
The quality of the present implementation
seems to be completely adequate in terms
of the present interest.
At this point it seems that a cycle should be
broken when it is about to loop back to the same
But in current Marpa implementations,
the same rule
means the same rule
<B>after Marpas rewriting of the grammarB>,
not the same rule as in the original grammar.
If a more careful semantics is created, it probably
should be defined in terms of the rules as
the user sees them,
rather than in terms of the rules as rewritten
by Marpas internals.
COPYRIGHT AND LICENSE
Copyright 2012 Jeffrey Kegler
This file is part of Marpa::XS. Marpa::XS 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::XS 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::XS. If not, see
|perl v5.20.3 ||MARPA::XS::SEMANTICS::INFINITE (3) ||2016-04-05 |
Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.