Indietro

ⓘ Grammatica ambigua




                                     

ⓘ Grammatica ambigua

In informatica, una grammatica è detta ambigua se esistono stringhe da essa generate che possono essere prodotte con derivazioni sinistre diverse, 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 lanalisi sintattica parsificazione del codice sorgente. In genere, i generatori di parsificatori parser generator o compiler in inglese che permettono la definizione di linguaggi attraverso grammatiche ambigue ad esempio GNU Bison dispongono di metodi di risoluzione dellambiguità.

                                     

1. 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:

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

A → A + a | A − a | a