Introduzione alle grammatiche

Definizione di grammatica

Una grammatica (o grammatica generatrice) è una quadrupla definita come segue: $G=(X,V,S,P)$. La grammatica risulta essere l'insieme delle regole che specificano o generano in modo ricorso le formule be formate (ovvero le espressioni sinteticamente corrette) di un linguaggio.

In particolare:

• $X$ è l'alfabeto terminale della grammatica, ovvero l'insieme finito di simboli con cui si formano le parole del linguaggio, i relativi elementi vengono indicati con la lettera minuscola dell'alfabeto;
• $V$ è l'alfabeto non terminale della grammatica, ovvero l'insieme con cui si identificano le catoegorie sintattiche del linguaggio, dove gli elementi vengono indicati con la lettera maiuscola dell'alfabeto;
• $S$ è il simbolo di partenza per la grammatica scelto tra i non terminali, da questo viene fatta partire la generazione delle parole del linguaggio (esso è detto anche "scopo");
• $P$ è l'insieme delle produzioni della grammatica tipicamente espresse in un formalismo (ad esempio regole di riscrittura come la Baccus-Naur Form).

Per quest'ultimo punto occorre sottolineare che $X\cap V=\emptyset$

Una grammatica è uno strumento generativo e non deterministico di un linguaggio, perché la sostituzione di non terminali con i terminali non avviene in modo univoco.

Le grammatiche non sono tutte uguali, esiste infatti una gerarchia che descrive le differenti tipologie.

Produzioni

Sicuramente le produzioni sono il concetto che richiede maggiori spiegazioni, procediamo quindi col dire che cos'è formalmente una produzione. Una produzione è una coppia $(v,w)$ dove $v\in (X\cup V)^{+}$ e $v$ contiene un non terminale come sottostringa $\iff v\in (X\cup V)^{*}V(X\cup V)^{*}$, pertanto $v$ non potrà mai assumere il valore $\lambda$ (lambda) a differenza di $w$, infatti $w\in (X\cup V)^{*}$. Detto ciò, possiamo dire che una produzione permette di riscrivere in qualche modo un non terminale.

Uguaglianza di grammatiche

È utile sapere che una grammatica può generare un linguaggio, ma un linguaggio può essere generato da più grammatiche quindi, denotando con $L(G)$ l'insieme delle forme di frasi terminali (o semplicemente frasi), è possibile avere situazione del tipo $L(G)=L(G')$.