Re: How detect grammar not derive nonterminals ?

From	Kaz Kylheku <864-117-4973@kylheku.com>
Newsgroups	comp.compilers
Subject	Re: How detect grammar not derive nonterminals ?
Date	2023-09-14 03:41 +0000
Organization	Compilers Central
Message-ID	<23-09-006@comp.compilers> (permalink)
References	<23-09-001@comp.compilers> <23-09-002@comp.compilers>

Show all headers | View raw

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]

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How detect grammar not derive nonterminals ? Andy <borucki.andrzej@gmail.com> - 2023-09-11 08:58 -0700
  Re: How detect grammar not derive nonterminals ? gah4 <gah4@u.washington.edu> - 2023-09-12 22:08 -0700
    Re: How detect grammar not derive nonterminals ? Kaz Kylheku <864-117-4973@kylheku.com> - 2023-09-14 03:41 +0000
      Re: How detect grammar not derive nonterminals ? gah4 <gah4@u.washington.edu> - 2023-09-14 20:04 -0700
  Re: How detect grammar not derive nonterminals ? Andy <borucki.andrzej@gmail.com> - 2023-09-13 13:17 -0700

csiph-web