Grammatica formale

La grammatica formale, nella teoria dei linguaggi formali, è una struttura astratta che descrive un linguaggio formale in modo preciso, è cioè un sistema di regole che delineano matematicamente un insieme (di solito infinito) di sequenze finite di simboli (stringhe) appartenenti ad un alfabeto anch'esso finito.

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 connettivo logico 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.