webentwicklung-frage-antwort-db.com.de

Sind GCC- und Clang-Parser wirklich handgeschrieben?

Es scheint, dass GCC und LLVM-Clang handgeschriebene rekursive Abstiegsparser verwenden und nicht maschinengeneriertes, Bison-Flex-basiertes Bottom-Up-Parsing.

Könnte hier jemand bitte bestätigen, dass dies der Fall ist? Und wenn ja, warum verwenden Mainstream-Compiler-Frameworks handschriftliche Parser?

Update : interessanter Blog zu diesem Thema hier

83
JCLL

Ja:

  • GCC verwendete einst einen Yacc (Bison) -Parser, der jedoch in der 3.x-Reihe irgendwann durch einen handgeschriebenen rekursiven Descent-Parser ersetzt wurde: siehe http://gcc.gnu.org/ wiki/New_C_Parser für Links zu relevanten Patch-Beiträgen.

  • Clang verwendet auch einen handgeschriebenen rekursiven Abstiegsparser: Weitere Informationen finden Sie im Abschnitt "Ein einziger einheitlicher Parser für C, Objective C, C++ und Objective C++" am Ende von http://clang.llvm.org/features). html .

72

Es gibt einen Folk-Satz, der besagt, dass C schwer zu analysieren ist und C++ im Wesentlichen unmöglich ist.

Es ist nicht wahr.

Was wahr ist, ist, dass C und C++ mit LALR (1) -Parsern ziemlich schwer zu analysieren sind, ohne die Parsing-Maschinerie zu hacken und sich in Symboltabellendaten zu verheddern. Tatsächlich hat GCC sie mit YACC und zusätzlichem Hackery wie diesem analysiert, und ja, es war hässlich. Jetzt verwendet GCC handgeschriebene Parser, aber immer noch mit dem Symboltabellen-Hackery. Die Clang-Leute haben nie versucht, automatische Parser-Generatoren zu verwenden. AFAIK, der Clang-Parser, ist seit jeher handcodierter rekursiver Abstieg.

Was stimmt, ist, dass C und C++ mit stärkeren automatisch generierten Parsern, z. B. GLR-Parser , relativ einfach zu analysieren sind und Sie keine Hacks benötigen. Der Elsa C++ - Parser ist ein Beispiel dafür. Unser C++ Frontend ist ein anderes (wie alle unsere "Compiler" Frontends ist GLR eine wunderbare Parsing-Technologie).

Unser C++ - Frontend ist nicht so schnell wie das von GCC und sicherlich langsamer als Elsa. Wir haben wenig Energie in die sorgfältige Optimierung gesteckt, da wir andere dringlichere Probleme haben (trotzdem wurde es in Millionen von Zeilen C++ - Code verwendet). Elsa ist wahrscheinlich langsamer als GCC, nur weil es allgemeiner ist. Angesichts der heutigen Prozessorgeschwindigkeit sind diese Unterschiede in der Praxis möglicherweise nicht von Bedeutung.

Aber die "echten Compiler", die heute weit verbreitet sind, haben ihre Wurzeln in Compilern von vor 10 oder 20 Jahren oder mehr. Ineffizienzen waren dann viel wichtiger, und niemand hatte von GLR-Parsern gehört, sodass die Leute taten, was sie zu tun wussten. Clang ist sicherlich jünger, aber dann behalten Volkssätze ihre "Überzeugungskraft" für eine lange Zeit.

Sie müssen es nicht mehr so ​​machen. Sie können GLR und andere solche Parser sehr vernünftigerweise als Frontends verwenden, was die Wartbarkeit des Compilers verbessert.

Was ist , ist, dass es schwierig ist, eine Grammatik zu finden, die dem Verhalten Ihres freundlichen Nachbarschafts-Compilers entspricht. Während praktisch alle C++ - Compiler (die meisten) des ursprünglichen Standards implementieren, haben sie auch viele dunkle Eckenerweiterungen, z. B. DLL Spezifikationen in MS-Compilern usw.) Sie können Ihre Zeit damit verbringen, zu versuchen, die endgültige Grammatik an die Realität anzupassen, anstatt zu versuchen, Ihre Grammatik an die Einschränkungen Ihres Parsergenerators anzupassen.

