MadeEasy Subject Test: Compiler Design - Parsing

Question

A non left recursive and left facotred grammar in which all non-empty rules defining the same non terminal have disjoint first sets, such grammar is called _____________

a) LL(1)

b) LR(0)

c) LR(1)

d) None

asnwer given LL(1). but i think bcoz of follow there can be conflict hence none of these should be the answer. Is it right??

Answer 1

Let us understand this question and try to know why conflict occurs in LL(1) parser despite being non left recursive and non left factored..This happens in 2 scenarios :

A) When we have choice in productions and they are originating from same variables , if first of 2 productions have something in common , then both these productions will have to be placed into same column(terminal which is common in first of 2 productions and same row(variable which is responsible for the productions)..So in that case conflict will occur..

Said in other way , if they are disjoint , then we have only one possibility and that is due to null productions in which case we have to place in follow of lhs of production..In that case there may be collision also.

But in the question it is given : " all non-empty rules " indicating that they will not produce epsilon..

Hence the parser(grammar) is guaranteed to be LL(1)..

Hence A) is the correct answer..

Comments

But grammar can have null productions so it does not hold always so none should answer. Right???

---

Emphasise on the phrase "non empty rules"

---

Thanks. I got it.

---

"which all non-empty rules defining the same non terminal have disjoint first sets, such grammar is called"

This doesn't means that gramar will not have null production..They gave description about non- empty rules.nothing is said about empty rules.

---

@Habibkhan I think none is the answer. the statement given in question can't be interpreted as there are no empty productions.