State Machine Compiler für 8-bit AVRs?

Am 21.09.2019 um 11:29 schrieb Andreas Weber:

Meine Lexer und Parser habe ich bisher immer selbst geschrieben, das ist IMO kein Hexenwerk. C verfügt ja bereits über Konvertierungsroutinen, und wenn sich beide Seiten an diese halten, und sinnvolle Trennzeichen zwischen zwei Werten und Records einstreuen, wo sollten dann Probleme herkommen?

DoDi

Am 21.09.19 um 12:26 schrieb Hans-Peter Diettrich:

Dann hast du bis jetzt vielleicht keine komplizierte Grammatik gehabt.

Dazu müsste man beide Seiten selbst in der Hand haben. Sobald du an ein bestehendes Protokoll ran musst, kann man sich das nicht mehr aussuchen.

-- Andy

Am 21.09.19 um 19:09 schrieb Andreas Weber:

Eine komplizierte Grammatik ist in jedem Fall kompliziert, egal welche Werkzeuge man nutzt.

Wenn man das Prinzip verstanden hat, ist der Aufwand, um eine formal korrekte Definition für einen Parser-Generator zu schreiben oder den Parser gleich selbst zu schreiben, nicht sooo unterschiedlich. Das gilt umso mehr dann, wenn der vom Generator erzeugte Codestil nicht recht in die verwendete Umgebung passt und man auch noch eine Interface-Schicht bauen müsste.

Hergen

Am 21.09.2019 um 19:09 schrieb Andreas Weber:

Auch bei komplexeren Grammatiken ist das kein Hexenwerk.

Je nach dem, was für ein Protokoll das ist, will man da auch sowas wie Fehlerbehandlung haben. Wenn also irgendwo ein Trennzeichen verschluckt wird, soll der Parser sich davon erholen können und nicht nur "parse error" sagen und bis zum nächsten Powercycle bockig sein. Das in einer Grammatik auszudrücken ist zwar möglich, aber umständlich. Mit einem eigenen Parser hat man da durchaus einfachere Möglichkeiten (und sei es sowas wie "mit dem eigenen Parser die Paketierung zerlegen, und die Paket-Payloads dann mit was generiertem").

Stefan

Hallo Hergen,

Am 21.09.19 um 20:37 schrieb Hergen Lehmann:

Warum versuchen mich hier Leute davon zu überzeugen KEIN Werkzeug dafür einzusetzen?

Das fühlt sich für mich an als ob mir jemand erklärt: "Verwende doch Assembler, mach BRAUCHT keinen C Compiler. Das geht auch alles so. Die libc braucht man nicht, kann man auch in Assembler machen." Ich hoffe wir müssen an dieser Stelle nun keine Diskussion führen, warum man heute eben nicht mehr Assembler schreiben sollte ohne einen wirklich, wirklich guten Grund.

Ich habe über 10 Jahre die Parser selbst geschrieben. Mit Ragel kann ich mir den Zustandsautomaten visualisieren lassen (graphviz dot) was die Entwicklung deutlich vereinfacht und gleich noch als Dokumentation taugt. Die Lesbarkeit und damit die Wartbarkeit für andere ist IMHO auch deutlich höher.

Klar. In dem von mir angesprochenen Fall integriert sich das aber super in avr-gcc und AVR libc.

Ich fühle mich an die Diskussion mit Studenten erinnert, dass man git/mercurial/subversion gar nicht braucht, weil man ja die Order einfach wegkopieren und umbenennen kann.

Danke für deine Meinung, Gruß Andy

Am 21.09.2019 um 19:09 schrieb Andreas Weber:

Wäre C kompliziert genug?

Anscheinend werden nur LL(1) Grammatiken akzeptiert, und für die läßt sich ein Lexer von Hand leicht erzeugen. Bei wirklich komplizierten Grammatiken sind ggf. Umformungen notwendig, die nur jemand durchführen kann, der sich mit Grammatiken so gut auskennt daß er weiß, wie ein Parser funktioniert und ihn entsprechend auch selbst schreiben kann.

DoDi

Vermutlich weil es denen zu komplex ist. :-)

Ich hab fuer solche Anwendungen auf Microcontrollern auch schon flex genutzt und wuerde es jederzeit wieder machen.

Vorteile: Sehr flexibel, es ist eine kleinigkeit da mal eben einen neues Kommando hinzuzufuegen.

