c++ parser in python

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
wasser
User
Beiträge: 2
Registriert: Mittwoch 11. Juni 2008, 15:59

Mittwoch 11. Juni 2008, 18:00

Hallo an alle,

ich suche nun seit einiger Zeit nach einem C++ Parser, der in Python geschrieben
ist oder via extending von Python aus benutzt werden kann.

Ich finde hier aber entweder Lösungen, die nur einen Bruchteil der Syntax von
C++ verstehen oder Vorschläge, wie man einen solchen Parser schreiben könnte.
Leider gibt es sehr viele Möglichkeiten, von denen jede eine intensive
Einarbeitung verlangt. Deswegen wollte ich hier mal fragen, was ihr für die
einfachste Lösung haltet und ob es vielleicht noch ganz andere Varianten gibt.

1. Grammatik Tools
  • ANTLR
    hierfür gibt es schon eine C++ Grammatik, die allerdings C++ Code erzeugt.
    Ich weiß nicht, wie groß der Aufwand ist diese umzuschreiben.

    pyparsing
    scheint ein nettes Modul zu sein, aber noch keine C++ Grammatik zu finden?
    Eine vollständige C++ Grammatik zu schreiben erscheint mir ein wenig aussichtslos :?
2. Vorhandenen C++ Parser in Python einbinden
2.1 nette C++ parser 2.2 Python Binding Tools
  • Pyrex/SWIG
    Wenn ich es richtig verstehe muss man mit für alle c++ Header einen Wrapper Header schreiben.
    Aufwand schätze ich sehr hoch ein.

    Boost.Python + Py++
    mit Py++ kann man sich diese Wrapper Header erstellen lassen, klingt einfach!
    • python-ogre(source via svn) benutzt inzwischen wieder Boost mit Py++.
      Wenn man in den code schaut (/code_generators/...)
      sieht es aber alles andere als einfach aus.

      Habe für OpenC++ das mal versucht. Mir ist nicht ganz klar welchen Header ich
      durch Py++ jagen muss (einen? alle? selbst erstellen?) und wie man aus dem
      Ergebnis dann eine von diesen shared libraries bekomme, die man in python
      importieren kann.
3. xml output parsen
  • GCCXML
    gccxml ist ein guter Ansatz. Es druckt die interne Repräsentation aus,
    die GCC beim compilieren erstellt. D.h. die gesamte C++ Syntax wird erkannt.
    Leider werden bei der Ausgabe keine function bodies ausgegeben,
    nur Funktions und Klassen Deklarationen(?).
    Tragisch, weil es mit pygccxml schon ein Python Binding gibt.
    Eine Erweiterung hierfür wurde schon von djlauk.de geschrieben (thread,download),
    habe diese aber nicht zum Laufen bekommen.

    Elkhound/Elsa
    mit Elsa kann man c++ Dateien parsen und den "Abstract Syntax Tree" als xml ausgeben.
    Man könnte mit diesen Dateien weiterarbeiten, dann bleibt Parsen und interne
    Repräsentation als Aufgabe.
    Leider sieht die xml Ausgabe ein wenig wirr aus, Ausschnitt:

    Code: Alles auswählen

        <declarator _id="AST0x83083c0" decl="AST0x83082d8" var="TY0x8313588" type="TY0x8313740" context="1">
         <d_func _id="AST0x83082d8" loc="main.c:1:5" base="AST0x8308260" params="FL0x83082c0" cv="0" ismember="false">
          <d_name _id="AST0x8308260" loc="main.c:1:5" name="AST0x8308248">
           <pq_name _id="AST0x8308248" loc="main.c:1:5" name="main">
           </pq_name>
          </d_name>
          <list_d_func_params _id="FL0x83082c0">
           <_List_Item item="AST0x83082c0">
           <asttypeid _id="AST0x83082c0" spec="AST0x8308270" decl="AST0x8308298">
    
Für Ergänzungen, Korrektur und Hinweise, welches der beste/bequemste Weg ist, bin ich sehr dankbar!
btw. das Zielsystem ist Linux (ubuntu).
Grüße W.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Samstag 14. Juni 2008, 11:30

