In der formellen Sprachtheorie, eine Grammatik ohne Zusammenhänge (CFG)

ist eine formelle Grammatik, in der jede Produktionsregel von der Form ist

:V → w

wo V ein einzelnes Nichtendsymbol ist, und w eine Reihe von Terminals ist und/oder Nichtterminals (w leer sein kann).

Die durch Grammatiken ohne Zusammenhänge erzeugten Sprachen sind als die Sprachen ohne Zusammenhänge bekannt.

Grammatiken ohne Zusammenhänge sind in der Linguistik wichtig, für die Struktur von Sätzen und Wörtern auf natürlicher Sprache, und in der Informatik zu beschreiben, für die Struktur von Programmiersprachen und anderen formellen Sprachen zu beschreiben.

In der Linguistik verwenden einige Autoren die Begriff-Ausdruck-Struktur-Grammatik, um sich auf Grammatiken ohne Zusammenhänge zu beziehen, wodurch Ausdruck-Struktur-Grammatiken von Abhängigkeitsgrammatiken verschieden sind. In der Informatik ist eine populäre Notation für Grammatiken ohne Zusammenhänge Backus-Naur-Form oder BNF.

Hintergrund

Seit der Zeit von Pāini, mindestens, haben Linguisten die Grammatiken von Sprachen in Bezug auf ihre Block-Struktur beschrieben und beschrieben, wie Sätze von kleineren Ausdrücken, und schließlich individuellen Wörtern oder Wortelementen rekursiv aufgebaut werden. Ein wesentliches Eigentum dieser Block-Strukturen besteht darin, dass logische Einheiten nie überlappen. Zum Beispiel, der Satz:

: John, dessen blaues Auto in der Werkstatt war, ist zum grünen Laden spazieren gegangen.

kann logisch parenthesized wie folgt sein:

: (John, ((dessen blaues Auto) (war (in der Werkstatt))), (ist (zu (der grüne Laden)) spazieren gegangen)).

Eine Grammatik ohne Zusammenhänge stellt einen einfachen und mathematisch genauen Mechanismus zur Verfügung, für die Methoden zu beschreiben, durch die Ausdrücke in einer natürlichen Sprache von kleineren Blöcken gebaut werden, die "Block-Struktur" von Sätzen auf eine natürliche Weise gewinnend. Seine Einfachheit macht den Formalismus zugänglich der strengen mathematischen Studie. Wichtige Eigenschaften der Syntax der natürlichen Sprache wie Abmachung und Verweisung sind nicht ein Teil der Grammatik ohne Zusammenhänge, aber die grundlegende rekursive Struktur von Sätzen, dem Weg, auf den Klausel-Nest innerhalb anderer Klauseln und der Weg, auf den Listen von Adjektiven und Adverbien durch Substantive und Verben geschluckt werden, genau beschrieben werden.

Der Formalismus von Grammatiken ohne Zusammenhänge wurde Mitte der 1950er Jahre von Noam Chomsky und auch ihre Klassifikation als ein spezieller Typ der formellen Grammatik entwickelt (den er Grammatiken der Ausdruck-Struktur genannt hat). Was Chomsky genannt hat, ist eine Ausdruck-Struktur-Grammatik auch jetzt als eine Wahlkreis-Grammatik bekannt, wodurch Wahlkreis-Grammatiken im Gegensatz zu Abhängigkeitsgrammatiken stehen. Im generativen Grammatik-Fachwerk von Chomsky wurde die Syntax der natürlichen Sprache durch mit Transformationsregeln verbundene Regeln ohne Zusammenhänge beschrieben.

Block-Struktur wurde in Computerprogrammiersprachen durch das ALGOL-Projekt (1957-1960) eingeführt, das demzufolge auch eine Grammatik ohne Zusammenhänge gezeigt hat, um die resultierende ALGOL-Syntax zu beschreiben. Das ist eine Standardeigenschaft von Computersprachen geworden, und die Notation für in konkreten Beschreibungen von Computersprachen verwendete Grammatiken ist gekommen, um als Backus-Naur Form nach zwei Mitgliedern des ALGOL-Sprachdesignkomitees bekannt zu sein. Der "Block Struktur" Aspekt, dass Grammatik-Festnahme ohne Zusammenhänge für die Grammatik so grundsätzlich ist, dass die Begriffe Syntax und Grammatik häufig mit Grammatik-Regeln ohne Zusammenhänge besonders in der Informatik identifiziert werden. Wie man dann betrachtet, sind formelle durch die Grammatik nicht gewonnene Einschränkungen ein Teil der "Semantik" der Sprache.

