Mathe-Parserbau mit unterschiedlichen Zahlen-Typen
-
otze schrieb:
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:
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.
Wenn die Algos alle so toll sind und ich diese Algos anwende, dann sollte mein eigener Parser auch nicht viel langsamer sein als der eines Generator. Der Nebeneffekt einer Eigenentwicklung kann sein, dass man lernt besser mit der Programmiersprache umzugehen, in der man den Parser implementiert.
Und die Denkweise die man benötigt um eine Programmiersprache zu beherrschen ist ja gerade das A und O eines Compilers. Was bringt mir ein toller Compiler, der eine Sprache übersetzen kann, mit der niemand arbeiten will?
Und man lernt definitiv nicht was eine gute Programmiersprache ist wenn man nur Bücher über sie liest und deren Grammatik anguckt. Die Denkweise lernt man nur indem man etwas programmiert und wenn es nur der immer gleiche Parser ist - nur in den Konzepten einer anderen Sprache konzipiert.
Eine Sprache mit einem Generator erstellen, die einem selbst gefällt - das kann jeder. Aber eine Sprache zu entwickeln, die auch noch anderen gefällt und die produktiv einsetzbar sein soll, da sieht das schon ganz anders aus.
Und Generatoren müssen auch entwickelt und verbessert werden. Wer soll das machen wenn niemand weiß wie man einen Algo optimal in einer Sprache implementiert?
-
Du wolltest dir doch ein Buch über Compilerbau zulegen. Ich wette, wenn du das durchgearbeitet hast, wirst du unsere Sichtweise zu den handgeschriebenen Parsern besser nachvollziehen können.
-
Antoras, lass dich nicht von deiner Sache abbringen. Sicherlich ist ein Buch über Compilerbau nötig, um die Theorie zu verstehen (von dem bekannten "Dragonbook" von Avo/Ullman kann ich dir aber nur sagen: der ist staubtrocken!), einen Lexer/Parser sowie einen kleinen Compiler sollte man aber mal selber implementiert haben (so wie du ja auch schreibst: um die Sprache und die Hintergründe des Programmierens besser zu verstehen).
Meinen ersten Compiler habe ich vor ca. 20 Jahren zuerst in Assembler und dann später in C (auf dem Amiga) erstellt und ich bin immer noch stolz darauf (und ich denke, du bist bzw. wirst es dann auch sein).
Bzgl. der Compilergeneratoren (insb. yacc) kann ich nur sagen: grauenhaft, was der an C-Code erzeugt.
Ich hoffe, die Leute, die den yacc hier immer wieder vorschlagen, sind nicht die gleichen, die auch sagen: "goto ist böse" -)Sicherlich sind LR-Grammatiken allgemeingültiger als LL-Grammatiken, dafür lassen sich aber auch aus letzterem einfacher Parser generieren. Insbesondere bei Spracherweiterungen müssen bei den Compilergeneratoren komplett neue DFA bzw. Aktionstabellen aufgebaut werden (während bei den Top-Down-Parsern einfacher lokale Änderungen vollzogen werden können).
-
Th69 schrieb:
Bzgl. der Compilergeneratoren (insb. yacc) kann ich nur sagen: grauenhaft, was der an C-Code erzeugt.
Ich hoffe, die Leute, die den yacc hier immer wieder vorschlagen, sind nicht die gleichen, die auch sagen: "goto ist böse" -)Stichwort: tablen-driven vs directly programmed. Auch ein Grund, warum man von Hand nie die Performance eines generierten Parsers erreichen wird.
Sicherlich sind LR-Grammatiken allgemeingültiger als LL-Grammatiken, dafür lassen sich aber auch aus letzterem einfacher Parser generieren. Insbesondere bei Spracherweiterungen müssen bei den Compilergeneratoren komplett neue DFA bzw. Aktionstabellen aufgebaut werden (während bei den Top-Down-Parsern einfacher lokale Änderungen vollzogen werden können).
*klick* *1SekundeWarten* *neuerParserFertig*
-
Auf die pure Geschwindigkeit kommt es doch heutzutage gar nicht mehr so an. Wart-/Erweiter- und Lesbarkeit sind da oft wichtiger.
Und die eingesetzte Programmiersprache macht auch noch mal einen Unterschied. In Java brauche ich mir dank des Runtime-Compiler der IDE und wegen des Sprachdesigns um so was erst recht keine Gedanken mehr machen.life schrieb:
Ich wette, wenn du das durchgearbeitet hast, wirst du unsere Sichtweise zu den handgeschriebenen Parsern besser nachvollziehen können.
Vielleicht hast du recht. Aber bis dahin hab ich dann bestimmt auch schon meinen eigenen Parser geschrieben und kann den Aufwand und die Geschwindigkeit eines handgeschriebenes Parsers nicht nur an der Theorie sondern auch an der Praxis beurteilen...
-
Warum sollte man sich generierten Code durchlesen wollen? Wart- und Erweiterbarkeit ist über die Grammatik für den Generator gegeben. Diese sollte man natürlich dann lesbar gestalten.
Denk einfach mal an einen C++-Compiler. Interessiert es dich da, ob der generierte Assemblercode lesbar ist oder nicht? Würdest du Geschwindigkeitseinbußen in Kauf nehmen, nur damit dein Compiler Assemblercode generiert, der deinen Schönheitsansprüchen gerecht wird?
Btw: Ich gehe mal davon aus, dass du den Parser zu Übungszwecken bzw. aus Spaß an der Sache schreibst. Dagegen ist natürlich nichts einzuwenden.
-
Antoras schrieb:
Wenn die Algos alle so toll sind und ich diese Algos anwende, dann sollte mein eigener Parser auch nicht viel langsamer sein als der eines Generator. Der Nebeneffekt einer Eigenentwicklung kann sein, dass man lernt besser mit der Programmiersprache umzugehen, in der man den Parser implementiert.
Der Punkt ist, dass du den Algorithmus sehr einfach implementieren kannst. Ein LR(1) Parser ist ein Stack der die Zustände speichert, eine Aktionstabelle, die angibt, was bei einem bestimmten Lookahead in einem Zustand für eine Aktion ausgeführt werden soll (nächstes zeichen lesen oder Regel reduzieren), sowie einer Zustandsübergangstabelle, die angibt was nach dem nächsten gelesenen Zeichen bzw der Reduktion für ein Zustandsübergang auf dem Stack stattfindet. Trotzdem kannst du schon primitivste Sprachen nicht mit nem LR(1) Parser von Hand implementieren. Das was der Parser braucht ist eine bestimmte Form der Sprachanalyse, die die Zustände und die möglichen Aktionen berechnet. Schon Sprachen mit 5 Regeln können dabei >20 Zustände haben, und jeder Zustand hat so viele Tabelleneinträge für Aktionen(und Zustandsübergänge), wie es mögliche Eingaben gibt.
Und sowas macht man nicht von Hand. Das ist witzlos. Sowas macht man an der Uni um die Theorie zu verstehen. Da nimmt man kleine Beispielsprachen die aus den Zeichen "abc" bestehen und maximal 4 Buchstaben lang sind und 5 grammatikalische Regeln haben. Und die Parsetabellen brauchen dann auch schon 2-3 Seiten für die Konstruktion.
Und die Denkweise die man benötigt um eine Programmiersprache zu beherrschen ist ja gerade das A und O eines Compilers. Was bringt mir ein toller Compiler, der eine Sprache übersetzen kann, mit der niemand arbeiten will?
Zusammenhang? Natürlich schreibt man einen Compiler für eine Sprache von der man glaubt, das sie nützlich ist. Aber das hängt doch nicht davon ab, ob ich mich zum Sklaven mache und nen Parser von Hand implementiere. Und Programmierpraxis brauchste eh genug um einen Compiler zu schreiben. Der Parsergenerator nimmt dir doch nur einen verschwindend geringen Teil ab. Die Sprache ordentlich definieren musst du immer noch, und was du mit dem geparsten Code machst, regelt der Parser auch in keinster Weise. Wenn du nichts weiter machen würdest, ättest du ein Programm, dass angibt, ob eine Eingabe gültig ist doer nicht. Super. Sehe jetzt nicht, wo man dort verlernt, eine Programmiersprache zu beherrschen.
Und man lernt definitiv nicht was eine gute Programmiersprache ist wenn man nur Bücher über sie liest und deren Grammatik anguckt. Die Denkweise lernt man nur indem man etwas programmiert und wenn es nur der immer gleiche Parser ist - nur in den Konzepten einer anderen Sprache konzipiert.
Bullshit. Was du behauptest ist grad: "Wenn man weiß, wie man ein Auto fährt, kann man auch eins selber bauen".
Was interessiert mich, wie C funktioniert, wenn ich eine funktionale Sprache implementiere? Ich kann der totale Guru für imperative Programmiersprachen sein und eine unglaublich schlechte funktionale Sprache definieren. Umgekehrt kann ich ein Guru in funktionalen Sprachen sein und Haskell2.0 definieren, ohne ein tiefes Verständnis für C zu haben - dann sieht der Compiler halt scheisse aus und ist fast komplett aus tools generiert.
Sprachdesign lernt man auch nicht aus Verwendung einer Sprache. Aus der Sprachverwendung lernt man nur, was einem nicht gefällt. Dann implementiert man den Parser und merkt: "Ohh, das ist ja notwendig, weil der Parser sonst 10 Jahre zum compilieren braucht". Diese Erkenntnis erhält man aber nicht durch Sprachanwendung. Sprachanwendung hilft einem dann dabei zu verstehen, ob die eigene Sprache überhaupt so wie gedacht funktioniert. Vielleicht ist C "mit vielen neuen Features" doch nicht so pralle wie gedacht, weil die neuen Features fiese Wechselwirkungen haben. Das ist aber aus der Sprachverwendung von C nicht vorher herauszufinden.Eine Sprache mit einem Generator erstellen, die einem selbst gefällt - das kann jeder. Aber eine Sprache zu entwickeln, die auch noch anderen gefällt und die produktiv einsetzbar sein soll, da sieht das schon ganz anders aus.
Da stimme ich dir zu. Aber einer guten Sprache ist egal, wie ihr Compiler generiert wurde. Und ein guter Programmierer wird selbst eher zu yacc greifen, als einen Parser von hand zu schreiben, weil er diese Fingerübung (und nichts anderes ist das) nicht mehr braucht.
-
otze schrieb:
Und ein guter Programmierer wird selbst eher zu yacc greifen, als einen Parser von hand zu schreiben, weil er diese Fingerübung (und nichts anderes ist das) nicht mehr braucht.
und ich dachte je älter desto häufiger wird etwas neu gemacht
imo um ein guter programmierer zu werden sollte man diese übung schon mal gemacht haben
-
@life
Stimmt, es macht eigentlich keinen Sinn sich generierten Code angucken zu wollen.@otze
Die Hälfte von dem Zeugs, das du geschrieben hast hab ich nicht verstanden. Ich werde mir jetzt erst mal ein wenig Theoriewissen aneignen, dann kann ich das ja immer noch aufgreifen, wenn es dann noch was aufzugreifen gibt...
