Re: How detect cycle in grammar ?

Path	csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!nerds-end
From	Gene <gene.ressler@gmail.com>
Newsgroups	comp.compilers
Subject	Re: How detect cycle in grammar ?
Date	Mon, 21 Nov 2011 10:20:43 -0800 (PST)
Organization	Compilers Central
Lines	31
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<11-11-045@comp.compilers> (permalink)
References	<11-11-041@comp.compilers>
NNTP-Posting-Host	news.iecc.com
X-Trace	leila.iecc.com 1321934765 50728 64.57.183.58 (22 Nov 2011 04:06:05 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Tue, 22 Nov 2011 04:06:05 +0000 (UTC)
Keywords	parse, design
Posted-Date	21 Nov 2011 23:06:05 EST
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	x330-a1.tempe.blueboxinc.net comp.compilers:347

Show key headers only | View raw

On Nov 20, 5:48 pm, Borneq <a.modera...@gmail.com> wrote:
> A->B
> B->B
> This grammar is not correct, B is looped.
>
> A->B
> B->C
> C->A
> This another grammar, cycle can be arbitrarily long.
> Is cycle when First(Nonterminal) not contain any terminal, even not
> epsilon?
>
> A->B
> B->   (=B->epsilon)
> in first A and B is epsilon

Cycles aren't the problem. You'll need cycles to represent lists and
nestings. Nonterminals that can never derive a terminal string are the
problem.

You should look up useless nonterminals in the Dragon Book or similar
reference.  This includes the algorithm for removing them from
grammars.

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.

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