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

Groups > comp.compilers > #359

Re: How detect cycle in grammar ?

Show all headers | View raw

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?

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

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