Grammatica formale

La grammatica formale, nella teoria dei linguaggi formali, è una struttura astratta che descrive un linguaggio formale in modo preciso, è cioè un sistema di regole che delineano matematicamente un insieme (di solito infinito) di sequenze finite di simboli (stringhe) appartenenti ad un alfabeto anch'esso finito.

Le grammatiche formali si suddividono in due categorie principali: generativa e analitica.

• Una grammatica generativa, il genere più conosciuto, è un sistema di regole grazie alle quali tutte le possibili stringhe nella lingua da descrivere sono generate tramite la riscrittura successiva di stringhe che cominciano con un simbolo iniziale predefinito. Una grammatica generativa, infatti, formalizza un algoritmo che genera stringhe linguistiche.

• Una grammatica analitica, invece, è un sistema di regole che presuppone una stringa arbitraria come input e che successivamente riduce o analizza quella stringa di input finali concedendo ad un connettivo logico un risultato del tipo "sì/no" indicando se la stringa di input è o non è parte della lingua descritta dalla grammatica. Una grammatica analitica infatti descrive un parser linguistico.

In breve, una grammatica analitica descrive come leggere una lingua, mentre una grammatica generativa descrive come scriverla.

Grammatiche generative

Una grammatica generativa consiste di un sistema di regole per trasformare delle stringhe. Per generare una stringa linguistica, si comincia con una stringa consistente di un solo simbolo iniziale e si applicano successivamente le regole (per qualsiasi numero di volte, in ogni ordine) per riscrivere questa stringa. La lingua consiste di tutte le stringhe che possono essere generate in questo modo. Qualsiasi particolare sequenza di scelte legali prese durante questo processo di riscrittura garantisce una particolare stringa linguistica, e se ci sono più modi differenti di generare un'unica stringa, allora la grammatica viene definita grammatica ambigua.

Ad esempio se abbiamo un alfabeto $\Sigma =\{a,b\},N=\{S\},S$ simbolo iniziale e le regole di produzione seguenti:

1. $S\to aSb$
2. $S\to ba$

possiamo quindi iniziare con "$S$" e scegliere una regola da applicare. Se scegliamo la regola 1, sostituiremo $S$ con $aSb$ per ottenere "$aSb$". Se scegliamo di nuovo la regola 1, sostituiremo '$S$' con '$aSb$' per ottenere "$aaSbb$". Questo processo viene ripetuto finché non abbiamo soltanto simboli terminali. Per concludere il nostro esempio, se ora scegliamo la regola 2, sostituiremo '$S$' con '$ba$' per ottenere "$aababb$", e tutto è fatto. Possiamo scrivere questa serie di scelte più brevemente, usando i simboli: $S\to aSb\to aaSbb\to aababb$. La lingua della grammatica è il sistema di tutte le stringhe che possono essere generate usando questo processo: $\left\{ba,abab,aababb,aaababbb,...\right\}$.

Definizione formale

Nella formalizzazione classica delle grammatiche generative proposta per prima da Noam Chomsky negli anni '50, una grammatica ${\mathcal {G}}$ consiste in una quadrupla ${\mathcal {G}}=\left\langle N,\Sigma ,P,S\right\rangle$, in cui

1. $N$ sono i simboli non terminali che possono essere riscritti
2. $\Sigma$ sono i simboli terminali disgiunti da $N$
3. $S\in N$ detto assioma è il simbolo non terminale iniziale.
4. $P$ sono le regole di produzione, una relazione binaria di cardinalità finita su $(N\cup \Sigma )^{*}\circ N\circ (N\cup \Sigma )^{*}\times (N\cup \Sigma )^{*}$, che normalmente scriviamo come $\alpha \to \beta$

   dove ${}^{*}$ è la stella di Kleene e $\cup$ è l'unione dei simboli con la restrizione che la parte sinistra di una regola (p.e. la parte sinistra di $\to$) deve contenere almeno un simbolo non terminale.

