Was bedeutet "kontextfrei" im Begriff "kontextfreie Grammatik"?

Angesichts der Menge an Material, das versucht zu erklären, was eine kontextfreie Grammatik (CFG) ist, fand ich es überraschend, dass nur wenige (in meiner Stichprobe weniger als 1 von 20) eine Erklärung dafür geben, warum solche Grammatiken als "kontextfreie Grammatik" bezeichnet werden. kostenlos". Und meines Erachtens gelingt dies keinem.

Meine Frage ist, warum kontextfreie Grammatiken als kontextfrei bezeichnet werden. Was ist "der Kontext"? Ich hatte die Intuition, dass der Kontext andere Sprachkonstrukte sein könnten, die das derzeit analysierte Konstrukt umgeben, aber das scheint nicht der Fall zu sein. Kann mir jemand eine genaue Erklärung geben?

Es bedeutet, dass alle Produktionsregeln ein einziges Nicht-Terminal auf der linken Seite haben.

Zum Beispiel ist diese Grammatik, die Zeichenfolgen übereinstimmender Klammern ("()", "() ()", "()) ()", ...) erkennt, kontextfrei:

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

Die linke Seite jeder Regel besteht aus einem einzelnen Nicht-Terminal (in diesem Fall ist es immer so S, aber es könnte mehr geben.)

Betrachten Sie nun diese andere Grammatik, die Zeichenfolgen der Form {a ^ nb ^ nc ^ n: n> = 1} erkennt (z. B. "abc", "aabbcc", "aaabbbccc"):

S  → abc
S  → aSBc
cB → WB
WB → WX
WX → BX
BX → Bc
bB → bb

Wenn dem Nicht-Terminal Bdas Terminal- / Literal-Zeichen vorangestellt ist c, schreiben Sie diesen Begriff in um, WBaber wenn ihm vorangestellt ist b, erweitern Sie bbstattdessen auf. Darauf spielt vermutlich die Kontextsensitivität der kontextsensitiven Grammatik an.

Eine kontextfreie Sprache kann als Push-Down-Automat erkannt werden . Während eine Zustandsmaschine keinen Hilfsspeicher benötigt, dh ihre Entscheidung nur auf dem aktuellen Zustand und der Eingabe basiert, verfügt ein Push-Down-Automat auch über einen Stapel und kann zur Entscheidungsfindung ganz oben auf dem Stapel nachsehen.

Um dies in Aktion zu sehen, können Sie verschachtelte Klammern analysieren, indem Sie bei jeder Begegnung mit einer von links nach rechts gehen und eine linke Klammer auf einen Stapel schieben und bei jeder Begegnung mit einer rechten Klammer aufspringen. Wenn Sie nie versuchen, von einem leeren Stapel zu springen und der Stapel am Ende der Zeichenfolge leer ist, ist die Zeichenfolge gültig.

Für eine kontextsensitive Sprache reicht ein PDA nicht aus. Sie benötigen einen linear begrenzten Automaten wie eine Turing-Maschine, deren Band nicht unbegrenzt ist (obwohl die Menge des verfügbaren Bandes proportional zur Eingabe ist). Beachten Sie, dass dies Computer ziemlich gut beschreibt - wir stellen sie uns gerne als Turing-Maschinen vor, aber in der realen Welt können Sie nicht beliebig mehr RAM während des Programms abrufen. Wenn Ihnen nicht klar ist, wie leistungsfähiger ein LBA als ein PDA ist, kann ein LBA einen PDA emulieren, indem ein Teil seines Bands als Stapel verwendet wird. Sie können jedoch auch festlegen, dass das Band auf andere Weise verwendet wird.

(Wenn Sie sich fragen, was eine Finite-State-Maschine erkennen kann, sind reguläre Ausdrücke die Antwort. Aber nicht die regulären Ausdrücke für Steroide mit Capture-Gruppen und Look-behind / Look-ahead, die Sie in Programmiersprachen sehen. Ich meine die, die Sie erstellen können mit Operatoren wie [abc], |, *, +, und ?. Sie sehen , dass abbbzRegex passt ab*znur von der aktuellen Position in der Zeichenfolge und regex, keine Stapel erforderlich halten.)

