Als formale Grammatiken werden mathematische Modelle bezeichnet, welche dann in der Folge zur Erzeugung von formalen Sprachen verwendet werden können. Formale Grammatiken finden u.a. Anwendung in der Computerlinguistik und im Compilerbau. Die unterschiedlichen Typen von Grammatiken werden analog der Chomsky-Hierarchie klassifiziert.
Eine Grammatik ist ein Quadrupel G = (N,T,R,S) mit
- der endlichen Menge von Symbolen, auch Nichtterminale, Nonterminals oder Variablen genannt,
- der endlichen Menge von sprachbildenden terminalen Zeichen, den Terminalen T.
- der endlichen Menge R von Produktionsregeln, auch Produktionen oder Regeln genannt und
- dem Startsymbol S eines Satzes.
- die Nichtterminale N und die Terminale sind disjunkt (das bedeutet elementfremd) und
- das Startsymbol S ist Teil der Menge der Nonterminals N.
Zu den grundlegenden Begriffen im Zusammenhang mit einer formalen Grammatik gehören: Vokabular: Das Vokabular ist die Menge aller terminalen und nichtterminalen Elemente einer formalen Grammatik.
Nonterminal: Nonterminals kennzeichnen eine syntaktische Kategorie und sind im wesentlichen Hilfssymbole, die für die Erzeugung bzw. Erkennung der Sätze der formalen Sprache durch die Grammatik dienen. Zur Notation: Nonterminals werden in der Regel durch Großbuchstaben oder in «Klammerung» dargestellt.
Terminal: Terminale Elemente sind diejenigen aus denen sich die Worte der zu erzeugenden formalen Sprache zusammensetzen und kennzeichnen damit deren Alphabet. Zu deren Notation: Terminals werden in der Regel in Kleinbuchstaben dargestellt.
Produktionen: Die Menge der Produktionsregeln ist eine zweistellige Relation (u,v). Der linke und der rechte Teil dieser Relation sind Mengen von Zeichenreihen über dem Vokabular, wobei ausgeschlossen wird, dass der linke Teil der Relation nur terminale Elemente enthält. Diese Einschränkung besteht für den rechten Teil der Relation nicht. Weiterhin ist die leere Zeichenreihe im rechten Teil zugelassen, jedoch im linken Teil der Relation ausgeschlossen.
Startsymbol: Das Startsymbol kennzeichnet den Beginn der Erzeugung bzw. Erkennung von Sätzen der formalen Sprache durch die Grammatik.
Als ein Beispiel sei folgendes Quadrupel gegeben:
Zur Erzeugung einer formalen Sprache kann es immer mehrere formale Grammatiken geben.