libphorward 0.22

Langsam, aber stetig tut sich etwas bei meiner hobbymäßig weiterentwickelten C library libphorward, die auch als Phorward Toolkit, Phorward Foundation Libraries oder inzwischen auch einfach nur noch als The Phorward library bezeichnet wird.

Irgendwie scheine ich ein wenig mehr Disziplin dort hinein bekommen zu haben. Das liegt zum Teil daran, dass sich etwas bei UniCC getan hat, aber auch weil die Library inzwischen eine feste Basis hat, die nur noch geringfügig geändert und erweitert, aber nicht mehr komplett verworfen oder bereinigt wird. Leider ist immernoch nicht ganz genau klar, was der exakte Zweck der Library oder des Toolkits nun wirklich sein soll. In der Dokumentation dazu steht inzwischen folgender Abschnitt unter dem Titel “Intention behind this library”:

The cornerstone for this library was laid in 2006 during some experimenting with several algorithms and their implementation. It rapidly turned out to become a general purpose library serving as the base toolchain for several, mostly unfinished software projects which had their origin at J.M.K S.F. Software Technologies, which was later renamed to Phorward Software Technologies.

The library was then released to the public in 2011, together with the open source parser generator UniCC. Since then, it was gradually extended to newer and more enhanced features, mostly on tools relating to parser and compiler construction, but also features already known from other projects and remastered in a more generic and powerful way.

The final destination of the Phorward library is not entirely clear yet. For now, it mostly serves as a kind of playground for different projections, but it is also used by the UniCC parser generator and the meanwhile discontinued RapidBATCH scripting language as its foundation library.

Aber die Version 0.22 formiert sich langsam, und hat einige Neuerungen zu bieten, wie man dem Changelog detailliert entnehmen kann…

Phorward BNF

Das Endprodukt der zahlreichen Überarbeitungen in der Parsing Library, die bereits 2012 innerhalb der libphorward begonnen wurde, ist nun wieder ein neue Grammatik-Beschreibungssprache, die nun den offiziellen Namen PBNF trägt. Diese ähnelt der von pynetree und bis libphorward v0.21 verwendeten BNF-Sprache, hat aber eine deutlich vereinfachte Syntax, die auch UniCCv2 verwenden können soll.

Hier das vielfach verwendete 4-function-calculator Beispiel:

AST-Knoten werden jetzt mit dem = oder := Operatoren definiert.

Command-line tools

Die command-line tools pregex, plex und pparse sind jetzt einheitlich und flexibel nutzbar:

Und dann ist auch noch die Doku verbessert worden. Ich denke in Kürze ist es soweit, das v0.22 offiziell released wird, und es geht mit v0.23 weiter… bis hoffentlich bald, v1.0?

GLR parsing

Update 24.02.2018: Das was ich hier vorher geschrieben hatte war totaler Murks. Jetzt wälze ich erstmal nochmal die Paper dazu und dann sollte ich das nochmal ganz neu aufrollen…

So mal wieder nach längerer Zeit ein neues Posting hier. Muss mal wieder ein paar Gedanken sammeln. Beschäftige mich seit ca. zwei Wochen nun endlich mal mit GLR Parsern, obwohl ich in dem Buch Parsing Techniques von Grune und Jacobs, welches ich schon seit einiger Zeit sporadisch wälze, noch gar nicht in dem Kapitel angekommen bin (zzt. Kapitel 7.2 auf Seite 210, von ca. 640 Seiten). Aber das Parse-Verfahren habe ich mir schon mehrfach angeschaut, es aber nie wirklich umgesetzt.

Aber für die Umsetzung erstmal ein wenig Forschung betrieben…

…und einen (eigenen!) Algorithmus aufgebaut…

…der auch direkt unter Verwendung eines Graph-structured Stack arbeitet. Ich finde bei diesen Informatikbüchern ja immer interessant, dass manche Sache sehr theoretisch behandelt werden. Da wird dann einfach mal der komplette Parse-Stack kopiert und nach einem missglückten Shift dann komplett verworfen. Naja, wenn man das ganze implementieren will, noch dazu in einer Programmiersprache ohne Garbage Collection, dann kopiert man sicherlich nicht erstmal alle Element eines dynamisch allokierten Stacks und deren dynamsiche Stack-Elemente, um diese dann einen Shift später wieder frei zu geben. Mega-Ineffizient.