EDIT November 2012: Seit dem Schreiben dieser Antwort haben wir unser C++ - Front-End verbessert, um vollständige C++ 11-Versionen, einschließlich ANSI-, GNU- und MS-Variantendialekte, zu verarbeiten. Obwohl es viele zusätzliche Dinge gab, müssen wir unsere Parsing-Engine nicht ändern. Wir haben gerade die Grammatikregeln überarbeitet. Wir mussten die semantische Analyse ändern; C++ 11 ist semantisch sehr kompliziert, und diese Arbeit überfordert die Ausführung des Parsers.

BEARBEITEN Februar 2015: ... behandelt jetzt volles C++ 14. (Siehe lesbar machen AST aus c ++ für die GLR-Analyse eines einfachen Codebits und C++ 's berüchtigtste "ärgerlichste Analyse").

EDIT April 2017: Jetzt behandelt (Entwurf) C++ 17.

97
Ira Baxter

Der Parser von Clang ist ein handgeschriebener rekursiver Parser, ebenso wie einige andere Open-Source- und kommerzielle C- und C++ - Frontends.

Clang verwendet einen rekursiven Parser aus mehreren Gründen:

  • Leistung : Ein handgeschriebener Parser ermöglicht es uns, einen schnellen Parser zu schreiben, der die Hot-Paths nach Bedarf optimiert, und wir haben immer die Kontrolle über diese Leistung . Ein schneller Parser hat es Clang ermöglicht, in anderen Entwicklungstools verwendet zu werden, in denen "echte" Parser normalerweise nicht verwendet werden, z. B. Syntaxhervorhebung und Code-Vervollständigung in einer IDE.
  • Diagnose und Fehlerbehebung : Da Sie mit einem handgeschriebenen rekursiven Parser die volle Kontrolle haben, können Sie problemlos Sonderfälle hinzufügen, die häufige Probleme erkennen und bieten eine hervorragende Diagnose und Fehlerbehebung (siehe z. B. http://clang.llvm.org/features.html#expressivediags ) Bei automatisch generierten Parsern sind Sie auf die Funktionen des Generators beschränkt.
  • Einfachheit : Parser rekursiver Abstammung sind einfach zu schreiben, zu verstehen und zu debuggen. Sie müssen kein Parser-Experte sein oder ein neues Tool erlernen, um den Parser zu erweitern/verbessern (was besonders für ein Open-Source-Projekt wichtig ist), aber Sie können trotzdem großartige Ergebnisse erzielen.

Insgesamt spielt es für einen C++ - Compiler keine Rolle: Der Parsing-Teil von C++ ist nicht trivial, aber dennoch einer der einfacheren Teile. Es lohnt sich also, ihn einfach zu halten. Die semantische Analyse - insbesondere Namenssuche, Initialisierung, Überladungsauflösung und Template-Instanziierung - ist um Größenordnungen komplizierter als das Parsen. Wenn Sie einen Beweis benötigen, überprüfen Sie die Verteilung von Code und Commits in Clangs "Sema" -Komponente (für die semantische Analyse) im Vergleich zu ihrer "Parse" -Komponente (für die Analyse).

30
Doug

gccs Parser ist handgeschrieben. . Ich vermute dasselbe für Klirren. Dies hat wahrscheinlich einige Gründe:

  • Leistung : Etwas, das Sie für Ihre spezielle Aufgabe von Hand optimiert haben, ist fast immer leistungsfähiger als eine allgemeine Lösung. Abstraktion hat normalerweise einen Leistungseinbruch
  • Timing : Zumindest im Fall von GCC ist GCC älter als viele kostenlose Entwicklertools (erschien 1987). Zu dieser Zeit gab es keine kostenlose Version von yacc usw., von der ich mir vorstellen konnte, dass sie für die Menschen bei der FSF eine Priorität gewesen wäre.

Dies ist wahrscheinlich kein Fall von "hier nicht erfunden" -Syndrom, sondern eher im Sinne von "Es wurde nichts speziell für das, was wir brauchten, optimiert, also haben wir unser eigenes geschrieben".

8
Rafe Kettler

Seltsame Antworten da!

C/C++ - Grammatiken sind nicht kontextfrei. Sie sind aufgrund der Foo * -Leiste kontextsensitiv. Mehrdeutigkeit. Wir müssen eine Liste von typedefs erstellen, um zu wissen, ob Foo ein Typ ist oder nicht.

Ira Baxter: Ich verstehe den Sinn Ihrer GLR-Sache nicht. Warum einen Analysebaum bauen, der Mehrdeutigkeiten enthält? Analysieren bedeutet, Mehrdeutigkeiten zu lösen und den Syntaxbaum zu erstellen. Sie lösen diese Unklarheiten in einem zweiten Durchgang, sodass dies nicht weniger hässlich ist. Für mich ist es viel hässlicher ...

Yacc ist ein LR (1) -Parser-Generator (oder LALR (1)), kann jedoch leicht so geändert werden, dass er kontextsensitiv ist. Und da ist nichts Hässliches drin. Yacc/Bison wurde entwickelt, um das Parsen der C-Sprache zu erleichtern. Daher ist es wahrscheinlich nicht das hässlichste Tool, um einen C-Parser zu generieren ...

Bis GCC 3.x wird der C-Parser von yacc/bison generiert, wobei die typedefs-Tabelle während des Parsens erstellt wird. Mit "in parse" typedefs table building wird die C-Grammatik lokal kontextfrei und außerdem "local LR (1)".

In Gcc 4.x ist es ein rekursiver Abstiegsparser. Es ist genau der gleiche Parser wie in Gcc 3.x, es ist immer noch LR (1) und es gelten die gleichen Grammatikregeln. Der Unterschied besteht darin, dass der yacc-Parser von Hand neu geschrieben wurde, die Verschiebung/Reduzierung nun im Aufrufstapel verborgen ist und es kein "state454: if (nextsym == '(') goto state398" wie in gcc 3.x yaccs gibt Parser, so dass es einfacher ist, Fehler zu patchen, zu behandeln und schönere Nachrichten auszudrucken, und einige der nächsten Kompilierungsschritte während des Parsens durchzuführen.

Warum sind sie von yacc zu rekursiver Abstammung gewechselt? Weil es durchaus notwendig ist, yacc zu vermeiden, um C++ zu analysieren, und weil GCC davon träumt, mehrsprachiger Compiler zu sein, d. Aus diesem Grund werden der C++ - und der C-Parser auf dieselbe Weise geschrieben.

C++ ist schwieriger zu analysieren als C, da es nicht "lokal" LR (1) wie C ist, sondern nicht einmal LR (k). Ansehen func<4 > 2>, bei der es sich um eine mit 4> 2 instanziierte Schablonenfunktion handelt, d. h. func<4 > 2> muss gelesen werden als func<1>. Dies ist definitiv nicht LR (1). Nun überlege, func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>. Hier kann ein rekursiver Abstieg Mehrdeutigkeiten leicht lösen, und zwar zum Preis einiger weiterer Funktionsaufrufe (parse_template_parameter ist die mehrdeutige Parserfunktion. Wenn parse_template_parameter (17tokens) fehlgeschlagen ist, versuchen Sie es erneut mit parse_template_parameter (15tokens), parse_template_parameter (13tokens) ... bis Es klappt).

Ich weiß nicht, warum es nicht möglich ist, rekursive Untergrammatiken in yacc/bison einzufügen. Vielleicht ist dies der nächste Schritt in der Entwicklung von gcc/GNU-Parsern?

6
reuns