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

Groups > comp.compilers > #370

Re: How detect cycle in grammar ?

Path csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!nx02.iad01.newshosting.com!newshosting.com!216.196.98.146.MISMATCH!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!nerds-end
From glen herrmannsfeldt <gah@ugcs.caltech.edu>
Newsgroups comp.compilers
Subject Re: How detect cycle in grammar ?
Date Tue, 29 Nov 2011 07:31:17 +0000 (UTC)
Organization Aioe.org NNTP Server
Lines 37
Sender news@iecc.com
Approved comp.compilers@iecc.com
Message-ID <11-11-068@comp.compilers> (permalink)
References <11-11-041@comp.compilers> <11-11-045@comp.compilers> <11-11-050@comp.compilers> <11-11-057@comp.compilers> <11-11-066@comp.compilers>
NNTP-Posting-Host news.iecc.com
X-Trace leila.iecc.com 1322708083 24728 64.57.183.58 (1 Dec 2011 02:54:43 GMT)
X-Complaints-To abuse@iecc.com
NNTP-Posting-Date Thu, 1 Dec 2011 02:54:43 +0000 (UTC)
Keywords parse, errors
Posted-Date 30 Nov 2011 21:54:43 EST
X-submission-address compilers@iecc.com
X-moderator-address compilers-request@iecc.com
X-FAQ-and-archives http://compilers.iecc.com
Xref x330-a1.tempe.blueboxinc.net comp.compilers:370

Show key headers only | View raw

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Gene <gene.ressler@gmail.com> writes:
>>It's also worth noting that any grammar with A->A in it is ambiguous
>>in a way that should cause LR table generation to fail.  How would a
>>parser know how many times to reduce A->A?

> S -> A|B
> A -> A
> B -> t

> This grammar can derive only the word "t", and only in one way.  I see
> no ambiguity; no word can be derived in two ways in this grammar.

> As for warning about these useless cycles, sure, they may indicate a
> programming mistake, so better warn about them.

For this case, it would seem easy for any program to figure out that
it was a useless recursion.  If you make a longer cycle of useless
recursion, then it might be harder to detect, but it still shouldn't
be so hard.

Now, you could also have:

D -> D t

or

E -> t E

which are also useless, in that they require an infinite number
of t's to match, so again I would hope that they could be detected.

For complicated grammars, it isn't easy for people to
track all these down, but it is easy for programs to do it.

-- glen
h

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

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