Other sources of ambiguity
Introduction: Most of the potential ambiguity in grammars for programming languages comes from expression syntax and can be handled by exploiting precedence rules as shown in section 3.4. Another classical example of ambiguity is the “dangling-else” problem. Imperative languages like Pascal or C often let the else-part of a conditional be optional. The problem is that it is not clear how to
parse, for example,
if p then if q then s1 else s2
According to the grammar, the else can equally well match either if. The usual convention is that an else matches the closest not previously matched if, which, in the example, will make the else match the second if.
How do we make this clear in the grammar? We can treat if, then and else as a kind of right-associative operators, as this would make them group to the right, making an if-then match the closest else. However, the grammar transformations shown in section 3.4 cannot directly be applied to grammar 3.3, as the productions for conditionals do not have the right form.
Instead we use the following observation: When an if and an else match, all ifs that occur between these must have matching elses. This can easily be proven by assuming otherwise and concluding that this leads to a contradiction.
Hence, we make two non-terminals: One for matched (i.e. with else-part) conditionals and one for unmatched (i.e. without else-part) conditionals. The result is shown in grammar 3.13. This grammar also resolves the associativity of semicolon (right) and the precedence of if over semicolon.
An alternative to rewriting grammars to resolve ambiguity is to use an ambiguous grammar and resolve conflicts by using precedence rules during parsing. We shall look into this in section 3.16.
All cases of ambiguity must be treated carefully: It is not enough that we eliminate ambiguity, we must do so in a way that results in the desired structure: The structure of arithmetic expressions is significant, and it makes a difference to which if an else is matched.
Stat -> Stat2;Stat
Stat -> Stat2
Stat2 -> Matched
Stat2 -> Unmatched
Matched -> if Exp then Matched else Matched
Matched -> id :=Exp
Unmatched -> if Exp then Matched else Unmatched
Unmatched -> if Exp then Stat2
Grammar 3.13: Unambiguous grammar for statements