Re: How detect cycle in grammar ?

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

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