Mehrdeutigkeitsauflösung beim Erstellen eines C++ Parsers

Question

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

Zum Beispiel: Konflikt shift-reduce auftritt, während "operator + < ......" Parsen, wenn ein weniger als angetroffen wird:

Wir analysieren kann es als:

(1)

Template-id -> Operator-function-id · < ......>

oder:

(2)

unqualifizierte-id -> Operator-function-id · wo (1) müssen Verschiebung aber (2) müssen reduziert werden.

jedoch der Standard hat:

Nach Namen lookup (3.4) feststellt, dass ein Name, ein Template-Name ist oder daß eine Bedienungsperson Funktions-ID oder eine literaloperator-ID bezieht sich auf eine Reihe von überladenen Funktionen Jedes Mitglied davon ist eine Funktionsvorlage. Wenn darauf eine < folgt, wird < immer als Trennzeichen für eine Template-Argumentliste und niemals als Kleiner-als-Operator genommen. Beim Analysieren einer Vorlagen-Argumentliste wird das erste nicht verschachtelte> 137 als Endtrennzeichen und nicht als Größer-als-Operator verwendet.

Also wir wählen zu verschieben.

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

1. Gibt es einen Teil in Standard, die „Verschiebung“ bezeichnet ist die Standardeinstellung, wenn Mehrdeutigkeit auftritt?

Deklarator

(1), wenn ein noptr-declarator analysiert wird und eine links paren angetroffen wird, sollte ich es verringern gemäß:

PTR-declarator -> noptr- declarator ·

oder verschieben, um die links paren zu erfüllen:

declarator -> noptr-declarator · Parameter-and-Qualifikations

Parameter-and-Qualifikationsspiele ->· links paren Parameter-Deklaration-Klausel rechts paren ......

(2), wenn eine declarator-ID analysiert wird und eine linke Klammer auftritt, soll ich reduzieren wird sie nach:

noptr-declarator -> declarator-id · noptr-declarator -> noptr-declarator · \ left-Halterung mit konstanter Ausdruck \ rechten Klammer Attribut-specifier-Seq

oder die linke Quadrat verschieben zu erfüllen:

?

noptr-declarator -> declarator-id · Attribut-specifier-Seq

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

Answer 1

Anknüpfend auf Tonyd Kommentar: Why can't C++ be parsed with a LR(1) parser?

Mancherorts Sie im Wesentlichen halten müssen, um den durch das Parsen erzeugt Zweideutigkeit, und löst es durch die Namensauflösung zu tun, oder äquivalent sehen, müssen Sie die Namensauflösung in den Parsing-Prozess verwickeln. 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 in Bezug auf Syntax als auch auf semantische 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.

Answer 2

C++ ist Turing Complete to parse.

Sehr relevant post here.