Grammatiken ohne Zusammenhänge sind einfach genug, den Aufbau von effizienten Syntaxanalyse-Algorithmen zu erlauben, die, für eine gegebene Schnur, bestimmen, ob und wie er von der Grammatik erzeugt werden kann. Earley parser ist ein Beispiel solch eines Algorithmus, während der weit verwendete LR und LL parsers einfachere Algorithmen sind, die sich nur mit einschränkenderen Teilmengen von Grammatiken ohne Zusammenhänge befassen.

Formelle Definitionen

Eine Grammatik ohne Zusammenhänge G wird durch den 4-Tupel-definiert:

wo

1. ist ein begrenzter Satz; jedes Element wird einen Nichtendcharakter oder eine Variable genannt. Jede Variable vertritt einen verschiedenen Typ des Ausdrucks oder der Klausel im Satz. Variablen werden auch manchmal syntaktische Kategorien genannt. Jede Variable definiert eine Subsprache der Sprache, die dadurch definiert ist.

1. ist ein begrenzter Satz von Terminals, die davon zusammenhanglos sind, die den wirklichen Inhalt des Satzes zusammensetzen. Der Satz von Terminals ist das Alphabet der durch die Grammatik definierten Sprache.

1. ist eine begrenzte Beziehung von dazu. Die Mitglieder dessen werden die (umschreiben) Regeln oder Produktion der Grammatik genannt. (auch allgemein symbolisiert durch)

1. ist die Anfang-Variable (oder Anfang-Symbol), verwendet, um den ganzen Satz (oder Programm) zu vertreten. Es muss ein Element dessen sein.

Das Sternchen vertritt die Sternoperation von Kleene.

Produktionsregel-Notation

Eine Produktionsregel darin wird mathematisch als ein Paar formalisiert, wo ein Nichtterminal ist und eine Reihe von Variablen und Nichtterminals ist; anstatt bestellte Paar-Notation zu verwenden, werden Produktionsregeln gewöhnlich mit einem Pfeil-Maschinenbediener mit als seine linke Seite und als seine rechte Seite geschrieben:

.

Es wird zugelassen, um die leere Schnur zu sein, und in diesem Fall ist es üblich, um es durch ε anzuzeigen. Die Form wird einen ε-production genannt.

Regel-Anwendung

Für irgendwelche Schnuren sagen wir Erträge, schriftlich als, wenn mit und solch dass und. So, ist das Ergebnis, die Regel darauf anzuwenden.

Wiederholende Regel-Anwendung

Für irgendwelchen (oder in einigen Lehrbüchern), wenn solch dass

Sprache ohne Zusammenhänge

Die Sprache einer Grammatik ist der Satz

:Wie man

sagt, ist eine Sprache eine Sprache ohne Zusammenhänge (CFL), wenn dort ein CFG, solch dass besteht.

Richtiger CFGs

Wie man

sagt, ist eine Grammatik ohne Zusammenhänge richtig, wenn sie hat

• keine unzugänglichen Symbole:
• keine unproduktiven Symbole:
• kein ε-productions: ε (zeigt der richtige Pfeil in diesem Fall logisch an, "bezieht ein" und nicht grammatische "Erträge")
• keine Zyklen:

Beispiel

Die Grammatik, mit der Produktion

:S → aSa,

:S → bSb,

:S → ε,

ist

ohne Zusammenhänge. Es ist nicht richtig, da es einen ε-production einschließt. Eine typische Abstammung in dieser Grammatik ist

:S → aSa → aaSaa → aabSbaa → aabbaa.

Das macht das verständlich

.

