Warum sind mehrdeutige Grammatiken schlecht?

30

Ich verstehe, dass wenn es 2 oder mehr linke oder rechte Ableitungsbäume gibt, die Grammatik mehrdeutig ist, aber ich kann nicht verstehen, warum es so schlimm ist, dass jeder es loswerden will.

HIRAK MONDAL
quelle
1
Verwandte, aber nicht identisch: softwareengineering.stackexchange.com/q/343872/206652 (Haftungsausschluss: Ich habe die akzeptierte Antwort geschrieben)
marstato
Siehe auch: " Eine eindeutige Grammatik finden ".
Rob
1
In der Tat sind eindeutige Formulare für den praktischen Gebrauch besser, eindeutige Formulare verwenden weniger Produktionsregeln und bilden einen kleineren Baum in hoher Auflösung (daher benötigt der effiziente Compiler weniger Zeit zum Parsen). Die meisten Tools bieten die Möglichkeit, Mehrdeutigkeiten explizit außerhalb der Seitengrammatik aufzulösen.
Grijesh Chauhan
3
"Jeder will es loswerden". Nun, das stimmt einfach nicht. In kommerziell relevanten Sprachen kommt es häufig zu Mehrdeutigkeiten, wenn sich die Sprachen weiterentwickeln. ZB C ++ hat 2011 absichtlich die Mehrdeutigkeit hinzugefügt std::vector<std::vector<int>>, die früher ein Leerzeichen zwischen sich benötigt >>hat. Die wichtigste Erkenntnis ist, dass diese Sprachen viel mehr Benutzer als Anbieter haben. Die Behebung einer geringfügigen Störung für die Benutzer rechtfertigt daher eine Menge Arbeit für die Implementierer.
MSalters

Antworten:

52

Betrachten Sie die folgende Grammatik für arithmetische Ausdrücke: Betrachten Sie den folgenden Ausdruck: Was ist ihr Wert? Hier sind zwei mögliche Analysebäume:

XX+XXXXXX/Xvarconst
abc

(X - X) - X Bildbeschreibung hier eingeben

Nach der einen links sollten wir als interpretieren, was die übliche Interpretation ist. Nach dem einen auf der rechten Seite sollten wir es als interpretieren , was wahrscheinlich nicht das ist, was beabsichtigt war.abc(ab)ca(bc)=ab+c

Beim Kompilieren eines Programms soll die Interpretation der Syntax eindeutig sein. Der einfachste Weg, dies durchzusetzen, ist die Verwendung einer eindeutigen Grammatik. Wenn die Grammatik nicht eindeutig ist, können wir Regeln bereitstellen, nach denen die Operatoren Vorrang haben und die Assoziativität. Diese Regeln können äquivalent ausgedrückt werden, indem die Grammatik auf eine bestimmte Weise eindeutig gemacht wird.


Analysieren von Bäumen, die mit dem Syntaxbaumgenerator generiert wurden .

Yuval Filmus
quelle
12
@HIRAKMONDAL Die Tatsache, dass die Syntax nicht eindeutig ist, ist kein wirkliches Problem. Das Problem ist, dass die beiden unterschiedlichen Analysebäume ein unterschiedliches Verhalten aufweisen. Wenn Ihre Sprache eine mehrdeutige Grammatik hat, aber alle Analysebäume für einen Ausdruck semantisch äquivalent sind, ist dies kein Problem (z. B. nehmen Sie Yuval als Beispiel und betrachten Sie den Fall, in dem Sie den einzigen Operator haben +).
Bakuriu
14
@ Bakuriu Was du gesagt hast, ist wahr, aber "semantisch äquivalent" ist eine große Aufgabe. Beispielsweise ist Gleitkomma-Arithmetik tatsächlich nicht assoziativ (die beiden "+" - Bäume wären also nicht äquivalent). Selbst wenn die Antwort auf die gleiche Weise ausfiel, ist in Sprachen, in denen Ausdrücke Nebenwirkungen haben können, eine undefinierte Auswertungsreihenfolge von großer Bedeutung. Was Sie gesagt haben, ist technisch gesehen richtig, aber in der Praxis wäre es sehr ungewöhnlich, dass die Mehrdeutigkeit einer Grammatik keine Auswirkungen auf die Verwendung dieser Grammatik hat.
Richard Rast
Einige Sprachen suchen heutzutage nach Integer-Überläufen in Additionen, so dass auch a + b + c für Integer von der Reihenfolge der Auswertung abhängt.
gnasher729
3
Schlimmer noch, in einigen Fällen bietet die Grammatik keine Möglichkeit, die alternative Bedeutung zu erreichen. Ich habe dies in Abfragesprachen gesehen, in denen die Wahl der Escape-Grammatik (z. B. das Doppelte des Sonderzeichens zum Escape) bestimmte Abfragen nicht ausdrücken kann.
Hören Sie auf, Monica
12

