Terminale und nicht terminale Symbole

Im Informatik, terminale und nicht terminale Symbole sind die lexikalischen Elemente zur Angabe der Produktionsregeln Konstituieren Sie a formelle Grammatik. Terminalsymbole sind die elementaren Symbole der Sprache definiert durch eine formelle Grammatik. Nicht terminale Symbole (oder syntaktische Variablen) werden durch Gruppen von Terminalsymbolen gemäß den Produktionsregeln ersetzt.

Die Terminals und Nicht -Terminals einer bestimmten Grammatik sind zwei disjunkte Sätze.

Terminalsymbole

Terminalsymbole sind wörtliche Symbole, die in den Ausgaben der Produktionsregeln einer formalen Grammatik erscheinen können und die mit den Regeln der Grammatik nicht geändert werden können. Das Anwenden der Regeln auf eine Quellzeichenfolge von Symbolen endet normalerweise in einer endgültigen Ausgabezeichenfolge, die nur aus terminalen Symbolen besteht.

Betrachten Sie eine Grammatik, die durch zwei Regeln definiert ist. Verwenden von pictorischen Markierungen, die miteinander interagieren:

  1. Das Symbol ר kann werden дament
  2. Das Symbol ר kann werden д

Hier д ist ein terminales Symbol, weil es keine Regel gibt, die es in etwas anderes ändern würde. Auf der anderen Seite, ר hat zwei Regeln, die es ändern können, daher ist es nicht terminal. EIN formelle Sprache definiert oder generiert Durch eine bestimmte Grammatik sind die Saiten, die von der Grammatik erzeugt werden können und das besteht nur aus terminalen Symbolen.

Nicht terminale Symbole

Nicht terminale Symbole sind die Symbole, die ersetzt werden können. Sie können auch einfach genannt werden syntaktische Variablen. Eine formelle Grammatik beinhaltet a Starten Sie das Symbol, ein bestimmtes Mitglied der Set von Nicht -Terminals, aus denen alle Strings in der Sprache durch aufeinanderfolgende Anwendungen der Produktionsregeln abgeleitet werden können. Tatsächlich ist die durch eine Grammatik definierte Sprache genau der Satz von Terminal Saiten, die so abgeleitet werden können.

Kontextfreie Grammatiken sind jene Grammatiken, in denen die linke Seite jeder Produktionsregel nur aus einem einzigen nicht terminalen Symbol besteht. Diese Einschränkung ist nicht trivial; Nicht alle Sprachen können durch kontextfreie Grammatiken generiert werden. Wer als kontextfreie Sprachen bezeichnet wird. Dies sind genau die Sprachen, die von einem nicht deterministischen Anerkennung erkannt werden können Automat nach unten drücken. Kontextfreie Sprachen sind die theoretische Grundlage für die Syntax der meisten Programmiersprachen.

Produktionsregeln

Eine Grammatik ist definiert durch Produktionsregeln (oder nur 'Produktionen'), die angeben, welche Symbole die anderen Symbole ersetzen können; Diese Regeln können verwendet werden Saiten erzeugen, oder um sie zu analysieren. Jede solche Regel hat a Kopfoder linke Seite, die aus der Saite besteht, die ersetzt werden kann, und a Karosserieoder rechte Seite, die aus einer Schnur besteht, die sie ersetzen kann. Regeln werden oft in der Form geschrieben Kopf → Karosserie; z. B. die Regel a → b Gibt das an a kann durch ersetzt werden durch b.

In der klassischen Formalisierung generativer Grammatiken, die zuerst von vorgeschlagen wurden von Noam Chomsky in den 1950ern,[1][2] eine Grammatik G besteht aus den folgenden Komponenten:

  • Ein endliches Set N von Nicht terminale Symbole.
  • Ein endliches Set Σ von Terminalsymbole das ist disjunkt aus N.
  • Ein endliches Set P von Produktionsregeln, jede Regel der Form
wo ist der Kleene Star Bediener und ∪ bezeichnet Set Union, Also repräsentiert null oder mehr Symbole, und N bedeutet einen nicht terminal Symbol. Das heißt, jede Produktionsregel kartiert von einer Zeichenfolge von Symbolen zu einer anderen, wobei die erste Zeichenfolge mindestens ein nicht terminales Symbol enthält. In dem Fall, dass der Körper ausschließlich aus dem besteht leerer String[Anmerkung 1]kann es mit einer besonderen Notation bezeichnet werden (oft Λ, e oder ε) um Verwirrung zu vermeiden.
  • Ein angesehenes Symbol das ist das Starten Sie das Symbol.

Eine Grammatik wird offiziell als das geordnete Vierfach definiert . Eine solche formale Grammatik wird oft als als genannt System umschreiben oder ein Phrasenstruktur Grammatik in der Literatur.[3][4]

Beispiel

Zum Beispiel stellt Folgendes eine Ganzzahl dar (die signiert werden kann) in einer Variante von ausgedrückt wird Backus -Naur -Form:

<Ziffer> :: = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'<ganze Zahl> :: = ['-'] <Ziffer> {<Ziffer>}

In diesem Beispiel die Symbole (-, 0,1,2,3,4,5,6,7,8,9) sind terminale Symbole und und sind nicht terminale Symbole.[Anmerkung 2]

Ein weiteres Beispiel ist:

In diesem Beispiel die Symbole A B C D sind terminale Symbole und S, a sind nicht terminale Symbole.

Siehe auch

Anmerkungen

  1. ^ Es enthält überhaupt keine Symbole.
  2. ^ Dieses Beispiel unterstützt Saiten mit führenden Nullen wie "0056" oder "0000" sowie negative Null-Saiten wie "-0" und "-00000".


Verweise

  1. ^ Chomsky, Noam (1956). "Drei Modelle für die Beschreibung der Sprache". IRE -Transaktionen zur Informationstheorie. 2 (3): 113–123. doi:10.1109/tit.1956.1056813.
  2. ^ Chomsky, Noam (1957). Syntaktische Strukturen. Den Haag: Mouton.
  3. ^ Ginsburg, Seymour (1975). Algebraische und automatische theoretische Eigenschaften formaler Sprachen. Nordholland. S. 8–9. ISBN 0-7204-2506-9.
  4. ^ Harrison, Michael A. (1978). Einführung in die formale Sprachtheorie. Reading, Mass.: Addison-Wesley Publishing Company. pp.13. ISBN 0-201-02955-3.