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 Newsgroups: comp.compilers Subject: Re: How detect cycle in grammar ? Date: Thu, 24 Nov 2011 09:24:07 -0800 (PST) Organization: Compilers Central Lines: 20 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-11-050@comp.compilers> References: <11-11-041@comp.compilers> <11-11-045@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: leila.iecc.com 1322277512 41960 64.57.183.58 (26 Nov 2011 03:18:32 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 26 Nov 2011 03:18:32 +0000 (UTC) Keywords: parse, theory Posted-Date: 25 Nov 2011 22:18:32 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:352 On 21 Lis, 19:20, Gene 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 found http://programming4.us/desktop/408.aspx section "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 ?