Zum Aufwand für das Einbinden existierender Parser kann ich nichts sagen. PyParsing scheint mir als PEG für eine als LL(k) vorliegende Grammatik möglich, allerdings mag ich die Namensgebung des Autors nicht sonderlich und würde es selbst bauen. Ein naiver Ansatz ohne Memoization ist allerdings nicht sonderlich effizient. Ich hatte neulich nochmal einen anderen PEG für Python entdeckt, finde den aber gerade nicht wieder. PyPy enthält auch einen PEG parser, AFAIK. Allgemein ist kein Mangel an Parsergeneratoren für Python.

Die vorhandene ANTLR-Grammatik sieht in der Tat sehr komplex und mit extrem viel C++-Code gespickt aus. Warum ist das so? Wenn ich mir diese Grammatik anschaue, ist das doch nicht so wild. Oder sind es die "Disambiguation rules", die das so kompliziert machen?

Ich habe C++ immer gemieden, daher kenne ich mich mit den Feinheiten der Grammatik nicht so aus, unterschätze vielleicht den Aufwand, wenn ich vermute, dass die erwähnte Grammatik doch in wenigen Tagen umgesetzt werden könnte, sodass ein AST für die Sprache erzeugt wird.

Mein Präferenz wäre dabei ein PEG. LALR-Parsergeneratoren mit ihren shift-reduce-Konflikten finde ich nervig, auch wenn ich linksrekursive Grammatiken "natürlicher" finde als ihre rechtsrekursiven bzw. iterativen Vettern. EBNF-basierte LL(1)-Generatoren wie Coco/R werden zu einfach sein, ANTLR mit LL(*) ist wohl besser, aber irgendwie auch wuchtig und umständlich. Recht nett sieht Treetop aus, ist aber Ruby. Es gibt übrigens laut Wikipedia ein Paper, wie man Linksrekursion mit PEGs realisieren kann.

Stefan
lunar

Samstag 14. Juni 2008, 11:57

Die Komplexität von C++ rührt daher, dass C++ nicht kontextfrei zu formulieren ist. Damit der Parser ein bestimmtes Codestück korrekt parsen kann, muss er wissen, was einzelne Namen bedeuten. Man kommt also unweigerlich zu einer Art Teufelskreis: Der Parser muss, um den Code korrekt in einen AST übersetzen zu können, den AST selbst heranziehen, um die Bedeutung einzelner Identifier erschließen zu können. Das betrifft iirc Templates, Typedefs und Makros. Im Endeffekt muss man wohl schon einen halben Compiler schreiben, um den Code korrekt parsen zu können.

Beim Stöbern im Netz bin ich auf Parsing C++ gestoßen. In diesem Artikel beschreibt jemand seine Recherche zum Thema C++ Parsing. Darin sind einige interessante Links zum Thema aufgeführt, die die Problematik des Parsens weit über die Gebiete meines Wissens hinaus behandeln ;)
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Samstag 14. Juni 2008, 18:59

Noch schlimmer ist wohl nur Perl, wo manche Zweideutigkeiten in der Semantik erst während der *Ausführung* aufgelöst werden können...
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Samstag 14. Juni 2008, 20:08

Joa. C++ Parsen ist ein Krampf. Es gab da mal Versuche die Grammatik zu vereinfachen, aber aus dem ist irgendwie nix geworden. Der GCC bekommt es anscheinend bis heute nicht zusammen Macros und Templates zu mischen, wenn in deinem Template ein Beistrich vorkommt:

Code: Alles auswählen

BOOST_FOREACH(Pair<keytype, valuetype> pair, ...) { ... }
Den Blödsinn im Kleinformat gibts übrigens in Ruby, da geht das alles noch zur Compile-time (im Gegensatz zu Perl), aber da muss auch der Lexer schon eine Ahnung vom AST haben, weil zb die Unterscheidung zwischen Regexp und Divisionsoperator von den defineirten Methoden in einer Datei abhängig ist. (Absoluter Schwachsinn)
TUFKAB – the user formerly known as blackbird
wasser
User
Beiträge: 2
Registriert: Mittwoch 11. Juni 2008, 15:59

