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 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> 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 On Nov 20, 5:48 pm, Borneq 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.