Einführung in die Grammatiken

Theorie Icon Grammatiken stellen eine Möglichkeit dar, um Sprachen zu beschreiben. Sie verwenden Produktionsregeln, die definieren, welche Wörter ausgehend von einem Startsymbol aufgebaut werden können.

Grammatiken bieten also einen Weg, unendliche Sprachen auf endliche Weise eindeutig zu spezifizieren. Grammatiken sind Mechanismen zur Generierung (Erzeugung) von Wörtern.

Definition

Eine Grammatik ist ein 4-Tupel folgender Zusammensetzung: \( G = (V, \sum, P, S) \):

  • Eine Menge von Variablen \(V\)
  • Ein Alphabet \(\sum\), disjunkt zu \(V (V \cap \sum = \emptyset\))
  • Eine Menge von Produktionsregeln \(P\) der Form \(w \rightarrow v\) für beliebige Wörter \(w\) und \(v\) über \(V \cup \sum \)
  • Ein Startsymbol \(S \in V\)

Aufbau einer Grammatik

Theorie Icon In der Literatur sind Variablen auch unter der Bezeichnung Nichtterminalsymbole bekannt und die Elemente des Alphabets heißen Terminalsymbole. Die Begriffe ergeben sich daraus, dass Variablen durch ein anderes Wort ersetzt (abgeleitet) werden können. Dagegen können alleinstehende Terminalsymbole nicht abgeleitet werden und sobald das Wort nur aus Terminalsymbolen besteht, terminiert (d. h. beendet nach gewisser Zeit) der Ableitungsvorgang. In einem späteren Beispiel werden die Begriffe deutlicher.

Zur besseren Unterscheidung von Variablen und Nichtterminalsymbolen wird in der Literatur die Konvention verwendet, dass für Variablen Großbuchstaben \((A, B, C, ...)\) und für Nichtterminalsymbole Kleinbuchstaben \((a, b, c, ...)\) verwendet werden.