Grammatiche ambigue

lezione Grammatiche ambigue
	Tipo: lezione
	Materia: Linguaggi formali e automi
	Avanzamento: lezione completa al 100%

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

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}\neq \varnothing$ , allora la grammatica per il linguaggio $L_{1}\cup L_{2}$ è ambigua perché ammette due distinte derivazioni $\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|\varepsilon

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: $\exists x\in L_{1},\exists y\in L_{2}$ t.c. $x=uv\land y=vz$ con $v\neq \varepsilon$ , $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}\ {\overset {+}{\Rightarrow }}\ uS_{2}\ {\overset {+}{\Rightarrow }}\ uvz

S\Rightarrow S_{1}S_{2}\ {\overset {+}{\Rightarrow }}\ uvS_{2}\ {\overset {+}{\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}\#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 \ if\ EXP\ then\ S\ else\ S\ |\ if\ EXP\ then\ S\ |\ 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:

if\ EXP\ then\ if\ EXP\ then\ ISTR\ else\ ISTR

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 \ if\ EXP\ then\ S\ else\ S\ endif\ |\ if\ EXP\ then\ S\ endif\ |\ ISTR

forzare gli annidiati ad avere else:

S\ \to \ S_{E}\ |\ S_{T}

S_{E}\ \to \ if\ EXP\ then\ S_{E}\ else\ S_{E}\ |\ ISTR

S_{T}\ \to \ if\ EXP\ then\ S_{E}\ else\ S_{T}\ |\ if\ EXP\ then\ S

Ambiguità in regexp

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

a^{+}aa*

la sua grammatica ( $S\to AaB,\quad A\to aA,|\quad B\to aB|\varepsilon$ ) è 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|\varepsilon

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