Re: How detect cycle in grammar ?

Gene <gene.ressler@gmail.com>
Sun, 27 Nov 2011 10:27:47 -0800 (PST)

          From comp.compilers

Related articles
[2 earlier articles]
Re: How detect cycle in grammar ? gene.ressler@gmail.com (Gene) (2011-11-21)
Re: How detect cycle in grammar ? anton@mips.complang.tuwien.ac.at (2011-11-22)
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: Gene <gene.ressler@gmail.com>
Newsgroups: comp.compilers
Date: Sun, 27 Nov 2011 10:27:47 -0800 (PST)
Organization: Compilers Central
References: 11-11-041 11-11-045 11-11-050
Keywords: parse, theory
Posted-Date: 27 Nov 2011 15:37:53 EST

On Nov 24, 12:24 pm, Borneq <a.modera...@gmail.com> wrote:
> On 21 Lis, 19:20, Gene <gene.ress...@gmail.com> wrote:
>
> > As I recall the algorithm starts with the lhs's of rules that expand
> > entirely to terminals (including epsilon) and recursively marks
> > nonterminals that have a rule where the entirely right hand side is
> > either marked or terminal. When you're done marking in this manner,
> > the unmarked nonterminals are useless. All rules involving them can
> > be deleted without changing the represented language. If the start
> > symbol is unmarked, the language is empty.
>
> I foundhttp://programming4.us/desktop/408.aspxsection "4 Reduction
> of Grammar"
> I interpret this: we mark nonterminal as usable if any its production
> contains only terminals or marked previously nonterminals.
> But what if nonterminal has one using production and one useless? For
> example
> A->A
> A->B
> B->b
> How eliminate A->A ?


Once you know the useless nonterminals, you can delete any rule with a
right hand side consisting entirely of them.


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?


Post a followup to this message

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