warning: work in progress.
“ambiguous grammar” is a misnomer. It should be called multi-parse-tree 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 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)