Im Gegensatz zu den anderen vorhandenen Antworten [ 1 , 2 ] gibt es in der Tat ein Anwendungsgebiet, in dem mehrdeutige Grammatiken nützlich sind . Wenn Sie im Bereich der Verarbeitung natürlicher Sprache (NLP) die natürliche Sprache (NL) mit formalen Grammatiken analysieren möchten, haben Sie das Problem, dass NL auf verschiedenen Ebenen von Natur aus mehrdeutig ist [nach Koh18, Kap. 6.4]:

  • Syntaktische Mehrdeutigkeit:

    Peter verfolgte den Mann im roten Sportwagen

    War Peter oder der Mann im roten Sportwagen?

  • Semantische Mehrdeutigkeit:

    Peter ging zur Bank

    Eine Bank, auf der man sitzen kann oder eine Bank, bei der man Geld abheben kann?

  • Pragmatische Ambiguität:

    Zwei Männer trugen zwei Taschen

    Haben sie die Taschen zusammen getragen oder hat jeder zwei Taschen getragen?

Unterschiedliche Ansätze für NLP behandeln die Verarbeitung im Allgemeinen und insbesondere diese Unklarheiten unterschiedlich. Beispielsweise könnte Ihre Pipeline folgendermaßen aussehen:

  1. Analysiere NL mit mehrdeutiger Grammatik
  2. Für jede resultierende AST: Modellgenerierung ausführen, um mehrdeutige semantische Bedeutungen zu generieren und unmögliche syntaktische Mehrdeutigkeiten ab Schritt 1 auszuschließen
  3. Für jedes resultierende Modell: Speichern Sie es in Ihrem Cache.

Du machst diese Pipeline für jeden Satz. Je mehr Text beispielsweise aus demselben Buch stammt, das Sie bearbeiten, desto mehr können Sie unmöglich überflüssige Modelle, die bis zu Schritt 3 überlebt haben, aus vorherigen Sätzen ausschließen.

Im Gegensatz zur Programmiersprache können wir die Anforderung loslassen, dass jeder NL-Satz eine genaue Semantik hat. Stattdessen können wir beim Parsen größerer Texte einfach mehrere mögliche semantische Modelle verwalten. Spätere Erkenntnisse helfen uns von Zeit zu Zeit, frühere Unklarheiten auszuschließen.

Wenn Sie sich mit Parsern die Hände schmutzig machen möchten, die mehrere Ableitungen für mehrdeutige Grammatik ausgeben können, schauen Sie sich das Grammatical Framework an . Auch [Koh18, ch. 5] enthält eine Einführung, die etwas zeigt, das meiner obigen Pipeline ähnelt. Da es sich bei [Koh18] jedoch um Vorlesungsunterlagen handelt, sind diese möglicherweise ohne die Vorlesungen nicht so einfach zu verstehen.


Verweise

[Koh18]: Michael Kohlhase. "Logikbasierte Verarbeitung natürlicher Sprache. Wintersemester 2018/19. Vorlesungsskript." URL: https://kwarc.info/teaching/LBS/notes.pdf . URL natürlich Beschreibung: https://kwarc.info/courses/lbs/ (in deutscher Sprache)

[Koh18, ch. 5]: Siehe Kapitel 5, "Fragmente implementieren: Grammatische und logische Rahmenbedingungen", in [Koh18]

[Koh18, ch. 6.4] Siehe Kapitel 6.4, "Die rechnerische Rolle von Mehrdeutigkeiten", in [Koh18]

