grammatica

grammatica

grammatica in informatica teorica, termine che designa una struttura formale per un linguaggio L in grado di generare tutte e sole le stringhe del linguaggio. Per questo si parla di grammatica G generativa del linguaggio L o di linguaggio L generato dalla grammatica G, indicandolo con L(G).

Formalmente, una grammatica G è una quadrupla 〈A_N, A, P, s〉 dove A è l’alfabeto del linguaggio (detto anche alfabeto dei simboli terminali, perché solo essi compaiono al termine della generazione di una stringa del linguaggio), A_N è un insieme di simboli utilizzati nella generazione delle stringhe che non compaiono tuttavia nelle stringhe stesse (per questo è detto alfabeto dei simboli non terminali), s è un particolare elemento di A_N, scelto come simbolo (non terminale) di partenza, detto assioma, P è un insieme di regole di riscrittura (dette produzioni) del tipo α → β così intendendo che la stringa a sinistra della freccia può essere rimpiazzata da quella a destra ed essendo α una stringa non vuota di simboli terminali e non terminali e β una stringa di simboli terminali e non terminali che può anche essere vuota. Poiché l’insieme delle stringhe costruibili con i simboli di un alfabeto A è generalmente indicato con A* se vi si include la stringa vuota e con A⁺ se la si esclude, nella generica regola α → β, si ha α ∈ V ⁺ e β ∈ V *, dove con V si è indicato A_N ∪ A.

Si dice derivazione diretta generata dalla grammatica G una relazione definita in V * e indicata con

così definita: se φ e σ appartengono rispettivamente a V ⁺ e V *, allora

se esistono α ∈ V ⁺ e β, γ, δ ∈ V * tali che φ = γαδ, σ = γβδ e α → β ∈ P (è cioè una produzione). Si definisce poi derivazione, denotata con

la relazione che si ottiene per chiusura transitiva della derivazione diretta

se e solo se esistono α₁, α₂, …, α_n ∈ V * tali che φ = α₁, σ = α_n e per ogni 1 ≤ i ≤ n si ha che

Il linguaggio generato dalla grammatica G è l’insieme

cioè l’insieme di tutte e sole le stringhe formate solo da simboli dell’alfabeto A (simboli terminali) e derivabili dall’assioma s.

Queste definizioni si applicano, sebbene con alcuni importanti limiti, anche alla generazione dei linguaggi naturali. Il termine grammatica generativa è stato infatti introdotto dal linguista e filosofo Noam Chomsky (Filadelfia, Pennsylvania, 1928) che negli anni Sessanta del secolo scorso sviluppò la teoria delle grammatiche generative, a partire dall’analisi della struttura del linguaggio (il suo Syntactic structures, Le strutture della sintassi, fu pubblicato nel 1957). Successivamente Chomsky sviluppò operatori di trasformazione delle stringhe per riuscire a esprimere la grande plasticità dei linguaggi naturali. La difficoltà di rendere un linguaggio formale pienamente adeguato a descrivere un linguaggio naturale viene meno se si considera un linguaggio di programmazione pienamente descritto dall’insieme di regole che permette la costruzione delle stringhe che gli appartengono. Così, la maggiore applicazione delle grammatiche generative si è avuta nella costruzione di linguaggi formali e nell’automazione di quella fase della programmazione in cui l’automa deve stabilire se una data istruzione è scritta in modo corretto o meno (cioè appartiene o meno al linguaggio in cui è scritto il programma) e successivamente tradurla in linguaggio direttamente interpretabile dall’elaboratore che la deve eseguire. Per questo, il compilatore di un elaboratore elettronico fa un’analisi sintattica di ogni istruzione, comunica gli eventuali errori (indicandoli, appunto, come errori sintattici) e se l’istruzione è corretta provvede alla sua traduzione in linguaggio macchina.

Per fare ciò deve avere una completa descrizione della grammatica del linguaggio utilizzato e applica le sue produzioni per vedere se la stringa immessa è o meno derivabile a partire dal suo insieme di produzioni. In questo caso l’automa funziona come un riconoscitore del linguaggio generato dalla grammatica.

A titolo di esempio, si consideri un linguaggio L costituito da una grammatica G che abbia come insieme dei simboli terminali A = {studia, Aldo, Eva, storia, filosofia} e come insieme di simboli non terminali l’insieme A_N = {F, S, P, C}, con F che indica una frase e costituisce l’assioma, S che indica un soggetto, P un predicato, cioè il verbo, C un complemento.

Le produzioni siano: F → SPC; S → Aldo; S → Eva; P → studia; C → storia; C → filosofia.

La frase (stringa) «Aldo studia storia» può essere generata da G. Infatti, a partire dal simbolo iniziale F e applicando le produzioni, si ha la derivazione:

Al contrario, una frase come «studiastoriafilosofia» non è una frase del linguaggio L perché non può essere generata in G a partire dal simbolo F.

A ogni derivazione grammaticale può essere associato un → albero che abbia come radice l’assioma e come foglie terminali gli elementi dell’alfabeto A.