Weil die nutzung so einfach ist, wenn man einmal damit umgehen kann, nutzt man es auch fuer Kleinigkeiten (z.B Debuginterface) wo man sonst eher denken wuerde: "Och, noe, dafuer bin ich jetzt zu faul"

Nachteile: Erzeugt ziemlich grossen C-Source. Das bekommt man von Hand bestimmt effizienter hin. Allerdings ist das bei den fetten Flash heutiger Controller kein Problem.

Nicht zwangslaeufig weil die sich ja auch mit dem verwendeten Generator auskennen muessen und ihn auch haben muessen.

Olaf

Am 21.09.19 um 11:29 schrieb Andreas Weber:

Den kannte ich noch nicht, danke für's Aufschlauen.

Mit dem guten alten yacc und seinen Nachfahren (bison) müsste es auch gehen. Links/rechts-rekursiv mit 1 token look-ahead. Hat bisher bei mir für alles gereicht.

Da kommt auch nur eine Matrix raus und eine function, die inputs entgegennimmt und an den passenden Stellen die Aktionen triggert.

Der yacc war übrigens ursprünglich nicht für den Compilerbau vorgesehen, sondern zum automatisierten Übersetzen von Zustands- Automaten in Weinberger-Arrays. Weinberger-Arrays sind so was ähnliches wie PALs, nur älter und nur maskenprogrammierbar.

Das ist der gleiche Weinberger, der für das W in awk steht. (Aho, Weinberger, Kernighan). Die ganze UNIX/C-Truppe bei AT&T waren eigentlich Halbleiterleute und Digitaldesigner. Unix und C waren nur "Abfallprodukte".

Gruß, Gerhard

Natuerlich! Die ganzen Programmierer sind nur Abfallprodukte der Hardwareentwicklung. Ich erzaehle denen das andauernd, aber sie wollen es einfach nicht akzeptieren. :)

Olaf

Kann ich dir nicht beantworten.

Was genau stört dich denn an der Ragel-Syntax bzw. was für Features hättest du gerne, die im Moment fehlen? Kannst du eventuell eine Beispielgrammatik teilen um zu illustrieren, wie du es im Moment (als Workaround) löst und was du gerne hättest?

Eventuell kommen dann bessere Tipps. Viele Grüße, Johannes

Wenn *das* stimmen würde, dann würde ich das gerne mal sehen. Denn eine vollständige, fehlerfreie C-Grammatik "von Hand" zu schreiben, ohne Werkzeugunterstützung, halte ich für so gut wie unmöglich. Insofern, wenn du das wirklich gemacht hast, würde ich das gerne von dir lernen. Deine Chance, dein Können unter Beweis zu stellen.

Meine persönliche Vermutung, die sich mit deinen bisherigen Äußerungen allerdings viel besser deckt, ist, dass das lediglich pures Geschwätz ist. Vermutlich hast du einen Parser für urgendein Subset von C geschrieben, der bei jeder minimalen Deviation im Codestil schon krachend auseinanderfällt.

C ist defintiv kein LL(1), das weißt du ja sicherlich.

Gruß, Johannes

Pascal-Compiler waren schon immer mit rekursivem Abstieg, und sogar der gcc war nur bis Version 3 yacc/bison-basiert und hat jetzt einen handgeschnitzten Parser.

Wenn's praktisch alle so machen, dann muss es wohl möglich sein; das mit dem leeren Geschwätz ist also ein Bumerang.

Dass man für ernsthafte Sprachen die Symboltabelle massieren muss, ist unschön, aber wirklich context-frei ist in der Praxis wenig.

Was ist foo *bar? Eine Variablen-Deklaration? Eine Multiplikation?

Ausführliche Diskussion in :

Gruß, Gerhard

Weil sie den C und C++ gemerged haben. Und C++ /hat/ keine wohldefinierte Grammatik mehr. Ist also wirklich schwierig, dafür einen Parser zu schreiben. Das sind unter anderem, nur für den Parser, etwa

Insofern stehe ich zu meiner Aussage und widerspreche, dass es "praktische alle" eben mit handgeschnitzten Parsern machen. Im Gegenteil, wenn du mal suchst:

Die Wenigsten schreiben also einen Lexer/Parser "von Hand". Noch weniger, wenn es keinen triftigen Grund dafür gibt (bei GCC ist wiegesagt C++ der Grund).

Ich habe ja schon geschrieben, C ist kein LL(1). Keine mir bekannte (nicht-esoterische) Programmiersprache ist LL(1), so nebenbei.

