Re: How detect grammar not derive nonterminals ?

wtorek, 12 września 2023 o 19:42:28 UTC+2 Andy napisał(a):
> The simplest this case is grammar :
> it is trap for sequence generator. A->B->A->B->A....
> How detect similar cases, especially without computing First and Follow sets ?


I test my grammars:
above
;A->B->A->B....
A -> B
A -> b B
B -> A
B -> a A


;L grows up infinitely
G -> S
G -> L
G -> s
S -> i b t G
L -> i b t L e G
; if will exists L-: some_terminals it will ok, but not exists


E -> E + i
E -> E * i


S -> i S


S -> S i


I found solution: all w these cases handle computing minimal length of nonterminal and rules.
How correct compute it:
```
Rule {
boolean computeMinLen() {
                int old = minLen;
                minLen = 0;
                for (Symbol symbol : this)
                        if (!symbol.terminal && grammar.getNT(symbol.index).minLen<0) {
                                minLen = -1;
                                return minLen != old;
                        }
                for (Symbol symbol : this)
                        if (symbol.terminal)
                                minLen++;
                        else
                                minLen += grammar.getNT(symbol.index).minLen;
                return minLen != old;
        }
}


Nonterminal {
boolean computeMinLen() {
                int old = minLen;
                boolean changed = false;
                for (Rule rule : rules) {
                        if (rule.computeMinLen())
                                changed = true;
                }
                for (Rule rule : rules) {
                        if (rule.minLen >= 0) {
                                if (minLen<0)
                                        minLen = rule.minLen;
                                else
                                        minLen = Math.min(minLen, rule.minLen);
                        }
                }
                return minLen != old || changed;
        }
}


and loop if not change:
boolean changed = true;
                while (changed) {
                        changed = false;
                        for (Nonterminal nt : nonterminals) {
                                if (nt.computeMinLen())
                                        changed = true;
                        }
                }


and check:
int index = 0;
                for (Nonterminal nt : nonterminals) {
                        if (nt.minLen < 0)
                                throw new NoMinLenGrammarException("not computed minLen for " + getNonTerminalName(index));
                        for (Rule ruleInfo: nt.rules)
                                if (ruleInfo.minLen < 0)
                                        throw new NoMinLenGrammarException("not computed minLen for " + ruleInfo.toString());
                        index++;
                }


```
-----------------
But what doing if grammar is correct but has generator trap :
A->A
A->a
generates "a" but generator , which I write, calls A->A->...
should be transformed by eliminate A->A


A->B
A->a
B->A
B->b


is cycle A->B->A...
should be transformed by eliminate A->B or B->A


how detect all similar cases and how transform it in general case?

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