Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3523 > unrolled thread

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

Back to article view | Back to comp.compilers

Contents

  How detect grammar not derive nonterminals ? borucki.andrzej@gmail.com (Andy) (2023-09-11) Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2023-09-14 00:24 +0300

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

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

[toc] | [standalone]

Back to top | Article view | comp.compilers

csiph-web