Parser-generator für mathematische Funktionen

[DaDave]

Hallo zusammen,

ich werde in den nächsten Monaten meine Bachelor-Arbeit schreiben und soll in Java ein Programm schreiben was mathematische Ausdrücke auswertet.
Auch durchaus komplexere Sachen wie z.B. "(5*23.9+x)-44/2.6" (natürlich mit vorher definierten x). Es sollen auch Funktionen und variablen abgespeichert werden können.

Jetzt ist mir ja schon klar das ich sinnvoller Weise einen Paser-Generator benutzen sollte. Allerdings ist das Angebot doch recht groß. (JavaCC, ANTLR, SableCC, etc.)

Und überall ist von einem AST die Rede, welcher erstellt wird. Da ich allerdings wirklich auf Speicherplatz und Performanz achten muss wäre mir eine Art ByteCode lieber...

Habt Ihr irgendwelche Ideen welcher Parser-Generator dafür am sinnvollsten wäre?
Oder sich gut oder eher nicht dafür eignen würde?


Das wär echt schon eine große Hilfe!

Danke und mit freundlichen Grüßen
DaDave

 

[diggaa1984]

lol warte noch 1 monat und du bekommst ne alpha meiner studienarbeit die quasi das dann auch kann ^^

 

[Wildcard]

Was meinst du mit 'eine Art bytecode'?

 

[DaDave]

erstmal danke an diggaa1984 für den Tipp^^

und dann zu dem ByteCode:

ich stelle mir darunter vor das ich mir eine Codierung ausdenke oder nutze um dann die geparsten Ausdrücke oder variablen Definition im langfristigen Speicher ab zu legen.
Und dieser Code kann dann ohne weiteres verändern oder analysieren von einer Stackmaschine abgearbeitet werden...wenn er benötigt wird....

 

[0x7F800000]

ich werde in den nächsten Monaten meine Bachelor-Arbeit schreiben und soll in Java ein Programm schreiben was mathematische Ausdrücke auswertet.

Bachelor arbeit in was? Wenn das Informatik ist, dann ist die Diskussion imho unangebracht, weil ja eigentlich du uns erzählen solltest, wie man am besten parser generatoren schreibt, nicht andersrum
Wenn das Mathe sein soll, dann verstehe ich nicht ganz, wieso du dich um das parsen selbst kümmern musst? Für mathematiker gibt's doch tonnen verschieden gearteter numerischer- und CAS-systeme, die manchmal mehr oder weniger brauchbar sind: wenn du irgendein spezielles Algo implementieren willst, dann nimm einfach die passendste mathematische DSL und gut ist...

Auch durchaus komplexere Sachen wie z.B. "(5*23.9+x)-44/2.6" (natürlich mit vorher definierten x). Es sollen auch Funktionen und variablen abgespeichert werden können.

das ist noch nicht wirklich "komplex", wie man sowas baut hat Beni mal in der FAQ beschrieben, solche Ausdrücke kann man auch rein intuitiv als erstsemestler ohne jegliche compilerbau-vorkenntnisse wunderbar parsen.

Jetzt ist mir ja schon klar das ich sinnvoller Weise einen Paser-Generator benutzen sollte. Allerdings ist das Angebot doch recht groß. (JavaCC, ANTLR, SableCC, etc.)

Was ist nochmal das Ziel? Wie gesagt, wenn es um Parsergeneratoren an sich geht, ist verwendung eines fertigen irgendwie bisschen witzlos imho :bahnhof:

Und überall ist von einem AST die Rede, welcher erstellt wird.

Selbstverständlich, darum geht's ja beim Parsen: aus einer Kette von Tokens ein AST herzustellen. Was wolltest du denn stattdessen?

Da ich allerdings wirklich auf Speicherplatz und Performanz achten muss wäre mir eine Art ByteCode lieber...

solang der parser in linearer Zeit durch den code durchrennt, ist die performance brutalst egal (bei diggaa1984 ist der Ansatz wesentlich mächtiger, aber leider nicht mehr linear, da muss man schon genauer hinschauen )
Das mit der performance ist so: wenn du fleißig bist und 1000 zeilen code schreibst, ist der parser nach 0 ms fertig. Wenn du ganz fleißig bist, und 10000 zeilen code schreibst, dann ist der parser immer noch nach ungefähr 0ms fertig.... Alles was du jemals manuell eintippen kannst, sollte den parser eigentlich nicht überfordern. Worauf man stattdessen lieber achten sollte, ist eine vernünftig ausformulierte grammatik, bei der die produktionen irgendeinen anschaulichen Sinn haben, damit man die eigentliche funktionalität leichter implementieren kann, wenn der parser-generator mit dem wilden herumjonglieren fertig ist.

und dann zu dem ByteCode:

ich stelle mir darunter vor das ich mir eine Codierung ausdenke oder nutze um dann die geparsten Ausdrücke oder variablen Definition im langfristigen Speicher ab zu legen.
Und dieser Code kann dann ohne weiteres verändern oder analysieren von einer Stackmaschine abgearbeitet werden...wenn er benötigt wird....

ööhm, das war jetzt noch weniger verständlich? ???:L

 

[DaDave]

hehe, also fange ich nochmal von vorne an

ich schreibe eine Bachelorabrbeit in Informatik...
Und klar sollt ihr hier nicht meine arbeit schrieben


bin leider durch nachholveranstaltungen etwas hinter dem Zeitplan..
ich soll so eine Art programmierbaren Taschenrechner programmieren...
...der halt eine Umfangene Bibliothek von Funktionen besitzt und sich auch welche hinzufügen lassen etc..
Die Abneigung gegen die ASTs ist eine der vorlagen..die ich erfüllen muss...
Daher dachte ich halt an eine Art ByteCode :rtfm:

