Wo wird die Kontextsensitivität im C++ Kompilierungsprozess aufgelöst?

Question

Gestern habe ich nach C++ Kontextsensitivität gefragt, siehe hier. Unter vielen ausgezeichneten Antworten ist hier die akzeptierte Antwort von dmckee.

Ich denke jedoch immer noch, dass dazu etwas gesagt werden kann (vielleicht einige terminologische Verwirrung?). Die Frage lautet: Mit welchem Teil der Kompilierung befasst sich die Mehrdeutigkeit?

Zur Klärung meiner Terminologie: Eine CFG ist eine Grammatik, die nur ein Nichtterminalsymbol auf der linken Seite der Regel hat (z.B. A->zC), eine CSG ist eine, die ein Terminal (plus ein Nichtterminal) auf der linken Seite hat (aAv->QT), wobei Großbuchstaben Nichtterminale und Kleinbuchstaben Terminale sind.

Gibt es eine Darstellung wie die letztere im Grammatik parsing von C++ Quellcode?

Vielen Dank und entschuldigen Sie die Hartnäckigkeit.

Answer 1

Es gibt keinen mir bekannten C++-Front-End (Parser, Namens- / Typauflöser), der einen kontextsensitiven Parser mit CSG-Grammatikregeln implementiert, wie du es definiert hast (einschließlich dem von uns erstellten). Praktisch alle von ihnen arbeiten explizit oder implizit mit einer kontextfreien Grammatik, die immer noch Ambiguitäten aufweist.

Viele von ihnen verwenden eine Kombination aus Top-Down-Analyse und verwobener Sammlung von Typinformationen, um zwischen den mehrdeutigen Fällen zu unterscheiden.

Das Verflechten von Parser und Typsammlung macht den Aufbau eines Parsers auf diese Weise wirklich unübersichtlich und schwierig und führt zum Sprichwort "C++ ist schwer zu parsen".

Wie bei vielen solchen "Sätzen" ist dies nicht wahr, es sei denn, du bestehst auch darauf, mit einer Hand auf dem Rücken zu parsen (z.B., rekursiver Abstieg, LL(k), LALR [z.B., YACC]). Wenn du eine Parsertechnologie verwendest, die mit Ambiguitäten umgehen kann, ist die C++-Grammatik tatsächlich nicht so schwer. Wir (und andere, wie z.B. der Elsa C++-Parser) verwenden aus diesem Grund die GLR-Parsertechnologie. (Wir gehen noch einen Schritt weiter und erfassen Makrodefinitionen, Verwendungen und Vorprozessorbedingungen in der C++-Grammatik, da wir daran interessiert sind, den Code zu transformieren, bevor der Prozessor ihn zerstört hat; normalerweise werden Vorprozessoranweisungen vollständig unabhängig in einem eigenen Vorprozessor behandelt).

Ich denke, Elsa vermischt immer noch die Ambiguitätsauflösung in den Parsvorgang, aber weil das Parsen so sauber ist, ist dies einfacher zu machen. Unser Front-End erstellt einen AST mit Ambiguitätsknoten, und nachdem der Baum aufgebaut ist, durchlaufen wir den Baum unter Verwendung eines Attributgrammatikauswerters, um Namen und Typen zu sammeln und die Zweige der Ambiguitäten zu eliminieren, die typinkonsistent sind. Letzteres ist ein wirklich schönes Schema und entkoppelt das Parsen und die Namensauflösung vollständig.

Was tatsächlich schwierig ist, ist die Namensauflösung. C++ hat ein recht kryptisches Schema zur Namenssuche, das sich über die 600 Seiten des Standards erstreckt und durch verschiedene Dialekte auf verschiedene Weise gebeugt wird. Die Trennung der Namensauflösung vom Parsen macht diese Hässlichkeit besser handhabbar, aber das Sprichwort sollte eigentlich "C++ ist schwer zu namensauflösen" lauten.

Answer 2

