Initially the ambiguous grammar is as follows (with some cropped production rules):

<STMT>         -->  <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN>      -->  if condition then <STMT>
<IF-THEN-ELSE> -->  if condition then <STMT> else <STMT>

To resolve the ambiguity, the previous grammar is transformed into the following one in the book I study:

<STMT>           -->  <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN>        -->  if condition then <STMT>
<IF-THEN-ELSE>   -->  if condition then <E-STMT> else <STMT>
<E-STMT>         -->  <E-IF-THEN-ELSE>
<E-IF-THEN-ELSE> -->  if condition then <E-STMT> else <E-STMT>

What I cannot get is that why the following rule is necessary.

<E-IF-THEN-ELSE> -->  if condition then <E-STMT> else <E-STMT>

As far as I think about, the update on <IF-THEN-ELSE> and introduction of <E-STMT> is sufficient to resolve the ambiguity. Could you please give an example refuting my argument? Thanks..

  • $\begingroup$ It would seem that your language is ambiguous. For if A then if B then P else Q it is not clear where the else should belong. Note that most languages solve this by having end, fi or { ... } as delimiters. (I don't see how the second grammar solves anything. Did you crop too much?) $\endgroup$ – Raphael Oct 30 '14 at 9:53
  • $\begingroup$ Not really... To produce your example you have to follow <STMT> --> <IF-THEN> --> <STMT> --> <IF-THEN-ELSE> --> <E-STMT>. You cannot execute <STMT> --> <IF-THEN-ELSE> --> ... Because, <IF-THEN-ELSE> mandates derivation with <E-STMT> which mandates a closing else for an if clause. $\endgroup$ – suat Oct 30 '14 at 11:15
  • $\begingroup$ So the second grammar does not allow else-free inner conditionals? That seems odd, and is also not what the first grammar does. $\endgroup$ – Raphael Oct 30 '14 at 13:04
  • $\begingroup$ @Raphael Using <IF-ELSE> sequentially it is possible. However, the aim is to associate else clauses with the closest if clauses. So, you are right; the meaning changes. But it is accepted in this case considering the aim. I just cannot understand the necessity of <E-IF-THEN-ELSE>. I could not produce an example requiring the introduction of this rule. $\endgroup$ – suat Oct 30 '14 at 13:11
  • $\begingroup$ @Raphael This is pretty much like the problem of operator precedence in arithmetic expressions. The simplest is an ambiguous grammar, but specific non-terminals such as TERM or FACTOR are used to impose a specific shape of the parse tree. $\endgroup$ – babou Dec 29 '14 at 17:30

I assume that one can also derive some atomic statements from <STMT> and <E-STMT>, otherwise the language of both grammars would be empty and all would be quite trivial. :-) But that aside:

The new grammar should do two things: it should be unambiguous and it should generate the same language.

The variables <E-STMT> and <E-IF-THEN-ELSE> are introduced to remember part of the context in which the variable occurs. What you want to accomplish, is that the variables <STMT>, <IF-THEN> and <IF-THEN-ELSE> cannot occur in a position directly preceeding an else symbol, and also that the variables <E-STMT> and <E-IF-THEN-ELSE> must occur in a position directly preceeding an else symbol. So, if we see a <E-STMT> or <E-IF-THEN-ELSE> somewhere, we know that the next symbol must be else, and if we see an other variable we know that the next symbol cannot be an else. This way we have some week form of "context-awareness".

If we remove the rule for <E-IF-THEN-ELSE> and replace the rule for <E-STMT> by


then we can derive the following:

<STMT> $\to$
<IF-THEN-ELSE> $\to$
if condition then <E-STMT> else <STMT> $\to$
if condition then <E-IF-THEN-ELSE> else <STMT> $\to$
if condition then if condition then <E-STMT> else <STMT> else <STMT>

and here a <STMT> variable which directly preceeds an else symbol. This will lead to ambiguities.

If we try to fix this and additionally change the if-then-else rule to

<IF-THEN-ELSE> --> if condition then <E-STMT> else <E-STMT>

then we can perform the derivation

<STMT> $\to$ <IF-THEN-ELSE> $\to$ if condition then <E-STMT> else <E-STMT>

and here we have an <E-STMT> variable without a following else symbol. Since the <E-STMT> generates no if statements without else clause, the language of the new grammar is not the same.

The grammar which was proposed in the book solves both these problems.

| cite | improve this answer | |
  • 1
    $\begingroup$ "it should be unambiguous and it should generate the same language" -- in the context of compilers, it should also generate the same (up to minor changes) syntax trees. $\endgroup$ – Raphael Oct 30 '14 at 15:28

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.