Naja, und nachdem ich zuerst dachte, es könnte auch klappen, wenn man den Lookahead global hält, wurde ich eines besseren belehrt, denn das geht (rein logisch gesehen) nicht. Es scheint aber so ungefähr zu funktionieren, wie hier, nur das da momentan noch das Stack merging fehlt (zusammenführen mehrerer Stack-Stränge bei einem gemeinsamen Shift). Dazu muss ich aber erstmal noch ein bisschen forschen und testen.

Was es jetzt noch zu lösen gilt (und wo warscheinlich die meiste arbeit drin steckt):

  • Einen eindeutigen (den besten?) Syntaxbaum aus den (bei ambigen Grammatiken dann mehrpfadigen) Parse-Graphen erzeugen
  • Effiziente Garbage Collection
  • Lookahead-Caching bzw. geht das nicht doch mit einem Lookahead?

Bin mal gespannt…

Drafting UniCC v2

Ich denke, das ist die beste Lösung.

Sogar UniCC v1.3 nimmt langsam immer mehr Gestalt an, sogar Features kommen hinzu. Alles Features, die zwar für UniCC 1.x nicht mehr tragend sind, aber deren Ergebnis in UniCC v2 mit wenig Anpassung direkt nutzbar sein werden.

Trotzdem, die letzten Tage waren Scheiße. Weil ich das alles mache um ein Projekt von der Arbeit hoffentlich nach vorne zu bringen, oder wenn ich Pech habe wird es komplett eingestampft.

UniCC ist eigentlich ein zu Code gewordenes Stück meines Lebens. Ursprünglich wollte ich nur ein Tool haben, um RapidBATCH 6 zu entwickeln. Dann wuchs es immer mehr aus. UniCC sollte dann den Parser Generator anagram nacheifern. Dann kamen immer mehr Ideen, Features, Pitfalls, krankes Zeug hinzu. Eigentlich alles quatsch, fand ich damals aber geil. UniCC ist meiner Meinung nach sogar besser als anagram geworden, wenn auch ohne IDE, dafür aber mit noch mehr Flexibilität. Diese Flexibilität bricht ihm auch letztendlich das Genick. Zu viele Features, zu viele Bugs. Lieber einfach, schlank und straightforward. Und eine halbe Konkurrenz zu ANTLR, als GLR multi-target language Paradigma? Das wäre toll. Man wird ja wohl noch träumen dürfen…

UniCC v2 sollte auf der Codebasis der pparse-Erweiterung der libphorward basieren und die Code-Generierung vom UniCC v1 beinhalten. Und einen direkten Interpreter für Parser beinhalten, um Grammatiken sofort zu testen. Das wäre ein finaler Parser Generator.

Hier geht’s zum UniCC v2 Wiki-Doodle…

Parsergeneratoren – Dilemma?

Ja…wohin nun?

Da haben wir den Salat! Einmal den UniCC gepuschelt, schon fragt man sich, warum man den ganzen aufwand der letzten Jahre getrieben hat, einen Parser Generator (und zwar exakt denselben Algorithmus) in die libphorward einzubauen.

Und dann stellt man auch wieder fest, das gewisse Java-Werkzeuge aus dem Bereich (okay, in dem Fall ALL(*)) noch besser sind… ach kein Plan.

A step Phorward.

Manchmal ist es so, dass man Dinge mal einige Zeit zur Seite legt, bevor man damit wieder weitermacht. Letzte Woche war es bei mir wieder mal soweit, die etwas angestaubten Spielsachen der alten Zeit wieder rauszukramen… meine private Software ;). Da ist ja wirklich viel passiert die letzten, ja man kann sagen 10 Jahre, und dennoch gab es nicht wirklich was neues.

Und doch, es macht mir immernoch Spaß. Zumindest es in einer gewissen Weise auch zu einem Ende zu bringen oder sich vielleicht auch von manchen Dingen zu trennen, an denen man sehr lange festgehalten hat, wo man aber letztendlich keine weitere Zeit mehr reinstecken möchte oder auch sollte.

