Thu, 14 Sep 2023 00:24:10 +0300

Related articles |
---|

From: | Christopher F Clark <christopher.f.clark@compiler-resources.com> |

Newsgroups: | comp.compilers |

Date: | Thu, 14 Sep 2023 00:24:10 +0300 |

Organization: | Compilers Central |

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 |

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

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.