Nun, da die Segelflugsaison inzwischen leider vorbei ist beschäftige ich mich mal wieder ein wenig mit dem Programmierkram ausserhalb der Arbeit (auch wenn man dazu nach der Arbeit kaum noch Lust zu hat… leider!).

Mitte des Jahres habe ich das Programm UniCC, ein LALR(1) Parser Generator, veröffentlicht. An sich ist diese Software genial, da sie eben genau das kann, was ich an solch ein Programm an Anforderungen und Erwartungen stelle. Aber vielleicht hab ich mich damit auch selbst etwas übernommen, da UniCC einen Nachteil hat: Sich selbst! Der Parser Generator ist nämlich nun doch so flexibel, komplex, vielseitig und universell, das er schon wieder viel zu kompliziert ist. Eben eine typische, eierlegende Wollmilchsau.

Was ich zur Zeit lieber hätte wäre eine Möglichkeit einen Parser für einfache Sprachen, die man “mal eben” parsen möchte, direkt im C-Code zu beschreiben.

Mein Augenmerk fiel dabei auf EBNF, also die Extendend Backus-Naur Form. Sie beschreibt bereits fast vollständig einen rekursive Absteigenden Parser, wenn man einen entsprechenden Parser Generator dafür schreibt.

Zuerst hatte ich überlegt, das ganze als Kommentare zu erlauben, die dann von einem Parser Generator (der natürlich dafür geschrieben werden müsste) geparst wird. Das hat aber auch wieder den Nachteil, das man seinen C-Code nicht direkt an den Compiler schicken kann um ihn dann auszführen, ein Zwischenschritt mit Zwischendatei ist notwendig.

Ok – dann wohl doch eher eine Library? Hier mal ein Enwurf für die Verewendung einer  Mini-Library die einen Parser in EBNF einlesen und parsen kann. Die Funktion der lexikalischen Analyse übernehmen natürlich die genialen Regular Expression Funktionen der Phorward Foundation Library 😀 …

Natürlich kann man das nicht im C-Code in einen rekursiv absteigenden Parser umsetzen. Was man aber machen könnte wäre es, einen Parse-Tree daraus zu erzeugen. Das gestaltet sich aber auch nicht so einfach, wenn man sich mal überlegt wie das ganze dann als Baum aussehen müsste, denn für alle Klammern in einer EBNF-Grammatik müsste man wieder anonyme Nichtterminale im Hintergrund erzeugen, die dann dort eingesetzt werden – und dann pack da mal noch Code für eine Baumdefinition rein… vergiss es!

Bei meinen Recherchen bin ich dann aber auf TBNF gestoßen. TBNF steht für “Translational Backus Naur Form”. Der Gedanke dahinter ist, Syntax und Abstract Syntax Tree (AST) der Sprache in einer einzelnen Definition zu hinterlegen – genial! Das wäre quasi das komplette Compiler-Frontend bis zur Zwischensprache in einer Definition. Dafür gibt es einen Artikel bei ACM (Association for Computer Machinery), den ich mir dann auch mal kostenpflichtig gegönnt habe.

Tja, so wie es aussieht würde ich das mal probieren, als C-Library umzusetzen. Eine TBNF-Sprache als Eingabe, die man so ähnlich benutzt wie die o.g. Library. Das würde aber bedeuten, daß der Parser auch LALR(1) wird, weil man das als Rekursive Descent eben nicht so schön umsetzen kann – erst recht nicht in Form eines ASTs.

Das Ergebnis eines Parse-Prozesses ist dann ein AST als Datenstruktur, den man dann direkt mit einer weiteren Funktion transferieren kann. Zur Traversierung könnte das Projekt Mantra, das ich ebenfalls dieses Jahr begonnen und dann mangels Nutzen eingestellt hatte, noch interessant werden.

Hier mal ein rudimentärer Entwurf.

Interessant sind die Funktionen r_set_node(), die einen AST-Knoten definieren. Die dort möglichen Emit-Ereignisse sind

• BOTTOMUP beim Eintritt in den Knoten
• PASSOVER beim Durchlaufen der Unterknoten
• TOPDOWN beim Austritt aus dem Knoten

Auch UniCC könnte im Nachhinein davon Profitieren, wenn man über Optionals solch eine Funktionaltität im Parser Template unterstützen würde.

Gut, das wäre dann der vierte Parser-Generator den ich schreiben würde… neben min_lalr1, JS/CC und UniCC… mal schauen wo der Wahninn dann noch hinführt. Aber dieses TBNF ist schon eine coole Sache, die ich in jedem Fall mal implementieren möchte.