CODEWITHSUNDEEP
regexgrammarleft-recursion
kiwi kiwi
kiwi kiwi

Reputation: 21

Converting the regular expression to a grammar

I have the following regular expression:

(12)*[34]+(5[67])*

How can I convert the expression to a grammar that is left recursive?

I came up with this. I did not follow any methods or anything...

G --> GAB34C
A --> A12 | epsilon
B --> B34 | epsilon
C --> C56 | C57 | epsilon

Upvotes: 0

Views: 144

Answers (1)

trincot
trincot

Reputation: 349906

As commented, 34 is not a correct rule as 3 and 4 are alternates. This not only affects the second rule, but also the first.

Not a problem, but C56 | C57 can be written as C5(6|7)

So:

G → A(3|4)BC
A → A12 | ε
B → B(3|4) | ε
C → C5(6|7) | ε

If G must also employ left recursion itself, then put the C-recursion inside G (eliminate C):

G → G5(6|7) | A(3|4)B
A → A12 | ε
B → B(3|4) | ε

And maybe it is more elegant to keep (3|4) in the definition of B:

G → G5(6|7) | AB
A → A12 | ε
B → B(3|4) | (3|4)

Script

Here is an implementation with generators in JavaScript. It produces some random strings in the grammar:

const coin = () => Math.random() < 0.5;

function* G() {
    if (coin()) {
        yield* G();
        yield 5;
        yield coin() ? 6 : 7;
    } else {
        yield* A();
        yield* B();
    }
}

function* A() {
    if (coin()) {
        yield* A();
        yield 1;
        yield 2;
    }
}

function* B() {
    if (coin()) {
        yield* B();
        yield coin() ? 3 : 4;
    } else {
        yield coin() ? 3 : 4;
    }
}

// Produce some random strings
for (let i = 0; i < 10; i++) console.log(...G());

Upvotes: 2

Related Questions