Die Sprache ist ohne Zusammenhänge, jedoch kann es bewiesen werden, dass es nicht regelmäßig ist.

Beispiele

Gut gebildete Parenthesen

Das kanonische Beispiel eines Zusammenhangs freie Grammatik ist das Parenthese-Zusammenbringen, das den allgemeinen Fall vertretend ist. Es gibt zwei Endsymbole" (" und")" und ein Nichtendsymbol S. Die Produktionsregeln sind

:S → SS

:S → (S)

:S →

Die erste Regel erlaubt Ss zu multiplizieren; die zweite Regel erlaubt Ss, eingeschlossen durch das Zusammenbringen von Parenthesen zu werden; und die dritte Regel begrenzt den recursion.

Gut gebildet hat Parenthesen und eckige Klammern verschachtelt

Ein zweites kanonisches Beispiel ist zwei verschiedene Arten des Zusammenbringens von verschachtelten Parenthesen, die durch die Produktion beschrieben sind:

:S → SS:S → :S → (S)

:S → []

:S → [S]

mit Endsymbolen [] und Nichtterminal S.

Die folgende Folge kann in dieser Grammatik abgeleitet werden:

: ([[[ [] []]] ([])])

Jedoch gibt es keine Grammatik ohne Zusammenhänge, um alle Folgen von zwei verschiedenen Typen von Parenthesen, jedes getrennt erwogene Ignorieren der andere zu erzeugen, aber wo die zwei Typen in einander zum Beispiel nicht zu nisten brauchen:

: [[[[((((]]]])))) (([)) (([)) ([) (]) (]) (])

Eine regelmäßige Grammatik

:S → ein

:S → als

:S → Bakkalaureus der Naturwissenschaften

Die Terminals hier sind a und b, während das einzige Nichtterminal S ist.

Die beschriebene Sprache ist alle nichtleeren Reihen von s und s dieses Ende darin.

Diese Grammatik ist regelmäßig: Keine Regel hat mehr als ein Nichtterminal in seiner Rechte, und jedes dieser Nichtterminals ist an demselben Ende der Rechte.

Jede regelmäßige Grammatik entspricht direkt zu einem nichtdeterministischen begrenzten Automaten, so wissen wir, dass das eine regelmäßige Sprache ist.

Jede regelmäßige Grammatik, ist jedoch nicht ohne Zusammenhänge alle Grammatiken ohne Zusammenhänge sind regelmäßig.

Es ist üblich, alle Rechten für dieselbe linke Seite auf derselben Linie, mit | (das Pfeife-Symbol) zu verzeichnen, um sie zu trennen. Folglich kann die Grammatik oben mehr knapp wie folgt beschrieben werden:

:S → | als | Bakkalaureus der Naturwissenschaften

Das Zusammenbringen von Paaren

In einer Grammatik ohne Zusammenhänge können wir Charaktere auf die Weise paarweise anordnen wir tun mit Klammern. Das einfachste Beispiel:

:S → aSb

:S → ab

Diese Grammatik erzeugt die Sprache, die (gemäß dem Pumpenden Lemma für regelmäßige Sprachen) nicht regelmäßig ist.

Der spezielle Charakter ε tritt für die leere Schnur ein. Durch das Ändern der obengenannten Grammatik zu

:S → aSb | ε\

wir erhalten eine Grammatik, die die Sprache stattdessen erzeugt. Das unterscheidet sich nur, in dem es die leere Schnur enthält, während die ursprüngliche Grammatik nicht getan hat.

Algebraische Ausdrücke

Hier ist eine Grammatik ohne Zusammenhänge für das syntaktisch richtige Infix algebraische Ausdrücke in den Variablen x, y und z:

1. S  x
2. S  y
3. S  z
4. S  S + S
5. S  S - S
6. S  S * S
7. S  S / S
8. S  (S)

Diese Grammatik kann zum Beispiel die Schnur erzeugen

:(x + y) * x - z * y / (x + x)

wie folgt:

:S (das Anfang-Symbol)

: → S - S (durch die Regel 5)

: → S * S - S (durch die Regel 6, die auf den leftmost S angewandt ist)

