The given grammar is an ambiguous one and specifically due to 2 S in one production and left factoring.Let us see how :
==> If we write i == "if " , e = "expr" t = "then" , S = "stmt" and b = "other" then , we have :
S --> ietSeS | ietS | b
As clear from the given grammar it suffers from left factoring problem as ietS comes in 2 productions as we can see clearly..So to eliminate this problem which is characteristic of non determinism we have :
Let ietS = A , then we can rewrite the grammar as :
S --> ietSS' | b
S' --> eS | ϵ ,
Thus the left factoring is removed..
Now the analysis becomes simpler ..
Say we have input string : ietietbeb then we have 2 derivation trees for it, one substituting epsilon for earlier S' and which is in the bottom level of derivation tree..So the grammar is an ambiguous one..
This problem is more commonly known as "dangling else problem"..There are various approaches to resolve the ambiguity associated with the problem ..
Sometimes the CFG is modified so that it is unambiguous, such as by requiring an endif
statement or making else
mandatory. In other cases the CFG is left ambiguous, but the ambiguity is resolved by making the overall phrase grammar context-sensitive, such as by associating an else
with the nearest if
. In this latter case the grammar is unambiguous, but the CF grammar is ambiguous.
Overall the language is not inherently ambiguous as ambiguity is of removable nature here..Hence option 1) is correct here..
Also let me mention :
The factors left recursion and left factoring are possible causes of ambiguity..They will not create ambiguity always..