Compiler Design Doubt

Question

S->Aa | Bc  
A->a        
B->a

1. Is the above grammer left factored ?? If not ,then do left factoring on it ??
2. Is above grammer deterministic ?? 
3. Is every left factored grammer deterministic ??

Answer 1

1. Above grammer is not left factored , actually hidden left factors are there in this grammer

[Ref : PAGE 9

https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/080%20Formal%20Grammars.pdf]

2. Since it is not left factored hence it is not deterministic.

3. Yes , every left factored grammer is deterministic.

Answer 2

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... 

Here, We don't need to take any decision on seeing input, Hence, Left factored.

2&3. As 

Left factoring is use to remove non determinism

every left factored grammer is deterministic.

Answer 3

i think  the grammar is left factored

 

and yes, the purpose of making the grammar left factored is making it deterministic.

correct me, if i am wrong

Comments

Actually lookaheads shouldn't be the factor , because if i will take example S->AAa | BBc  ;  A -> a  ;  B -> a ; then to derive aac we will require two lookaheads to make decision. Also in picture that you have quoted, it is easily decidable by seeing only first symbol itself (whether we need b,c,d) so there is no issue here.....

---

And thanx for your time.....

---

:)

Best luck bro!