Jedenfalls hat meine Website phorward-software.com ein Update erfahren… es gibt jetzt dort einen aktualisierten Projekte-Bereich für die Projekte phorward, pynetree, JS/CC und UniCC.

  • Vor allem an phorward (libphorward, bzw. das Phorward Toolkit) habe ich immernoch Bock weiterzumachen, da es für mich die einzige Möglichkeit ist, weiterhin was in C zu coden und diese Library wirklich alle Themen abdeckt, die ich persönlich super interessant finde. Die libphorward ist ja quasi mein eigenes Steckenpferd einer libmega (Insider wissen, was gemeint ist!) die richtig geile C-Funktionen bereithält (plist, pstack, pstr), und noch dazu add-ons für reguläre Ausdrücke (pregex), Lexing (plex), Parsing (pparse) und sogar virtuelle Maschinen (pvm) bereitstellt. Ursprünglicher Zweck dahinter war es immernoch, einmal ein RapidBATCH damit neu zu entwickeln. Das steht aber weiterhin noch in den Sternen.
  • pynetree ist ja das im letzten Jahr gestartete Projekt einer Python-Parser-Bibliothek mit linksrekursiven Grammatiken, die durch einen Top-Down-Packrat-Parser geparst werden, und sich gemeinsam mit phorward eine eigene TBNF-Sprache teilt. Hier wird auf jeden Fall noch weitergemacht!
  • JS/CC, der JavaScript-Compiler-Compiler, den ich bereits 2007 veröffentlich habe, hat neue Freunde gefunden. Er wird von mir nicht mehr weiterentwickelt oder verfolgt, scheint aber durch die Programmierer Andrew Brobston und Sergiy Shatunov eine gelungende Anbindung an Node.JS gefunden zu haben und wird in einem ganz anderen Rahmen als ursprünglich gedacht weiterentwickelt. Finde ich aber gut, immerhin ein Open Source Projekt welches von Menschen gebraucht, genutzt und sogar Weiterentwickelt wird. JS/CC wird jetzt unter jscc.brobston.com, respektive bei GitHub unter https://github.com/abrobston/jscc weiterentwickelt.
  • UniCC, das eigentlich als “universeller Parser Generator” gedachte Vorzeigeprojekt von mir vor inzwischen auch schon wieder 4 Jahren wird jetzt mehr oder minder eingestampft. Es erfolgt jetzt noch einmal ein Update des Benutzerhandbuchs sowie eine komplette Neu-Lizenzierung der Software unter der BSD-Lizenz, dann wird sie freigelassen. Immerhin: Der UniCC compiliert nach wie vor mit der aktuellsten libphorward, die als Unterbau fungiert. Einziger mir bekannter Einsatz dieses Tools ist das Projekt impact bei MEGA, dessen gesamte Formelsprache in UniCC entwickelt worden ist, und immerhin sogar auf 8 verschiedenen Architekturen läuft.

Alles in allem Plane ich auch, die Webseite unter phorward.info nochmal neu aufzusetzen, warscheinlich als ViUR Projekt und auch mehr mit dem Open Source Hintergedanken. Sozusagen als “mein Software Blog”, ohne es weiterhin auf dieser kommerziellen Schiene, auf der Phorward Software ja ursprünglich aufbaute, zu fahren. Da ist nämlich nichts mehr.

Coding parsers…

…wird mit der libphorward jetzt immer geiler! Seit gestern gibts ein neues README-File mit schönem Demoprogramm und neuer Featureliste… damit mal Tacheles gesprochen wird, wozu das Ding eigentlich da ist:

Schneller kann man keinen Parser definieren, ausführen und den Parsebaum als Ergebnis sehen… und alles direkt im C-Code!

Alleinstellungsmerkmal?? 🙂 I hope so…

Schönere Grammatik ;)

Soo die libphorward hat jetzt auch eine schönere Grammatik für ihre BNF-Sprache. Die bereits beim self-hosting Prozess verwendete Grammatik sieht jetzt so aus:

Kann sich doch eher sehen lassen, oder? Die $-Zeichen definieren Terminaldeklarationen, es sind auch anonyme Terminaldeklarationen erlaubt, und Inline-Terminals werden jetzt über einen Pattern-Matching-Mechanismus auf existenz geprüft, so dass diese nicht extra definiert werden müssen (so wie % und  ;).

Ausserdem ist die Entwicklung jetzt erstmal nach Bitbucket umgezogen, weil Sourceforge der Meinung war, meinen Benutzernamen mit dem Namen eines indischen Java-Entwicklers, mit dem ich nichts gemeinsam habe, zu verlinken, weil da irgendein blöder Bug drin ist. Ausserdem benutzen wir Bitbucket auch bei mausbrand, und bin damit bisher sehr gut gefahren :).

libphorward selfhosted!

Seit Freitag ist die libphorward nun self-hosted.

Was heißt das nun konkret? Nun es hört sich ein wenig an wie autofellatio, ist aber noch viel, viel geiler! Die libphorward wurde nun um ein weiteres Modul, das Programm ppgram2c  erweitert.