Zunächst gibt es den Unterschied zwischen Sprache und Grammatik. Eine Sprache ist eine Menge von Zeichenfolgen. Eine Grammatik ist eine Methode zur Beschreibung einer Menge von Zeichenfolgen (man sagt oft, dass eine Grammatik die Zeichenfolgen "generiert"). Eine bestimmte Sprache kann von mehreren Grammatiken beschrieben werden.

Die bekannteste Art von Grammatik sind die produktionsbasierten. Diese wurden von Chomsky in

• unbeschränkten Grammatiken, bei denen beliebige Elemente auf beiden Seiten der Produktionen stehen können

• monotonen Grammatiken, bei denen die linke Seite höchstens so lang ist wie die rechte Seite

• kontextsensitiven Grammatiken, bei denen nur ein Nichtterminal erweitert wird

• kontextfreien Grammatiken, bei denen die linke Seite der Produktionen nur aus einem Nichtterminal besteht

• regulären Grammatiken, bei denen die linke Seite der Produktionen nur aus einem Nichtterminal besteht und die rechte Seite der Produktion nur ein Nichtterminal als letztes Element haben darf

Monotone und kontextsensitive Grammatiken werden auch als Typ-1-Grammatiken bezeichnet. Sie sind in der Lage, dieselben Sprachen zu generieren. Sie sind weniger leistungsfähig als Typ-0-Grammatiken. Soweit ich weiß, obwohl ich Beweise gesehen habe, dass es Sprachen gibt, die eine Typ-0-Grammatik haben, aber keine Typ-1-Grammatik, kenne ich kein Beispiel.

Kontextsensitive Grammatiken werden als Typ-2-Grammatiken bezeichnet. Sie sind weniger leistungsfähig als Typ-1-Grammatiken. Das Standardbeispiel für eine Sprache, für die es keine Typ-2-Grammatik, aber eine Typ-1-Grammatik gibt, sind Zeichenfolgen, die aus jeweils gleicher Anzahl von a, b und c bestehen, wobei das a vor dem b und das b vor dem c steht.

Reguläre Grammatiken werden auch als Typ-3-Grammatiken bezeichnet. Sie sind weniger leistungsfähig als Typ-2-Grammatiken. Das Standardbeispiel für eine Sprache, für die es keine Typ-3-Grammatik, aber eine Typ-2-Grammatik gibt, sind Zeichenfolgen mit korrekt übereinstimmenden Klammern.

Die Ambiguität in Grammatiken liegt außerhalb dieser Hierarchie. Eine Grammatik ist mehrdeutig, wenn eine bestimmte Zeichenfolge auf verschiedene Weisen generiert werden kann. Es gibt eindeutige Typ-1-Grammatiken und mehrdeutige Typ-3-Grammatiken.

Dann gibt es andere Arten von Grammatiken, die nicht Teil der Chomsky-Klassifikation sind (zweistufige Grammatiken, attributbasierte Grammatiken, baumbasierte Grammatiken, ...), auch wenn sie auf Produktionen basieren. Einige davon sind sogar in der Lage, die Semantik von Programmiersprachen zu beschreiben.

Dann gibt es Parsing-Algorithmen. Diese basieren oft auf CFG und legen weitere Einschränkungen fest, um eine bessere Parsing-Geschwindigkeit zu erreichen (das Parsen eines CSG erfordert exponentielle Zeit, ein CFG erfordert kubische Zeit, gängige Algorithmen benötigen nur lineare Zeit). Diese Einschränkungen führen zu anderen Grammatikklassen.

CSG- und monotone Grammatiken sind tatsächlich von geringer Bedeutung für die Beschreibung oder Kompilierung einer Programmiersprache: Ihr Gesamtverhalten ist nicht offensichtlich und wird aus lokalen Eigenschaften synthetisiert, daher sind sie schwer zu verstehen und die Zuordnung von Semantik zu Produktionen ist problematisch, ihr Parsen ist teuer - im Allgemeinen exponentiell - und das Fehlermanagement ist schwierig. Die nicht-Chomsky-Grammatiken wurden eingeführt, um diese Probleme zu lösen.

