Es ist nett, einen Parsebaum zu haben – häufig will man aber gleich Code ausführen, wenn man eine Regel erkennt. Wir können das mit einer Ableitung unserer Rule-Klasse erreichen:
class RuleWithAction(grammar.Rule):
def _parse(self, rawRule):
self.action = "$1"
ruleAction = rawRule.split("---")
if len(ruleAction)==2:
self.action = ruleAction[1].strip()
else:
if len(ruleAction)!=1:
raise ValueError("Too many --- in '%s'"%
rawRule)
grammar.Rule._parse(self, ruleAction[0])
def runAction(self, currentNonterms):
symVals = self._getSymVals(currentNonterms)
val = eval(
re.sub(r"\$(\d+)",
lambda m: symVals[int(m.group(1))-1],
self.action)
)
currentNonterms.push(self.getLeft(), val)
return val
Im Wesentlichen haben wir die _parse-Methode überschrieben. Sie splittet den String, den sie übergeben bekommt, an einer Folge von drei Minuszeichen. Wenn das Ergebnis die Länge zwei hat, wird der zweite Teil in der Instanzvariablen action gespeichert, ansonsten bleibt dort die Vorbelegung "$1". Danach wird einfach die _parse-Methode der Oberklasse aufgerufen. Was bei diesem Aufruf genau vorgeht und warum der so komisch aussieht, werden wir noch sehen.
Der Sinn dieses Vorgehens wird bei einer Inspektion der Methode runAction klar – dort wird nämlich self.action per eval als Python-Ausdruck ausgewertet. Davor allerdings läuft noch ein regulärer Ausdruck, der alle Strings der Form $n (mit einer ganzen Zahl n) durch ihre Entsprechung in einer Liste ersetzt. Diese Liste kommt aus einer Methode _getSymVals, die zu jeder Konstituente auf der rechten Seite der Regel ihren augenblicklichen Wert (der davon abhängt, welche Regeln vorher liefen) in die Liste schreibt. Haben wir beispielsweise auf der rechten Seite der Regel etwas wie NP VP ".", und hätten vorherige Regelauswertungen dazu geführt, dass NP auf "fritz" und VP auf "isst" abgeleitet werden, wäre die Liste, die _getSymVals zurückgibt, etwas wie ["Fritz", "isst", "."].
Leider gibt es dabei ein paar Subtilitäten, die hier zu weit führen und in einen Parsingkurs gehören, weshalb ich _getSymVals nicht diskutiere – wenn ihr wollt, könnt ihr euch überlegen, warum es die Hilfsklasse MultiStack in actionrule.py (vgl. Anhang) braucht, damit runRuleSeq in Kooperation mit _getSymVals die Werte der Nonterminale in einer Linksableitung korrekt berechnen kann. Gegenstand dieses Programmierkurses ist es jedoch nicht.
Anmerkung: Aus Sicherheitsaspekten ist es häufig keine gute Idee, eval auf strings loszulassen, die aus einer Datei oder allgemein von einer/m BenutzerIn kommen. Es kann dabei leicht zu so genannten privilege escalations kommen, etwa, wenn ihr euren Parser am Netz laufen lasst und Grammatik aus einem Web-Formular lest. Stellt euch vor, was passiert, wenn der Server das Programm unter euerer User-Id startet und böswillige Menschen ein os.system("rm -rf ~") als Aktion eingegeben haben. Das Privileg dazu wolltet ihr ihnen wahrscheinlich nicht einräumen (ganz genau genommen kann hier gar nicht von Eskalation geredet werden, denn wir haben ja gerade beliebige Python-Ausdrücke als Aktionen zugelassen und nur vielleicht nicht überlegt, dass eine solche Aktion eben auch das Löschen des Homeverzeichnesses sein kann).
Dieses Problem taucht immer dann auf, wenn BenutzerInnen von Programmen weniger tun dürfen sollen als das Programm selbst und ist notorisch kompliziert in den Griff zu bekommen. Wir wollen hier davon ausgehen, dass unser Programm nicht in derartigen Situationen läuft.
Diese Regeln müssen jetzt von Grammar auch verwendet werden. Hier ist hilfreich, dass Klassen in Python first class sind, d.h., wir können Grammar sagen, welche Regelklasse es verwenden soll. Das geht z.B. so:
class Grammar: def __init__(self, sourceName, ruleString=None, ruleClass=Rule): self.ruleClass = ruleClass [...] def _parseRules(self, ruleString): for rawRule in filter(operator.truth, [...] self._addRule(self.ruleClass(rawRule))
Tatsächlich steht das so bereits in dem Code, den ihr von der Vorlesungsseite herunterziehen konntet.
Mit ein paar zusätzlichen Ingredienzien kann man damit beispielsweise Zahlwörter erzeugen:
examples> genNumbers.py 2 78 458759456 2 zwei 78 achtundsiebzig 458759456 vierhundertachtundfünfzigmillionen sie benhundertneu nundfünfzigtausend vierhundertsech sundfünfzig
Was dazu über unsere Infrastruktur hinaus nötig ist, steht im Anhang dieser Seite (“Infrastruktur” meint hier grammar.py, symbol.py, word.py sowie topDownParser.py).
Die Grammatik, mit der das Beispiel oben gerechnet wurde, findet ihr in genNumbers.py – vielleicht macht es euch ja Spaß, diese Grammatik zu verbessern (Brüche wären nett…). Schickt mir gerne Ergebnisse eurer Mühen.
Wenn ihr allerdings ernsthaft Grammatik entwickeln wollt, ist der Top-Down-Parser von der letzten Seite untauglich, weil viel zu langsam – was nicht an Python, sondern am Algorithmus liegt.
Erheblich (bei größeren Zahlen um Größenordnungen) flotter gehts mit dem Modul shiftReduceParser, das ihr ebenfalls im Anhang findet. Er wird automatisch verwendet, wenn ihr ihn irgendwo in euren Python-Pfad legt. Dafür sorgt das Konstrukt
try: from shiftReduceParser import ShiftReduceParser, ShiftReduceGrammar ParserClass, GrammarClass = ShiftReduceParser, ShiftReduceGrammar except ImportError: pass
(wieder macht uns der Umstand, dass Klassen first class sind, das Leben deutlich einfacher). Es lohnt sich, den Geschwindigkeitsunterschied zwischen den beiden Parsern für etwas größere Zahlen anzusehen – wir werden in Programmieren II noch mehr Beispiele sehen, in denen die Wahl des Algorithmus entscheidend für die Nutzbarkeit eines Programms sein wird.
Dafür ist der Shift-Reduce-Parser in dem Modul relativ verwickelt (er bringt sogar seine eigene Grammatik-Klasse mit, die so tolle und letztlich rekursive Funktionen wie first und follow berechnen kann). Ihr solltet wohl erst dort reingucken, wenn ihr euch mal von der theoretischen Seite her mit tabellengesteuerten Shift-Reduce-Parsern beschäftigt habt. Nur als Warnung: Ich habe gegenüber Hellwigs Rezept einiges geändert, weil unser “Regeln statt Bäume zurückgeben”-Ansatz das nötig gemacht hat. Kommentieren werde ich den Parser erst, wenn mich jemand darum bittet…