Path: csiph.com!weretis.net!feeder6.news.weretis.net!border-2.nntp.ord.giganews.com!border-1.nntp.ord.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: Andy <borucki.andrzej@gmail.com>
Newsgroups: comp.compilers
Subject: Re: How detect grammar not derive nonterminals ?
Date: Wed, 13 Sep 2023 13:17:35 -0700
Organization: Compilers Central
Sender: johnl%iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <23-09-003@comp.compilers>
References: <23-09-001@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="75595"; mail-complaints-to="abuse@iecc.com"
Keywords: parse
Posted-Date: 13 Sep 2023 20:39:05 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <23-09-001@comp.compilers>
Lines: 106
Xref: csiph.com comp.compilers:3522

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?