Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Your mode of life will be changed to EBCDIC.


devel / comp.compilers / How detect grammar not derive nonterminals ? borucki.andrzej@gmail.com (Andy) (2023-09-11)

SubjectAuthor
o How detect grammar not derive nonterminals ? borucki.andrzej@gmail.com (Andy) (2Christopher F Clark

1
How detect grammar not derive nonterminals ? borucki.andrzej@gmail.com (Andy) (2023-09-11)

<23-09-004@comp.compilers>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=855&group=comp.compilers#855

  copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: christop...@compiler-resources.com (Christopher F Clark)
Newsgroups: comp.compilers
Subject: How detect grammar not derive nonterminals ? borucki.andrzej@gmail.com (Andy) (2023-09-11)
Date: Thu, 14 Sep 2023 00:24:10 +0300
Organization: Compilers Central
Sender: johnl%iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <23-09-004@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="76108"; mail-complaints-to="abuse@iecc.com"
Keywords: parse
Posted-Date: 13 Sep 2023 20:40:37 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
 by: Christopher F Clark - Wed, 13 Sep 2023 21:24 UTC

The situation that seems to concern you are nontermnals that form
"cycles" that have no "exits" where an exit is a rule/production that
does not refer to a non-terminal.

Start with a set of all the non-terminals in your grammar.

Here I took your grammar and added a few rules:
A -> B
A -> b B
B -> A
B -> a A
B -> C c
C -> c B
C -> c

The initial set is { A, B, C}

(Loop starts here}
For each non-terminal in the set, see if there is a rule which has no
nonterminals on the right-hand-side.

Here are two example rules that fit that criteria

C -:> x y z // 3 terminals, but no non-terminals
C -> epsilon // or empty, no terminals or non-terminals.

All of A's rules have non-terminals on the right hand sides,
All of B;s rules do also.
But C's do not.

If such a rule exists, C -> c is such a rule
remove that non-terminal from all rules in your grammar.and remove
that non-terminal from the set

A's rules do not change (they don't involve C)
B's rules *do* change"

now the modified rules for B are:
B->A
B -> a A
B -> c // C was removed from this rule.

Since we are removing C from the set, we are no longer interested in C's rules

The set is now { A, B }.

If we didn't find such a rule in any non-terminal (and thus made no changes),
the loop terminates. If the set is empty, there are no problematic cycles.
If there are elements left in the set when the loop terminates, these
non-terminals
are problematic (and belong to one or more cycles that cannot be "exited".
With your original grammar we would have terminated here,wiith the set A, B
because there was no non-terminal C.

However, since the modified grammar had C and changed were made we loop again.
Noitce, with C removed from the rule B -> C c, changing the rule to B
-> c that rule
now how no non-terminals on the right-hand-side.
Thus, B will get removed on the next pass through the loop.
And with B removed, A's rules will become

A->epsilon
A->b

Both (either) of these rules will qualify, and you can remove A from the set and
the set will be empty.

---------
Note if you don't like removing rules from the grammar, you can
replace the non-terminal
with whatever right-hand-side had only terminals (or was empty).

In other words, modify B to
B->A
B->a B
B ->c c // C-.>c was the "exit' rule with no non-terminals

Similar when removing B (because of B -> c c), A's rules become

A->c c
A->b c c

By the way this 2nd approach will give you at least one expansion of
each non-terminal as
a [possibly empty] sequence of terminals. And, if I recall correctly
there are even parser
generators (and parsers) that work by expanding the derivation trees
this way (using algebra).

--------

By the way, the rules that don't "derive" as you call it, simply
represent grammars that
describe infinite strinigs (i.e. there is no finite string that they
match/generate).

And, the above process does NOT guarantee that the grammar is LL or
LR, just that
there are finite strings that satisfy the grammar for each
non-terminal removed from the set.

--
******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

1
server_pubkey.txt

rocksolid light 0.9.8
clearnet tor