Unterabschnitte
Jeder Identifier besteht aus einem Buchstaben gefolgt von beliebig vielen Buchstaben oder Ziffern. |
Idf |
 |
Buchstabe|Buchstabe A |
A |
 |
Buchstabe|Buchstabe A|Ziffer|Ziffer A |
Buchstabe |
 |
,,A''|,,B''|...|,,Z''|,,a''|...|,,z'' |
Ziffer |
 |
,,0''|...|,,9'' |
|
Man kann die Ableitung eines Wortes mit Hilfe der Symbole

und

darstellen. Dabei steht
für die Anwendung von nur einer Regel und
-
für die Anwendung beliebig vieler Regeln.
Eine Grammatik ist ein 4er-Tupel

wobei
: endliche Menge von Nichtterminalen44
: endliche Menge von Terminalsymbolen. Dabei gilt
.
: Produktions bzw. Regelsystem. Einzelne Teile des Systems heißen ,,Produktion'' oder ,,Regel''.
: Das Startsymbol
Die Sprache enthält alle durch die Grammatik G erzeugbaren Wörter:
Zwei Grammatiken

und

heißen äquivalent, wenn sie dieselbe Sprache erzeugen:
Fußnoten
- ... Nichtterminalen44
- Nichtterminale kann man auch Variablen nennen.