Grammatica formale

Da Wikipedia, l'enciclopedia libera.

In informatica una grammatica formale è una struttura astratta che descrive un linguaggio formale in modo preciso, è cioè un sistema di regole che delineano matematicamente un sistema (di solito infinito) di lunghezze finite (stringhe) usando un alfabeto (di solito finito). Le grammatiche formali sono chiamate così per analogia con la grammatica delle lingue umane.

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.

[modifica] Grammatiche generative

Per approfondire, vedi la voce 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 "start" 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.

Per esempio, supponiamo che l'alfabeto consista di ' $a$ ' e ' $b$ ', che il simbolo start sia ' $S$ ' e che si abbiano le regole seguenti:

1. $S \longrightarrow aSb$

2. $S \longrightarrow ba$

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

[modifica] Definizione formale

Nella formalizzazione classica delle grammatiche generative proposta per prima da Noam Chomsky negli anni 50, una grammatica G consiste delle seguenti componenti:

Un sistema finito $N$ di simboli non terminali.
Un sistema finito $Σ$ di simboli terminali disgiunto da $N$ .
Un sistema finito $P$ di regole produttive dove una regola è della forma

string in $(\Sigma \cup N)^{*} \longrightarrow$ string in $(\Sigma \cup N)^{*}$

(dove

*

è la stella di Kleene e $\cup$ è l´unione) con la restrizione che la parte sinistra di una regola (p.e. la parte sinistra di $\longrightarrow$ ) deve contenere almeno un simbolo non terminale.

Un simbolo $S$ in $N$ indicato come simbolo start.

Di solito una tale grammaticale formale $G$ è semplicemente riassunta come $(N,Σ, P, S)$ .

Il linguaggio generato da una grammatica formale $G = (N,Σ, P, S)$ , denotato come $\boldsymbol{L}(G)$ , viene definito come tutte quelle stringhe su $Σ$ che possono essere generate iniziando con il simbolo start $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.

[modifica] 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 \longrightarrow aBSc$

2. $S \longrightarrow abc$

3. $Ba \longrightarrow aB$

4. $Bb \longrightarrow bb$

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

$\boldsymbol{S} \longrightarrow (2) abc$
$\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (2) a\boldsymbol{Ba}bcc \longrightarrow (3) aa\boldsymbol{Bb}cc \longrightarrow (4) aabbcc$
$\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (1) aBaB\boldsymbol{S}cc \longrightarrow (2) a\boldsymbol{Ba}Babccc \longrightarrow (3) aaB\boldsymbol{Ba}bccc\longrightarrow (3) aa\boldsymbol{Ba}Bbccc$ $\longrightarrow (3) aaaB\boldsymbol{Bb}ccc \longrightarrow (4) aaa\boldsymbol{Bb}bccc \longrightarrow (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 $\left \{ a^{n}b^{n}c^{n} | n > 0 \right \}$ dove $a n$ denota una stringa di n $a$ .

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.

[modifica] 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 extracontestuali 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 extra contestuali ci sono algoritmi ben conosciuti per generare parser LL e parser LR.

[modifica] Grammatiche libere dal contesto

Per approfondire, vedi la voce Grammatica libera dal contesto.

Nelle grammatiche libere dal contesto, o context-free, la parte sinistra di una regola produttiva può soltanto essere formata da un solo simbolo non terminale. Il linguaggio sopra definito non è un linguaggio context-free, ma per esempio il linguaggio $a n b n | n > 0$ sì, dato che può essere definito dalla grammatica $G 2$ con $N=\left \{S\right \}$ , $\Sigma=\left \{a,b\right \}$ , $S$ come simbolo iniziale e le seguenti regole produttive:

1. $S \longrightarrow aSb$

2. $S \longrightarrow ab$

[modifica] Grammatiche regolari

Per approfondire, vedi la voce 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 ( $ε$ ), oppure essere nella forma $a$ oppure nella forma $a B$ , con $a$ e $B$ appartenenti rispettivamente ad $N$ e a $Σ$ (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 $G 3$ , con $N=\left \{S, A,B\right \}$ , $\Sigma=\left \{a,b\right \}$ , $S$ come simbolo iniziale e le seguenti regole produttive:

1. $S \longrightarrow aA$

2. $A \longrightarrow aA$

3. $A \longrightarrow bB$

4. $B \longrightarrow bB$

5. $B \longrightarrow \epsilon$

[modifica] 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 costrutire pratici strumenti di traduzione linguistici.

Una conferenza annuale è dedicata alle grammatiche formali: [1]

[modifica] 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 gramamtica 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 parsificaziones (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.

[modifica] Voci correlate

Albero sintattico concreto
Albero sintatico astratto
Grammatica ambigua
Grammatica generativa
Linguaggio formale

Teoria degli automi: linguaggi formali e grammatiche formali
gerarchia di Chomsky	Grammatiche	Linguaggi	automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Sensibile al contesto	Sensibile al contesto	Lineare-limitato
Tipo-2	Libero dal contesto	Libero dal contesto	Automa a pila
Tipo-3	Lineare (o Regolare)	Lineare (o Regolare)	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.

Progetto Linguistica - Voci di linguistica - Il bar linguistico generale

Linguistica - Storia della linguistica - Linguisti Settori di linguistica generale: Fonetica e Fonologia - Grammatica - Morfologia - Sintassi - Semantica - Pragmatica Altre discipline linguistiche: Dialettologia - Etno-linguistica - Glottologia - Grammatica storica - Lessicologia - Linguistica applicata - Linguistica cognitiva - Linguistica comparativa - Linguistica computazionale - Linguistica testuale - Psicolinguistica - Retorica - Sociolinguistica
Wikizionario - Wikiquote - Wikibooks - Wikisource