: → S * S - S / S (durch die Regel 7, die auf den niedrigstwertigen S angewandt ist)

: → (S) * S - S / S (durch die Regel 8, die auf den leftmost S angewandt ist)

: → (S) * S - S / (S) (durch die Regel 8, die auf den niedrigstwertigen S angewandt ist)

: → (S + S) * S - S / (S) (usw.).

: → (S + S) * S - S * S / (S)

: → (S + S) * S - S * S / (S + S)

: → (x + S) * S - S * S / (S + S)

: → (x + y) * S - S * S / (S + S)

: → (x + y) * x - S * y / (S + S)

: → (x + y) * x - S * y / (x + S)

: → (x + y) * x - z * y / (x + S)

: → (x + y) * x - z * y / (x + x)

Bemerken Sie, dass viele Wahlen laufend gemacht wurden, betreffs dessen umschreiben, war dabei, als nächstes durchgeführt zu werden.

Diese Wahlen sehen ziemlich willkürlich aus. Eigentlich sind sie im Sinn, dass die schließlich erzeugte Schnur immer dasselbe ist. Zum Beispiel schreiben das zweite und dritte um

: → S * S - S (durch die Regel 6, die auf den leftmost S angewandt ist): → S * S - S / S (durch die Regel 7, die auf den niedrigstwertigen S angewandt ist)

konnte in der entgegengesetzten Ordnung getan werden:

: → S - S / S (durch die Regel 7, die auf den niedrigstwertigen S angewandt ist)

: → S * S - S / S (durch die Regel 6, die auf den leftmost S angewandt ist)

Außerdem wurden viele Wahlen gemacht, auf dem Regel, für jeden zu gelten, ausgewählt hat.

Wenn sie

die Wahlen gemacht und nicht nur ändert, betrifft die Ordnung, in der sie gewöhnlich gemacht wurden, welche Endschnur am Ende herauskommt.

Wollen Blick darauf ausführlicher wir. Denken Sie den Syntaxanalyse-Baum dieser Abstammung:

S

|

/ | \

S - S

/ \

/ | \/| \

S * S S / S

/ | | \

/ | \x / | \/| \

(S) S * S (S)

/ | | \

/ | \z y / | \

S + S S + S

| | | |

x y x x

</Code>

Oben nach und nach anfangend, wird ein S im Baum ausgebreitet, bis nicht mehr nicht unausgebreitet, es (Nichtterminals) bleiben.

Die Auswahl einer verschiedenen Ordnung der Vergrößerung wird eine verschiedene Abstammung, aber denselben Syntaxanalyse-Baum erzeugen.

Der Syntaxanalyse-Baum wird sich nur ändern, wenn wir eine verschiedene Regel aufpicken, an einer Position im Baum zu gelten.

Aber kann ein verschiedener Syntaxanalyse-Baum, noch dieselbe Endschnur, erzeugen

welcher ist in diesem Fall?

Ja, für diese besondere Grammatik ist das möglich.

Grammatiken mit diesem Eigentum werden zweideutig genannt.

Zum Beispiel, kann mit diesen zwei verschiedenen Syntaxanalyse-Bäumen erzeugt werden:

S S

| |

/ | \/| \

S * S S + S

/ \/\

/ | \z x / | \

S + S S * S

| | | |

x y y z

</Code>

Jedoch ist die durch diese Grammatik beschriebene Sprache nicht von Natur aus zweideutig:

eine alternative, eindeutige Grammatik kann für die Sprache zum Beispiel gegeben werden:

:T &rarr; x

:T &rarr; y

:T &rarr; z

:S &rarr; S + T

:S &rarr; S - T

:S &rarr; S * T

:S &rarr; S / T

:T &rarr; (S)

:S &rarr; T

(wieder als das Anfang-Symbol aufpickend). Diese alternative Grammatik wird mit einem Syntaxanalyse-Baum erzeugen, der dem linken oben, d. h. implizit das Annehmen der Vereinigung ähnlich ist, die nicht gemäß der Standardmaschinenbediener-Priorität ist. Mehr wohl durchdachte, eindeutige und Grammatiken ohne Zusammenhänge können gebaut werden, die Syntaxanalyse-Bäume erzeugen, die der ganzen gewünschten Maschinenbediener-Priorität und Associativity-Regeln folgen.

