Mathe-Parserbau mit unterschiedlichen Zahlen-Typen

Antoras

Hallo,

bin gerade dabei einen Matheparser zu schreiben. Der Parser arbeitet nach dem Bottom-Up verfahren. Bisher funktioniert auch alles. Ich will aber noch eine Unterstützung für unterschiedliche Zahlen-Typen einbauen. Zusammengefasst unter rationale Zahlen (alle Brüche), komplexe Zahlen (Zahlen mit einem angehängten i) und irrationale Zahlen (alle anderen Zahlen). Um Rationale und Irrationale unterscheiden zu können hab ich mir gedacht muss man die Rationalen in Klammern setzen (ich möchte, dass man wählen kann ob der Parser den Kommawert eines Bruchs oder eben den Bruch selbst ausgibt).
Bisher hat die Entwicklung gut geklappt weil ich strikt nach meiner EBNF arbeiten konnte. Jetzt hab ich aber das Problem, dass ich u.U. die eingelesene Token ja mehrmals überprüfen muss um den Zahlentyp bestimmen zu können. Vor allem die Rationalen stelle ein Problem dar, da sie ja aus fünf Token bestehen ('(', 'Zahl', '/', 'Zahl', ')').
Hier mal meine EBNF:

Expression = (Term) {("+"|"-") (Term)};
Term = (Factor) {("*"|"/"|"%"|"^") (Factor)};
Factor = [("+"|"-") {("+"|"-")}] ("(" (Expression) ")"|(Function)|(Constant)|(Number));
Function = (Identifier) "(" [(Expression) {","(Expression)}] ")";
Constant = (Identifier);
Identifier = (("a"-"Z")|"_") {("a"-"Z")|"_"};
Number = (Rational)|(Irrational)|(Complex);
? Rational = "[" (Integer) ["/" (Integer)] "]";
? Rational = "[" (Expression) "]"
Irrational = (Float);
Complex = [(Irrational) ("+"|"-") [(Irrational)]] "i";
Integer = (Digit) {(Digit)};
Float = (Digit) ["."] {(Digit)};
Digit = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9";

Wenn ich wie bei den beiden Fragezeichen dargestellt alle fünf Token parse, dann hab ich das Problem, dass ja ein Fehlen auftreten kann (wenn Zahl nicht Rational). Bei der zweiten Variante hab ich zwar die komplette Expression, muss aber wieder umständlich alle Token überprüfen.

Mein zweites Problem ist, dass ich statt eckigen Klammmern gerne Runde benutzen würde um Rationale zu kennzeichnen. Das funktioniert aber nicht, da die Klammern bereits in der Factor-Ebene geparst werden.

Kann mir jemand einen Tipp geben wie ich die beiden Probleme am besten anzugehen habe?

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Themen rund um den PC in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Zeus

Irgendwie ist deine ganze Grammatik sehr seltsam. Hast du eine transformierte Grammatik für deinen LL-Parser?

Antoras

Was ist eine transformierte Grammatik? Ich hab nur diese EBNF, nach der ich meinen Mathe-Parser geschrieben hab. Einen Generator, der testet ob die EBNF korrekt ist hab ich nie eingesetzt. Das war bisher immer nur für mich - sozusagen als Stütze, damit ich weiß was ich als nächstes machen muss.

Zeus

Ach ich konstruktiere dir mal ein Fall aus deinen Regeln ein kleines Beispiel:

Number = (Integer)|(Float);

Integer = (Digit) {(Digit)};
Float = (Digit) ["."] {(Digit)};

Digit = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9";

Eine Zahl keine eine Integer oder ein Float. Wenn der Parser in Number steckt, sein Zeichen hat, müss er ja eintscheiden ob Float Aufruft oder Integer. Die Zeichen kann aber beginnen mit 0-9 für Integer als auch für Floats.
Hast du nun ein Float eingegeben wird ein Integer erkannt, in den Fall wenn man den Parser genauso runterschreibt, erst Integer prüfen, dann Float.

Transformiert in:

Number' = (PrefixDigit')
PrefixDigit' = (Digit) ((Integer') | (Float'))
Float' =  "." (Integer');
Integer' = {(Digit)}; // Vorsicht kein passendes Zeichen ist kein Fehler -> epsilon Abschluss!!

Digit = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9";

steigt der Parser korrekt ab.

Beim Parsen von der Eingabe 1+1 sieht es allerdings aus, dass der Parser nie zu Integer absteigen kann.

otze

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.

Zeus

Oh ja, da war ich wohl zu müde. Ich guck mir das heute abend genauer an.

Antoras

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.

Zeus

Ist dein Bottom-Up-Parser nicht klassisch aufgebaut?

Antoras

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).

Zeus

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.pdf

Hast du dein Algo selbst entwickelt oder nach eine Vorlage?

otze

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.

Th69

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...

Antoras

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:

http://www.wi.uni-muenster.de/pi/lehre/ss09/SeminarCompilerbau/abgaben/Adrian-Heinemann---Syntaxanalyse-LR1-LALR---2.pdf

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.

Zeus

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.

Th69

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 ?

Antoras

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.

Th69

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.pdf

Meine 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.

life

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".

volkard

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.