Mathe-Parserbau mit unterschiedlichen Zahlen-Typen
-
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.
-
volkard schrieb:
life schrieb:
Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.
Kann man das begründen oder beweisen?
Ja.
1. Jede halbwegs nützlich zu implementierende Sprache ist LR(k)
2. Effiziente LR(k) Parser basieren darauf, dass man die einzelnen Zustände vorher berechnet
3. Jede halbwegs sinnvolle Sprache hat mehrere 100 bis 1000 Parsezustände(C++ irgendwas über 5000)
4. LR(k) Kollektionen für einen einzelnen Zustand zu berechnen ist mehr als Mühsam.
5. Der Code für einen LR(K) Parser selbst ist dann eine Sache von 15 Minuten
=> macht absolut keinen Sinn.Natürlich kann man auch einen anderen Parser selbst basteln, der nichtmal halb so effizient ist, aber warum sollte man? Compiler sind selbst mit Parser-Generatoren immer noch eine frickelige Angelegenheit in der es mehr als genug itneressante Probleme gibt, mit denen man sich beschäftigen kann( Eindeutige LR(k) Grammatik,Codegenerierung/Codeausführung mit einer VM, Optimierung...).
-
otze schrieb:
volkard schrieb:
life schrieb:
Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.
Kann man das begründen oder beweisen?
Ja.
1. Jede halbwegs nützlich zu implementierende Sprache ist LR(k)
Ah, auf solche Axiome habe ich doch gewartet. Und damit ist der Fall auch schon erledigt.
-
volkard schrieb:
Ah, auf solche Axiome habe ich doch gewartet. Und damit ist der Fall auch schon erledigt.
Naja, mit LL kriegste sofort Probleme, wenn du geschachtelte ifs mit optionalem else erlaubst. Das können die nämlich nicht(Nebenbei hat man bereits bei ll das selbe Problem, dass man da First und Follow Mengen berechnen muss um das effizient hinzukriegen. Also rettet einen auch ne ll-Grammatik nicht das Leben). LR ist die nächststärkere echte Obermenge zu LL. Alles was darüber geht wie earley oder CYK ist halt langsam. CYK kann man zwar super von Hand implementieren auch mit der Grammatik, aber das ist nicht Produktionstauglich, wenn man nicht grad eine echte kontextfreie oder sogar kontextsensitive Grammatik hat. Das ist der Unterschied zwischen O(n) und O(n^3). Benutzt man dann etwas nach der Bauart von Spirit, dann wird man sehr schnell richtig richtig langsam. Dann machts auch keinen Spaß mehr. Solch kleine Parser sind zwar für Sachen wie XML noch super von der Hand machbar, und es spricht nichts dagegen damit mal zu experimentieren, aber wenn man etwas wie nen Compiler schreiben will, dann sollte man direkt die richtigen Techniken verwenden, damit das Projekt nicht daran scheitert, dass sich der Compiler totrechnet, oder weil er am Ende die Grammatik einfach nicht parsen kann.
Die ganze Theorie die an den Unis gelehrt wird und die von Ullman und den anderen niedergeschrieben wurde hat ja auch einen Sinn. Die existiert definitiv nicht, damit jeder das Rad quadratisch neu erfindet.
Das Spannende an Sprachen sind die Grammatiken. Nicht die Parser. Da lernt man am Meisten, wenn einem yacc sagt, dass die Grammatik einen shift/reduce Konflikt hat und man die dann erstmal irgendwie umformulieren muss, damit das passt. Da lernt man auch, warum es in c++ das template keyword vor Funktionsaufrufen geben muss und warum bestimmte andere Sachen in der Sprache so gemacht wurden, wie sie jetzt sind(und warum C++ nicht LR(k) ist und warum deswegen die Compilerbauer fluchen). Die Algorithmen selbst sind dagegen total uninteressant, da sie auch nur das Ende einer langen Theorie darstellen.
Aber ich stelle mal die Gegenfrage: an welcher Stelle siehst du den Mehrwert?
-
otze schrieb:
Da lernt man auch, warum es in c++ das template keyword vor Funktionsaufrufen geben muss
Wie, wo?
template foo();?
MfG SideWinder
-
otze schrieb:
Aber ich stelle mal die Gegenfrage: an welcher Stelle siehst du den Mehrwert?
Ich muß mich nicht auf eine Grammatik festlegen. Da jeder mit Yacc/Bison eine kleine Sprache bauen kann und es viele sogar tun, erhoffe ich mir dort auch nicht die interessanten Entwicklungen.
http://www.c-plusplus.net/forum/viewtopic-var-t-is-270187-and-postdays-is-0-and-postorder-is-asc-and-start-is-4.html
