Seite 1 von 1
[Pyparsing] Kein Backtracking?
Verfasst: Donnerstag 3. April 2008, 07:46
von sma
Es hat mich überrascht, dass das folgende Pyparsing-Programm nicht wie gedacht funktioniert. Ich hätte vermutet, das alle möglichen Pfade beschritten würden und das System den korrekten finden würde. Mache ich etwas falsch?
Code: Alles auswählen
from pyparsing import *
identifier = Word(alphas)
keyword = identifier + ":"
unary_expr = identifier + ZeroOrMore(identifier)
keyword_expr = unary_expr + ZeroOrMore(keyword + unary_expr)
print keyword_expr.parseString("a at: b c")
Wie man sieht, gibt es Bezeichner und Schlüsselworte, das sind Bezeichner, die mit einem ":" enden. Eine Folge von Bezeichnern bindet stärker als eine Folge von Schlüsselworten, hinter denen jeweils wieder eine Folge von Bezeichnern stehen kann.
Der Parser entscheidet sich jetzt in `unary_expr` dafür, nach dem Erkennen von "a" als Bezeichner bei "at:" das "at" als weiteren Bezeichner zu erkennen und dann abzubrechen, weil ":" unbekannt ist.
Mir ist das eigentlich bei meinem eigenen Kombinatorparser aufgefallen, aber ich dachte zunächst, ich habe das zu einfach implementiert. Offenbar macht aber auch Pyparsing kein vollständiges Backtracking, oder?
Reguläre Ausdrücke wären ein Lösungansatz, doch geht es auch anders?
Code: Alles auswählen
identifier = Regex("[a-zA-Z][a-zA-Z0-9]*\\b(?!:(?!=))")
keyword = Regex("[a-zA-Z][a-zA-Z0-9]*:(?!=)")
Stefan
Verfasst: Donnerstag 3. April 2008, 09:11
von BlackJack
Nope, PyParsing macht kein vollständiges Backtracking. Wenn man die Grammatik nicht so umschreiben kann, dass das nicht notwendig ist, sollte man als Lösungsansatz überlegen, ob man die Sprache/Grammatik nicht so ändern möchte, dass kein Backtracking notwendig ist.
Aus Effizienzgründen werden Sprachen ja in der Regel so entworfen, das man mit einem Token "vorauslesen" entscheiden kann, welche Regel in der Grammatik dafür zuständig ist. Wenn man beim Backtracking nicht aufpasst, kann man sich schnell mal einen Parser mit exponentieller Laufzeit basteln.
Verfasst: Donnerstag 3. April 2008, 09:58
von sma
Die Bedeutung von L?(1) wird IMHO heutzutage überschätzt. Ruby lässt sich AFAIK nicht in LL(k) parsen, wenn man nicht im Scanner trickst. Und ich werde bestimmt nicht durchsetzen können, nur um es einfacher zu haben, einen Parser zu schreiben, dass die Sprache Ruby geändert wird ;) Genauso ist es mit meinem Ausschnitt aus Smalltalk.
Mir ist bekannt, dass ich Grammatikbeschreibungen meist umschreiben kann, aber genau diesen Aufwand möchte ich ja eigentlich durch einen mächtigeren Parsergenerator und zum Preis erhöhter Laufzeit genau nicht haben. Mich nervt schon, dass Pyparsing (prinzipbedingt als PEG) nicht mit Linksrekursion umgehen kann. Dafür hat ein PEG zumindest einen unbeschränken Lookahead, was schon mal hilfreich bei Fällen wie `parameters = "(" name {"," name} [, "..."] ")"` ist.
Linksrekursion ist praktisch, wenn man die typischen linksassoziativen Operatoren wie + implementieren möchte: `sum = sum "+" num | num`. Man kann jetzt an jede Alternative die offensichtliche Implementierung schreiben. Ohne Linksrekursion muss man das als `sum = num {"+" num}` umschreiben und semantische Aktionen werden komplizierter, weil wir da eine häßliche while-Schleife sehen, deren vorausgehender, folgender und innerer Code angegeben werden muss. Alternativ hilft ein `foldl`.
Was wollte ich eigentlilch sagen? Nun, es ist eben offenbar wie es ist :)
Stefan
Verfasst: Donnerstag 3. April 2008, 11:07
von sma
Hier ist ein Kombinatorparser mit unbeschränktem Backtracking. Die einzelnen Parser verarbeiten nicht nur einem Strom von Zeichen sondern parallel jeweils eine Menge von Strömen (das ließe sich mit Monaden eleganter realisieren).
Code: Alles auswählen
def empty():
def parser(ss):
return ss
return parser
def word(pattern):
pattern = re.compile("\\s*(%s)" % pattern)
def parser(ss):
r = ()
for s in ss:
m = pattern.match(s)
if m: r += (s[m.end(1):],)
return r
return parser
def alt(p1, p2):
def parser(ss):
return p1(ss) + p2(ss) if ss else ()
return parser
def seq(p1, p2):
def parser(ss):
return p2(p1(ss))
return parser
def rep(p):
return alt(empty(), lambda ss: rep(p)(p(ss)))
In `alt` musste ich eine explizite Abbruchbedingung einbauen, sonst gab es immer Endlosrekursionen. Aus dem selben Grund gibt es den lambda-Ausdruck in `rep`. Kein Wunder, dass Parserkombinatoren für Haskell erfunden wurden.
Die Parser erkennen einen Satz einer Sprache, wenn wenigstens ein Strom der Ergebnismenge leer ist, die Ergebnismenge selbst aber nicht.
Ich glaube, ich bleibe bei PEGs...
Stefan
Verfasst: Donnerstag 3. April 2008, 22:44
von mitsuhiko
sma hat geschrieben:Die Bedeutung von L?(1) wird IMHO heutzutage überschätzt. Ruby lässt sich AFAIK nicht in LL(k) parsen, wenn man nicht im Scanner trickst.
Ruby hat nichtmal eine festgelegte Gramatik. Schon der Lexer muss ein wenig herumparsen, damit feststeht was das aktuelle Zeichen eigentlich darstellt. Noch dazu muss der Lexer eine Liste von definierten Variablen und Methoden halten. Ziemlich wirr.
Verfasst: Samstag 5. April 2008, 09:19
von sma
Nun, Ruby hat natürlich eine festgelegte Grammatik, denn es gibt diese .y-Datei für die C-Implementierung von Ruby. Was es nicht gibt, ist eine formale kontextfreie Grammatik. Damit sich die Sprache mit einem LALR(1)-Parser übersetzen lässt, muss der Scanner aka Lexer zaubern. Der Parser definiert Zustände, die dann den Scanner beeinflussen, wie er die nächsten Zeichen zu verstehen hat.
Mir ist jetzt aber beim Überfliegen von yylex in ruby_parser (einer Ruby-Implementation des Ruby Parsers inklusive Scanner) nicht aufgefallen, wo der Scanner da eine Liste der definierten Variablen und Methoden hält. Um Zeile 1970 herum werden identifier erkannt. Aber da passiert nichts Spannendes.
Dennoch: 2751 Zeilen für den Scanner und einige Hilfsklassen und nochmal 1648 Zeilen für die Grammatikbeschreibung, die dann zu 5983 Zeilen Ruby-Code wird - das ist schon eine recht sperrige und unhandliche Sprache. Dabei ist der Ruby-Code noch sehr kompakt.
Python lässt sich auf Token-Ebene mit einer CFG beschreiben, doch auch hier ist der Scanner komplexer, da er nicht kontextfrei ist und einen state braucht. Dies macht es schwer, Python mit einer PEG wie Pyparsing zu verarbeiten. Der Scanner für Python braucht allerdings gerade mal 345 Zeilen inkl. Kommentaren, etwas, dass in der Ruby-Variante ja komplett fehlt.
Stefan