Weitere Beispiele

Beispiel 1

Eine Grammatik ohne Zusammenhänge für die Sprache, die aus allen Schnuren über {a, b} besteht, eine ungleiche Zahl von a's und b's enthaltend:

:S &rarr; U | V

:U &rarr; TaU | TaT

:V &rarr; TbV | TbT

:T &rarr; aTbT | bTaT |

&epsilon;

Hier kann das Nichtterminal T alle Schnuren mit derselben Zahl von a's wie b's erzeugen, das Nichtterminal U erzeugt alle Schnuren mit mehr a's, als b's und das Nichtterminal V alle Schnuren mit weniger a's erzeugt als b's.

Beispiel 2

Ein anderes Beispiel einer nichtregelmäßigen Sprache ist. Es ist ohne Zusammenhänge, weil es durch die folgende Grammatik ohne Zusammenhänge erzeugt werden kann:

:S &rarr; bSbb | Ein

:A &rarr; aA |

&epsilon;

Andere Beispiele

Die Bildungsregeln für die Begriffe und Formeln der formalen Logik passen die Definition der Grammatik ohne Zusammenhänge, außer dass der Satz von Symbolen unendlich sein kann und es mehr als ein Anfang-Symbol geben kann.

Abstammungen und Syntax-Bäume

Eine Abstammung einer Schnur für eine Grammatik ist eine Folge von Grammatik-Regel-Anwendungen, die das Anfang-Symbol in die Schnur umgestaltet.

Eine Abstammung beweist, dass die Schnur der Sprache der Grammatik gehört.

Eine Abstammung wird durch das Geben für jeden Schritt völlig bestimmt:

• die Regel hat in diesem Schritt gegolten
• das Ereignis seiner linken Seite, auf die es angewandt wird

Für die Klarheit wird die Zwischenschnur gewöhnlich ebenso gegeben.

Zum Beispiel, mit der Grammatik:

(1) S  S + S

(2) S  1

(3) S  ein

die Schnur

1 + 1 + ein

kann mit der Abstammung abgeleitet werden:

S

 (Regel 1 auf dem ersten S)

S+S

 (Regel 1 auf dem zweiten S)

S+S+S

 (Regel 2 auf dem zweiten S)

S+1+S

 (Regel 3 auf dem Drittel S)

S+1+a

 (Regel 2 auf dem ersten S)

1+1+a

Häufig wird einer Strategie gefolgt, der deterministisch das folgende Nichtterminal bestimmt, um umzuschreiben:

• in einer leftmost Abstammung ist es immer das leftmost Nichtterminal;
• in einer niedrigstwertigen Abstammung ist es immer das niedrigstwertige Nichtterminal.

In Anbetracht solch einer Strategie wird eine Abstammung durch die Folge von angewandten Regeln völlig bestimmt. Zum Beispiel, die leftmost Abstammung

S  (Regel 1 auf dem ersten S) S+S  (Regel 2 auf dem ersten S)

1+S

 (Regel 1 auf dem ersten S)

1+S+S

 (Regel 2 auf dem ersten S)

1+1+S

 (Regel 3 auf dem ersten S)

1+1+a

kann als zusammengefasst werden

Regel 1, Regel 2, Regel 1, Regel 2, Regel 3

Die Unterscheidung zwischen leftmost Abstammung und niedrigstwertiger Abstammung ist wichtig, weil im grössten Teil von parsers die Transformation des Eingangs durch das Geben eines Stückes des Codes für jede Grammatik-Regel definiert wird, die durchgeführt wird, wann auch immer die Regel angewandt wird. Deshalb ist es wichtig zu wissen, ob der parser einen leftmost oder eine niedrigstwertige Abstammung bestimmt, weil das die Ordnung bestimmt, in der die Stücke des Codes durchgeführt werden. Sieh für ein Beispiel LL parsers und LR parsers.