Il linguaggio generato da una grammatica formale ${\mathcal {G}}=\left\langle N,\Sigma ,P,S\right\rangle$, denotato come $L({\mathcal {G}})$, viene definito come tutte quelle stringhe su $\Sigma$ che possono essere generate iniziando con l'assioma $S$ e poi applicando iterativamente le regole produttive di $P$ fino a quando non vi siano più simboli non terminali.

Due grammatiche si dicono tra loro equivalenti se e solo se generano lo stesso linguaggio.

Esempio

Si consideri, per esempio, la grammatica $G$ con $N=\left\{S,B\right\}$, $\Sigma =\left\{a,b,c\right\}$, $P$ consistente delle regole produttive seguenti

1. $S\to aBSc$

2. $S\to abc$

3. $Ba\to aB$

4. $Bb\to bb$

e il simbolo non terminale $S$ come simbolo di partenza. Alcuni esempi di derivazione delle stringhe in $L({\mathcal {G}})$ sono:

• ${\boldsymbol {S}}\to (2)abc$
• ${\boldsymbol {S}}\to (1)aB{\boldsymbol {S}}c\to (2)a{\boldsymbol {Ba}}bcc\to (3)aa{\boldsymbol {Bb}}cc\to (4)aabbcc$
• ${\boldsymbol {S}}\to (1)aB{\boldsymbol {S}}c\to (1)aBaB{\boldsymbol {S}}cc\to (2)a{\boldsymbol {Ba}}Babccc\to (3)aaB{\boldsymbol {Ba}}bccc\to (3)aa{\boldsymbol {Ba}}Bbccc$$\to (3)aaaB{\boldsymbol {Bb}}ccc\to (4)aaa{\boldsymbol {Bb}}bccc\to (4)aaabbbccc$

(dove le regole di produzione utilizzate sono indicate fra parentesi e la parte sostituita è indicata ogni volta in grassetto).

La grammatica definisce il linguaggio $\{a^{n}b^{n}c^{n}|n>0\,\}$.

Le grammatiche generative formali sono identiche al sistema di Lindenmayer (sistemi L), sennonché i sistemi L non sono caratterizzati da una distinzione tra terminali e non terminali, i sistemi L hanno restrizioni nell'ordine in cui le regole sono applicate e i sistemi L possono funzionare per sempre, generando una sequenza infinita di stringhe. Tipicamente ogni stringa è associata con un sistema di punti nello spazio e l'output del sistema L viene definito come il limite di quei sistemi.

La gerarchia di Chomsky

Quando Noam Chomsky formalizzò per primo le grammatiche generative negli anni 50, le classificò in quattro tipi conosciuti ora come gerarchia di Chomsky. La differenza tra questi tipi è che hanno regole di produzione strette e possono esprimere meno linguaggi formali. Due tipi importanti sono: le grammatiche context-free (in italiano grammatiche libere da contesto) e le grammatiche regolari. I linguaggi che possono essere descritti con una tale grammatica sono definiti rispettivamente linguaggi liberi dal contesto e linguaggi regolari. Anche se molto meno potenti delle grammatiche non restrittive, che possono infatti esprimere qualsiasi lingua che possa essere accettata da una macchina di Turing, questi due tipi ristretti di grammatiche sono le più usate perché i parser utilizzati possono essere impiegati efficientemente. Per esempio, per grammatiche non contestuali ci sono algoritmi ben conosciuti per generare parser LL e parser LR.

Grammatiche libere dal contesto (Tipo 2)

Nelle grammatiche libere dal contesto, o non contestuali (in inglese context-free), la parte sinistra di una regola produttiva può soltanto essere formata da un solo simbolo non terminale. Il linguaggio sopra definito nell'esempio non è un linguaggio context-free, ma il linguaggio ${a^{n}b^{n}|n>0}$ sì, dato che può essere definito dalla grammatica ${\mathcal {G}}_{2}=\left\langle N=\{S\},\Sigma =\{a,b\},P,S\right\rangle$ con le seguenti regole produttive:

1. $S\to aSb$

2. $S\to ab$

In particolare la grammatica di questo esempio è lineare, sottoinsieme proprio delle grammatiche libere dal contesto, poiché nella parte destra c'è un solo simbolo non terminale, quando ne possono avere più di uno.

