# Parser-generator für mathematische Funktionen



## DaDave (27. Apr 2009)

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 (27. Apr 2009)

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


----------



## Wildcard (27. Apr 2009)

Was meinst du mit 'eine Art bytecode'?


----------



## DaDave (27. Apr 2009)

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 (27. Apr 2009)

DaDave hat gesagt.:


> 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 (27. Apr 2009)

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 (28. Apr 2009)

DaDave hat gesagt.:


> 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 (28. Apr 2009)

*@ 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 (28. Apr 2009)

diggaa1984 hat gesagt.:


> *@ 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 (28. Apr 2009)

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 (28. Apr 2009)

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 (29. Apr 2009)

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

Danke für eure Hilfe


----------



## Landei (30. Apr 2009)

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


----------

