C++ parsen



  • 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/



  • @phlox81
    Für welche Sprachen und aus welchen Grund hast du schon Parser geschrieben? Die Motivation anderer Leute die auch schonmal einen Parser geschrieben haben finde ich interessant :). Den Lexer an sich finde ich eigtl nicht unbedingt so schwer, das Problem liegt meiner Meinung nach in der Überprüfung der Semantik.

    @Th69
    Danke für die Informationen :). Vorallem den Thread bei gamedev finde ich interessant. Leider wurde es ja bisher noch nicht geschafft, einen C++-Parser an Hand von boost::spirit zu entwickeln. Wie auch in gamedev schon beschrieben steht, läuft es darauf hinaus, dass man es doch selbst entwickeln muss.

    Edit:
    Ich habe mir nun folgendes Buch gegönnt. Ich hoffe mal, dass es sein Geld wert ist.
    http://www.amazon.de/Compiler-Prinzipien-Techniken-Pearson-Studium/dp/3827370973/ref=sr_1_1?ie=UTF8&qid=1295098835&sr=8-1



  • skNiNe schrieb:

    @phlox81
    Für welche Sprachen und aus welchen Grund hast du schon Parser geschrieben? Die Motivation anderer Leute die auch schonmal einen Parser geschrieben haben finde ich interessant :). Den Lexer an sich finde ich eigtl nicht unbedingt so schwer, das Problem liegt meiner Meinung nach in der Überprüfung der Semantik.

    Das ist immer die Frage was man machen will, ich habe mich eigentlich immer darauf beschränkt, nur Code zu generieren, und bedingt auch zu parsen (statt 10 Editboxen eine).
    Schwierig wirds natürlich wenn man auch den eigentlichen Logikcode parsen will, ansonsten kann man relativ einfach eine Regel bauen die den inhalt zwischen zwei {} in einen String schreibt.

    Ich habe 2 Parser für TTCN3 geschrieben, unter anderem dort auch die Aufrufe später überprüft. Und Parser für diverse andere Dinge.



  • wieviele jahre bist du denn bereit dafür zeit zu investieren? das ist fast ne lebensaufgabe



  • skNiNe schrieb:

    Leider wurde es ja bisher noch nicht geschafft, einen C++-Parser an Hand von boost::spirit zu entwickeln. Wie auch in gamedev schon beschrieben steht, läuft es darauf hinaus, dass man es doch selbst entwickeln muss.

    Es ist nicht so, dass es ganz von Hand einfacher wäre als mit Boost.Spirit. Aber vielleicht musst du zu einem mächtigeren Lexer-/Parserframework (z.B. Flex/Bison-Kombination) greifen.



  • Nexus schrieb:

    skNiNe schrieb:

    Leider wurde es ja bisher noch nicht geschafft, einen C++-Parser an Hand von boost::spirit zu entwickeln. Wie auch in gamedev schon beschrieben steht, läuft es darauf hinaus, dass man es doch selbst entwickeln muss.

    Es ist nicht so, dass es ganz von Hand einfacher wäre als mit Boost.Spirit. Aber vielleicht musst du zu einem mächtigeren Lexer-/Parserframework (z.B. Flex/Bison-Kombination) greifen.

    lol. Tschuldigung, aber spirit ist mächtig genug, und ich kann mir nicht vorstellen, was Flex/Bison besser als Spirit könnte.
    Evtl. interessant könnte hier der Quellcode von LLVM/clang sein, die haben ja einen kompletten Kompiler neu gebaut, also müssten sie auch einen Parser haben.
    Dieser ist zumindest Opensource, evtl. sogar unter einer BSD ähnlichen Lizenz (also nich GPL).


Anmelden zum Antworten