The Gateway to Computer Science Excellence
0 votes

S->Aa | Bc  

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

in Compiler Design by
retagged by | 161 views

3 Answers

+2 votes

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

[Ref : PAGE 9]

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

3. Yes , every left factored grammer is deterministic.

0 votes
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
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 ??

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!
0 votes

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.


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,503 answers
95,331 users