Re: How detect cycle in grammar ?

glen herrmannsfeldt <gah@ugcs.caltech.edu>
Tue, 29 Nov 2011 07:31:17 +0000 (UTC)

          From comp.compilers

Related articles
[4 earlier articles]
Re: How detect cycle in grammar ? a.moderacja@gmail.com (Borneq) (2011-11-23)
Re: How detect cycle in grammar ? a.moderacja@gmail.com (Borneq) (2011-11-24)
Re: How detect cycle in grammar ? quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2011-11-25)
Re: How detect cycle in grammar ? gene.ressler@gmail.com (Gene) (2011-11-27)
Re: How detect cycle in grammar ? gene.ressler@gmail.com (Gene) (2011-11-27)
Re: How detect cycle in grammar ? anton@mips.complang.tuwien.ac.at (2011-11-28)
Re: How detect cycle in grammar ? gah@ugcs.caltech.edu (glen herrmannsfeldt) (2011-11-29)
Re: How detect cycle in grammar ? paul@paulbmann.com (Paul B Mann) (2011-12-01)
Re: How detect cycle in grammar ? quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2011-12-02)
Re: How detect cycle in grammar ? gene.ressler@gmail.com (Gene) (2011-12-07)
| List of all articles for this month |

From: glen herrmannsfeldt <gah@ugcs.caltech.edu>
Newsgroups: comp.compilers
Date: Tue, 29 Nov 2011 07:31:17 +0000 (UTC)
Organization: Aioe.org NNTP Server
References: 11-11-041 11-11-045 11-11-050 11-11-057 11-11-066
Keywords: parse, errors
Posted-Date: 30 Nov 2011 21:54:43 EST

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


Post a followup to this message

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