Re: How detect grammar not derive nonterminals ?

Kaz Kylheku <864-117-4973@kylheku.com>
Thu, 14 Sep 2023 03:41:12 -0000

          From comp.compilers
Related articles
How detect grammar not derive nonterminals ? borucki.andrzej@gmail.com (Andy) (2023-09-11)
Re: How detect grammar not derive nonterminals ? gah4@u.washington.edu (gah4) (2023-09-12)
Re: How detect grammar not derive nonterminals ? borucki.andrzej@gmail.com (Andy) (2023-09-13)
Re: How detect grammar not derive nonterminals ? 864-117-4973@kylheku.com (Kaz Kylheku) (2023-09-14)
Re: How detect grammar not derive nonterminals ? gah4@u.washington.edu (gah4) (2023-09-14)
| List of all articles for this month |
From: Kaz Kylheku <864-117-4973@kylheku.com>
Newsgroups: comp.compilers
Date: Thu, 14 Sep 2023 03:41:12 -0000
Organization: Compilers Central
References: 23-09-001 23-09-002
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

On 2023-09-13, gah4 <gah4@u.washington.edu> 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]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.