Ich bräuchte nur ein bischen Hilfe bei der Auswahl der des Parser-generators... :autsch:

 

[0x7F800000]

hehe, also fange ich nochmal von vorne an

öhm, ja, hallo erstma^^

Die Abneigung gegen die ASTs ist eine der vorlagen..die ich erfüllen muss...
Daher dachte ich halt an eine Art ByteCode :rtfm:

Informatik Bachelor... Okay, und was hast du dir zum Compilerbau alles angehört? So wie ich das grad verstehe, sollst du eine komplett neue sprache für mathematische berechnungen entwerfen, und einen compiler dafür konstruieren, der code als eifache textdatei entgegennimmt, lext, parst, in AST umwandelt, den AST lange und kompliziert umwurschtelt und optimiert, in irgendeinen anderen Baum übersetzt, und das ganze am ende als Bytecode (etwa für die JVM?) ausgibt. Geile Sache. Wenn du das hinbekommst, rast es wirklich allen Interpretern davon, das ist eine durchaus hübsche idee...

Ein üblicher Fehler, der bei praktisch jeder "mathematiker-programmiersprache" auftritt: die fangen mit dem design der bibliothek an, statt sich gedanken über die sprache selbst zu machen. Am ende kommen dann irgendwelche behinderte Konstrukte heraus, die Syntaktisch etwa so "hochentwickelt" wie bat-stapelverarbeitungsanweisungen sind, dafür aber irgendwelchen krassen scheiß für die algebraische forschung können.
Das ist eigentlich auch ok, solange man diese sachen dann wirklich lediglich als "programmierbare taschenrechner" betrachtet: als Programmiersprachen sind sie meistens zum wegschmeißen... for-abfrage dort if-schleife da, und das war's schon :autsch:

Okay, wie du aus der Compilerbau Vorlesung evtl. weisst, fürhrt meistens kein Weg um AST's drumherum, als zwischenschritt werden sie doch überall benötigt... Was ist dann eigentlich deine frage dann: schreib den parser-generator entweder selbst, oder nimm halt AntLR oder so... AST's produzieren die alle. Automatische Übersetzung in bytecode ist afaik bisher zukunftsmusik und aktuelles forschungsgebiet. Also, ein Programm, das dir aus einer grammatik einen fertigen compiler anfertigt, solltest du nicht finden können, höchstens irgendwas experimentelles unausgereiftes & unbrauchbares... Sowas muss man afaik leider wohl selbst erledigen.

 

[diggaa1984]

@ 0x7F800000:
manchmal weiss ich echt nich ob ich bei deinen Beiträgen lachen oder heulen soll, aber der hier war noch zum lachen ... die sind immer so derbe direkt und nicht durch die Blume

aber danke fürs lob wegen mächtigkeit und nich vorhandener performance .. ich hoffe dass wirft mich später nich so zurück ^^

 

[0x7F800000]

@ 0x7F800000:
manchmal weiss ich echt nich ob ich bei deinen Beiträgen lachen oder heulen soll, aber der hier war noch zum lachen

öhm, echt? ja, dann lieber lachen, das ist gut für die gesundheit

die sind immer so derbe direkt und nicht durch die Blume

die Aussage war eigentlich völlig neutral gemeint. O(n³) ist nun mal nicht linear, und wesentlich mächtiger ist es, weil es komplett alle kontextfreie grammatiken erschlägt, was ich, wie gesagt, ziemlich cool finde. Hab's einfach gesagt so wie es ist

aber danke fürs lob wegen mächtigkeit und nich vorhandener performance .. ich hoffe dass wirft mich später nich so zurück ^^

das hoffen wir doch Aber wie extrem lange soll so eine Logische Formel schon werden? Irgendwann passt sie doch nicht mehr ins hirn, da sind die menschlichen kapazitäten etwas schneller erschöpft, als etwa bei java-code, oder? Daher wird es wohl auch mit O(n³) locker hinhauen Und wenn das Programm eh spezialisiert und selten, und ohne viel konkurrenz ist, dann werden sich die forscher ja wohl evtl. auch paar minuten gedulden können, wenn's wirklich sein muss

 

[diggaa1984]

ja das mit der blume bezog sich eigentlich zB auf den beitrag vor meinem

der kommentar zu meinem algo war ja auch völlig neutral und so, das wollte ich gar nich anzweifeln

ich bin sogar am überlegen ob ich es ermögliche, dass der Nutzer selbst ne jar oder ne .class angeben kann, in welcher er nen eigenen Parser unterbringt. Und im Programm kann er wählen zwischen dem langsamen CYK-Algorithmus oder seiner eigenen Variante Fänd ich n fetziges Feature, auch wenns gar nich gefordert wird, aber zumindest wird das Programm dann nur noch attraktiver

 

[Der Müde Joe]

Hab jetzt nicht alles gelesen.. aber

>ich soll so eine Art programmierbaren Taschenrechner programmieren...

Mit diesem Antlr code:
http://www.java-forum.org/java-basi...er-matheaufgaben-zu-erstellen.html#post435758

wurde dieses Programm erstellt (folgt)

ach...mist...100KB beschränkung...such mir kurz einen Link

EDIT:
des sollte er sein
http://nicolas.baumgardt.ch/content/calc/binaries/Calculator.jar

 

[DaDave]

cool Danke für den Tipp...denke ich werde dann Antlr nehmen!

Danke für eure Hilfe

 

[Landei]

Schau dir den Shunting-Yard-Algorithmus an, der macht aus Infix-Notation einen Stack mit Postfix-(oder Umgekehrt Polnische Notation)-Notation, also:
(a + b) * (c + d) wird zu a b + c d + *, Klammern fallen alle weg, und man kann dann ganz einfach von links nach rechts durchrechnen...