Zur Zeit zerbreche ich mir den Kopf darüber, wie man eine linksrekursive Grammatik mit einem rekursiv-absteigenden Parser parsen kann.

Darauf gekommen bin ich durch das Open-Source-Projekt RpaTk von Martin Stoilov – ein im übrigen sehr geniales Projekt. Es enthält einen grundlegend anderen Ansatz als meine bisherigen Entwicklungen, nämlich einen rekursiv-absteigenden Parser, der Backtracking verwendet und noch einige Geschwindigkeitsoptimierungen durch Caching. Das alles läuft dann auch noch auf Basis einer virtuellen Maschine, die ziemlich rasantes Parsing ermöglicht. Ein sehr durchdachtes Konzept, auch wenn es in direkter Konkurrenz zu den letzten Entwicklungen in der libphorward steht, und dieser auch meilenweit voraus ist – Hut ab. Habe mit dem Autor auch Kontakt aufgenommen, weil ich es einfach verstehen will, wie man mit einem rekursiv-absteigenden Parser eine linksrekursive Grammatik parst.

Nehmen wir mal als Beispiel die Grammatik

und würden diese als plumpen rekursiven Abstieg umsetzen, so wird er noch vor dem lesen des ersten Zeichens in eine Endlosschleife verfallen, weil sich e rekursiv aufruft.

Es muss also ein Mechanismus geschaffen werden, der zuerst schaut, ob bereits eine entsprechende Produktion bearbeitet wird und dann nur die Produktionen erlauben, welche nicht in eine erneute Rekursion verfallen. Dazu muss man zuerst prüfen, welche der Produktionen zu einer linksrekursion führen, indem man jede Produktion durchläuft, expandiert und schaut, ob sie sich (auch ein einer tieferen Expansion) selbst aufruft. Dies aber immer nur für das linkeste Nichtterminal, alles andere kann man getrost ignorieren.

Schematisch habe ich das mal für den Eingabestring

auf der Tafel skizziert, nämlich ab dem Punkt, wo er sich bereits in der Produktion e+X befindet und was dann zu tun ist. Man kann sich die linksrekursion dabei als eine Art Schleife vorstellen: Es wird solange versucht, e wieder zu ersetzen, bis eine Produktion fehlschlägt.

Nachdem ich das so skizziert hatte, kam ich auch endlich dazu, ein Programm zu schreiben, welches dies so halbwegs umsetzt. Allerdings bin ich mit dem Ergebnis noch nicht so hundertprozentig im reinen, aber dieser Parser ist immerhin dazu in der Lage, eine linksrekursive Grammatik über den rekursiven Abstieg zu parsen ohne in eine Endlosschleife zu fallen.

Der Trick liegt eigentlich darin: Die mit L markierten Zustände probieren zuerst alle linksrekursiven Produktionen aus. Sofern eine linksrekursive Produktion funktioniert, beginnt der Zustand erneut mit den linksrekursiven Produktionen und verschiebt den Punkt (dot) auf 1. Wenn aber beim ersten Versuch alle linksrekursiven Versuche fehlschlagen, wird mit den nicht-linksrekursiven Versuchen fortgefahren.

Befindet sich bereits ein linksrekursiver Aufruf an selber Leseposition auf dem Stapel, so werden NUR die nicht-linksrekursiven Produktionen versucht.

Hier das Programm, welches dies ansatzweise umsetzt. Ich denke aber, dass ich mich mit dem Thema noch mehr beschäftigen werde, und es demnächst zu einem Update kommt.

Eines ist aber Klar: Ansätze von RpaTk werden in libphorward einfließen, wie z.B. die einfache aber sehr effiziente Definition, dass man z.B. AST-Knoten aus Nichtterminalsymbolen erzeugt, und nicht aus Produktionen. Möchte man dann ein differierenden AST haben, muss man hierfür ein neues Nichtterminal definieren. Das ist unterm Strich gesehen einfacher, als einzelnen Produktionen einen bestimmten Knotentyp zuzuweisen, wie es momentan der Fall ist.