Es gibt wieder was neues aus der Welt des Compilerbaus von mir:
Nachdem ich mir mal letzte Woche das Paper Packrat Parsers Can Support Left Recursion [Warth, Douglass, Millstein] durchgelesen hatte und den dort gezeigten Algorithmus implementierte, fiel der Groschen: Linksrekursive Grammatiken lassen sich nun DOCH mit einem Nicht-LR-Parser parsen! Also das, wonach ich die ganze Zeit gesucht hatte… oft war ich nah dran, aber es hat dann doch nicht gereicht oder anderweitige Probleme aufgezeigt, die das “proof of concept” nicht werden lassen wollten. Die Lösung ist nun ein modifizierter Packrat-Parser! So ungefährt muss es auch mein lieber Martin Stoilov mit seinem rpatk gelöst haben.
Da ich mir erst nicht so ganz sicher war, ob mein Ansatz jetzt wirklich funktioniert, musste ich zuerst noch ein paar Tests durchführen bzw. es etwas voranbringen… die waren aber diesmal wirklich erfolgreich! Man kann damit arbeiten wie mit einer Grammatik für einen LR-Parser. Einzig und allein die Reihenfolge der Produktionen ist hier zu beachten, was bei einem LR-Parser (wie z.B. libphorward) nicht der Fall ist.
Habe das ganze mal in Python ausprogrammiert und inzwischen schon zu einem kleinen Open Source Projekt gemacht, welches auf den Namen pyParse pynetree hört, und unter der MIT-Lizenz steht.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#-*- coding: utf-8 -*- from pyparse import Parser g = { "factor": ["INT", "( expr )"], "mul": "term * factor", "div": "term / factor", "term": ["mul", "div", "factor"], "add": "expr + term", "sub": "expr - term", "expr": ["add", "sub", "term"], "calc": "expr" } p = Parser(g, "calc") p.addToken("INT", r"\d+") p.addAction("INT") p.addAction("mul") p.addAction("div") p.addAction("add") p.addAction("sub") p.addAction("calc") p.dump(p.parse("1 + 2 * ( 3 + 4 ) * 5 - 6 / 7")) |
und gibt
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
calc sub add INT (1) mul mul INT (2) add INT (3) INT (4) INT (5) div INT (6) INT (7) |
aus.
pyparse kann inzwischen sogar eine BNF-Grammatik ähnlich der libphorward interpretieren (selbstverständlich ist der Parser dafür in pyParse entwickelt!)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#-*- coding: utf-8 -*- from pyparse import Parser p = Parser("$INT /\\d+/ %emit;" "f: INT | '(' e ')';" "mul %emit: t '*' f;" "div %emit: t '/' f;" "t: mul | div | f;" "add %emit: e '+' t;" "sub %emit: e '-' t;" "e %goal: add | sub | t;") p.dump(p.parse("123+456*789")) |
pyParse wird wohl dann als erstes mal in ViUR eingebaut… GEIL! 😀