warning: work in progress.
“ambiguous grammar” is a misnomer. It should be called multi-parse-tree grammar.
[ Ambiguous grammar ] [ 2015-12-15 https://en.wikipedia.org/wiki/Ambiguous_grammar ]
when a grammar can have multiple parse tree, it's called “ambiguous grammar”.
S → S + S | S - S | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
and given this string
there are 2 parse trees.
S •S ••1 •- •S ••S •••2 ••+ ••S •••3
S •S ••S •••1 ••- ••S •••2 •+ •S ••3
given a list of operators, their associativity and precedence, we need to construct a grammar, and unambiguous one
given this grammar
E → E + T | T
T → T * F | F
F → ( E ) | NUMBER
NUMBER → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
and given this string
there are more than 1 parse tree. Here's one. todo xxxxxxxxxxxxxxxxx
Note: a grammar for computer language in BNF generates one unique language, a set of sentences that's valid by the grammar. So, in that sense, it is never ambiguous.
ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation.
Many languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars.
Any non-empty language admits an ambiguous grammar by taking an unambiguous grammar and introducing a duplicate rule or synonym (the only language without ambiguous grammars is the empty language).
A language that only admits ambiguous grammars is called an inherently ambiguous language, and there are inherently ambiguous context-free languages. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.
The general decision problem of whether a grammar is ambiguous is undecidable because it can be shown that it is equivalent to the Post correspondence problem.
dangling else problem
[ Dangling else ] [ https://en.wikipedia.org/wiki/Dangling_else ]
dangling else problem, shows practical example of ambiguous grammar.
The dangling else is a problem in computer programming in which an optional else clause in an if–then(–else) statement results in nested conditionals being ambiguous. Formally, the reference context-free grammar of the language is ambiguous, meaning there is more than one correct parse tree.
if a then if b then s else s2
can be parsed as either
if a then (if b then s) else s2
if a then (if b then s else s2)