Parser zum zerlegen von Gleichungen



  • Hallo,

    ich suche einen Parser zum zerlegen von einfachen Gleichungen für einen Assembler.

    Es geht um Dinge wie "0x0700 + $Label1" oder "1946 * 4 + 12" u.ä. , die eigentlichen Befehle hab ich bereits decodiert.
    Der Parser soll also einen gegebenen kurzen String in seine Bestandteile Zahlen, Operatoren, Klammern und Labels in eine Art Token-Baum zerlegen. Diesen Baum möchte ich dann später, wenn z.B. die Adresse der Labels bekannt ist, abarbeiten und das Ergebnis, immer eine Zahl, erhalten.

    Gibt es da was fertiges?
    Oder wenigstens eine Art Anleitung wie man sowas am besten/einfachsten angeht?

    Danke schon mal für alle hilfreichen Antworten.

    Grüße
    Erik



  • Hi,

    such mal im Netz nach Postfix-Infix-Convertern. Die machen das im Prinzip schon fast so wie Du es willst.

    Gruß Mümmel



  • Eine google-suche über das Forum sollte dir eigentlich zig Threads zu dem Thema liefern. Th69 hat da meines Wissens was fertiges in der Schublade.
    Ansonsten gehört das Thema zu den Standardaufgaben und -beispielen des Parsens, da sollten im Netz eigentlich hunderte Beispiele und Implemenatierungen zu finden sein.



  • Ja, hallo, mein Name wurde genannt, hier bin ich... -)

    Hallo erik, in welcher Sprache benötigst du denn den Parser?

    Einen sog. Funktionsparser für math. Ausdrücke habe ich hier beschrieben:
    http://www.c-plusplus.net/forum/viewtopic-var-p-is-1780654.html#1780654
    Jedoch wertet dieser gleich den math. Ausdruck aus, d.h. den Token-Baum müßtest du dann noch erstellen.

    Und einen Artikel zum Thema (allerdings für C#) gibt es unter
    http://www.mycsharp.de/wbb2/thread.php?threadid=71995
    Hier wird intern (im sog. Optimized-Modus) ein Baum aufgebaut, welchen du dann verwenden könntest.



  • Hallo,

    Danke erst mal für Eure Antworten.

    Das mein Problem nicht neu ist war mir klar schließlich gibt es Unmengen an (Script-)Sprachen usw. und die müssen dieses Problem ja auch alle lösen. Da ich nie studiert o.ä. habe, ich vermute mal das Parser und vergleichbares auf fast jeden ernst gemeinten Lehrplan steht, habe ich auch keinen Plan wo ich da mit suchen anfangen sollte.

    Der Parser soll möglichst in C++ sein aber ähnliches kann ich bestimmt passend konvertieren. 😉

    Ich bin fast so weit das ich aus dem String eine lineare Liste mit Zahlen, Labels, Operatoren und Klammern habe. Diese Liste müsste dann in einen Baum überführt werden in dem jedes Element eine mathematische Operation mit ihren 2 Parametern ist von denen wieder keines, eines oder beides neue Operation-Objekte sein können. Dann müsste man den Baum von den Blättern zur Wurzel abarbeiten bis maximal "Label + Zahl" (mehr als eine einfache Addition kann der Linker später nicht) oder eine konkrete Zahl übrig bleibt. Im ersten Fall muss ich schauen ob ich das Label auflösen kann (um doch noch ein konkretes Ergebnis zu bekommen) oder es ein externes ist und im zweiten Fall ists damit fertig und der Befehl kann in den CPU-Verwertbaren Bit-Code umgesetzt werden.

    Danke für Eure Links und Suchworte, die werd ich mir jetzt mal vornehmen.

    Grüße
    Erik



  • für sowas gibts lexer/parser generatorn wie lex/yacc und ähnliches...



  • Hallo,

    ich hab wohl gestern Abend in meiner Baum-Beschreibung die Unary-Operatoren vergessen 🙄 aber ansonsten bin ich der Meinung das mein Weg recht gut ist.

    Ich hab noch mal überlegt, ich möchte diesen Weg auch auf jeden Fall selber gehen da ich ja auch was bei lernen möchte, also einfach nur Code kopieren möchte ich sicher nicht. Aus diesem Grunde möchte ich auch keine Generatoren einsetzen, nebst dessen das die für mein Problem wahrscheinlich ein paar Nummern zu groß sind. Und da meine lineare Liste fast funktioniert hat sich das mit dem Lexer sowieso schon erledigt.
    Es bleibt also nur noch die Umwandlung der linearen Liste in einen Baum. Ob ich dabei Prioritäten der Operatoren beachten möchte weiß ich noch nicht, ich möchte mich auf jeden Fall so nah wie möglich an C orientieren.
    Den Baum abzuarbeiten sollte dann eine leichte Übung sein.

    @Th69: Danke für Deinen Code, aber so richtig verstanden hab ich das noch nicht alles. 😕 Ich werd mir das die nächsten Tage genauer reinziehen.

    Grüße
    Erik



  • Ich hab noch mal überlegt, ich möchte diesen Weg auch auf jeden Fall selber gehen da ich ja auch was bei lernen möchte, also einfach nur Code kopieren möchte ich sicher nicht. Aus diesem Grunde möchte ich auch keine Generatoren einsetzen

    Du willst garnicht bei regulaeren Ausdruecken und Grammatiken anfangen. Glaub mir! Arbeite die Tutorials fuer lex/yacc odet flex/bison durch. Da ist genug Stoff drin und du musst fast alles selbst machen.



  • Hallo,

    knivil schrieb:

    Du willst garnicht bei regulaeren Ausdruecken und Grammatiken anfangen. Glaub mir! Arbeite die Tutorials fuer lex/yacc odet flex/bison durch. Da ist genug Stoff drin und du musst fast alles selbst machen.

    Hä, ich verstehe nicht was Du meinst. 😕
    Gerade weil ich mir die Einführungsseiten von flex, yacc und bison angesehen hab bin ich mir ziemlich sicher das ich nicht mit Kanonen auf Spatzen schießen möchte, außerdem lerne ich dabei nicht wie es intern funktioniert sondern nur wie ich ein mächtiges Tool benutze.

    Mit regulären Ausdrücken usw. hab ich nichts zu tun, ein char-Array nach ein paar Operator-Zeichen und Klammern zu durchsuchen oder Zahlen und Labels zu erkennen ist in meinem Fall nicht schwer. Es gibt auch nur 2 Doppeldeutigkeiten + und - können Rechenoperator oder Vorzeichen sein, alles andere ist exakt eindeutig.

    Grüße
    Erik



  • bin ich mir ziemlich sicher das ich nicht mit Kanonen auf Spatzen schießen möchte

    Im Vergleich zu flex/bison gibt es viel groessere Kanonen, die bei viel kleineren Spatzen benutzt werden. Dabei ist flex/bison in meinen Augen ein Leichtgewicht. Zu dem Tutorial: Ich meinte http://www.gnu.org/software/bison/manual/bison.html .


Log in to reply