[Pyparsing] Kein Backtracking?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

[Pyparsing] Kein Backtracking?

Beitragvon sma » Donnerstag 3. April 2008, 07:46

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
BlackJack

Beitragvon BlackJack » Donnerstag 3. April 2008, 09:11

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.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Donnerstag 3. April 2008, 09:58

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
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Donnerstag 3. April 2008, 11:07

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
Benutzeravatar
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Beitragvon mitsuhiko » Donnerstag 3. April 2008, 22:44

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.
TUFKAB – the user formerly known as blackbird
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Samstag 5. April 2008, 09:19

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

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]