Gruß, Johannes

Deinem Geschwätz nach kommen mir Zweifel an Deiner Lernfähigkeit :-(

Hatte ich seinerzeit als "ToPas" bei SourceForge reingestellt.

Dein Vermutungslevel ist als unbrauchbar notiert. Vielleicht informierst Du Dich mal über den VisualBasic Discompiler zur Justierung Deiner Meinung.

Auch hier ist das Gegenteil der Fall. Mein Parser hat aufgedeckt, daß Microsofts Header zu Visual C nicht standardardkonform sind, ein Workaround wurde eingebaut. Dazu noch ein paar Erweiterungen für gcc.

Bis auf 1 Ausnahme ist C98 erstaunlicherweise LL(1), insgesamt also LL(2). Das Fehlen einer offiziellen LL-Grammatik sagt ja definitiv nichts über eine Sprache aus :-]

DoDi

Sehr gut. Endlich lieferst du mal was. Ich habe mal meine VM angeworfen und dein Meisterwerk getestet:

Danach nochmal neugestartet, nichtdeterminsitisch fliegt einem eine Access Violation schon beim BLOSSEN START des Programms um die Ohren. Gacker! Ist das eine neue Form nichtdeterministischer Programmierung? Wow, ich bin echt beeindruckt.

Aber zum Kernstück. Deinem Parser, der ja, wir errinern uns an meine ursprüngliche Aussage:

Keywords für dich, DoDi, zum mitschreiben: - vollständig - fehlerfrei

Okay, okay, das ist also die Messlatte. Siebenzeiler in C:

int foo(int y, ...) { int *x[12]; x[3] = x[9]; x[10] = *(&(*(x + 3))); "foo"; return 0; }

Einfach, oder? Das ist korrektes C. Na dann!

error translation_unit

Wer hätte das gedacht, DoDi? Dass es richtig schwer ist, eine fehlerfreie Grammatik hinzukriegen? Danke, dass du das schön bewiesen hast.

Das ist genau der Grund, warum man Parser Generatoren erfunden hat, weil es Leute gibt, denen aufgefallen ist, dass einem Menschen halt Cornercases oft durch die Lappen gehen. So wie dir.

Bestätigt, wolltest du schreiben. Siehe oben.

Ja sorry aber "VisualBasic Discompiler" ist offenbar so ein unbrauchbarer Suchbegriff, dass Google gleich sagt: "Showing results for Visual Basic Decompiler"

Ich habe also keine Ahnung, worauf du hinaus willst. Du aber offenbar auch nicht, sondern willst ja wohl nur von deinem Turbofail ablenken.

...das händische Schreiben korrekter, vollständiger Parser richtig schwer ist.

C ist also kein LL(1), richtig.

Immerhin, muss man dir zu Gute halten, hast du ausnahmsweise was geliefert, statt immer nur heiße Luft zu produzieren. Auch wenn es jetzt halt nicht dein Argument gestärkt hat, sondern exakt das Gegenteil bewiesen.

Gruß, Johannes

Wenn hier einer den Oberlehrer macht, dann du. Und er muss dir auch nichts liefern, du hast nichts bei ihm gekauft.

Wirklich bewiesen hast du garnix. Du hast ein paar Exotencompiler aufgezählt die einen Parsergenerator benutzen, aber die wichtigen Compiler, die jeder hernimmt, wie gcc oder clang benutzen rekursiven Abstieg. Und der gcc frisst dein Beispiel in einer halben Millisekunde, problemlos, bis auf ein paar Bemerkungen, dass das Beispiel nix Sinnvolles macht.

Pascal nimmt auch rekursiven Abstieg. Und da sind Bösartigkeiten wie das with-statement drinnen:

with record_variablenliste do begin ... end

und zwischen begin & end sind die Komponenten der records plötzlich keine rec.a und rec.b mehr, sondern einfach nur noch a und b. Wenn's zufällig globale a und b gab, dann gibt's die eben vorrübergehend nicht mehr. Bring das mal einem Parsergenerator nahe, wenn Variablen- namen eben zwischendurch für etwas völlig anderes mit möglicherweise einem anderen Typ stehen.

In Jensen-Wirth's Pascal, User Manual and Report (insgesamt ein beeindruckend dünnes Heftchen für seine Wichtigkeit) ist im Anhang die ganze Grammatik in BNF und die Blasendiagramme für den Parser drinnen.

