Introduzione alle grammatiche

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search

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 .