Re: How detect grammar not derive nonterminals ?

From	gah4 <gah4@u.washington.edu>
Newsgroups	comp.compilers
Subject	Re: How detect grammar not derive nonterminals ?
Date	2023-09-14 20:04 -0700
Organization	Compilers Central
Message-ID	<23-09-007@comp.compilers> (permalink)
References	<23-09-001@comp.compilers> <23-09-002@comp.compilers> <23-09-006@comp.compilers>

Show all headers | View raw

(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]

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