# 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)