Mathe-Parserbau mit unterschiedlichen Zahlen-Typen
-
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
-
SideWinder schrieb:
Wie, wo?
mal schauen, ob ich das jetzt spontan richtig hinkriege, häufig benutzen tue ich das feature nämlich nicht:
template<class T> void foo() { T::template bar<int>(); }machst du das nicht, steht dort:
T::bar<int>();und dann sind die "<" mehrdeutig.
@Volkard man muss sich sehr anstrengen, um aus LR(k) rauszukommen. Die umfassen ja den Großteil der kontextfreien Grammatiken. Und ich glaube, das es den Meisten auch schwer fällt, Kontextsensitive Grammatiken zu formulieren. Ich könnte es nicht :). Deine Sprache dort ist sicherlich auch komplett LR(1) oder könnte mit sehr wenigen Handgriffen LR(1) gemacht werden. Der Unterschied ist ja meist nur, ob man ein neues Keyword einführt.
-
@otze
Hast du einen Clown gefrühstückt? Wie soll dir das Template-Keyword an ganz andere Stelle helfen um eine Mehrdeutigkeit in der Syntax zu helfen? Abgesehen davon, dass ich sowas zum Ersten mal sehe.
-
Wie wärs mit: wenn vor einem Bezeichner "template" steht, dann ist die darauf folgende "<" kein Größer-zeichen?
Wüsste nicht, wo ich den Clown gefrühstückt habe.
Hier mal ein Link: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1528.html
geht zwar nur am Rande darum, aber da steht im zweiten Absatz: "The template keyword is only supposed to provide syntactic disambiguation"
//edit
Hier noch besser: http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/topic/com.ibm.xlcpp8a.doc/language/ref/keyword_template_qualifier.htm
-
Also ich hab mal die Beispiele ohne Template-Keyword compiliert und kommt das gleiche raus wie mit.
-
tipp: mach mal die Microsoftschen Compilererweiterungen aus. Benutz am besten den gcc mit --pedantic. Das nur so als weitere Lehre: was der Compiler annimmt, muss nicht richtig sein. Genauso, wie: was der Compiler ablehnt, muss nicht falsch sein(export templates).
-
Jemand der selbst nicht nachdenken will, sollte lieber nicht über Lehre sprechen.
Ausserdem funktioniert es trotzdem.
-
template<class T> void foo() { T::template bar<int>();//funktioniert T::bar<int>();//Fehler! //test.cpp|4|Fehler: expected primary-expression before »int«| //test.cpp|4|Fehler: expected »;« before »int«| //||=== Build finished: 2 errors, 0 warnings ===| } struct Bar { template<class T> static void bar(){} }; int main() { foo<Bar>(); }gcc 4.5.0
Offensichtlich denkst du nicht nach, darum ist das auch kein Problem, dass ich nicht lehren sollte. Überleg dir einfach mal selbst die Mehrdeutigkeit des "<".
//edit und woran machst du fest, dass ich nicht nachdenken will?
-
Ich hätte klug sein sollen, mein Mund halten und mit einen Grinsen.
Dein Fall ist einfach Specification Bullshit, der sich genauso verhält wie Template Argumenten in Templates:
std::vector<boost::array<int>> // >> ist ein Shift-Operator, nein heute sind zwei '>'Es muss keine Mehrdeutigkeit auf '<' bestehen.
In der C++ Spezifikation steht, dass das Template Keyword beim Funktionsaufruf optional ist. Falls du es angibst gehst du sicher, dass du die Templatefunktion aufruft, in diesen Sinn gibst also evtl Mehrdeutigkeiten auf vorhandene uberschriebene Funktionen. Später (in Bezug auf die Seitenzahl) gibt der Standard vor, dass bei den Fall eine Template Methode gemeint ist, diese nur mit Hilfe von des Schlüsselwort aufzulösen ist. Diese "ill-Formed" kann man Auflösen, wenn das Interesse besteht. Immerhin schafft es Microsoft Visual Compiler und Borland C++ Builder es auch ohne.
-
Ne, das stimmt so nicht. 14.2.4 bricht dir das Genick(und lässt dein Grinsen gefrieren):
When the name of a member template specialization appears [...]after a nested-name-specifier in a qualified-id, and the [...] qualified-id explicitly depends on a template-parameter but does not refer to a member of the current instantiation, the member template name must be prefixed by the keyword template. Otherwise the name is assumed to name a non-template.
(schnell abgetippt, sind also tippfehler drin...)
Beispiel dazu aus dem Standard:template <class T> void f(T* p) { //... T::adjust<100>();//ill-formed: < means less than T::template adjust<100>();//OK: < starts template argument list }Aber das war auch nicht kern meiner Aussage. Natürlich kann man das irgendwie auflösen, weil da simmernoch Kontextfrei ist. Aber nicht in einem LR Parser. Das muss manuell abgefangen werden. Und genau das ist der Grund, warum Compilerhersteller da kotzen.
-
Danke für den Beleg.
P.S: Ich vermisse die "member template specialization" in dein Zitat
-
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...
