lalr

Ich habe einen LALR (1) Parser für C ++ 17 geschrieben. Ich fand 156 Ambiguitäten, einige von ihnen kann ich nach Standard lösen, aber die anderen kann ich nicht.

Zum Beispiel: Der Shift-Reduce-Konflikt tritt beim Parsen von " operator + & lt; ...... " auf, wenn ein kleiner als auftritt:

Wir können es wie folgt analysieren:

(1)

Vorlagen-ID - & gt; Operator-Funktions-ID · & lt; ...... & gt;

oder:

(2)

unqualifizierte ID - & gt; Operator-Funktions-ID · Wo (1) muss verschoben werden, (2) muss reduziert werden.

Allerdings hat der Standard:

Nach dem Namen-Lookup (3.4) wird festgestellt, dass ein Name ein Template-Name ist oder dass sich eine Operator-Function-ID oder eine Literaloperator-ID auf eine Menge überladener Funktionen bezieht, von denen jedes Mitglied eine Funktionsvorlage ist. Wenn darauf ein & lt; folgt, wird das & lt; wird immer als Trennzeichen einer Template-Argument-Liste und niemals als Kleiner-als-Operator genommen. Beim Analysieren einer Schablonen-Argumentliste wird das erste nicht verschachtelte & gt; 137 als Endbegrenzer anstelle eines Größer-als-Operators genommen.

Also entscheiden wir uns zu verschieben.

Leider gibt es viele Unklarheiten, die Auflösung kann ich nicht finden. Hier liste ich einige von ihnen auf (Einige von ihnen können eindeutig eine Wahl treffen, aber ich kann den Beweis nicht finden):

1. Gibt es einen Teil im Standard, der angibt, dass "Shifting" die Standardeinstellung ist, wenn Mehrdeutigkeiten auftreten?

Deklarator

(1) Wenn ein Noptr-Deklarator geparst wird und ein Linker-Paren gefunden wird, sollte ich ihn wie folgt reduzieren:

ptr-Deklarator - & gt; noptr-Deklarator ·

oder verschieben Sie den linken Teil nach:

Deklarator - & gt; noptr-deklarator · Parameter und Qualifier

Parameter und Qualifier - & gt; · linksparren Parameter-Deklarationsklausel rechts-paren ......

(2) Wenn eine Deklarator-ID analysiert wird und eine linke Klammer gefunden wird, sollte ich sie wie folgt reduzieren:

noptr-Deklarator - & gt; Deklarator-ID · noptr-Deklarator - & gt; noptr-deklarator · \ left-bracket? Konstantenausdruck \ right-bracket? attribut-specifier-seq

oder verschieben Sie das linke Quadrat nach:

noptr-Deklarator - & gt; deklarator-id · Attribut-Spezifizierer-seq

(Attribut-Spezifizierer-Seq ist [[.......]])

Im Anschluss an TonyDs Kommentar: Siehe Warum kann C ++ nicht mit einem LR (1) -Parser analysiert werden?

An einigen Stellen müssen Sie die Mehrdeutigkeit, die durch das Parsen entsteht, im Wesentlichen beibehalten und sie auflösen, indem Sie die Namensauflösung oder ausführen. Sie müssen die Namensauflösung in den Analyseprozess einbinden. In jedem Fall müssen Sie den Standard interpretieren, um zu bestimmen, wie die Mehrdeutigkeiten gelöst werden sollten, und ja, das ist eine sehr schwierige Aufgabe.

Dann erfahren Sie, was die Compiler wirklich tun ; sowohl GCC als auch MS haben viele Erweiterungen und Variationen vom Standard, sowohl hinsichtlich der Syntax als auch der semantischen Interpretationen (diese erzeugen Programme, die unterschiedliche Ergebnisse unter verschiedenen Compilern erzeugen). Schließlich können Sie herausfinden, was für Abscheulichkeiten in den System-Header-Dateien sind; Dies sind Hacks, die von den Compiler-Leuten hinzugefügt wurden, um ihr Leben bequemer zu machen, und sind, wenn überhaupt, sehr schlecht dokumentiert.