Die anderen Antworten sind ziemlich lang, auch wenn sie genau und richtig sind. Dies ist die Kurzversion.

Wenn Sie eine Zeichenfolge (Terminals und Nichtterminals) haben und ein Nichtterminal in der Zeichenfolge ersetzen möchten, können Sie dies mit einer kontextfreien Grammatik unabhängig von den Zeichen tun, die das Nichtterminal umgeben.

Beachten Sie die folgenden Regeln (Kleinbuchstaben sind Terminals, Großbuchstaben sind Nichtterminals):

A -> a
AB -> a

In der ersten Regel können Sie eine ersetzen, A unabhängig davon, was um sie herum angezeigt wird (Kontext). In der zweiten Regel können Sie nicht ersetzen, es Asei denn, es wird gefolgt B. Während in diesem Fall beide Nichtterminals ersetzt werden, ist der wichtige Punkt, dass die Nichtterminals die AAngelegenheit umgeben. Man kann nicht ersetzen BAmit aoder Bmit a: nur Agefolgt von einem, Bweil die Reihenfolge, der Kontext der Nichtterminale wichtig ist. Dies bedeutet, dass der Kontext eines Nichtterminals in der zweiten Regel eine kontextsensitive Rolle spielt, während die erste Regel kontextfrei ist.

Um die Unterscheidung und die Terminologie besser zu verstehen, ist es eine gute Idee, eine kontextfreie Sprache wie a ⁿ b ⁿ mit einer kontextsensitiven Sprache wie a ⁿ b ⁿ c ^{n zu vergleichen} . (Notation: a, b und c sind Literale hier und der Exponent n bedeutet die wörtlichen Wiederholen n - mal, n > 0 ist , sagen.) Zum Beispiel, aabbcoder aabbbccsind nicht in der zweiten Sprache, wohingegen aabbccist.

Ein Akzeptor für die kontextfreie Sprache a ⁿ b ⁿ kann ein Paar zusammenziehen, aund zwar bunabhängig davon, was um ihn herum vorkommt (dh unabhängig davon, in welchem ​​Kontext ab vorkommt), und es funktioniert ordnungsgemäß, indem er nur Zeichenfolgen in der Sprache akzeptiert und alles andere ablehnt. dh die Grammatik ist S -> aSb | ab. Beachten Sie, dass sich auf der linken Seite der Produktion (en) keine Terminals befinden . (Es gibt zwei Produktionsregeln, aber wir schreiben sie nur kompakt.) Der Akzeptor kann im Grunde genommen eine lokale, kontextfreie Entscheidung treffen.

Im Gegensatz dazu können Sie so etwas für die kontextsensitive Sprache a ⁿ b ⁿ c ⁿ nicht tun , weil Sie sich für letztere irgendwie an den Kontext erinnern müssen, in dem Sie sich befanden, dh an wie viele Kontraktionen von ab Sie, um sie mit Kontraktionen abzugleichen von bc. Eine Grammatik für die letztere Sprache ist

S -> abc | aBSc
Ba -> aB
Bb -> bb

Beachten Sie, dass Sie in den letzten beiden Regeln links sowohl Terminals als auch Nicht-Terminals haben. Die Terminals auf der linken Seite sind der Kontext, in dem die Nicht-Terminals erweitert werden können.

