Ambiguous Grammar

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”.

example

S → S + S | S - S | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

and given this string 1-2+3

there are 2 parse trees.

S
•S
••1
•-
•S
••S
•••2
••+
••S
•••3

and

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

try it

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 3+4*5

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.[1]

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

or as

if a then (if b then s else s2)