Formalismus zur Beschreibung der Syntax einer formalen Sprache.

Sie stellt ein Alphabet, d. h. eine endliche Menge von Zeichen zur Bildung von Wörtern, eine Menge von Nichtterminalsymbolen (meist verwendet zur Beschreibung von syntaktischen Einheiten) und eine Menge von Ableitungsregeln zur Generierung von Wörtern aus einem ausgezeichneten Nichtterminalzeichen, dem Startsymbol, bereit.

Formal wird eine (allgemeine) Grammatik durch ein Tupel [Σ, V, R, S] beschrieben, wobei das Alphabet Σ eine beliebige endliche Menge, der Vorrat V an Nichttermninalsymbolen eine dazu disjunkte endliche Menge, die Regelmenge R eine binäre Relation auf (V ∪ Σ)^∗ und das Startsymbol S ein Element aus V sind.

Ein Wort über einem Alphabet Σ entsteht durch Aneinanderreihung von endlich vielen Buchstaben. Die Anzahl der aneinandergereihten Buchstaben ergibt die Länge eines Wortes. Die Menge Σ^∗ bezeichnet die Menge aller Wörter über Σ. Das leere Wort, das keinen Buchstaben enthält und die Länge 0 hat, wird mit ϵ bezeichnet.

Die Regelmenge R der Grammatik definiert eine Ableitungsrelation auf der Menge der Satzformen, also der Wörter über Σ ∪ V. Dabei ist eine Satz-form v₂ aus einer Satzform v₁ direkt ableitbar (v₁ ⇒ v₂), falls man in v₁ die linke Seite der Regel auffinden kann und v₂ durch Ersetzen dieser linken Seite durch die rechte Seite entsteht. v₁ ⇒ v₂ gilt also genau dann, wenn Wörter w und w′ und eine Regel (u₁, u₂) existieren mit v₁ = wu₁w′ und v₂ = wu₂w′. Die reflexiv–transitive Hülle von ⇒ wird mit ⇒^∗ notiert. Die von der Grammatik G erzeugte Sprache L(G) ist die Menge der Wörter über Σ, die aus dem Startsymbol von G ableitbar sind, also L(G) = {w | w ∈ Σ^∗, S ⇒^∗w}. Zwei Grammatiken G₁ und G₂ sind äquivalent, wenn L(G₁) = L(G₂) ist.

Eine Grammatik heißt ϵ-frei, falls auf der rechten Seite von Regeln nie das leere Wort steht. Sie heißt ϵ-treu, wenn es höchstens eine Regel mit ϵ auf der rechten Seite gibt, nämlich (S, ϵ) und das Startsymbol S dann in keiner rechten Seite anderer Regeln vorkommt. Bei einer normalen Grammatik kommt auf jeder linken Seite einer Regel mindestens ein Nichtterminalsymbol vor. Eine separierte Grammatik arbeitet zunächst ausschließlich auf Hilfssymbolen, d. h. Regeln haben die Form (u, v), wobei u und v nichtleere Wörter aus Nichtterminalzeichen sind. Darüberhinaus sind Regeln der Form (h, a) zugelassen, wobei h ∈ V und a ∈ Σ ∪ {ϵ} ist. Zu jeder Grammatik gibt es eine äquivalente normale und eine äquivalente separierte Grammatik. Der Ableitungsweg eines Wortes aus dem Startsymbol gibt dem Wort eine grammatische Struktur.

Für kontextsensitive Grammatiken und kontextfreie Grammatiken kann diese Struktur durch den Ableitungsbaum widergespiegelt werden. Bei kontextsensitiven Grammatiken ersetzt eine Regel ein einziges Hilfssymbol, der Rest der linken Seite erscheint auch auf der rechten Seite. Regeln haben also die Form \begin{eqnarray}(wh{w}{^{\prime} },\,wv{w}{^{\prime} })\end{eqnarray} mit w, w′, v ∈ (V ∪ Σ)^∗ und h ∈ V. w und w′ heißen linker bzw. rechter Kontext der Regel. Sind in allen Regeln die w und w′ das leere Wort, heißt die Grammatik kontextfrei. Der Ableitungsbaum zu einem Wort der Sprache hat das Startsymbol als Wurzel; jeder Knoten hat diejenigen Zeichen als Nachfolger, durch die er im Ableitungsprozeß ersetzt wurde.

Die Abbildung zeigt einen Ableitungsbaum für das Wort z + z ∗ (z + z) und die Grammatik G = [{z, +, ∗,(,)}, {S, T, F}, {(S, T), (S, S + T), (T, F), (T, T ∗ F), (F, z), (F,(S))}, S].

Die Grammatik realisiert die Regel Punktrechnung vor Strichrechnung und berücksichtigt die Klammerung, denn der Ableitungsbaum faßt die Teilausdrücke diesen Regeln entsprechend zusammen. Bei eindeutigen Grammatiken (Grammatiken, die zu jedem Wort genau eine Links- bzw. Rechtsableitung liefern), ist der Ableitungsbaum eindeutig bestimmt.

Eine nicht eindeutige Grammatik heißt mehrdeutig. Jede ϵ-treue und kontextsensitive Grammatik ist monoton, d. h. mit Ausnahme der Regel (S, ϵ) sind alle rechten Seiten von Regeln mindestens so lang wie ihre linken Seiten. Zu jeder monotonen Grammatik gibt es eine äquivalente kontextsensitive Grammatik. Für monotone Grammatiken G ist die Zugehörigkeit eines Wortes zu L(G) entscheidbar, weil der Suchraum zum Finden einer geeigneten Ableitung eines Wortes durch dessen Länge beschränkt werden kann. Eine kontextfreie Gram-matik heißt linear, wenn auf der rechten Seite von Regeln höchstens ein Nichtterminalzeichen (neben Alphabetzeichen) vorkommt. Sie heißt rechts-linear, falls Nichtterminalzeichen auf der rechten Seite der Regeln höchstens als letztes Zeichen vorkommen, und linkslinear, falls Nichtterminalzeichen auf der rechten Seite von Regeln höchstens als erstes Zeichen vorkommen. Eine kontextfreie Grammatik heißt reduziert, falls sie nur produktive und erreichbare Nichtterminals enthält. Zu einer beliebigen kontextfreien Grammatik kann immer eine reduzierte Grammatik konstruiert werden.