Example: If-Then-Else Statement

The Hanging-Else Problem

The following is a very simple grammar with a complex problem:

When this grammar is analyzed by the GOLD Parser Builder (or any other generator for that matter), a problem arises in the LALR(1) parse tables. Invariably, a shift-reduce error occurs when the parser reaches the "else" option on the If-Then statement.

This type of error is caused by ambiguity in the grammar itself; in the case of the above grammar, the parser does not know where it can reduce a rule or must push a token onto the parse stack. Technical issues aside, it is important to understand why this grammar is ambiguous.

The ambiguity of the grammar can be seen with a very simple piece of  source code:

The sample source code could be interpreted two distinct ways by the grammar. The first interpretation would bind the "else" to the first "if".

The second interpretation would bind the "else" to the second 'if" statement:

Fortunately, there are two approaches you can take to resolve the problem.

Hanging-Else Solution #1: Modify the Grammar

This approach modifies the grammar such that the scope of the "if" statement is explicitly stated. Another terminal is added to the end of each "if" statement, in this case an "end". A number of programming languages use this approach; the most notable are: Visual Basic and Ada.

As seen below, the ambiguity of the original grammar has been resolved.

Hanging-Else Solution #2: Restrict the "Else"

This solution resolves the hanging-else problem by restricting the "if-then" statement to remove ambiguity. Two levels of statements are declared with the second, "restricted", group only used in the "then" clause of a "if-then-else" statement. The "restricted" group is completely identical the the first with one exception: only the "if-then-else" variant of the if statement is allowed.

In other words, no "if" statements without "else" clauses can appear inside the "then" part of an "if-then-else" statement. Using this solution, the "else" will bind to the last "If" statement, and still allows chaining. This is the case with the C/C++ programming language family.

Unfortunately, this adds a number of rules, but it is ultimately the price you pay for such a grammar.