Mathe-Parserbau mit unterschiedlichen Zahlen-Typen
-
Zeus: Bootom-Up-Parser sind nicht LL. Das sind Top-Down-Parser. Und zum Beispiel nem Earley-Parser ist das Format der Grammatik egal, solange sie Kontextfrei ist. Ähnliches gilt für den CYK-Parser.
//edit und den zweiten Satz deines Posts kann kein Mensch lesen...irgendwa sfehlt da.
//edit2 und ich würde mich nicht drauf festnageln (weil das nur mit Mühe zu beweisen ist), aber ich glaube die Grammatik ist sogar LR(1). Und dann ist das alles kein Problem. Dafür gibts schnelle Parser//edit (weils mir grad aufgefallen ist):
Lass doch vorher nen lexer drüber laufen, dort kannst du die verschiedenen Zahlentypen enorm einfach erkennen. Wenn du das hast, brauchste die Zahlen nurnoch geschickt zwischenspeichern und im tokenstream steht dann statt dem Zahlenstring nur noch ein identifier der angibt, dass es sich an der Stelle um einen Float/Integer/Komplexe Zahl handelt.
-
Oh ja, da war ich wohl zu müde. Ich guck mir das heute abend genauer an.
-
Nach der Lösung von dir, Zeus, hab ich meinen Scanner implementiert. Dieser kann bereits zuverlässig Integers/Floats/Complexe erkennen. Hab das in der EBNF noch gar nicht beachetet, werd ich gleich nachtragen.
Mein Hauptproblem ist eher, dass ich nicht weiß wie ich zuverlässig Rationale erkennen soll, da diese ja aus mehreren Token bestehen. Ich könnte den Klammerausdruck mit einem ineinander verschachteltem Abfragen-Konstrukt schon parsen, allerdings glaube ich nicht, dass das eine gute und elegante Lösung ist.
-
Ist dein Bottom-Up-Parser nicht klassisch aufgebaut?
-
Tut mir leid, mit der Theorie hab ich es nicht so. Was ist ein klassischer Aufbau?
Ich hab halt einen Scanner, der aus dem Eingangsstring Tokens erzeugt, die dann dem Parser gegeben werden, der die Syntax nach dem Bottom-Up Prinzip auf Korrektheit überprüft. Der Parser stellt dann einen Syntaxbaum auf, der zum Ende noch ausgewertet wird.
Hab gerade bei Wikipedia vorbei geguckt. Mein Parser ist momentan wohl ein LR(1)-Parser. Was ich brauche ist aber ein LR(k)-Parser wobei k eben die Anzahl an Zeichen sind, die ich brauche um Rationale zu erkennen (da sie bei mir aus fünf Token bestehen müsste der Parser noch vier Token voraussehen können).
-
Du hast ein Stack, ein Aktion(Action)Tabelle/Liste und eine Spring(Goto)-Tabelle/Liste.
In deinen Stack werden die Eingabe "gelagert", dass in Abhänigkeit zu Aktionen und zu Zustandsänderungen führt.
Diese Tabellen werden anhand deine Grammatik erstellt.Sehr grob. Besser Info hier:
http://www.wi.uni-muenster.de/pi/lehre/ss09/SeminarCompilerbau/abgaben/Adrian-Heinemann---Syntaxanalyse-LR1-LALR---2.pdfHast du dein Algo selbst entwickelt oder nach eine Vorlage?
-
Bist du dir sicher,d ass dein Parser LR(1) ist? da kommt man nämlich eigentlich nicht "einfach so" drauf(schon allein, weil ein LR(1) Parser eine sehr komplizierte Konstruktion hat).
Mal ein Tipp: jag die Grammatik testweise durch yacc/Bison. wenn er damit zufrieden ist, dann liegts an deinem Parser.
Nächster Tipp: benutze yacc/Bison anstatt deinen eigenen Parser zusammenzufriemeln.
-
Hallo Antoras,
wieso verwendest du überhaupt einen Bottom-Up-Parser, denn ein Top-Down-Parser ist ja um einiges einfacher zu implementieren (auch wenn du dann die EBNF-Definition umschreiben mußt, damit keine linksseitigen Rekursionen entstehen bzw. Doppelbedeutungen von vorherein beachtet werden müssen - Zeus hatte darauf ja schon hingedeutet)?
Den Parser hast du mit C++ geschrieben, oder? Verwendest du eine bestimmte Lib dafür, z.B. boost.Spirit?
Einen erweiterbaren (Top-Down) Parser für math. Formeln (wenn auch in C#) habe ich hier veröffentlicht: http://www.mycsharp.de/wbb2/thread.php?threadid=71995
Kannst dir den ja mal als Anschauungsmaterial ansehen...
-
Zeus schrieb:
Du hast ein Stack, ein Aktion(Action)Tabelle/Liste und eine Spring(Goto)-Tabelle/Liste.
In deinen Stack werden die Eingabe "gelagert", dass in Abhänigkeit zu Aktionen und zu Zustandsänderungen führt.
Diese Tabellen werden anhand deine Grammatik erstellt.Ich hab halt einen AST. Und der wird anhand meiner EBNF vom Parser aufgestellt.
Zeus schrieb:
Danke, werde ich mir mal angucken.
Zeus schrieb:
Hast du dein Algo selbst entwickelt oder nach eine Vorlage?
Halb halb. Inspiriert wurde ich z.T. durch die beiden Parsertutorials aus dem Forum hier: Interpreterbau - Ein Anfang und Compilerbau
otze schrieb:
Bist du dir sicher,d ass dein Parser LR(1) ist? da kommt man nämlich eigentlich nicht "einfach so" drauf(schon allein, weil ein LR(1) Parser eine sehr komplizierte Konstruktion hat).
Ich hab das nur in diversen Artikeln gelesen. LR(k) soll angeben in wie weit der Parser vorausschauen kann. Und da mein Parser halt z.B. nur weiß, dass auf eine Zahl mit darauf folgendem Pluszeichen halt wieder eine Zahl kommen muss, hab ich angenommen, dass der Parser eben 1 Zeichen voraussehen kann. Aber wahrscheinlicher ist, dass ich nur kompletten Bockmist verstanden hab...
otze schrieb:
Mal ein Tipp: jag die Grammatik testweise durch yacc/Bison. wenn er damit zufrieden ist, dann liegts an deinem Parser.
Nächster Tipp: benutze yacc/Bison anstatt deinen eigenen Parser zusammenzufriemeln.
Das mit yacc/Bison werd ich mal ausprobieren. Aber nur zum Testen, nicht um mir einen Parser zu generieren. Compilerbau ist nämlich gerade das was mich interessiert, am Ergebnis (also, dass der Parser funktioniert) bin ich nur in zweiter Linie interessiert.
Th69 schrieb:
wieso verwendest du überhaupt einen Bottom-Up-Parser
Hab mal einen kleinen Top-Down-Parser geschrieben, der ich aber immer als etwas frickelig empfunden hab. Und als jemand aus einem anderen Forum mal gemeint hat, dass Bottom-Up-Parser deutlich effizienter sind, vor allem wenn der Parser mehr können soll als ein paar mathematische Funktionen, bin ich halt umgestiegen.
Th69 schrieb:
Den Parser hast du mit C++ geschrieben, oder?
Nö, die ersten Versuche waren C. Für den jetzigen Parser verwende ich Scala.
Th69 schrieb:
Einen erweiterbaren (Top-Down) Parser für math. Formeln (wenn auch in C#) habe ich hier veröffentlicht: http://www.mycsharp.de/wbb2/thread.php?threadid=71995
Kannst dir den ja mal als Anschauungsmaterial ansehen...Hab ich schon entdeckt. Danke dafür. Von den Zielen, die ich mir bei dem Matheparser vorgenommen hab, hab ich aber eigentlich alle erreicht (Funktionen, Konstanten, Operationen erkennen). Das einzige was noch fehlt ist die Erkennung des Zahlentyps.
Mir fehlt da aber auch einfach noch das Theoriewissen dazu. Sollte mir dafür wohl am besten noch ein Buch zulegen.
-
Wenn ich mich nicht verguckt habe, sind beide Parser im Artikel Top-Down-Parser. Top-Down-Parser sind nicht uneffizient, ledenfalls nicht von Haus aus. Eine LL(1)-Grammatik sind genauso effizient. Evtl. ist die Begrenzung des Stack gemeint, aber mit ~4000 Rekursionsaufrufen, will ich die Datei eh nicht sehen wollen. LR(1) Parser können halt eine beliebige größe Datei parsen.
Wenn du Grammatiken hast die LL(k)/LR(k) mit k > 1 dann wird knifflig, dann brauchst du Backtracking oder sonstige Mechanismus um die Grammatik zu bewältigen, dann kannst du nicht mehr in lineare Zeit parsen.
Aber die Matheexpression sind eigentlich so einfach, dass man sie in eine LL(1)-Grammatik beschreiben kann, so dass du nur aufpassen musst, dass du dein Parser nicht mit eine EBNF fütterst, die für dich eindeutig aussieht, aber nicht in der Form einer LL(1)-Grammatik ist.
-
Zeus: 100%ige Zustimmung
Antoras:
bzgl.Ich hab halt einen AST. Und der wird anhand meiner EBNF vom Parser aufgestellt.
komme ich bei dir ins Grübeln, ob du wirklich von Hand einen Bottom-Up-Parser implementiert hast (da dir die Theorie ja anscheinend fehlt, sind dir die Begrifflichkeiten evtl. nicht ganz klar: http://de.wikipedia.org/wiki/Bottom-Up-Parser bzw. http://de.wikipedia.org/wiki/LR-Parser).
Ich denke, du hast genauso einen Top-Down-Parser erstellt, wie in den beschriebenen Parser-Tutorials aus diesem Forum, nur eben daraus dann einen AST erstellt...Oder verwendest du ScalaBison http://www.cs.uwm.edu/~boyland/scala-bison.html ?
-
Also, jetzt wo ihr das so sagt glaube ich, dass ich wirklich einen Top-Down-Parser hab. Zumindest triffst das was ich jetzt nochmal über Bottom-Up-Parser gelesen hab nicht auf meinen Parser zu.
Ich glaub, ich leg mir jetzt wirklich erst mal ein Buch über Compilerbau zu. Das Parsen von Rationalen kann ich ja noch über ein einfaches Backtracking-Verfahren implementieren. Hauptsache das geht mal. Wenn ich dann ein bisschen mehr Ahnung von der Theorie hab, dann kann ich nochmal gucken wie man das besser lösen kann.
Zeus schrieb:
Aber die Matheexpression sind eigentlich so einfach, dass man sie in eine LL(1)-Grammatik beschreiben kann, so dass du nur aufpassen musst, dass du dein Parser nicht mit eine EBNF fütterst, die für dich eindeutig aussieht, aber nicht in der Form einer LL(1)-Grammatik ist.
Ich hab keinen Parsergenerator wie yacc/Bison geschrieben. Mit der EBNF kann mein Parser also nichts anfangen - er arbeitet nur nach dem Prinzip der EBNF.
-
Hallo antoras,
wußte ich's doch -)
Zum Thema EBNF parsen (bzw. nachbauen) kann ich dir besonders das "combinator parsing" empfehlen (gerade bei funktionalen Sprachen wie Scala), s. z.B:
http://www.codecommit.com/blog/scala/the-magic-behind-parser-combinators
http://lamp.epfl.ch/teaching/foundations_of_software/docs/combinator_parsing.pdfMeine Diplomarbeit habe ich auch u.a. mit "combinator parsing" in der - heute nicht mehr verwendeten - funktionalen Sprache "Gofer" (http://de.wikipedia.org/wiki/Gofer) geschrieben.
-
Das wichtigste, das ich von den Compilerbau Vorlesungen mitgenommen habe ist, niemals auf die Idee zu kommen selbst einen Parser zu schreiben, sondern einfach immer einen Parsergenerator zu nehmen ;).
Sobald man verstanden hat, wie die Parsergeneratoren arbeiten, ist das ganze Problem auch imho irgendwie "entzaubert".
-
life schrieb:
Das wichtigste, das ich von den Compilerbau Vorlesungen mitgenommen habe ist, niemals auf die Idee zu kommen selbst einen Parser zu schreiben, sondern einfach immer einen Parsergenerator zu nehmen ;).
Das ist das wichtigste Problem an klassischen Compilerbau-Vorlesungen.
-
@Th69
Danke, guck ich mir mal näher an.@life
Ich bezweifle, dass man Compilerbau wirklich versteht wenn man sich nur mit der Theorie auseinandersetzt. Wenn du gut bist versteht du vllt. 90% aber nie die vollen 100%.
-
Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.
Analog würde ich auch keine neuen Erkenntnisse erlangen, wenn ich ein Programm in Maschinensprache statt Assembler schreiben würde, sofern man weiß wie genau die Übersetzung Assembler->Maschinensprache aussieht.
-
life schrieb:
Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.
Kann man das begründen oder beweisen?
-
volkard schrieb:
life schrieb:
Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.
Kann man das begründen oder beweisen?
Weil ich, faul wie ich bin, keine Lust hätte selber nachzudenken, sondern stattdessen einfach die mir bekannten Grammatik->Parser Algorithmen von Hand nachspielen würde. Wenn man den Algorithmus aber schon vorher verstanden hat, bringt einen ein langwieriges von Hand nachspielen von Algorithmen rein garnichts.
-
life schrieb:
volkard schrieb:
life schrieb:
Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.
Kann man das begründen oder beweisen?
Weil ich, faul wie ich bin, keine Lust hätte selber nachzudenken, sondern stattdessen einfach die mir bekannten Grammatik->Parser Algorithmen von Hand nachspielen würde. Wenn man den Algorithmus aber schon vorher verstanden hat, bringt einen ein langwieriges von Hand nachspielen von Algorithmen rein garnichts.
Hmm. Aber dafür verlierst Du Flexibilität. Nichts, was man brauchen würde, wenn man nur C oder nur Pascal baut.