ComFreek
quelle
Vielen Dank .. Ich hatte den gleichen Zweifel und du
hast ihn
1
Ganz zu schweigen von Problemen mit Büffelbüffelbüffelbüffelbüffel ... für eine passende Anzahl von Büffeln
Hagen von Eitzen
Sie schreiben, "im Gegensatz", aber ich würde dies die andere Seite der Medaille nennen, von dem, was ich geantwortet habe. Das Parsen natürlicher Sprachen mit ihren mehrdeutigen Grammatiken ist so schwierig, dass traditionelle Parser es nicht können!
Davislor
1
@ComFreek Ich sollte hier genauer sein. Ein kurzer Blick auf GF (Danke für den Link!) Zeigt, dass es kontextfreie Grammatiken mit drei Erweiterungen liest (z. B. Reduplikation zulassen) und eine Liste aller möglichen Ableitungen zurückgibt. Algorithmen dafür gibt es seit den 50er Jahren. Die Fähigkeit, vollständig allgemeine CFGs zu verarbeiten, bedeutet jedoch, dass Ihre Worst-Case-Laufzeit in die Höhe geht. In der Praxis versuchen Softwareingenieure, auch bei Verwendung eines allgemeinen Parsers wie GLL eine Teilmenge von CFGs wie LL-Grammatiken zu verwenden, die dies können effizienter analysiert werden.
Davislor
1
@ComFreek Es ist also nicht so, dass Computer mit CFG nicht umgehen können (obwohl natürliche Sprachen nicht wirklich kontextfrei sind und bei der maschinellen Übersetzung ganz andere Techniken zum Einsatz kommen). Wenn Sie von Ihrem Parser verlangen, dass er mit Mehrdeutigkeiten umgeht, schließt dies bestimmte Verknüpfungen aus, die ihn effizienter gemacht hätten.
Davislor
10

Auch wenn es einen genau definierten Weg gibt, mit Mehrdeutigkeiten umzugehen (mehrdeutige Ausdrücke sind beispielsweise Syntaxfehler), verursachen diese Grammatiken dennoch Probleme. Sobald Sie Mehrdeutigkeiten in eine Grammatik einführen, kann ein Parser nicht mehr sicher sein, dass die erste Übereinstimmung endgültig ist. Es muss weiterhin alle anderen Methoden ausprobieren, um eine Aussage zu analysieren und Unklarheiten auszuschließen. Sie haben es auch nicht mit einer einfachen Sprache wie LL (1) zu tun, sodass Sie keinen einfachen, kleinen und schnellen Parser verwenden können. Ihre Grammatik enthält Symbole, die auf verschiedene Arten gelesen werden können. Sie müssen also darauf vorbereitet sein, viel zurückzuverfolgen.

In einigen eingeschränkten Domänen können Sie möglicherweise nicht nachweisen, dass alle möglichen Methoden zum Parsen eines Ausdrucks gleichwertig sind (z. B. weil sie eine assoziative Operation darstellen). (a + b) + c = a + (b + c).

Davislor
quelle
9

Does IF a THEN IF b THEN x ELSE yMittelwert

IF a THEN
    IF b THEN
        x
    ELSE
        y

oder

IF a THEN
    IF b THEN x
ELSE
    y

? AKA das sonst baumelnde Problem .

David Richerby
quelle
1
Das ist ein gutes Beispiel dafür, dass selbst eine nicht mehrdeutige Grammatik (wie in Java, C, C ++, ...) aus menschlicher Sicht offensichtliche (!) Mehrdeutigkeiten zulässt. Obwohl wir formal und rechnerisch in Ordnung sind, haben wir jetzt mehr ein UX / Bug-freies Entwicklungsproblem.
ComFreek
5

Nehmen wir zum Beispiel die ärgerlichste Analyse in C ++:

bar foo(foobar());

Handelt es sich um eine Funktionsdeklaration foovom Typ bar(foobar())(der Parameter ist ein Funktionszeiger, der ein zurückgibt foobar) oder um eine Variablendeklaration foovom Typ, die intmit einer Standardinitialisierung initialisiert wurde foobar?

Dies wird in Compilern durch die Annahme des ersten unterschieden, es sei denn, der Ausdruck in der Parameterliste kann nicht als Typ interpretiert werden.

Wenn Sie einen so mehrdeutigen Ausdruck erhalten, hat der Compiler 2 Optionen

  1. Nehmen Sie an, dass der Ausdruck eine bestimmte Ableitung ist, und fügen Sie der Grammatik einen Disambiguator hinzu, damit die andere Ableitung ausgedrückt werden kann.

  2. Fehler heraus und erfordern Disambiguierung in beiden Richtungen

Das erste kann natürlich herausfallen, das zweite erfordert, dass der Compiler-Programmierer die Mehrdeutigkeit kennt.

