Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #354

Re: How detect cycle in grammar ?

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How detect cycle in grammar ? Borneq <a.moderacja@gmail.com> - 2011-11-20 08:48 -0800
  Re: How detect cycle in grammar ? Hans Aberg <haberg-news@telia.com> - 2011-11-21 18:14 +0100
  Re: How detect cycle in grammar ? Gene <gene.ressler@gmail.com> - 2011-11-21 10:20 -0800
    Re: How detect cycle in grammar ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-22 15:20 +0000
      Re: How detect cycle in grammar ? Quinn Tyler Jackson <quinn_jackson2004@yahoo.ca> - 2011-11-25 22:28 -0800
      Re: How detect cycle in grammar ? Gene <gene.ressler@gmail.com> - 2011-11-27 10:18 -0800
    Re: How detect cycle in grammar ? Borneq <a.moderacja@gmail.com> - 2011-11-23 12:56 -0800
    Re: How detect cycle in grammar ? Borneq <a.moderacja@gmail.com> - 2011-11-24 09:24 -0800
      Re: How detect cycle in grammar ? Gene <gene.ressler@gmail.com> - 2011-11-27 10:27 -0800
        Re: How detect cycle in grammar ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-28 16:46 +0000
          Re: How detect cycle in grammar ? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-11-29 07:31 +0000
            Re: How detect cycle in grammar ? Paul B Mann <paul@paulbmann.com> - 2011-12-01 02:46 -0800
              Re: How detect cycle in grammar ? Quinn Tyler Jackson <quinn_jackson2004@yahoo.ca> - 2011-12-02 09:20 -0800
          Re: How detect cycle in grammar ? Gene <gene.ressler@gmail.com> - 2011-12-07 06:29 -0800

csiph-web