Samstag 14. Juni 2008, 20:41

Hi,

danke für die Recherche! :) sind allesamt gute Links.
Werde demnächst weiterforschen, weil mich das Thema Parser/Parsergeneratoren interessiert.

Habe inzwischen zwei Updates:

Synopsis hat schon ein Python Modul!
pygccxml hat sogar einen Wrapper dafür.
Leider kann man aber wieder nur Deklarationen sehen (oder übersehe ich da was?) :?

Weil ich ein wenig Probleme hatte loszulegen, hier eine kurze Anleitung, ist nämlich ein schönes Modul. gccxml-bodies
Daniel Lauk hat eine Seite seines Projektes gccxml-bodies erstellt.
Kompiliert einwandfrei mit gcc-3.4 oder drunter, aber dann in setup_build.sh umstellen

Code: Alles auswählen

$ hg clone http://freehg.org/u/djlauk/gccxml-bodies/ 
$ cd gccxml-bodies
$ ./setup_build.sh
$ cd build
$ make
($ make install)
Aufruf dann so:

Code: Alles auswählen

$ gccxml -fxml=<output-file> -fxml-body  <input-file>
Ausschnitt aus der Ausgabe:

Code: Alles auswählen

<Function id="_3" name="main" returns="_151" context="_1" location="f0:4" file="f0" line="4" endline="8">
    <body:Dump xmlns:body="http://www.djlauk.de/">
      <body:Body>
        <body:Compound_Stmt>
          <body:Compound_Stmt>
            <body:Expr_Stmt>
              <body:Call_Expr>
                <body:Address>
                  <body:Addr_Expr>
                    <body:Function_Decl id="_231" name="puts" />
                  </body:Addr_Expr>
                </body:Address>
                <body:Arguments>
                  <body:Argument>
                    <body:Nop_Expr>
                      <body:Addr_Expr>
                        <body:String_Cst>Hello World!</body:String_Cst>
Werde jetzt versuchen pygccxml umzubauen.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Sonntag 15. Juni 2008, 11:04

lunar, interessanter Text über das Parsen von C++, den du da gefunden hast. Dass es keinen Refactoring-Support für C++ gibt, gilt allerdings nicht mehr. Mindestens die Eclipse CDT können da etwas. Da gäbe es dann auch einen in Java geschriebenen C++-Parser, was aber wohl nur in Frage käme, wenn man massiv mit Java und Jython experimentieren will. Ich hätte jedoch das Vertrauen, dass die CDT-Jungs da einen korrekten Parser gebaut haben und an dessen AST (in Java) zu kommen, ist möglich. Ich hatte mir das mal angeschaut, als ich überlegte, ob ich den Code wohl nutzen könnte, um einen Berg C-Sourcen mit Funktionsdeklarationen im K&R-Format in das ANSI-Format umwandeln könnte - das ganze manuell zu machen war dann aber doch einfacher als stundenlang Code zu hacken...

Der Autor des Artikel gibt noch den Tipp, einen GLR-Parser zu benutzen. Sowas gibt es auch für Python. Erfahrungen mit GLR habe ich jedoch nur bislang mit einer Java-Version gemacht, kann also nicht sagen, ob das Ding gut ist.

mitsuhiko Rant über den Ruby-Parser kann ich nicht so ganz nachvollziehen. Ruby zu parsen ist ein Krampf, das ist schon richtig, aber entweder hatte ich damals, als ich 2001 den JRuby-Parser baute, etwas falsch gemacht oder das mit den Regexp ist nicht richtig. Probleme machen eher, dass man die Klammern von Methodenaufrufen weglassen kann und das es diese nachgestellten Bedingungen.

Dennoch: Es ist einer Sprache nicht vorzuwerfen, wenn sie kompliziert zu parsen ist, so es denn für den Anwender einfach genug ist, die Randfälle zu verstehen. Wenn umgekehrt eine Sprache zwar einfach zu parsen ist (wie Lisp), dafür aber alle Anwender klagen, dass sie nichts verstehen, ist auch keinem geholfen.

Stefan
lunar

Sonntag 15. Juni 2008, 11:20