Eine Abstammung beeindruckt auch in einem fühlen eine hierarchische Struktur auf der Schnur, die abgeleitet wird. Zum Beispiel, wenn die Schnur "1 + 1 +" gemäß der leftmost Abstammung abgeleitet wird:

:S &rarr; S + S (1)

: &rarr; 1 + S (2)

: &rarr; 1 + S + S (1)

: &rarr; 1 + 1 + S (2)

: &rarr; 1 + 1 + (3)

die Struktur der Schnur würde sein:

: {{1} + {{1} +} }\

wo {...} Zeigt eine Teilkette an, die als das Gehören S anerkannt ist. Diese Hierarchie kann auch als ein Baum gesehen werden:

S / | \

/ | \

/ | \

S '+' S

| / | \

| / | \

'1' S '+' S

| |

'1' 'ein'

</Code>

Dieser Baum wird einen konkreten Syntax-Baum genannt (sieh auch abstrakten Syntax-Baum) der Schnur. In diesem Fall definieren der präsentierte leftmost und die niedrigstwertigen Abstammungen denselben Syntax-Baum; jedoch gibt es eine andere (niedrigstwertige) Abstammung derselben Schnur

:S &rarr; S + S (1)

: &rarr; S + (3)

: &rarr; S + S + (1)

: &rarr; S + 1 + (2)

: &rarr; 1 + 1 + (2)

und das definiert den folgenden Syntax-Baum:

S

/ | \ / | \ / | \ S '+' S

/ | \|

/ | \|

S '+' S 'ein'

| |

'1' '1'

</Code>

Wenn, für bestimmte Schnuren auf der Sprache der Grammatik, es mehr als einen Parsebaum gibt, dann, wie man sagt, ist die Grammatik eine zweideutige Grammatik. Solche Grammatiken sind gewöhnlich hart grammatisch zu analysieren, weil der parser nicht immer entscheiden kann, welche Grammatik-Regel er anwenden muss. Gewöhnlich ist Zweideutigkeit eine Eigenschaft der Grammatik, nicht die Sprache, und eine eindeutige Grammatik kann gefunden werden, dass das dieselbe Sprache ohne Zusammenhänge erzeugt. Jedoch gibt es bestimmte Sprachen, die nur durch zweideutige Grammatiken erzeugt werden können; solche Sprachen werden von Natur aus zweideutig genannt.

Normale Formen

Jede Grammatik ohne Zusammenhänge, die die leere Schnur nicht erzeugt, kann in diejenige umgestaltet werden, in der keine Regel die leere Schnur als ein Produkt [eine Regel mit ε hat, wie ein Produkt einen ε-production] genannt wird. Wenn es wirklich die leere Schnur erzeugt, wird es notwendig sein, die Regel einzuschließen, aber dort kein anderer ε-rule sein müssen. Jede Grammatik ohne Zusammenhänge ohne ε-production hat eine gleichwertige Grammatik in Chomsky normale Form oder Greibach normale Form. "Gleichwertig" hier bedeutet, dass die zwei Grammatiken dieselbe Sprache erzeugen.

Wegen der besonders einfachen Form von Produktionsregeln in Chomsky Normale Form-Grammatiken hat diese normale Form sowohl theoretische als auch praktische Implikationen. Zum Beispiel, in Anbetracht einer Grammatik ohne Zusammenhänge, kann man den Chomsky Normale Form verwenden, um einen polynomisch-maligen Algorithmus zu bauen, der entscheidet, ob eine gegebene Schnur auf der Sprache ist, die durch diese Grammatik oder nicht (der CYK Algorithmus) vertreten ist.

Unentscheidbare Probleme

Einige Fragen, die für breitere Klassen von Grammatiken unentscheidbar sind, werden entscheidbar für Grammatiken ohne Zusammenhänge; z.B ist das Leere-Problem (ob die Grammatik irgendwelche Endschnuren überhaupt erzeugt), für mit dem Zusammenhang empfindliche Grammatiken unentscheidbar, aber für Grammatiken ohne Zusammenhänge entscheidbar.

Und doch, viele Probleme bleiben unentscheidbar. Beispiele:

Allgemeinheit

