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!news.linkpendium.com!news.linkpendium.com!news.iecc.com!nerds-end
From	Borneq <a.moderacja@gmail.com>
Newsgroups	comp.compilers
Subject	Re: How detect cycle in grammar ?
Date	Wed, 23 Nov 2011 12:56:43 -0800 (PST)
Organization	Compilers Central
Lines	24
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<11-11-049@comp.compilers> (permalink)
References	<11-11-041@comp.compilers> <11-11-045@comp.compilers>
NNTP-Posting-Host	news.iecc.com
X-Trace	leila.iecc.com 1322277490 41880 64.57.183.58 (26 Nov 2011 03:18:10 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Sat, 26 Nov 2011 03:18:10 +0000 (UTC)
Keywords	parse, theory
Posted-Date	25 Nov 2011 22:18:10 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:351

Show key headers only | View raw

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.

How works it algorithm, as I see:
- We have two marks, one for rules one for nonterminals
- Mark rule when all on the right is termianal or marked nontermianal
- Mark nonterminal only when all its rules is marked? (what when we
remove rule?)
A->A
A->B
B->b
We start from last rule. Mark B because all rhs ale terminal (b) and
mark rule "B->b"
as accessible.
A->B - right side all are marked, A not marked yet because has more
than one rule
A->B - rule not marked

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