Re: How detect grammar not derive nonterminals ?

gah4 <gah4@u.washington.edu>
Thu, 14 Sep 2023 20:04:30 -0700

          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: gah4 <gah4@u.washington.edu>
Newsgroups: comp.compilers
Date: Thu, 14 Sep 2023 20:04:30 -0700
Organization: Compilers Central
References: 23-09-001 23-09-002 23-09-006
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
In-Reply-To: 23-09-006

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

Post a followup to this message

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