Grammatiche ambigue

Una grammatica è detta ambigua se genera stringhe uguali tramite almeno due derivazioni differenti (quindi due alberi di derivazione diversi). Per meglio specificare, questa ambiguità è detta ambiguità sintattica. Solitamente una grammatica ambigua risulta più sintetica, ma presenta problemi spiegati successivamente.

Definizioni

Esempio di albero che deriva una proposizione ambigua

Il grado di ambiguità di una proposizione $x$ su un linguaggio $L(G)$ è il numero di alberi di derivazione distinti che producono $x$ sulla grammatica $G$ (eventualmente infiniti).

Il grado di ambiguità di una grammatica $G$ è il massimo tra i gradi di ambiguità delle proposizioni che compongono il linguaggio $L(G)$.

Il problema di decidere se una grammatica è ambigua o no, è un problema indecidibile: non esiste un algoritmo che termini in un numero finito di passi con una risposta è decidibile/non è decidibile. L'assenza di ambiguità può essere però mostrata attraverso ragionamenti induttivi, permettendo così di analizzare un numero finiti di casi. Viceversa la presenza di ambiguità può essere dimostrata mostrando un caso d'esempio (detto witness).

Tipi di ambiguità

Nelle seguenti sezioni presentiamo alcune tipologie di ambiguità spesso ricorrenti e ne mostriamo un'idea di risoluzione per eliminare l'ambiguità delle stesse.

Ambiguità da ricorsione bilaterale

Una grammatica nella forma $A\to A...A$ è ambigua. Esempio:

$A\to AbA|c$

$cbcbc$ può essere generato in due modi:

• $A\Rightarrow AbA\Rightarrow Abc\Rightarrow AbAbc\Rightarrow cbAbc\Rightarrow cbcbc$
• $A\Rightarrow AbA\Rightarrow AbAbA\Rightarrow cbAbA\Rightarrow cbcbA\Rightarrow cbcbc$

La grammatica dell'esempio sopra può essere riscritta in formato non ambiguo nei seguenti modi:

$A\to cbA|c$

$A\to Abc|c$

Ambiguità dall'unione di linguaggi

Siano due linguaggi $L_1=L(G_1),L_2=L(G_2)$ che condividono alcune proposizioni, cioè $L_1\cap L_2\ne \varnothing$, allora la grammatica per il linguaggio $L_1\cup L_2$ è ambigua perché ammette due distinte derivazioni $\mathrm{\forall }x\in L_1\cap L_2$.

Ovviamente l'insieme delle proposizioni non ambigue è $(L_1\setminus L_2)\cup (L_2\setminus L_1)$. Questa situazione è facilmente risolvibile imponendo a priori che $L_1\cap L_2=\varnothing$.

Esempio:

$G_1$

$A\to Aa|a$

$G_2$

$A\to bA|aA|\epsilon$

Ambiguità dalla concatenazione di linguaggi

Similmente all'unione, la concatenazione può causare ambiguità. Questo avviene quando il suffisso di qualche preposizione del primo linguaggio è prefisso di qualche preposizione del secondo.

Formalmente: $\mathrm{\exists }x\in L_1,\mathrm{\exists }y\in L_2$ t.c. $x=uv\wedge y=vz$ con $v\ne \epsilon$, $u\in L_1$ e $z\in L_2$. In questo caso la grammatica $G=G_1{G}_2$ è ambigua per le preposizioni $uvz\in G$.

L'enunciato sopra è facilmente dimostrabile, due sono le possibili derivazioni:

$S\Rightarrow S_1{S}_2\stackrel{+}{\Rightarrow }u{S}_2\stackrel{+}{\Rightarrow }uvz$

$S\Rightarrow S_1{S}_2\stackrel{+}{\Rightarrow }uv{S}_2\stackrel{+}{\Rightarrow }uvz$

Un classico esempio sono la concatenazione di due linguaggi di Dyck che condividono una coppia di simboli. Per risolvere il problema è possibile inserire un nuovo simbolo terminale che agisca da separatore nell'assioma, ad esempio:

$S\to S_1\mathrm{\#}{S}_2$

Ambiguità in frasi condizionali

Questa ambiguità nasce dalla programmazione di compilatori. Si prenda per esempio il classico problema di annidiare clausole if-then di un linguaggio (questo problema è chiamato Dangling else):

$S\to ifEXPthenSelseS|ifEXPthenS|ISTR$

Non rientra in questo problema le clausole EXP e ISTR, che possiamo considerare anche terminali. Sia ora data la seguente stringa generata dalla grammatica di cui sopra:

$ifEXPthenifEXPthenISTRelseISTR$

Questa grammatica a quale sequenza di generazione corrisponde? Vediamo come possono essere applicate la parentesi graffe in stile linguaggio C:

if EXP then {
    if EXP then {
        ISTR
    } else {
        ISTR
    }
}

ma potrebbe anche essere interpretato come:

if EXP then {
    if EXP then {
        ISTR
    }
} else {
    ISTR
}

Queste due sequenze dimostrano l'ambiguità del linguaggio/grammatica.

Soluzioni

Proponiamo qui due possibili soluzioni:

• introdurre un terminale endif:

$S\to ifEXPthenSelseSendif|ifEXPthenSendif|ISTR$

• forzare gli annidiati ad avere else:

$S\to S_E|S_T$

$S_E\to ifEXPthen{S}_{E}else{S}_E|ISTR$

$S_T\to ifEXPthen{S}_{E}else{S}_T|ifEXPthenS$

Ambiguità in regexp

Molte espressioni regolari sono ambigue. Si prenda un esempio banale:

$a^{+}aa*$

la sua grammatica ($S\to AaB,A\to aA,|B\to aB|\epsilon$) è evidentemente ambigua.

La soluzione all'esempio sopra è eliminare la ridondanza di a*:

$a^{+}a$

$S\to Aa$

$A\to aA|a$

Ambiguità per perdita di ordine

Un'altra ambiguità molto comune avviene quando una stringa può essere generata utilizzando come punto di partenza due termini di una stessa regola. Spieghiamo meglio con un esempio:

$S\to aSb|aSbb|\epsilon$

Il problema di questa regola è che tutte le stringhe nella forma $a^n{b}^m$ con $m>2$ sono ambigue. Si prenda per esempio aabbb, essa può essere generata sia a partire da $aSb$ che a partire da $aSbb$.

Per risolvere queste ambiguità si divide la regola imponendo così un ordine alla derivazione:

$S\to aXb|X$

$X\to aXbb|\epsilon$

Si noti come la regola aXb non è stata inserita nella ricorsione perché non necessaria.