Informatica ambigue

In informatica, una grammatica è detta ambigua se esistono stringhe da essa generate che possono essere prodotte con derivazioni sinistre diverse (in inglese leftmost derivation), o, equivalentemente, che hanno più di un possibile albero sintattico. Un linguaggio è detto inerentemente ambiguo quando può essere generato solo da grammatiche ambigue.

Per quanto riguarda i linguaggi di programmazione, le grammatiche ambigue possono rendere difficile l'analisi sintattica (parsificazione) del codice sorgente. In genere, i generatori di parsificatori (parser generator o compiler compiler in inglese) che permettono la definizione di linguaggi attraverso grammatiche ambigue (ad esempio GNU Bison) dispongono di metodi di risoluzione dell'ambiguità.

Esempio di grammatica ambigua

La seguente grammatica libera dal contesto

A → A + A | A − A | a

è ambigua dal momento che esistono due diverse derivazioni sinistre per la stringa a + a − a:

In maniera equivalente, è ambigua poiché esistono due alberi di parsificazione diversi per la stessa stringa:

File:Esempio Alberi di Parsificazione per Grammatica Ambigua.png

Il linguaggio generato non è però inerentemente ambiguo: la seguente grammatica non ambigua genera lo stesso linguaggio:

A → A + a | A − a | a