Introduzione alle grammatiche
Definizione di grammatica
[modifica]Una grammatica (o grammatica generatrice) è una quadrupla definita come segue: . 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:
- è 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;
- è 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;
- è 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");
- è 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
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
[modifica]Sicuramente le produzioni sono il concetto che richiede maggiori spiegazioni, procediamo quindi col dire che cos'è formalmente una produzione. Una produzione è una coppia dove e contiene un non terminale come sottostringa , pertanto non potrà mai assumere il valore (lambda) a differenza di , infatti . Detto ciò, possiamo dire che una produzione permette di riscrivere in qualche modo un non terminale.
Uguaglianza di grammatiche
[modifica]È utile sapere che una grammatica può generare un linguaggio, ma un linguaggio può essere generato da più grammatiche quindi, denotando con l'insieme delle forme di frasi terminali (o semplicemente frasi), è possibile avere situazione del tipo .