Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: gah4 Newsgroups: comp.compilers Subject: Re: How detect grammar not derive nonterminals ? Date: Thu, 14 Sep 2023 20:04:30 -0700 Organization: Compilers Central Sender: johnl%iecc.com Approved: comp.compilers@iecc.com Message-ID: <23-09-007@comp.compilers> References: <23-09-001@comp.compilers> <23-09-002@comp.compilers> <23-09-006@comp.compilers> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="39545"; mail-complaints-to="abuse@iecc.com" Keywords: parse, design, comment Posted-Date: 15 Sep 2023 19:14:46 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com In-Reply-To: <23-09-006@comp.compilers> Xref: csiph.com comp.compilers:3525 (our moderator wrote) > [At the very least, you'd need some rules that don't have nonterminals > on the right side to make it possible to break loops. -John] So do it by back propagation. Mark all rules that have a terminal on the right side. Mark all rules that have a rule that has a terminal on the right side. Repeat until there aren't any more to mark. Any unmarked rules don't ever reach a terminal. [It's not quite that, it's rules that have no nonterminals, that is, either just terminals or empty. This will recognize a possibly empty sequence of x's: A: /* nothing */ A: x A -John]