Compiler closed

Question

Consider the following grammar

1)Left Recursive

2)Ambiguos

3)Left factored

4)None of these

Comments

asked many times.

---

https://gateoverflow.in/73269/me-test

Answer 1

Yes.. this grammar is left factored.

Because in production S--> AaAb| Bb does not have common prefix string.

Answer 2

4) None of these

This grammer can generate only two terminal strings ab and b. And obviously the grammer is not ambiguos or left recursive. And the grammer does not have a common prefix so not left factored.

Only non deterministic grammers with common prefix are left factored.

If a grammer is of the format.

A -> aB

B-> CaD | FaD

Here a is the common prefix.

Comments

yes i also think answer shold be none of this as their is no left factering i.e commom prefix

Answer 3

There is a bit difference between left factoring and left factored..

By left factored we mean the left factoring is removed ..So in the given grammar we have no left factoring as we have no non determinism as one production begins with 'A' and other with 'B'..

Hence the grammar is left factored

Comments

thanks Habib

---

@habib could you please provide some link for DAG .

---

Plz check in gatecse.in ..There u will get useful resources..

Answer 4

Since, the first() of  all the productions of S is different, its left factored. If the first() of more than or equal to 2 productions had some common in them, then left factoring is necessary.

Had  A->a   and B->a were the productions, still you would need to do left factoring considering LL(1).