ppgram2c ist ein Code-Generator, welcher eine Backus-Naur-notierte Parser-Beschreibung aus einer Datei einliest und anschließend als C-Programm wieder ausgibt, also sozusagen die Funktionsaufrufe, die nötig sind, um die gewünschte Grammatik direkt in C mit dem libphorward Funktion des parser-Moduls zu definieren.

Aus der BNF-Notation für die eigene BNF-Sprache mit der Syntax:

Ich muss gestehen, das diese Grammatik noch recht unschön definiert ist, was aber daran liegt, das noch ein paar Bugs vorliegen (equal, percent und semicolon mussten wegen Mehrfachverwendung als eigene Symbole definiert werden, sollte später so nicht sein).

Aus dieser Grammatik erzeugt ppgram2c nun folgenden C-Code (mit ein wenig awk-Hokuspokus drumherum):

Also wer’s nachtesten will, es ist

ppgram2c –indent 1 src/parse/gram.syn

was hier im Hintergrund aufgerufen wird. Es erzeugt das meiste von dem Code above.

OK nun zum Highlight des ganzen: Der Parser parst seine eigene Grammatik und erzeugt den Code für sich selbst. Folglich konnte der Parser erfolgreich durch sein eigenes Duplikat ersetzt werden. Die nachfolgenden Parser der libphorward sind allesamt Klone von sich selbst, also werden mit sich selbst geparst und dann selbst Bestandteil der Toolchain. Diesen Mechanismus nennt man im Compilerbau bootstrapping, und wurde bisher bei all meinen Compilerprojekten erfolgreich umgesetzt, also JS/CC, UniCC (welcher min_lalr1 benutzt) und nun auch der libphorward.

Damit wurden der rekursive-absteigende Parser der libphorward sowie die handgeschriebene LALR(1)-Grammatik hinfällig, da sie durch ihren eigenen Klon ersetzt wurden. (Hoffentlich hat der Klon keinen Fehler…)

Damit ist die libphorward selfhosted (selbst-gastgebend) und kann sich selbst compilieren (zumindest den Parser ;-)). Was nun folgt ist pure geile Scheiße! 😀

Man liest sich…

libphorward on the way!

Obwohl ich ja nur noch privat C programmiere, mache ich es inzwischen sogar wieder viel lieber als es zu Zeiten von MEGA noch war.

Tja, was macht man so als Nerd wenn man Freitagnacht wieder mal vorm Rechner sitzt weil man keine Freunde hat die mit einem Biertrinken gehen? Richtig, man trinkt Bier vorm Rechner und codet fleißig an seiner Software, die eh keiner braucht.

Naja jedenfalls hat die libphorward in letzter Zeit echt ziemlich krasse Sprünge gemacht, und mausert sich von der “Phorward Foundation Library” zum “Phorward Toolkit”. Eine universelle C-Bibliothek, die vor allem die Features

  • Erweiterte Datenstrukturen (parray, plist)
  • Erweiterte Stringfunktionalitäten
  • Reguläre Ausdrücke (pregex, plex)
  • Parser (zzt. ppgram)

unterstützt. Derzeit bin ich daran, die libphorward vor allem eines zu machen: Einfacher! 🙂

Ich bin jetzt auch von den negativen Gedanken bzgl. des Rpa/tk weg, weil ich das eh nicht mehr toppen kann. Daher: Einfachheit, Flexibilität, Features.

Das Resultat kann sich sehen lassen, es geht richtig gut voran momentan. Regex Library überarbeitet, so dass man damit (ENDZIEL!!!) JavaScript-kompatible Regular Expressions bauen kann sowie Lexer.

Das Parser Modul wird jetzt soweit gehackt, bis es sich selbst als Parser compiliere und ausführen kann (bootstrapping!) und dann gucken wir mal was draus wird.

libphorward_2014-11-15In jedem Fall wird das Teil immer geiler. Und das Beste: Der UniCC Parser Generator, der zwar nicht mehr weitergepflegt wird, wird damit immernoch am Leben gehalten. Musste zwar schon viel umbauen aber er lebt weiterhin und compiliert!

Was war heute sonst noch?

  • Die Ruhrcon 7 Reg eröffnet
  • Interstellar geschaut… kein so guter Film. Eigentlich ne coole Story, viel zu viel Amerikanerdreck, Schnulze und Unlogik. Naja nicht nochmal.

Naja. Was solls. Interessiert ja eh keinen, mein Bier ist leer und ich geh jetzt pennen, damit ich morgen ausschlafen kann und dann ab schön nach Hengsen 🙂 (my Graceland!).