sma hat geschrieben:Dennoch: Es ist einer Sprache nicht vorzuwerfen, wenn sie kompliziert zu parsen ist, so es denn für den Anwender einfach genug ist, die Randfälle zu verstehen. Wenn umgekehrt eine Sprache zwar einfach zu parsen ist (wie Lisp), dafür aber alle Anwender klagen, dass sie nichts verstehen, ist auch keinem geholfen.
C++ passt in beide Kategorien: Schwer zu parsen und schwer zu verstehen ;)
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Sonntag 15. Juni 2008, 12:03

sma hat geschrieben: Dennoch: Es ist einer Sprache nicht vorzuwerfen, wenn sie kompliziert zu parsen ist, so es denn für den Anwender einfach genug ist, die Randfälle zu verstehen. Wenn umgekehrt eine Sprache zwar einfach zu parsen ist (wie Lisp), dafür aber alle Anwender klagen, dass sie nichts verstehen, ist auch keinem geholfen.
Doch, das ist einer Sprache vorzuwerfen, denn es geht auch anders.

Und dass keiner Lisp versteht, liegt daran, dass es keiner verstehen will. Die Klammern wirken auf Neulinge (die ja meistens von C-Bastard-Sprachen kommen) ähnlich wie Pythons Einrückung: Buähh, andere Syntax!

Hat man das überwunden, stellt sich Lisp keineswegs anders dar als jede andere Sprache -- die "höheren" Features wie Makros haben durchaus ihre Pendants in den "leicht zu verstehenden" Sprachen: Templates in C++, Objektorientierung in Perl.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sonntag 15. Juni 2008, 12:28

birkenfeld hat geschrieben:Und dass keiner Lisp versteht, liegt daran, dass es keiner verstehen will. Die Klammern wirken auf Neulinge (die ja meistens von C-Bastard-Sprachen kommen) ähnlich wie Pythons Einrückung: Buähh, andere Syntax!
Stimmt genau. Natürlich ist es erstmal ungewohnt und ich muss auch sagen, dass die Klammern weniger übersichtlich sind als Blöcke (dafür andere Vorteile haben, code == data) aber mit etwas gutem Willen kann man durchaus zu einem Punkt kommen wo man aufhört gegen die Syntax zu kämpfen und die Vorteile ausnutzen kann. Dazu ist es natürlich sehr nützlich wenn man einen brauchbaren Lisp-Editor wie Emacs mit SLIME oder MrEd nutzt der Blöcke highlightet.

Bei C++ ist nur die Lernkurve ganz anders: am einfach ist es (vergleichsweise) einfach und die fortgeschrittenen Sachen werden dann so umständlich dass man sie nicht mehr nutzt, ergo verstehen nur wenige Leute wie die genau funktionieren. Wäre aber wohl mit jeder komplexeren Sprache genauso, die man mit "XY für Dummies" Büchern lernt.
birkenfeld hat geschrieben:Hat man das überwunden, stellt sich Lisp keineswegs anders dar als jede andere Sprache -- die "höheren" Features wie Makros haben durchaus ihre Pendants in den "leicht zu verstehenden" Sprachen: Templates in C++, Objektorientierung in Perl.
Wobei dann zu überlegen wäre, ob Makros und CLOS in CL nicht angenehmer zu nutzen sind :)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Sonntag 15. Juni 2008, 14:27

sma hat geschrieben:mitsuhiko Rant über den Ruby-Parser kann ich nicht so ganz nachvollziehen. Ruby zu parsen ist ein Krampf, das ist schon richtig, aber entweder hatte ich damals, als ich 2001 den JRuby-Parser baute, etwas falsch gemacht oder das mit den Regexp ist nicht richtig. Probleme machen eher, dass man die Klammern von Methodenaufrufen weglassen kann und das es diese nachgestellten Bedingungen.

Code: Alles auswählen

x = 42

def foo
  puts "WAHHH"
  23
end
und

Code: Alles auswählen

def x y
  puts x
end
Und dann unten drunter in beiden Fällen folgendes Statement:

Code: Alles auswählen

x /foo#/
Gibt folgenden Output:

Code: Alles auswählen

WAHHH
und

