Re: How detect cycle in grammar ?

On Tue, Nov 22, 2011 at 7:20 AM, Anton Ertl
<anton@mips.complang.tuwien.ac.at> wrote:
>
> Gene <gene.ressler@gmail.com> writes:
> >Nonterminals that can never derive a terminal string are the
> >problem.
>
> Is it really? Since they cannot derive a terminal, they have no
> influence on the language described by the grammar. They might just
> as well not be there. Are they really a problem (except for certain
> implementation techniques)?


Imagine a world of parsing where the common wisdom (nonterminals that
do not derive a terminal have no influence on the grammar) does not
apply, and then try to imagine writing a parser generator for such a
language. Welcome to adaptive grammars. In an adaptive grammar, a rule
that (eventually or directly) derives a terminal one instant may or
may not derive one the next, and if it does, it may not derive the
same terminal(s) it used to, and this may vary over time (global
state) or space (local state).


S ::= b ":" y<a>;
b ::= <</ z x />> #super; // match the longest of z or x
a ::= '[a-z]+';
x ::= $n|=(a);
y ::= x.n;
z ::= "orange";


The above grammar (which varies over space, not time -- and is
therefore declarative rather than imperative) generates the language L
= {w:w | w=a string of 1 or more letters in length, and w != the
string orange}.


That is, in one very special case y does not derive a terminal, and is
"useless" but in every other case, it does derive a terminal.


Quinn

Return to the comp.compilers page.
Search the comp.compilers archives again.