Grammatica formale

Da Wikipedia, l'enciclopedia libera.

In teoria dei linguaggi formali una grammatica formale è 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 connettore booleano 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[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Grammatica generativa.

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[modifica | modifica sorgente]

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 disgiunto 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi gerarchia di Chomsky.
Gerarchia-di-Chomsky.jpg

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)[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Grammatica libera dal contesto.

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^nb^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)[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Grammatica regolare.

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 singoli 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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 gramamtica analitica sono i seguenti:

Bibliografia[modifica | modifica sorgente]

  • Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Linguaggi modelli complessità, Milano, Franco Angeli Editore, 2003. ISBN 88-464-4470-1.

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

Conferenza sulle grammatiche

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky Grammatica formale Linguaggio Automa minimo
Tipo-0 (illimitato) Ricorsivamente enumerabile Macchina di Turing
(illimitato) Ricorsivo Decider
Tipo-1 Dipendente dal contesto Dipendente dal contesto Automa lineare
Tipo-2 Libera dal contesto Libero dal contesto Automa a pila ND
Tipo-3 Regolare Regolare A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sottostante.