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
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
generates "a" but generator , which I write, calls A->A->...
should be transformed by eliminate A->A
B
a
A
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?
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)