S ::= x
S ::= if E then S
S ::= if E then S else S

This is example if E then if E then x else x proves that it is ambiguous but I don't see why? Isn't it just an if statement within an if statement.

  • $\begingroup$ The else could be part of either if, according to the grammar. Search for "dangling else". $\endgroup$
    – rici
    Oct 30 '19 at 0:56

Rici is correct. The statement could be reasonably interpreted, as you first assumed:

if E then ( if E then x ) else x

It may also be interpreted:

if E then ( if E then x else x )

In a context-free grammar, the allowable set of expressions are determined through substitution. In the first interpretation I took your third statement and substituted the first S for the second statement, and then replaced all remain S with x. In the second interpretation, I took your second statement and replaced it with the third statement, and replaced the remaining S with x using the first statement.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.