Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: 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 Xref: csiph.com comp.compilers:3523 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 ------------------------------------------------------------------------------