In Anbetracht eines CFG erzeugt es die Sprache aller Schnuren über das Alphabet von in seinen Regeln verwendeten Endsymbolen?

Die Verminderung kann zu diesem Problem vom wohl bekannten unentscheidbaren Problem der Bestimmung demonstriert werden, ob eine Maschine von Turing einen besonderen Eingang (das Stockende Problem) akzeptiert. Die Verminderung verwendet das Konzept einer Berechnungsgeschichte, eine Schnur, die eine komplette Berechnung einer Maschine von Turing beschreibt. Wir können einen CFG bauen, der alle Schnuren erzeugt, die Berechnungsgeschichten für eine besondere Maschine von Turing auf einem besonderen Eingang nicht akzeptieren, und so es alle Schnuren nur akzeptieren wird, wenn die Maschine diesen Eingang nicht akzeptiert.

Sprachgleichheit

In Anbetracht zwei CFGs erzeugen sie dieselbe Sprache?

Die Unentscheidbarkeit dieses Problems ist eine direkte Folge des vorherigen: Wir können nicht sogar entscheiden, ob ein CFG zum trivialen CFG das Definieren der Sprache aller Schnuren gleichwertig ist.

Spracheinschließung

In Anbetracht zwei CFGs kann das erste alle Schnuren erzeugen, die das zweite erzeugen kann?

Wenn dieses Problem entscheidbar ist, dann konnten wir es verwenden, um zu bestimmen, ob zwei CFGs G1 und G2 dieselbe Sprache durch die Überprüfung erzeugen, ob L (G1) eine Teilmenge von L (G2) ist und L (G2) eine Teilmenge von L (G1) ist.

In einer niedrigeren Ebene der Hierarchie von Chomsky seiend

In Anbetracht einer mit dem Zusammenhang empfindlichen Grammatik beschreibt es eine Sprache ohne Zusammenhänge?

In Anbetracht einer Grammatik ohne Zusammenhänge beschreibt es eine regelmäßige Sprache?

Jedes dieser Probleme ist unentscheidbar.

Erweiterungen

Eine offensichtliche Weise, den Grammatik-Formalismus ohne Zusammenhänge zu erweitern, soll Nichtterminals erlauben, Argumente zu haben, von denen die Werte vorwärts innerhalb der Regeln passiert werden. Das erlaubt Eigenschaften der natürlichen Sprache wie Abmachung und Verweisung und Programmiersprache-Analoga wie der richtige Gebrauch und die Definition von Bezeichnern, um auf eine natürliche Weise ausgedrückt zu werden. Z.B können wir jetzt leicht ausdrücken, dass in englischen Sätzen das Thema und Verb in der Zahl zustimmen müssen.

In der Informatik schließen Beispiele dieser Annäherung Affix-Grammatiken ein, schreiben Grammatiken, mit einem Inhaltsverzeichnis versehene Grammatiken und Van Wijngaarden Zwei-Niveaus-Grammatiken zu.

Ähnliche Erweiterungen bestehen in der Linguistik.

Eine andere Erweiterung soll zusätzlichen Endsymbolen erlauben, an der linken Seite von Regeln zu erscheinen, ihre Anwendung beschränkend. Das erzeugt den Formalismus von mit dem Zusammenhang empfindlichen Grammatiken.

Beschränkungen

Es gibt mehrere wichtige Unterklassen der Grammatiken ohne Zusammenhänge:

• LR (k) Grammatiken (auch bekannt als deterministische Grammatiken ohne Zusammenhänge) erlauben (Schnur-Anerkennung) mit deterministischen pushdown Automaten grammatisch zu analysieren, aber sie können nur deterministische Sprachen ohne Zusammenhänge beschreiben.
• Einfacher LR, Blick vorn LR Grammatiken sind Unterklassen, die weitere Vereinfachung der Syntaxanalyse erlauben.
• LL (k) und LL (*) erlauben Grammatiken, durch den direkten Aufbau einer leftmost Abstammung, wie beschrieben, oben grammatisch zu analysieren, und beschreiben sogar weniger Sprachen.
• Einfache Grammatiken sind eine Unterklasse des LL (1) für sein theoretisches Eigentum größtenteils interessante Grammatiken, dass die Sprachgleichheit von einfachen Grammatiken entscheidbar ist, während Spracheinschließung nicht ist.
• Eingeklammerte Grammatiken haben das Eigentum, dass die Endsymbole in linke und richtige Klammer-Paare geteilt werden, die immer in Regeln zusammenpassen.
• Geradlinige Grammatiken haben keine Regeln mit mehr als einem Nichtterminal in der rechten Seite.
• Regelmäßige Grammatiken sind eine Unterklasse der geradlinigen Grammatiken und beschreiben die regelmäßigen Sprachen, d. h. sie entsprechen begrenzten Automaten und regelmäßigen Ausdrücken.