Und das ganze UCSD-Pascalsystem konnte man auf einem Z80 mit AT-Floppies compilieren.

Ja, für den SCPI-Parser auf dem BeagleBoneBlack nehme ich schon den yacc/bison und gcc. Für jeden Topf den passenden Deckel.

Gerhard

Wenn jemand groß Sprüche klopft, wie einfach das doch alles von Hand sei, Lexer/Parser für komplexe Grammatiken zu schreiben (zum Beispiel der von C), und dann in der Praxis halt schon bei simpelsten Beispielen voll auf die Nase fliegt, dann ist das ja schon ein interessantes Ergebnis.

Klar muss er nichts liefern, hat er ja bisher auch nie. Sobald es konkret wird, immer schön kneifen. Typisch Schäwtzer eben.

Doch, dass der Parser, den DoDi geschrieben hat, eben nur (wie ich ursprünglich vermutet hatte) ein (beliebiges) Subset von C parst. Wenn du das bestreitest, kannst du es ja gerne selber ausprobieren.

Das sind keine Compiler, hast du die Links mal angesehen? Die erzeugen teilweise nur einen AST und sind Libraries.

Das ist *professionelle* Software. Mit hunderttausenden Personenstunden, die da reingeflossen sind, sowohl in clang als auch in gcc. Und ich habe ausführlich beschrieben, warum die das so machen -- sowohl clang als auch gcc parsen eben auch C++, für das es keine ausdefinierte Grammatik gibt (als Bonus gibt's bessere Diagnostics dazu). Insofern sind die als Beispiel *völlig* ungeeignet, denn es ging grundsätzlich darum, ob und wie schwierig es ist, Lexer/Parser von Hand zu schreiben.

Ohne Not schreibt *niemand* einen Parser von Hand, auch nicht gcc und clang. Und wenn man sich dazu entscheidet, ist das *weitaus* schwieriger, als einen Parsergenerator zu nehmen.

Ich weiß echt nicht, wieso du ständig mit Pascal anfängst, das hat mit dem Thema überhaupt nichts zu tun. Ich habe nie bestritten, dass Recursive Descent ein ordentliches oder geeignetes Parsing-Verfahren ist. Ich sage lediglich, dass das Schreiben eines Parsers von Hand RICHTIG viel schwieriger ist, als einen Parsergenerator zu nehmen und dass man deswegen dafür einen RICHTIG guten Grund (und viel, viel mehr Zeit) braucht. Und bin extrem skeptisch wenn sich jemand hinstellt und sagt "das hab ich schon gemacht, war ganz einfach". Weil >40000 Zeilen Code zu schreiben, nur fürs Parsing, ist eben NICHT einfach.

Ja, da gehe ich mit. Wenn es einen guten Grund gibt, klar, dann schreibt man sich seinen eigenen Parser. Damit kommen eine interessante Vorteile, aber auch eben einige gewichtige Nachteile mit. Aber grundsätzlich die Komplexität zu trivialisieren ist kein guter Ansatz.

Gruß, Johannes

Am 23.09.2019 um 14:15 schrieb Gerhard Hoffmann:

Du hast nur bewiesen, daß Du einen Compiler nicht korrekt installieren kannst. Dein Problem, wenn dann benötigte Dateien nicht gefunden werden.

Laß gut sein, ich laß ihn weiter in meinem Filter schmoren. Mir fehlt nur noch ein Filter für Antworten auf seine Trollereien.

Wobei ich mich frage, wie der C Preprozessor in einen generierten Parser eingebaut werden kann. Aber die Antwort kenne ich inzwischen schon, Johannes kann das latürnich ;-)

DoDi

Aaaaaaaahahahahahaha!

Ja, klar. Wenn Dateien nicht gefunden werden, versucht er mal auf Adresse 0x7 zuzugreifen und löst eine allgemeine Schutzverletzung aus. Ist klar, die Fehlerbehandung der Profis. Perfekte Erklärung!

Gott, du bist so armselig mit deinen dumm-dreisten Ausreden und ständigen Herumlügereien. Ekelhaft und widerlich.

Neeeeeeeeein oh neeeeeeein, die allerschlimmste Strafe von allen. In deinem Filter zu "schmoren". Jetzt entgehen mir deine altklugen Ratschläge also in Zukunft, ich bin untröstlich.

Dass du nicht mal in der Lage bist, einen Newsreader zu bedienen, überrascht sicherlich niemanden mehr.

Alles Liebe, Dein Johannes