C++ parsen



  • Guten Abend,

    ich bin gerade dabei, zu planen, wie man einen C++-Parser umsetzen könnte (der Sinn und Zweck sei erstmal dahin gestellt :)). Da es wenig Sinn macht, C++ nach meinem Wissen zu parsen, halte ich mich selbstverständlich an den ISO-Standard. Dafür benutze ich folgendes Dokument:

    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf

    Ich hab schon eine Idee wie ich den lexikalischen Scanner umsetzen könnte / werde. Die eigentlichen Probleme hab ich damit, die ganzen möglichen Audrücke (Expressions, Statements, Declarations, Declarators, Classes usw.) zu parsen. Jedoch ist mir aufgefallen, dass am Ende des Dokuments im Kapitel "A Grammar summary" die exakte Definition wie etwas zu machen ist, schön zusammengefasst aufgelistet ist. Dabei bekam ich die Idee, ob es denn möglich ist (oder sogar empfohlen ist), die Beschreibung einfach 1 zu 1 umzusetzen.

    Beispiel:

    Im Kapitel A.4 Expressions steht ganz oben:

    primary-expression:
       literal
       this
       ( expression )
       id-expression
       lambda-expression
    

    Nun wäre es doch denkbar, im Parser eine Methode get_primary_expression bereit zu stellen, die wiederum die verschiedenen Möglichkeiten aufruft (bspw. get_literal usw.), bis es einen Treffer gab und somit die Art des Tokens ermittelt wurde. Ich habe bewusst das Präfix get_ anstatt is_ verwendet, da es mir direkt einen Token-Typ zurück liefern soll, falls es einen Treffer gab. Wenn es keine primary-expression ist, wird irgendein Kennzeichen zurückgegeben, welches besagt, dass es keinen Treffer gab. Wenn das Parsen auf diese Art und Weise möglich wäre, hätte ich dennoch ein Problem. Ich müsste auch andere Sachen (weiss nicht wie ich es beschreiben soll, evtl Semantik?) prüfen.

    Beispiel:

    Angenommen in der Definition wird beschrieben, dass ein primitiver Typ mit irgendwelchen Spezifizierern deklariert werden kann (bspw. "unsigned"). Jedoch gibt es für den Typ "bool" kein unsigned. Also solche Typ-spezifischen Sachen usw. Darunter zähle ich mal das validieren, ob der Rückgabetyp einer Funktion gleich dem lvalues ist. Jedoch kann ich aus dem ISO-Standard nicht erkennen, wo solche Fälle beschrieben sind.

    Ich wäre sehr dankbar für alle hilfreichen Beiträge :).

    Viele Grüße



  • Einen Parser für C++ zu schreiben ist alles andere als ein Kinderspiel. Man sieht das auch bei aktuellen Compilern, die Leerzeichen bei Templates erzwingen, um diese als solche überhaupt erkennen zu können. Überhaupt sind diese Compiler über Jahrzehnte entstanden - und das nicht als Ein-Mann-Projekt.

    Wenn du neben der Prüfung der Syntax dann auch noch die Semantik, etc. überprüfen willst, du also im Prinzip schon (fast) einen ganzen Compiler programmierst, dann ist das einfach nur sinnlos. Du wirst damit in absehbarer Zeit nicht fertig werden.

    Ansonsten gibt es zum Thema Compilerbau im Artikelbereich 2 Artikel:
    http://www.c-plusplus.net/forum/268247
    http://www.c-plusplus.net/forum/201764

    Ich würde dir nicht gänzlich von deinem Vorhaben abraten. Es macht ja auch sehr viel Spaß und ist wahnsinnig interessant. Du solltest aber nicht versuchen die gesamten Sprachfeatures, etc. zu implementieren, sondern nur einen ganz kleinen Bruchteil.



  • Der Hintergrund der ganzen Geschichte ist, dass ich eine Art Live-Parser (um in einer IDE eine gute Code-Completion + Refactoring für C++ bereitzustellen) erstellen möchte. Ich bin der Meinung, dass es nach wie vor keine solche Funktionalität gibt, die wirklich gut funktioniert. Wer schonmal Java mit eclipse programmiert hat, weiss was ich unter "gut funktionieren" verstehe.

    - IntelliSense ist komplett fürn Po. Sogar mit Visual Assist X ist es nicht unbedingt das Gelbe vom Ei.
    - C++ mit eclipse (CDT) funktioniert die Code-Completion bzw. Fehler-Anzeige immer erst nach der Kompilierung (wahrscheinlich weil er die Fehler aus dem Compiler Output parsed).
    - KDevelop4 finde ich ganz schick, der Nachteil an der ganzen Geschichte ist, dass es diese IDE nur für Linux gibt, bzw. im Moment noch "nur brauchbar für Linux"

    Des Weiteren finde ich das Thema wirklich sehr interessant. Ich bin jemand, der sich nicht unbedingt zufrieden gibt, einfach alles hin zu nehmen wie es ist, sondern viele Dinge die mich interessieren zu hinterfragen und zu verstehen. Ich weiss, dass das parsen von C++ ein harter Brocken ist, aber ich versteh nicht unbedingt warum. Sicher ist es schwer wenn man sich die ewig lange Definition aus dem ISO-Standard anschaut, aber wenn man sich doch direkt an die dort definierten Regeln hält, sollte es doch eigentlich möglich sein einen standardkonformen C++ Parser zu erstellen oder?



  • - IntelliSense ist komplett fürn Po. Sogar mit Visual Assist X ist es nicht unbedingt das Gelbe vom Ei.

    Schonmal VS 2010 ausprobiert?



  • Ja auch. In Visual Studio ist es meiner Meinung nach generell so, dass sich das Fenster der Code-Completion sogar manchmal erst gar nicht öffnet.



  • Nun du hast mit deine Beobachtung total recht und bewunder dein Mut dich mit so eine komplex Sprache dein Parser zu bauen, aber du solltest davon abgehen und Erfahrung mit einfache Sprache oder -stücken und mit den verwendeten Algorithmen sammeln. Das Problem mit der Spezifikation ist, dass sie je nach Paseralgorithmen nicht entscheidbar ist, weil sie für Menschen geschrieben ist.



  • Du musst die Sprache C++ in ihrer gesamten Einheit sehen. Bevor überhaupt etwas passiert, muss natürlich der Präprozessor ran, welcher die Dateien inkludiert und sich um die Makros, usw. kümmert.

    Wenn das geschehen ist, dann hat man den Code, welcher geparst werden kann. Betrachtet man die Syntax-Ebene erkennt man sofort, dass C++ schon mal nicht kontextfrei ist. Der Parser muss also an vielen Stellen entscheiden, ob es sich z.B. um ein Funktionsaufruf oder eine Zuweisung handelt. Von diesen Mehrdeutigkeiten gibt es in C++ sehr sehr sehr viele.

    Um diese Mehrdeutigkeiten aber aufzulösen benötigt der Parser sehr viele Informationen. Zum Beispiel Variablentyp, usw. Aber auch das reicht nicht, denn die Variable könnte ja an dieser Stelle auch in einen anderen Typ gecastet werden. Auch solche Dinge müssen beachtet werden.

    Und auch bei einem Funktionsaufruf muss die korrekte Funktion (Überladungen) aufgerufen werden. Und dann kommen noch die Templates dazu. Die Klassen mit ihrer Polymorphie und allen möglichen anderen Zeugs.

    Die Sprache macht also zunächst einen sehr einfachen Eindruck, aber umso weiter man denkt, umso schneller stellt man fest, dass man sich plötzlich in einem riesigen Dschungel befindet. Es gibt so viele Sonderfälle und Ausnahmen oder auch lückenhafte Standardisierungen. Da muss man sich dann als Entwickler eines Compilers auch noch Gedanken machen, wie sich der Compiler in diesem Fall am sinnvollsten verhalten soll, da der Standard nur eine oberflächliche Beschreibung gibt.

    Tja, und dann gibt es noch den Faktor Zeit. Und das gleich auf zwei Seiten. Einerseits muss man selber erst mal einen funktionsfähigen Parser geschrieben haben - das kostet ganz sicher viel Zeit. Andererseits muss dieser Parser auch sehr schnell viel Code verarbeiten können. Denken wir an den Anfang zurück, dann wird klar, dass durch die vielen Includes sehr viel Code anfällt. Das muss alles geparst werden bzw. muss man sich sehr viele Gedanken machen, wie man das optimieren kann.

    Vielleicht wird einem dann auch klar, warum aktuelle "Live-Parser" nicht die besten Ergebnisse bieten. Sie müssen einfach irgendwo Abstriche machen, damit sie dem Benutzer auch genau dann unterstützen können, wenn er es gerade braucht und nicht erst nach Minuten an Rechenzeit und wenn der Code schon wieder ganz anders aussieht.



  • Erstmal danke für die Antworten bisher :).

    Ich habe mich ja schon etwas damit befasst. Im Kapitel "2.2 Phases of translation" wird auch beschrieben, was vorher geschehen muss um erstmal zum eigentlichen parsen des Codes zu kommen. Ich bin mir sicher, dass es diverse Möglichkeiten gibt, die Ausführungs- bzw. Parsezeit zu verkürzen. Bspw. könnte man (bzw. sollte man grundsätzlich) Header-Dateien aus verwendeten Bibliotheken nur einmal vorher parsen (Standard-Lib, boost etc.). So dass nur die Dateien analysiert werden, die auch aktiv verändert werden. Des Weiteren hatte ich schon einmal das Vergnügen etwas in der Richtung eines Parsers zu erstellen (spricht mich irgendwie an :)) ... natürlich nicht in einem solchen Umfang. Mir ist dabei aufgefallen, dass die Rechner mittlerweile doch sehr schnell sind, so konnte ich auch lange Dateien in einer Ausführungszeit (laut GetTickCounts) von 0 - 16 ms parsen (inkl. Datei öffnen und die ganzen Spielerein drum herum). Zusätzlich könnte man sich auch diverse Algorithmen überlegen, um nur Code teilweise zu parsen. Also die komplette Source einmal und danach nur noch wenn bestimmte Events auftreten (Programmierer beendet eine Anweisung oder sowas). Was am sinnvollsten ist, müsste man sich eben zu einem späteren Zeitpunkt noch genauer überlegen.

    Naja ich werde mich mal weiterhin damit beschäftigen und C++-Code weiter analysieren um ein besseres Verständnis für die inneren Vorgänge aus der Sicht des Parsers zu bekommen. Natürlich würde ich mich über weitere Beiträge freuen :).



  • skNiNe schrieb:

    Ja auch. In Visual Studio ist es meiner Meinung nach generell so, dass sich das Fenster der Code-Completion sogar manchmal erst gar nicht öffnet.

    Die betonung liegt auf 2010 da wurde nämlich genau der teil komplett neugeschrieben und ich muss sagen, ich kann mich nicht beschweren. Die intelli sense kennt so ziemlich alles und das auch korrekt. Zugegeben, ganz an java oder c# kommt sie noch nicht ran, aber sehr nah.



  • Wenn dir die Code-Completion von KDevelop so gut gefällt, dann bau dir diesen Teil aus und verbessere ihn. Selber schreiben würde ich mir nicht zutrauen, ausser du hast etwas Erfahrung im Compilerbau und das scheint ja nicht der Fall zu sein.



  • Ich hab tatsächlich keine Erfahrung im Compilerbau. Aber ohne einen Anfang zu machen kommt man sicherlich auch nicht weiter. Ein Parser für eine Sprache wie C++ ist zwar kein guter Einstieg, aber es ist das, was ich brauche bzw. machen möchte. Ich werde mich hier ab und zu mal melden und euch über den aktuellen Stand informieren. Evtl. hat ja der ein oder andere interesse daran.



  • Ein Parser für eine Sprache wie C++ ist zwar kein guter Einstieg, aber es ist das, was ich brauche bzw. machen möchte.

    Du hoerst dich wie so ein Kiddi an, dass das naechste WoW oder Crysis entwickeln will aber vom Programmieren keinen Schimmer hat. Dann wird diesem Kiddi geraten doch erstmal Programmieren zu lernen, TicTacToe zu programmieren dann Tetris, Pong oder Packman. Als naechster Schritt waere dann ein Mehrspielermodus in den 4 Spielen oder gar sie netzwerkfaehig zu machen.

    Einsicht bei solchen ist selten zu finden. Du verwendest zwar Worte der Beschwichtigung aber im Endeffekt steht da nur: Ich will, ich will, ich will ...



  • Und? Lass ihn doch! Die Erfahrung muss jeder mal machen.



  • Kiddie ist genauso unzutreffend wie nicht programmieren können. Es gibt zwar tatsächlich oft Threads, in denen irgendwelche Kiddies Spiele programmieren wollen und nach den ersten Anblick eines Codes dann doch lieber alles bleiben lassen. Jedoch muss ich dich hier enttäuschen, da es sich nicht um einen solchen Thread handelt.

    Ich sehe keinen Grund, warum ich mich nicht damit beschäftigen sollte. Jedenfalls bin ich kein Entwickler, der tagtäglich nur seine Verwaltungsprogramme auf der Arbeit schreibt, sondern sich auch mit anderen und evtl. interessanteren Themen beschäftigt.



  • Dich abhalten liegt mir fern, es sind nur gutgemeinte Ratschlaege. Leider hast du die Analogie nicht verstanden.

    Crysis -> C++ Compiler
    Nicht Programmieren koennen -> keine Ahnung von Compilerbau
    Beschaeftige dich mit den Grundlagen -> Fange nicht mit einem C++ Compiler an
    Kiddi -> ich will, ich will, ....



  • Warum beschäftigst du dich nicht zuerst mit einer einfacheren Sprache, z.B. einer Skriptsprache? Wenn du noch keine Erfahrung mit Code parsen hast, wäre das doch ein guter Einstieg. Interessant ist es genauso, und du musst dich nicht ins Terrain der C++-Spitzfindigkeiten und Fallunterscheidungen begeben, die sogar vielen Programmierern nicht bekannt sind. Alleine schon die ganze Überladungsauflösung ist ziemlich komplex. Von Templates wollen wir gar nicht erst anfangen...

    Jedenfalls wird eine Skriptsprache deine Frustration verhindern, wenn du merkst, dass dich mit dem funktionierenden C++-Parser doch etwas überschätzt hast.

    Und Autovervollständigungstools für C++ funktionieren nicht immer 100% zuverlässig, gerade weil C++ im Gegensatz zu Java oder C# wahnsinnig komplex zu parsen ist. Ich halte es für sehr unrealistisch, dass du daran einfach mal so etwas ändern kannst.



  • skNiNe schrieb:

    Ich hab tatsächlich keine Erfahrung im Compilerbau. Aber ohne einen Anfang zu machen kommt man sicherlich auch nicht weiter. Ein Parser für eine Sprache wie C++ ist zwar kein guter Einstieg, aber es ist das, was ich brauche bzw. machen möchte. Ich werde mich hier ab und zu mal melden und euch über den aktuellen Stand informieren. Evtl. hat ja der ein oder andere interesse daran.

    da c ein subset von c++ ist würd ich erstmal damit anfangen... die erste hürde an der ich mir die zähne ausgebissen hab ist das typsystem. da würde ich mir speziell gedanken machen. die templates würd ich für den anfang rauslassen. die sollten wenn alles steht "leicht" umzusetzen sein. zeig doch mal deinen tokenizer. das schonmal ein guter anfang.



  • Ich war eben dabei mir den ISO-Standard von C anzuschauen. Ich bin mir aber nicht sicher ob es sehr viel leichter sein wird. Natürlich fallen Themen wie Operatorüberladung, Templates, Klassen usw. weg, aber dennoch müsste man den größten Teil von C++ bzw. die vielen Überschneidungen abbilden. Mein lexikalischer Scanner existiert bisher nur auf Blättern. Laut den Definitionen im C und C++ (sind da ja beide diesbezüglich recht ähnlich) wird bzw. sollte das so auch umsetzbar sein.

    Edit:
    Ich kann mich zum parsen einer Skriptsprache irgendwie nicht motivieren. Es soll ein Parser für etwas sein, was ich aktiv verwende. Mein Sprachspektrum liegt in C, C++, C# und Java. Dazu muss man sagen, dass ich C# nur zwangsweise lernen musste (und mich nicht überzeugt hat). Des Weiteren gibt es für C# und Java schon gute Lösungen für das Problem, welches ich lösen wollte.



  • Ich würde dir mal einen Blick auf Boost::wave empfehlen, die haben nicht nur einen Präprozessor sondern auch einen C++ Lexer, damit konnte man schon mal einen C++ Parser durchaus in angriff nehmen, aber das ist ein sehr langfristiges Projekt, gerade wenn du auch noch C++0x unterstützen willst (was sinnvoll wäre).

    Ich habe selber schon parser für verschiedene Sprachen und für C++ schon Teilparser geschrieben (Funktions deklarationen z.b.).

    Für die Praxis, schau dir mal boost::spirit an, da gibts auch einen minimal C Parser afaik in den Beispielen.



  • Hallo skNiNe,

    gerade wenn du noch keine Erfahrung im Compilerbau hast, solltest du ein bestehendes Framework verwenden, z.B. boost::spirit.

    Dafür gibt es auch schon einige C++-Parser Implementierungen (wahrscheinlich nicht komplett vollständig, aber als ersten Anfang besser als ganz bei Null zu beginnen!):
    http://boost-spirit.com/repository/grammars/show_contents.php
    http://www.mailund.dk/index.php/2008/10/03/newick-c-parser-in-boostspirit/

    Viele Beispiele (dazu auch ein paar für den C++-Parser) gibt es unter http://boost-spirit.com/repository/applications/show_contents.php

    Und hier ein Kurzeinstieg zu Parser mit boost::spirit: http://www.highscore.de/cpp/boost/parser.html

    Außerdem habe ich noch einen Parser gefunden, der intern auf boost::spirit aufsetzt: http://www.sweetsoftware.co.nz/parser_overview.php

    Hier übrigens eine ähnliche Anfrage bzgl. eigenen C++-Parser: http://www.gamedev.net/topic/349261-c-parser-for-visual-assist----suggestions/


Log in to reply