Warum sind mehrdeutige Grammatiken schlecht?

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.

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:

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.$a-b-c$$(a-b)-c$$a-(b-c) = a-b+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 .

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]

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

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 .

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.

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.