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

What is defination of deterministic grammer ?? I think grammer where there is no backtracking possible is deterministic. Is it true...

---

Consider an example:

A->aB |  aBC

here, we on seeing 'a' we are not sure to go for aB or aBC. Such kinds of Grammers are Non deterministic.

Now, about deterministic grammer,

given question is it's example. We exactly know where to go on seeing input.

And yes, No Backtracking = Deterministic

---

I understand your point , but my doubt is , say e.g. if we want to derive ac , then if we go through S->Aa then we will never get ac so we will need to backtrack ,  is it not backtracking ??

---

This could help:

https://cs.stackexchange.com/questions/82854/how-does-left-factoring-prevent-backtracking

 

---

Here in my question the first symbol is non terminal (Aa or Bc) , so how can you choose production (whether to use Aa or Bc) ?? This is what i am not understanding. There is no such hint about whether to choose "Bc to derive ac". So how can it is deterministic ??

---

Oh! I'm also confused there! But from above link

if we want 'ac' as op, then it'll go for Bc. Again why? see above marked comment. But I'm also not sure about it because it'll require a look ahead to see next input and then go for Bc.

  

---

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!