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

Bearbeiten

Für eine formale Grammatik   bezeichnet   die Menge der Nichtterminalsymbole. Ihr steht die Menge der Terminalsymbole   entgegen. Die Menge   der Produktionsregeln beschreibt, wie Nichtterminalsymbole durch neue Zeichenfolgen ersetzt werden dürfen. Das Startsymbol  , von dem aus alle Wörter abgeleitet werden, ist eines der Nichtterminalsymbole:  .

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

Beispiele

Bearbeiten

Die Grammatik

 .
 
 
 

erzeugt die Sprache aller a,b,c-Palindrome, zum Beispiel   oder  . Sie benötigt nur ein Nichtterminalsymbol, nämlich  .

Das Palindrom   lässt sich in   ableiten, indem das Nichtterminalsymbol   zunächst zu   ersetzt wird, das darin vorhandene   durch  , mit dem Ergebnis  . Dieses   wird dadurch entfernt, dass es durch das leere Wort   ersetzt wird, sodass man   erhält.

Ein Ableitungsbaum für das Palindrom   enthält die Terminalsymbole   in den Blättern und   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.

Literatur

Bearbeiten