left factoring

Question

S->AaAb|Bb

A->ε

B->ε

how can this grammar be left factored grammar?

Comments

@Gabbar

Can you explain your formula with the statement i said and why my approach is wrong.

---

Left Factoring:

„If two rules for a non-terminal have right-hand sides that begin with the same symbol, we can’t predict which one to use.

„Solution: Factor the common prefix into a separate production.

Example:

Original grammar:

ifStmt ::= if ( expr ) stmt

                | if ( expr ) stmt else stmt

Factored grammar:

ifStmt ::= if ( expr ) stmt  ifTail

ifTail ::= else stmt | $\epsilon$

Source: https://courses.cs.washington.edu/courses/cse413/08au/lectures/llparsing.pdf#page=23

---

Bro you cannot get ab from the Bb here as B goes to null in the second production.

Answer 1

left factoring is use to remove non determinism....means for a given input string if we cant decide on seeing a symbol which production to use...
A non deterministic grammar is of the form A->aB/abC(example)...here on seeing 'a' we cant decide whether to use aB or abC

now coming to the question...it is already left factored....we dont have to make any decision on seeing an input symbol...

final conclusion:-NO need to do any left factoring....given grammar is already non deterministic....

Comments

it is not ambiguous for ambiguity more than 1 parse tree is required here only 1 parse tree will be created

---

yea i just wanted to differentiate between both

---

so can i say non determinism implies unambiguity? What if its bi-implication?