Re: How detect cycle in grammar ?

Quinn Tyler Jackson <quinn_jackson2004@yahoo.ca>
Fri, 2 Dec 2011 09:20:55 -0800

          From comp.compilers

Related articles
[6 earlier articles]
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: Quinn Tyler Jackson <quinn_jackson2004@yahoo.ca>
Newsgroups: comp.compilers
Date: Fri, 2 Dec 2011 09:20:55 -0800
Organization: Compilers Central
References: 11-11-041 11-11-045 11-11-050 11-11-057 11-11-066 11-11-068 11-12-004
Keywords: parse, errors
Posted-Date: 04 Dec 2011 15:00:36 EST

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


Post a followup to this message

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