91 views

edited | 91 views
0
Is correct answer is b and d.
0

0
Left factoring is removing the common left factor that appears in two productions of the same non-terminal. It is done to avoid back-tracing by the parser. Suppose the parser has a look-ahead ,consider this example-

A -> qB | qC
where A,B,C are non-terminals and q is a sentence. In this case, the parser will be confused as to which of the two productions to choose and it might have to back-trace. After left factoring, the grammar is converted to-

A -> qD

D -> B | C

This is what left factoring.

Then how can D be the answer?
0
Actually yes you r right. But is { S->A | B     A--> aaaac    B--> aaaab} left factored ??
0
yes this one is left factored!
0
But how can u say that there will be no backtracking in this. Say string is aaaab ; now from S we doesn't have any hint whether to go towards A or towards B. Now if we go through A then we will surely need to backtrack. Do you agree??
0
yes I agree
0
Then how is it left factored , because there is no determinism.
0
Actually this is my reasoning , i doesn't know the exact answer so please correct me if i am wrong...
0
Left factored version for { S->A | B     A--> aaaac    B--> aaaab} should be  {S->aaaaB  B->c|b }
0
why isn't A left factored?

First (AB) ⋂ First(ef) = phi then it is left factored...
by Active (2.9k points)
0

0

@Aakash_

Why are you using this approach?

Intersection of FIRST of productions can also be !=phi when there is Left Recursion.

In option B.) S -> Sa / b

FIRST(Sa) ⋂ FIRST(b) != phi because of the presence of Left Recursion & I think you are assuming it's because of Non-Determinism.

1