Nichtterminalsymbol

Ein Nichtterminalsymbol (auch Nichtterminal, Nonterminalsymbol oder Variable genannt) einer formalen Grammatik ist ein Symbol, das nicht in den endgültigen Wörtern vorkommt, die in der Grammatik erzeugt werden können. Nichtterminalsymbole kommen nur in Zwischenschritten einer Ableitung vor und werden durch das Anwenden von Regeln in der Grammatik nach und nach ersetzt, bis nur noch Terminalsymbole vorhanden sind.

Definition

Für eine formale Grammatik ${\displaystyle G=(N,T,P,S)}$ bezeichnet ${\displaystyle N}$ die Menge der Nichtterminalsymbole. Ihr steht die Menge der Terminalsymbole ${\displaystyle T}$ entgegen. Die Menge ${\displaystyle P}$ der Produktionsregeln beschreibt, wie Nichtterminalsymbole durch neue Zeichenfolgen ersetzt werden dürfen. Das Startsymbol ${\displaystyle S}$, von dem aus alle Wörter abgeleitet werden, ist eines der Nichtterminalsymbole: ${\displaystyle S\in N}$.

Nichtterminale werden oft als Großbuchstaben geschrieben oder, etwa bei der Backus-Naur-Form, in spitze Klammern eingeschlossen.

Beispiele

Die Grammatik

${\displaystyle G=\left(N,T,P,S\right)}$.

${\displaystyle N=\{S\}}$

${\displaystyle T=\{a,b,c\}}$

${\displaystyle P:S\rightarrow aSa,S\rightarrow bSb,S\rightarrow cSc,S\rightarrow a,S\rightarrow b,S\rightarrow c,S\rightarrow \varepsilon }$

erzeugt die Sprache aller a,b,c-Palindrome, zum Beispiel ${\displaystyle abba}$ oder ${\displaystyle abcacba}$. Sie benötigt nur ein Nichtterminalsymbol, nämlich ${\displaystyle S}$.

Das Palindrom ${\displaystyle abba}$ lässt sich in ${\displaystyle G}$ ableiten, indem das Nichtterminalsymbol ${\displaystyle S}$ zunächst zu ${\displaystyle aSa}$ ersetzt wird, das darin vorhandene ${\displaystyle S}$ durch ${\displaystyle bSb}$, mit dem Ergebnis ${\displaystyle abSba}$. Dieses ${\displaystyle S}$ wird dadurch entfernt, dass es durch das leere Wort ${\displaystyle \varepsilon }$ ersetzt wird, sodass man ${\displaystyle abba}$ erhält.

Ein Ableitungsbaum für das Palindrom ${\displaystyle abcacba}$ enthält die Terminalsymbole ${\displaystyle a,b,c}$ in den Blättern und ${\displaystyle S}$ als Wurzel und innere Knoten.

Syntaxbäume in der Linguistik, die die grammatikalische Struktur eines Satzes darstellen, enthalten als Terminalsymbole die Wörter des Satzes und als Nichtterminale die grammatikalischen Konstituenten. Ein Satz besteht häufig aus einer Nominalphrase und einer Verbalphrase. Verbalphrasen können wiederum beispielsweise aus einem Verb und einer weiteren Nominalphrase bestehen. Nominalphrasen können zum Beispiel Nomen mit oder ohne vorangestelltem Artikel sein. Satz, Nominalphrase, Verbalphrase, Verb, Nomen und Artikel sind hier die Nichtterminalsymbole.

• 

  Ableitungsbaum von abcacba mit Nichtterminalsymbol S

• 

  Syntaxbaum zu John hit the ball

Literatur

• John E. Hopcroft, Jeffry D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Addison-Wesley, Bonn 1994, ISBN 3-89319-744-3.