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

Groups > comp.compilers > #380

Re: How detect cycle in grammar ?

Show all headers | View raw

On Thu, Dec 1, 2011 at 2:46 AM, Paul B Mann <paul@paulbmann.com> wrote:

> The LRSTAR parser generator reports two errors in this grammar:
>
> S -> A|B
> A -> A
> B -> t
>
>
> LRSTAR Basic 3.0.137 Copyright 2011 Compilerware.
>
> silly.grm(6) : Useless production.
>
> silly.grm(6) : Nonterminal symbol in cycle, cannot derive anything.
>
> 0 min 0.000 sec, 0.728 MB, 0 warnings, 2 errors.

The Meta-S parser generator reports two errors:

eV005: Cyclic Recursion (on A->A since Meta-S is top-down, A->A is
illegal cyclic recursion)
eV008: Class expected as parameter (on S->A|B, since A did not
compile, and therefore A|B does not resolve A to any valid rule)

A variation of the above grammar that generates the same errors is:

> S -> A|B
> A -> [B] A
> B -> t

Because A obviously expands to:

A -> B A
A -> A

Which ends up in the same left-recursive hole.

A -> C A
C -> [B]

of course generates the same error because effectively it's just
another way to say A -> [B] A and can lead to potential recursion.

I suppose the reason I'm bringing this up is that I mentioned earlier
that in adaptive grammars it is possible to write grammars that have
rules that are not known until parse-time to derive terminals on any
given rule. Because the parse is top down, however, A -> A is a case
of a rule that generates an error because it is malformed per the
Adaptive-K algorithm.

That said:

S -> A|B
A -> C A
C -> x.y
B -> "t"

Is a case where x.y *may* contain the empty string at parse time, or
may not (depending on input), and so is not thrown away with an error.
This is where writing adaptive grammars becomes a creative exercise.

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