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 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

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

  • 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.

Auf dieser Seite verwendete Medien

Palindrome abcacba.svg
Autor/Urheber: Zahnradzacken, Lizenz: CC BY-SA 3.0
Ein Syntaxbaum für "abcacba" in einer Grammatik, die Palindrome über {a,b,c} generiert.
ParseTree.svg
Image for use in basic articles dealing with parse trees, nodes, branches, X-Bar theory, linguistic theory.