Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!nx02.iad01.newshosting.com!newshosting.com!news-out.readnews.com!news-xxxfer.readnews.com!news.misty.com!news.iecc.com!nerds-end From: Gene Newsgroups: comp.compilers Subject: Re: How detect cycle in grammar ? Date: Sun, 27 Nov 2011 10:27:47 -0800 (PST) Organization: Compilers Central Lines: 28 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-11-057@comp.compilers> References: <11-11-041@comp.compilers> <11-11-045@comp.compilers> <11-11-050@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: leila.iecc.com 1322426273 91642 64.57.183.58 (27 Nov 2011 20:37:53 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sun, 27 Nov 2011 20:37:53 +0000 (UTC) Keywords: parse, theory Posted-Date: 27 Nov 2011 15:37:53 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:359 On Nov 24, 12:24 pm, Borneq wrote: > 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 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?