LR Syntaxanalyse erweitert LL, der grammatisch analysiert, um eine größere Reihe von Grammatiken zu unterstützen; der Reihe nach erweitert verallgemeinerte LR-Syntaxanalyse LR, der grammatisch analysiert, um willkürliche Grammatiken ohne Zusammenhänge zu unterstützen. Auf LL Grammatiken und LR Grammatiken führt es im Wesentlichen LL-Syntaxanalyse und LR-Syntaxanalyse beziehungsweise durch, während auf nichtdeterministischen Grammatiken es so effizient ist, wie erwartet werden kann. Obwohl GLR-Syntaxanalyse in den 1980er Jahren entwickelt wurde, setzen viele neue Sprachdefinitionen und parser Generatoren fort, auf LL, LALR oder LR zu basieren, der bis dato grammatisch analysiert.

Sprachanwendungen

Chomsky hat am Anfang gehofft, die Beschränkungen von Grammatiken ohne Zusammenhänge zu überwinden, indem er Transformationsregeln hinzugefügt hat.

Solche Regeln sind ein anderes Standardgerät in der traditionellen Linguistik; z.B passivization in Englisch. Viel generative Grammatik ist der Entdeckung von Weisen gewidmet worden, die beschreibenden Mechanismen der Grammatik der Ausdruck-Struktur zu raffinieren, und Transformation herrscht solch, dass genau die Arten von Dingen ausgedrückt werden können, dass natürliche Sprache wirklich erlaubt. Das Erlauben willkürlicher Transformationen entspricht diese Absicht nicht: Sie sind viel zu stark, abgeschlossener Turing seiend, wenn bedeutende Beschränkungen nicht hinzugefügt werden (z.B keine Transformationen, die einführen und dann Symbole auf eine Mode ohne Zusammenhänge umschreiben).

Die allgemeine Position von Chomsky bezüglich des non-context-freeness der natürlichen Sprache hat sich seitdem gehalten, obwohl seine spezifischen Beispiele bezüglich der Unangemessenheit von Grammatiken ohne Zusammenhänge (CFGs) in Bezug auf ihre schwache generative Kapazität später widerlegt wurden.

Gerald Gazdar und Geoffrey Pullum haben behauptet, dass trotz einiger nicht Zusammenhang freie Aufbauten auf natürlicher Sprache (wie Quer-Serienabhängigkeiten in schweizerischem Deutsch und Verdoppelung in Bambara) die große Mehrheit von Formen auf natürlicher Sprache tatsächlich ohne Zusammenhänge ist.

Siehe auch

• Die Syntaxanalyse der Ausdruck-Grammatik
• Stochastische Grammatik ohne Zusammenhänge
• Algorithmen für die Grammatik-Generation ohne Zusammenhänge

Syntaxanalyse von Algorithmen

• CYK Algorithmus
• GLR parser
• Algorithmus von Earley

Referenzen

• . Kapitel 4: Grammatiken ohne Zusammenhänge, Seiten 77-106; Kapitel 6: Eigenschaften von Sprachen ohne Zusammenhänge, Seiten 125-137.
• . Kapitel 2: Grammatiken ohne Zusammenhänge, Seiten 91-122; Abschnitt 4.1.2: Entscheidbare Probleme bezüglich Sprachen ohne Zusammenhänge, Seiten 156-159; Abschnitt 5.1.1: Die Verminderungen über Berechnungsgeschichten: Seiten 176-183.