Zurück zu C++. Der Standard beschreibt die C++-Sprache mit einer kontextfreien Grammatik, aber

• es gibt Mehrdeutigkeiten (zum Beispiel das berühmte "vexing parse"). Ein Compiler muss die Mehrdeutigkeiten erkennen und die richtige Interpretation verwenden (z.B. C x(); ist eine Funktionsdeklaration, nicht eine Objektdefinition).

• die Grammatik ist nicht LR(1) (eines der bekanntesten Teilgebiete von CFG, für das ein linearer Parsing-Algorithmus existiert). Andere Algorithmen (potenziell kostspieliger in Bezug auf Zeit oder Speicher) werden verwendet, entweder basierend auf einer allgemeineren Theorie oder durch Anpassung linearer Algorithmen an die C++-Regeln. Die Vereinfachung der Grammatik und die Ablehnung der inkorrekt akzeptierten Programme in der semantischen Analyse sind ebenfalls eine Möglichkeit.

• die Entsprechung zwischen Zeichenfolgen von Zeichen und Terminalen wird geändert (hauptsächlich durch Typ- und Vorlagen-Deklarationen, die Notwendigkeit, dies bei der Vorlagendefinition zu berücksichtigen, wurde mit der Verwendung von typename und template für abhängige Namen gelöst). Dies wird durch Abfrage der Symboltabelle in der Lexing-Phase gelöst, so dass eine bestimmte Zeichenfolge je nach Kontext ein Terminal oder ein anderes gibt.

• es gibt zusätzliche Einschränkungen (Notwendigkeit, einige Bezeichner zu deklarieren, Typüberprüfung, ...) die in einer mehr oder weniger formalen Variante der englischen Sprache beschrieben sind. Dies wird in der Regel als semantisch angesehen, auch wenn einige leistungsstärkere Grammatikbeschreibungen damit umgehen könnten.

Answer 3

Ira Baxter sagte: "Kein C++ Front-End (Parser, Namens-/Typauflöser), von dem ich weiß (einschließlich dem, das wir gebaut haben), implementiert einen kontextsensitiven Parser unter Verwendung von CSG-Grammatikregeln, wie Sie es definiert haben."

Es gibt eine kontextsensitive Grammatik mit der Meta-S-Distribution, die sich mit einer Reihe von C++-Parsing-Problemen "in der Grammatik" befasst, anstatt in irgendeiner anderen Phase des Parsens. Zum Beispiel - Vorwärtsmitgliedsdaten und Mitgliedsfunktionenreferenzen können in Inline-Mitgliedsfunktionen behandelt werden, während sie allein während der Parsenphase behandelt werden.

Traditionelle Parsen behandeln viele kontextsensitive Probleme während des Durchlaufs des abstrakten Syntaxbaums oder in anderen Phasen der Kompilierung.

Also ist meine Antwort: In "den meisten" Systemen wird Mehrdeutigkeit nach dem Parsen behandelt. In mindestens einem System wird ein Großteil davon direkt im Parsen behandelt. Daher ist die Antwort auf "Gibt es eine Darstellung wie letztere im Grammatikparsen von C++-Quellcode?" -

Ja. Zumindest in Meta-S ist eine Typ-0-CS-Analyse in der Grammatik möglich.

Answer 4

Ich würde wagen zu sagen, dass jedes kontextsensitive Problem bereits während der semantischen Analyse gelöst werden sollte.

Answer 5

Da sich niemand anderes meldet (und zugeben muss, dass ich sehr vage bin, was "echte" Compiler machen):

Die Mehrdeutigkeit einer Aussage wie

B = A();

wird durch Konsultation der Symboltabelle gelöst, um die Typen aller Nicht-Schlüsselwörter, Nicht-Operatoren in der Aussage (hier B und A) zu finden, und versucht, eine akzeptable Zuweisung aus ihnen zu bilden. Wenn keine solche Anordnung gefunden werden kann, wird ein Fehler ausgegeben.

Das wird vermutlich während der AST-Bildung früh im Parsenprozess durchgeführt, aber nach Abschluss des Lexens.