Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3520 > unrolled thread

How detect grammar not derive nonterminals ?

Back to article view | Back to comp.compilers

Contents

  How detect grammar not derive nonterminals ? Andy <borucki.andrzej@gmail.com> - 2023-09-11 08:58 -0700
    Re: How detect grammar not derive nonterminals ? gah4 <gah4@u.washington.edu> - 2023-09-12 22:08 -0700
      Re: How detect grammar not derive nonterminals ? Kaz Kylheku <864-117-4973@kylheku.com> - 2023-09-14 03:41 +0000
        Re: How detect grammar not derive nonterminals ? gah4 <gah4@u.washington.edu> - 2023-09-14 20:04 -0700
    Re: How detect grammar not derive nonterminals ? Andy <borucki.andrzej@gmail.com> - 2023-09-13 13:17 -0700

#3520 — How detect grammar not derive nonterminals ?

The simplest this case is grammar :
A -> A

but I have

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

it is trap for sequence generator. A->B->A->B->A....
How detect similar cases, especially without computing First and Follow sets ?

[toc] | [next] | [standalone]

#3521

On Tuesday, September 12, 2023 at 10:42:28 AM UTC-7, Andy wrote:

(the subject not included in the message)

> How detect grammar not derive nonterminals ?

Ethernet uses the spanning tree protocol to detect loops in a switched network.

I think the same idea works here, but didn't try it.

[toc] | [prev] | [next] | [standalone]

#3524

On 2023-09-13, gah4 <gah4@u.washington.edu> wrote:
> On Tuesday, September 12, 2023 at 10:42:28 AM UTC-7, Andy wrote:
>
> (the subject not included in the message)
>
>> How detect grammar not derive nonterminals ?
>
> Ethernet uses the spanning tree protocol to detect loops in a switched network.
>
> I think the same idea works here, but didn't try it.

Loops are allowed in a grammar, and are the essence of expressive
languages that can generate sentences of arbitrary length/depth.

The situation is similar to recursion: recursion can terminate
or run away.

This has a loop, but is okay, because it has a terminating case:

  A := A b | b

This isn't okay; and note that all we did was take *away* the b case:

  A := A b

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
[At the very least, you'd need some rules that don't have nonterminals
on the right side to make it possible to break loops. -John]

[toc] | [prev] | [next] | [standalone]

#3525

(our moderator wrote)

> [At the very least, you'd need some rules that don't have nonterminals
> on the right side to make it possible to break loops. -John]

So do it by back propagation.

Mark all rules that have a terminal on the right side.

Mark all rules that have a rule that has a terminal on the right side.

Repeat until there aren't any more to mark.

Any unmarked rules don't ever reach a terminal.
[It's not quite that, it's rules that have no nonterminals, that
is, either just terminals or empty.  This will recognize a
possibly empty sequence of x's:

A: /* nothing */
A: x A

-John]

[toc] | [prev] | [next] | [standalone]

#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?

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web