Ambiguous Grammar

The Wikipedia article describes what it means for a formal BNF grammar to be ambiguous. It has some interesting points but here are a few orthogonal points.

There are these stances towards ambiguity in a formal grammar:

Ban it.
Tolerate it with informal descriptions of which choice the parser makes.
Tolerate the grammar but reject syntactically ambiguous programs.
Tolerate the grammar and reject programs that are semantically ambiguous.

A syntax may produce the same program in two ways but the associated semantics may assign them the same meaning.

Stance 2 may fail in this scenario:

A programmer correctly understands part of the formal grammar and its semantics.
He writes a program with that understanding.
The compiler accepts the program but interprets the program according to a different parsing with different semantics.
The program produces unexpected results.

Stance 2 is taken by many languages and is the only stance with this problem.

Most languages defined with stance 2 could adopt 3 and also provide compilers that would automatically provide alternate unambiguous versions of an ambiguous input, one for each parsing. These alternates would have the respective semantics of the various parsings. The partially informed user would presumably easily choose the one he meant. IBM’s PL/I Checkout Compiler (circa 1962) would sometimes propose improvements to a program for the programmer’s approval.

A C example; in response to

if (a >= b) if(a==b) x(); else y();

the compiler would propose alternatives:

if (a >= b) {if(a==b) x();} else y();

if (a >= b) {if(a==b) x(); else y();}

It might volunteer that older compilers would have silently chosen the second.

Cloud: Ambiguous grammars with the common informal disambiguations can be transformed into unambiguous grammars with the same ultimate meaning.

stmt  ≡ exp = exp | {block} | if (exp) stmt [else stmt] | while (exp) stmt | …
block ≡ | block stmt

is ambiguous but

stmt ≡ exp = exp | {block} | if (exp) stmt else ttmt | while (exp) ttmt | …
ttmt  ≡ stmt | if (exp) stmt
block ≡ | block ttmt

is not. The new syntactic categories cb (compact block) and block together subsume the old block. Both grammars produce just the classic C statements but the latter grammar has the property that the semantics follows the syntax and it does not produce the first alternative parsing of the previous example.