Code: Alles auswählen

(?-mix:foo#)
Bitte um Erklärung :-)
TUFKAB – the user formerly known as blackbird
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Freitag 20. Juni 2008, 12:16

Und ich war mir so sicher... du hast (wie üblich) Recht. Der Ruby-Parser prüft, ob ein Identifier als Variable definiert ist und wählt in diesem Fall einen anderen Weg durch den Parser. Ich habe eben die ganze Zeit versucht, genau die Stelle im C-Code zu finden, bin aber gescheitert.

Es müsste an der Stelle sein, wo für 'stmt' zwischen 'command_call' und 'expr' unterschieden wird. Ersterer ist ein 'command', welches aus 'operation command_args' besteht. 'operation' ist ein tIDENTIFIER und das ist, was der Lexer in beiden Fällen liefert. Allerdings ist command die niedrigste Priorität, sodass 'expr' (was auch ein 'command_call' sein kann) mit 'arg' wohl zuerst geprüft wird. Hier gilt 'arg : arg '/' arg | primary' und eigentlich müsste damit immer '/' als Division erkannt werden. Denn 'primary' kann eine 'variable' sein und das ist ein tIDENTIFIER. Am Lexer liegt es jedenfalls nicht direkt, aber irgendwo im Parser muss ein State verändert werden.

Grummel.
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Freitag 20. Juni 2008, 22:31

sma hat geschrieben:Und ich war mir so sicher... du hast (wie üblich) Recht. Der Ruby-Parser prüft, ob ein Identifier als Variable definiert ist und wählt in diesem Fall einen anderen Weg durch den Parser. Ich habe eben die ganze Zeit versucht, genau die Stelle im C-Code zu finden, bin aber gescheitert.
Haha. Ich fühl mich geschmeichelt, aber der Schein trügt. Was parse.y angeht: da findet sich niemand zurecht :-)
Es müsste an der Stelle sein, wo für 'stmt' zwischen 'command_call' und 'expr' unterschieden wird. Ersterer ist ein 'command', welches aus 'operation command_args' besteht. 'operation' ist ein tIDENTIFIER und das ist, was der Lexer in beiden Fällen liefert. Allerdings ist command die niedrigste Priorität, sodass 'expr' (was auch ein 'command_call' sein kann) mit 'arg' wohl zuerst geprüft wird. Hier gilt 'arg : arg '/' arg | primary' und eigentlich müsste damit immer '/' als Division erkannt werden. Denn 'primary' kann eine 'variable' sein und das ist ein tIDENTIFIER. Am Lexer liegt es jedenfalls nicht direkt, aber irgendwo im Parser muss ein State verändert werden.
Lext der Lexer einfach drauf los oder spricht er mit dem Parser um über State Änderungen informiert zu werden? Wenn letzteres könnt ich mir das vorstellen, Lexer liefert immer eine Division und der Parser sagt dem Lexer dann ob er da der Meinung ist, dass hier dividiert oder regulär ausgedrückt wird.

Wie auch immer. Es war für mich komplex genug, dass ich mich entschieden hab das nicht in Pygments einzubasteln :-)
TUFKAB – the user formerly known as blackbird
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Samstag 21. Juni 2008, 08:48

Der Lexer kennt ein halbes Dutzend Zustände, die der Parser munter ändert - der Lexer aber auch. Bei '/' prüft der Lexer, ob er in einem Zustand ist, wo es unmöglich ein Operator sein kann und sagt sofort REGEX. Ansonsten entscheidet das der Parser - indem er prüft, ob die linke Seite eine lokale Variable ist.

Rubinius kann's übrigens nicht ;)

Stefan
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Sonntag 22. Juni 2008, 10:30

Es wird OT, aber... es hat mir ja keine Ruhe gelassen und nachdem es mir nicht gelang, die September-2001-Version von JRuby mit SVN auszuchecken, habe ich's mit git geschafft und konnte das besagte Beispiel durch den alten Parser (noch für Ruby 1.6) schicken: Es gibt einen "ambiguous"-Fehler. Wusste ich doch, dass da noch keine Magie im Spiel war ;)

Stefan
Antworten