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: 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> 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 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. 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