Mathe-Parserbau mit unterschiedlichen Zahlen-Typen

life

Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.

Analog würde ich auch keine neuen Erkenntnisse erlangen, wenn ich ein Programm in Maschinensprache statt Assembler schreiben würde, sofern man weiß wie genau die Übersetzung Assembler->Maschinensprache aussieht.

volkard

life schrieb:

Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.

Kann man das begründen oder beweisen?

life

volkard schrieb:

life schrieb:

Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.

Kann man das begründen oder beweisen?

Weil ich, faul wie ich bin, keine Lust hätte selber nachzudenken, sondern stattdessen einfach die mir bekannten Grammatik->Parser Algorithmen von Hand nachspielen würde. Wenn man den Algorithmus aber schon vorher verstanden hat, bringt einen ein langwieriges von Hand nachspielen von Algorithmen rein garnichts.

volkard

life schrieb:

volkard schrieb:

life schrieb:

Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.

Kann man das begründen oder beweisen?

Weil ich, faul wie ich bin, keine Lust hätte selber nachzudenken, sondern stattdessen einfach die mir bekannten Grammatik->Parser Algorithmen von Hand nachspielen würde. Wenn man den Algorithmus aber schon vorher verstanden hat, bringt einen ein langwieriges von Hand nachspielen von Algorithmen rein garnichts.

Hmm. Aber dafür verlierst Du Flexibilität. Nichts, was man brauchen würde, wenn man nur C oder nur Pascal baut.

otze

volkard schrieb:

life schrieb:

Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.

Kann man das begründen oder beweisen?

Ja.

1. Jede halbwegs nützlich zu implementierende Sprache ist LR(k)
2. Effiziente LR(k) Parser basieren darauf, dass man die einzelnen Zustände vorher berechnet
3. Jede halbwegs sinnvolle Sprache hat mehrere 100 bis 1000 Parsezustände(C++ irgendwas über 5000)
4. LR(k) Kollektionen für einen einzelnen Zustand zu berechnen ist mehr als Mühsam.
5. Der Code für einen LR(K) Parser selbst ist dann eine Sache von 15 Minuten
=> macht absolut keinen Sinn.

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

volkard

otze schrieb:

volkard schrieb:

life schrieb:

Einen Parser von Hand zu implementieren würde mir keinen Mehrwert bringen.

Kann man das begründen oder beweisen?

Ja.

1. Jede halbwegs nützlich zu implementierende Sprache ist LR(k)

Ah, auf solche Axiome habe ich doch gewartet. Und damit ist der Fall auch schon erledigt.

otze

volkard schrieb:

Ah, auf solche Axiome habe ich doch gewartet. Und damit ist der Fall auch schon erledigt.

Naja, mit LL kriegste sofort Probleme, wenn du geschachtelte ifs mit optionalem else erlaubst. Das können die nämlich nicht(Nebenbei hat man bereits bei ll das selbe Problem, dass man da First und Follow Mengen berechnen muss um das effizient hinzukriegen. Also rettet einen auch ne ll-Grammatik nicht das Leben). LR ist die nächststärkere echte Obermenge zu LL. Alles was darüber geht wie earley oder CYK ist halt langsam. CYK kann man zwar super von Hand implementieren auch mit der Grammatik, aber das ist nicht Produktionstauglich, wenn man nicht grad eine echte kontextfreie oder sogar kontextsensitive Grammatik hat. Das ist der Unterschied zwischen O(n) und O(n^3). Benutzt man dann etwas nach der Bauart von Spirit, dann wird man sehr schnell richtig richtig langsam. Dann machts auch keinen Spaß mehr. Solch kleine Parser sind zwar für Sachen wie XML noch super von der Hand machbar, und es spricht nichts dagegen damit mal zu experimentieren, aber wenn man etwas wie nen Compiler schreiben will, dann sollte man direkt die richtigen Techniken verwenden, damit das Projekt nicht daran scheitert, dass sich der Compiler totrechnet, oder weil er am Ende die Grammatik einfach nicht parsen kann.

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.

Das Spannende an Sprachen sind die Grammatiken. Nicht die Parser. Da lernt man am Meisten, wenn einem yacc sagt, dass die Grammatik einen shift/reduce Konflikt hat und man die dann erstmal irgendwie umformulieren muss, damit das passt. Da lernt man auch, warum es in c++ das template keyword vor Funktionsaufrufen geben muss und warum bestimmte andere Sachen in der Sprache so gemacht wurden, wie sie jetzt sind(und warum C++ nicht LR(k) ist und warum deswegen die Compilerbauer fluchen). Die Algorithmen selbst sind dagegen total uninteressant, da sie auch nur das Ende einer langen Theorie darstellen.

Aber ich stelle mal die Gegenfrage: an welcher Stelle siehst du den Mehrwert?

SideWinder

otze schrieb:

Da lernt man auch, warum es in c++ das template keyword vor Funktionsaufrufen geben muss

Wie, wo?

template foo();

?

MfG SideWinder

volkard

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

otze

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.

Zeus

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

otze

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

Zeus

Also ich hab mal die Beispiele ohne Template-Keyword compiliert und kommt das gleiche raus wie mit.

otze

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

Zeus

Jemand der selbst nicht nachdenken will, sollte lieber nicht über Lehre sprechen.

Ausserdem funktioniert es trotzdem.

otze

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?

Zeus

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.

otze

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.

Zeus

Danke für den Beleg.

P.S: Ich vermisse die "member template specialization" in dein Zitat

Antoras

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?