Bootnote zu "Vertrag" vs. "Erweitern" -Terminologie etc .: Obwohl die formalen Grammatiken [formal, hah] generativ sind, ist die Art und Weise, wie sie in Parsern implementiert werden, tatsächlich reduktionistisch, dh Sie wenden sich grundsätzlich an einen Nicht-Terminal Anwenden der Regeln "in umgekehrter Reihenfolge", weshalb selbst die oben angegebene erste Grammatik in einem Programm nicht praktikabel ist (es würde Ihnen den berühmten Konflikt um die Schichtreduzierung bringen, weil Sie nicht entscheiden können, welche Regel angewendet werden soll), sondern die beiden oben genannten Grammatiken reichen aus, um die Unterscheidung zwischen kontextfrei und kontextsensitiv zu veranschaulichen. Das Problem der Mehrdeutigkeit in kontextfreien Grammatiken ist ziemlich kompliziert und nicht wirklich das Thema dieser Frage, so dass ich hier nicht mehr darauf eingehen werde, zumal sich herausstellt, dass Wikipedia einen anständigen Artikel dazu hat. Im Gegensatz dazu sind seine Artikel über kontextfreie und besonders die über kontextsensitive Sprache! @ # $ @! # $, Besonders wenn Sie neu in dem Thema sind ... Ich denke, das steht mehr auf meiner TODO-Liste.

Die obigen Antworten geben eine ziemlich gute Definition dessen, was es ist. Mal sehen, ob ich es in meine eigenen Worte fassen kann, so dass Sie statt 20 23 Erklärungen haben. Der ganze Zweck einer Grammatik, jeder Grammatik, besteht darin, herauszufinden, ob ein bestimmter Satz ein Satz in der gegebenen Sprache ist. Was wir jedoch wirklich mit Grammatik und Syntaxanalyse anfangen, ist herauszufinden, was der Satz bedeutet. Es ist wie das alte Diagramm eines Satzes, den Sie im Englischunterricht in der Schule gemacht haben oder nicht. Ein Satz besteht aus einem Subjektteil und einem Prädikatteil, ein Subjektteil hat ein Substantiv und möglicherweise einige Adjektive, ein Prädikatteil hat ein Verb und möglicherweise ein Objektnomen, mit einigen weiteren Adjektiven usw.

Wenn es eine Grammatik für Englisch gäbe (und das glaube ich nicht, nicht im Sinne der Informatik), gäbe es Regeln der folgenden Form, die als Produktionen bezeichnet werden.

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun

usw...

Sie könnten dann ein Programm schreiben und ihm einen beliebigen Satz geben, und das Programm könnte die Grammatik verwenden, um herauszufinden, welcher Teil des Satzes jedes Wort ist und welche Beziehung sie zueinander haben.

Wenn es in jeder Produktion nur eins auf der linken Seite gibt, bedeutet dies, dass Sie immer dann, wenn Sie die rechte Seite im Satz sehen, auf der linken Seite ersetzen dürfen. Wenn Sie zum Beispiel Adjektiv Nomen sahen, konnten Sie "That's a SubjectPart" sagen, ohne auf irgendetwas außerhalb dieser Phrase zu achten.

Englisch (auch die vereinfachte Beschreibung des Englischen, die ich oben gegeben habe) ist jedoch kontextsensitiv. "Adjektiv Nomen" ist nicht immer ein SubjectPart, es könnte eine Nomenphrase in einem PredicatePart sein. Es kommt auf den Kontext an. Lassen Sie uns unsere pseudo-englische Grammatik etwas erweitern:

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun
PredicatePart -> VerbPhrase ObjectNounPhrase
VerbPhrase ObjectNounPhrase -> VerbPhrase Adjective Noun

Sie können ein "Adjektiv-Nomen" nur dann in eine ObjectNounPhrase umwandeln, wenn es direkt nach einer VerbPhrase steht.

Grundsätzlich ist eine Produktion, die Sie jederzeit anwenden können, unabhängig von ihrer Umgebung, kontextfrei.

Sie können jederzeit leicht feststellen, ob eine Grammatik kontextfrei ist. Prüfen Sie einfach, ob sich links neben den Pfeilen mehr als ein Symbol befindet.

Jede Sprache kann durch mehr als eine Grammatik beschrieben werden. Wenn eine Grammatik für eine Sprache kontextfrei ist, ist die Sprache kontextfrei. Für einige Sprachen kann nachgewiesen werden, dass keine kontextfreie Grammatik möglich ist. Ich nehme an, es könnte eine kontextfreie Grammatik für die vereinfachte pseudo-englische Teilmenge geben, die ich oben beschreibe.