Grammatiche regolari (Tipo 3)

In grammatica regolare la parte sinistra è, come per le grammatiche non contestuali, soltanto un simbolo non terminale; inoltre, ora la parte terminale è vincolata nel seguente modo: può essere nulla ($\epsilon$), oppure essere nella forma $a$ oppure nella forma $aB$, con $a$ e $B$ appartenenti rispettivamente ad $N$ e a $\Sigma$ (può cioè essere nulla, oppure un simbolo terminale seguito, eventualmente, da un solo simbolo non terminale). A volte si utilizza una definizione più ampia: si può cedere il passo a stringhe più lunghe di terminali o a simboli non terminali, ma a nient'altro, pur definendo la stessa classificazione linguistica.

Il linguaggio sopra descritto non è regolare, invece il linguaggio $\left\{a^{n}b^{m}|m,n>0\right\}$ (almeno una 'a' seguita da almeno una 'b', con 'a' e 'b' in numero generalmente differente) lo è, e lo si può definire tramite la grammatica ${\mathcal {G}}_{3}=\left\langle N=\{S,A,B\},\Sigma =\{a,b\},P,S\right\rangle$ con le seguenti regole produttive:

1. $S\to aA$

2. $A\to aA$

3. $A\to bB$

4. $B\to bB$

5. $B\to \epsilon$

Altre forme di grammatiche generative

Si sono recentemente sviluppate diverse estensioni e variazioni della gerarchia originaria chomskiana delle grammatiche formali, sia da parte dei linguisti che dagli studiosi di informatica, di solito o per aumentare la forza espressiva o per semplificarli al fine di analizzarli o parsificarli. Naturalmente questi due obiettivi tendono all'imparità: quanto più espressivo è un formalismo grammaticale, tanto più difficile è analizzare o parsificare utilizzando strumenti automatici. Alcune forme di grammatiche sviluppate recentemente includono:

• La grammatica ad albero aumenta l'espressività delle grammatiche generative convenzionali lasciando spazio a regole di riscrittura per operare su alberi di parser invece che solo su stringhe.
• La grammatica affissuale e la grammatica attributiva permettono di riscrivere regole da arricchire con attributi semantici e operazioni, utili sia per incrementare l'espressività grammaticale che per costruire pratici strumenti di traduzione linguistici.

Una conferenza annuale è dedicata alle grammatiche formali.

Grammatiche analitiche

Sebbene vi sia una mole ingente di letteratura sulla parsificazione degli algoritmi, la maggior parte di questi presume che la lingua sia inizialmente descritta da mezzi di grammatica formale generativa e che lo scopo sia trasformare questa grammatica generativa in un parser funzionale. Un approccio alternativo è la formalizzazione del linguaggio in termini di grammatica analitica al primo posto, che corrisponde più o meno direttamente alla struttura di un parser linguistico. Esempi di formalismi di grammatica analitica sono i seguenti:

• Linguaggio di parsificazione top-down (TDPL): una grammatica analitica altamente minimalista sviluppatasi all'inizio degli anni 70 per studiare il comportamento dei parser top-down.
• Grammatica espressiva di parsificazione (PEGs): una generalizzazione più recente del TDPL progettata attorno alle necessità di espressività pratica di un linguaggio di programmazione e di un compilatore.
• Grammatica di collegamento: una forma di grammatica analitica progettata per la linguistica che deriva la sua struttura sintattica dall'esaminazione delle relazioni posizionali fra coppie di parole.

Bibliografia

• Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Linguaggi modelli complessità, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1.
• Andrea de Prisco, Grammatiche e Automi (JPG), in MCmicrocomputer, n. 62, Roma, Technimedia, aprile 1987, pp. 154-156, ISSN 1123-2714. Trascrizione del testo, su digiTANTO.it.

Voci correlate

• Albero sintattico concreto
• Grammatica ambigua
• Linguaggio formale
• Grammatica ad attributi

Collegamenti esterni

Conferenza sulle grammatiche

Controllo di autorità	GND (DE) 4154991-0