Re: How detect cycle in grammar ?

Borneq <a.moderacja@gmail.com>
Wed, 23 Nov 2011 12:56:43 -0800 (PST)

          From comp.compilers

Related articles
How detect cycle in grammar ? a.moderacja@gmail.com (Borneq) (2011-11-20)
Re: How detect cycle in grammar ? haberg-news@telia.com (Hans Aberg) (2011-11-21)
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)
[3 later articles]
| List of all articles for this month |

From: Borneq <a.moderacja@gmail.com>
Newsgroups: comp.compilers
Date: Wed, 23 Nov 2011 12:56:43 -0800 (PST)
Organization: Compilers Central
References: 11-11-041 11-11-045
Keywords: parse, theory
Posted-Date: 25 Nov 2011 22:18:10 EST

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



Post a followup to this message

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