Um eine kontextfreie Grammatik zu analysieren, ist ein einfacheres Programm erforderlich. Wie in den anderen Antworten erwähnt, ist nicht die volle Leistung einer Turing-Maschine erforderlich, um eine kontextfreie Grammatik zu analysieren. Ein Lookahead LR (1) -Parser (eine Art Pushdown-Maschine) für eine bestimmte kontextfreie Grammatik kann jeden Satz in dieser Grammatik zeitlich und räumlich linear zur Satzlänge analysieren. Wenn der Satz in der Sprache vorliegt, erstellt der Parser einen Strukturbaum, der angibt, was jedes Symbol im Satz bedeutet (oder zumindest welche Rolle es in der Struktur spielt). Befindet sich der Satz nicht in der Grammatik, merkt der Parser, dass das erste Symbol nicht mit der Grammatik und den vorhergehenden Symbolen in Einklang zu bringen ist, und hört auf (beim ersten "Fehler").

Was noch besser ist, ist, dass es Programme gibt, mit denen Sie eine Beschreibung einer Grammatik und eine Liste von Anweisungen dazu geben können, was mit jedem Teil zu tun ist (in gewissem Sinne, indem jeder Produktion eine "Bedeutung" beigemessen wird), und dass das Programm den Parser schreibt für dich. Das Programm analysiert den Satz, findet die Struktur und führt Ihre Anweisungen für jeden Teil der Struktur aus. Diese Art von Programm wird Parser-Generator oder Compiler-Compiler genannt.

Diese Art der Sprachanalyse wurde für die automatische Analyse natürlicher Sprachen (wie Englisch) entwickelt. Es stellt sich jedoch heraus, dass dies für die Analyse von Computersprachen am nützlichsten ist. Ein Sprachdesigner kann eine Grammatik schreiben, die seine neue Sprache erfasst, und diese dann über den Parser-Generator ausführen, um ein Programm zu erhalten, das seine Sprache analysiert und übersetzt, interpretiert, kompiliert, ausführt usw., wenn er dies wünscht.

Tatsächlich kann man das in den meisten Fällen nicht wirklich tun. Beispielsweise sind ausgeglichene Klammern eine kontextfreie Sprache. Eine Sprache, in der alle Variablen deklariert werden müssen, bevor Sie sie verwenden, ist jedoch kontextsensitiv. Der Parser ist Teil des Compilers, es ist jedoch zusätzliche Logik erforderlich, um diese anderen Anforderungen durchzusetzen. Was Sie dann tun müssen, ist, eine Grammatik zu schreiben, die so viel wie möglich von Ihrer Sprache erfasst, diese durch einen Parser-Generator laufen zu lassen und dann Code zu schreiben, der den Rest der Anforderungen erzwingt (Symboltabellen-Handler usw.).

Wir verwenden im Allgemeinen keine kontextsensitiven Grammatiken, da diese viel schlechter unterstützt werden. Ich weiß nicht, ob es für kontextsensitive Sprachen ein Äquivalent zu einem LR (k) -Parser-Generator gibt. Ja, eine Turingmaschine (oder eine linear gebundene Maschine) kann eine analysieren, aber ich weiß nicht, ob es einen allgemeinen Algorithmus gibt, um eine kontextsensitive Grammatik in ein Programm für eine Turingmaschine in dem Sinne zu verwandeln, dass ein LR (1) ) Generator erstellt Analysetabellen für eine Pushdown-Maschine. Ich vermute, dass die Tabellen, die dem Parser zugrunde liegen, exponentiell größer wären. Auf jeden Fall wird CS-Schülern (wie mir selbst damals) normalerweise kontextfreie Grammatik und LR (1) -Parser-Generatoren wie YACC beigebracht.

Kontextfreie Grammatiken berücksichtigen keinen Kontext für Produktionsregeln. Kontext sind entweder Terminals oder Nicht-Terminals.

Also: Kontextfreie Grammatiken haben nur ein einzelnes Nicht-Terminal auf der linken Seite der Produktionsregeln.