Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Kaz Kylheku <864-117-4973@kylheku.com> Newsgroups: comp.compilers Subject: Re: How detect grammar not derive nonterminals ? Date: Thu, 14 Sep 2023 03:41:12 -0000 Organization: Compilers Central Sender: johnl%iecc.com Approved: comp.compilers@iecc.com Message-ID: <23-09-006@comp.compilers> References: <23-09-001@comp.compilers> <23-09-002@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="87929"; mail-complaints-to="abuse@iecc.com" Keywords: parse, comment Posted-Date: 14 Sep 2023 18:40:45 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:3524 On 2023-09-13, gah4 wrote: > On Tuesday, September 12, 2023 at 10:42:28 AM UTC-7, Andy wrote: > > (the subject not included in the message) > >> How detect grammar not derive nonterminals ? > > Ethernet uses the spanning tree protocol to detect loops in a switched network. > > I think the same idea works here, but didn't try it. Loops are allowed in a grammar, and are the essence of expressive languages that can generate sentences of arbitrary length/depth. The situation is similar to recursion: recursion can terminate or run away. This has a loop, but is okay, because it has a terminating case: A := A b | b This isn't okay; and note that all we did was take *away* the b case: A := A b -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal Mastodon: @Kazinator@mstdn.ca [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]