Bleibt diese Mehrdeutigkeit unentdeckt, können 2 verschiedene Compiler standardmäßig unterschiedliche Ableitungen für diesen mehrdeutigen Ausdruck verwenden. Dies führt dazu, dass Code aus nicht offensichtlichen Gründen nicht portierbar ist. Dies führt dazu, dass die Leute annehmen, dass es sich um einen Fehler in einem der Compiler handelt, während es sich tatsächlich um einen Fehler in der Sprachspezifikation handelt.

Ratschenfreak
quelle
5

Ich denke, die Frage enthält eine Annahme, die bestenfalls an der Grenze stimmt.

Im wirklichen Leben ist es ziemlich üblich, einfach mit mehrdeutigen Grammatiken zu leben, solange sie nicht (sozusagen) zu mehrdeutig sind.

Wenn Sie sich beispielsweise Grammatiken ansehen, die mit yacc kompiliert wurden (oder ähnlichen, wie Bison oder Byacc), werden Sie feststellen, dass einige Warnungen zu "N-Verschiebungs- / Reduzierungskonflikten" beim Kompilieren ausgegeben werden. Wenn yacc auf einen Verschiebungs- / Reduzierungskonflikt stößt, signalisiert dies eine Mehrdeutigkeit in der Grammatik.

Ein Verschiebungs- / Reduzierungskonflikt ist jedoch normalerweise ein eher geringes Problem. Der Parser-Generator wird den Konflikt zugunsten der "Verschiebung" und nicht der Reduzierung lösen. Die Grammatik ist vollkommen in Ordnung, wenn Sie das möchten (und es scheint in der Praxis vollkommen gut zu funktionieren).

Ein Verschiebungs- / Reduzierungskonflikt tritt normalerweise in einem Fall in dieser allgemeinen Reihenfolge auf (Verwendung von Großbuchstaben für Nicht-Terminals und Kleinbuchstaben für Terminals):

A -> B | c
B -> a | c

Wenn wir auf ein ctreffen, gibt es eine Mehrdeutigkeit: Sollen wir das cdirekt als ein Aanalysieren, oder sollten wir es als ein analysieren B, was wiederum ein ist A? In einem solchen Fall wählen yacc und solche die einfachere / kürzere Route und analysieren die Route cdirekt als eine A, anstatt die Route c-> B-> zu wählen A. Dies kann falsch sein, aber wenn ja, bedeutet dies wahrscheinlich, dass Sie einen wirklich einfachen Fehler in Ihrer Grammatik haben und Sie sollten die cOption überhaupt nicht als Möglichkeit zulassen A.

Im Gegensatz dazu könnten wir jetzt etwas ähnlicheres haben:

A -> B | C
B -> a | c
C -> b | c

Jetzt, wenn wir auf ein stoßen c, haben wir einen Konflikt, ob wir das cals ein Boder ein behandeln sollen C. Es ist viel unwahrscheinlicher, dass eine automatische Konfliktlösungsstrategie das wählt, was wir wirklich wollen. Keines von diesen ist eine "Verschiebung" - beide sind "Reduzierungen", so dass dies ein "Reduzieren / Reduzieren von Konflikten" ist (was diejenigen, die an Yacc gewöhnt sind, im Allgemeinen als ein viel größeres Problem als ein Verschieben / Reduzieren von Konflikten anerkennen).

Also, obwohl ich nicht sicher bin, ob ich so weit gehen würde zu sagen, dass jeder Zweideutigkeiten in seiner Grammatik wirklich begrüßt , ist es zumindest in einigen Fällen geringfügig genug, dass sich niemand wirklich sehr darum kümmert. In der Zusammenfassung mögen sie vielleicht die Idee, alle Mehrdeutigkeiten zu beseitigen - aber nicht genug, um es immer tatsächlich zu tun. Beispielsweise kann eine kleine, einfache Grammatik, die eine geringe Mehrdeutigkeit enthält, einer größeren, komplexeren Grammatik vorgezogen werden, die die Mehrdeutigkeit beseitigt (insbesondere, wenn Sie in den praktischen Bereich eintreten, aus der Grammatik tatsächlich einen Parser zu generieren, und feststellen, dass der Parser eindeutig ist) Grammatik erzeugt einen Parser, der nicht auf Ihrem Zielrechner läuft.

Jerry Sarg
quelle
Mann, ich wünschte, ich hätte diese hervorragende Erklärung für Schichtreduzierungskonflikte vor 5 Monaten gehabt! ^^; +1
HotelCalifornia