Neulich habe ich gezeigt, wie ein Python-Interpreter in Java aussehen könnte, der entweder als rekursiver AST-Interpreter für einen als Java-Objekte vorliegenden abstrakten Syntaxbaum (AST) oder als virtuelle Maschine für einen aus dem abstrakten Syntaxbaum abgeleiteten Maschinencode realisiert ist.
Heute möchte ich zeigen, wie man ein Python-Programm in einen AST übersetzen kann. Dies mache ich in Python. Dann kann sich das Programm selbst in einen AST übersetzen und wenn ich aus dem AST -- ebenfalls in Python -- einen Maschinencode erzeuge, brauche ich "nur noch" einen Interpreter für die virtuelle Maschine in der Zielsprache (z.B. Java) und habe dann einen vollständigen Python-Interpreter.
So der Plan.
Der Übersetzer, der aus einem Python-Programm einen AST erzeugt, geht in zwei Schnitten vor. Zuerst soll das als String vorliegende Programm in Wörter (sogenannte Token) erlegt werden. Dann analysiere ich die Liste der Token von links nach rechts mit Hilfe eines rekursiv absteigenden Algorithmus gemäß der Python-Grammatik und baue dabei den AST aus Exemplaren entsprechender Python-Klassen.
Bekanntlich bildet Python Blöcke durch Einrückung. Damit es der Algorithmus einfacher hat, sollen beim Zerlegen des Programms INDENT- und DEDENT-Token synthetisiert werden. Hierfür benutze ich eine vereinfachte Regel, die davon ausgeht, dass ich immer mit genau vier Leerzeichen einrücke.
Die Wörter finde ich mit einem relativ komplizierten regulären Ausdruck, den ich im folgenden erläutern möchte. Finde ich Leerzeichen am Anfang einer Zeile, berechne ich daraus die Einrückung. Alle Wörter landen dann in einer Liste:
from re import findall
def tokenize(s):
tokens = []
cur_indent = 0
new_indent = 0
for token in findall("(?m)^ *(?:#.*)?\n|#.*$|(^ +|\n|\\d+|\\w+|[()\\[\\]{}:.,;]|...)", s):
if token:
if token[0] == ' ':
new_indent = len(token) / 4
else:
if token == '\n':
new_indent = 0
else:
while cur_indent < new_indent:
tokens.append('!INDENT')
cur_indent += 1
while cur_indent > new_indent:
tokens.append('!DEDENT')
cur_indent -= 1
tokens.append(token)
if tokens[-1] != '\n':
tokens.append('\n')
while cur_indent > 0:
tokens.append('!DEDENT')
cur_indent -= 1
return tokens
Das '(?m)' am Anfang des regulären Ausdrucks bedeutet, dass er mehrzeilige Eingaben berücksichtigen soll. Dadurch trifft '^' nicht nur den Anfang des Strings zu, sondern auf jede Position nach einem \n.
Finde ich mit '^ *\n' oder mit '^ *#.*\n', zusammengefasst zu '^ *(?:#.*)?\n', eine leere Zeile mit oder ohne Kommentar, ignoriere ich sie komplett, denn dieser Ausdruck steht nicht in runden Klammern und wird damit von findall nicht geliefert, d.h. token ist in diesem Fall leer, was von dem ersten if in der for-Schleife geprüft wird.
Mit '#.*$' ignoriere ich außerdem Kommentare, die hinter anderen Token stehen. Hier darf ich nicht auch das \n schlucken, denn es wird noch zum Abschluss des Befehls gebraucht, daher prüfe ich hier auf $ als Zeilenende. Dank '(?m)' findet es nicht nur das Ende der Eingabe sondern jede Position vor \n.
Mit der Alternative '(^ +)' finde ich Leerzeichen am Anfang einer nicht-leeren Zeile, also die Einrückung. Das zweite if der for-Schleife berücksichtigt diese Alternative und berechnet die Einrückung unter der Annahme, dass jeweils um vier Leerzeichen eingerückt wird. Treffe ich später auf ein anderes Wort und hat sich die Einrückung gegenüber der vorherigen Zeile verändert, werden dann INDENT- bzw. DEDENT-Token synthetisiert.
Mit der Alternative '(\n)' finde ich das Zeilenende. In diesem Fall kann es keine komplett leere Zeile gewesen sein, das \n ist also wichtig als Ende eines Befehls und wird zur Liste der Token hinzugefügt. Außerdem setze ich die aktuelle Einrückung auf 0, denn in der nächsten Zeile könnte es direkt ohne Einrückung weitergehen.
Mit '(\\d+)' bzw. '(\\w+)' finde ich Zahlen oder Namen. Der Name muss mit einem Buchstaben beginnen (ansonsten hätte die erste Alternative gegriffen) und kann dann aus Buchstaben oder Ziffern bestehen. Außerdem gilt auch _ als Buchstabe. Namen können Schlüsselwörter oder Bezeichner für Variablen sein. Ich unterscheide dies hier nicht weiter.
Danach finde ich mit '([()\\[\\]{}:.,;])' die üblichen syntaktischen Elemente, verschiedene Klammern, Doppelpunkte, Punkte, Kommas oder Semikolons.
Der nächste Ausdruck, den ich im Beispiel oben nur mit ... abgekürzt habe, findet Operatoren: '([+\\-*/%<>=]=?|!=)'. Es sind die vier Grundrechenarten plus Modulo, denen optional ein = folgen kann. Es sind außerdem die üblichen Vergleichsoperatoren: kleiner, größer, gleich, kleinergleich, größergleich, gleichgleich oder ungleich.
Nun fehlt noch ein Ausdruck für Zeichenketten. Ich werde mich auf einzeilige Strings ohne r- oder b- oder u-Präfix beschränken, in denen besondere Zeichen mit \ markiert werden können: '(\'(?:\\\\[n\'\"\\\\]|[^\'])*\'|\"(?:\\\\[n'\"\\\\]|[^\"])*\")'. Strings sind in einfache oder doppelte Anführungsstriche eingeschlossen. Darin findet man entweder ein \ gefolgt von einem n, einem einfachen oder doppelten Anführungsstrich oder einem zweiten \ oder Zeichen, die keine Anführungsstriche sind. Die Explosion der Rückwärtsstriche in dem regulären Ausdruck kommt daher, dass der String, wenn dort ein \ stehen soll, schon mal \\ erwartet und auch der reguläre Ausdruck einen \ als \\, also \\\\ in einem String, erwartet. Für die Gruppierung muss ich (?:) statt einfach () benutzen, damit diese Gruppe nicht in dem Ergebnis von findall auftaucht.
Ich denke, damit habe ich alle syntaktischen Elemente erkannt, soweit ich sie in meiner Teilmenge von Python unterstützen möchte. Leerzeichen innerhalb einer Zeile werden wie üblich ignoriert, unbekannte Zeichen leider auch. Besser wäre, wenn sie einen Fehler erzeugen würden.
Die beiden while-Schleifen in dem dritten if erzeugen wie schon erwähnt ein INDENT-Token, wenn weiter eingerückt wurde und ein DEDENT-Token, wenn wieder ausgerückt wurde. Ich habe den beiden Token zur Unterscheidung von entsprechenden Namen, die ja gültige Bezeichner wären, ein ! vorangestellt.
Erreiche ich das Ende der Eingabe, kann es sein, dass ich noch eingerückt bin. Daher wird in der letzten while-Schleife ausgerückt. Da jede Zeile, auch die letzte, mit einem Zeilenumbruch \n beendet werden sollte, prüfe ich auch dies noch und füge ggf. ein fehlendes \n hinzu.
Das Programm kann sich nun selbst übersetzen (den regulären Ausdruck habe ich wieder gekürzt):
['from', 're', 'import', 'findall', '\n',
'def', 'tokenize', '(', 's', ')', ':', '\n',
'!INDENT',
'tokens', '=', '[', ']', '\n',
'cur_indent', '=', '0', '\n',
'new_indent', '=', '0', '\n',
'for', 'token', 'in', 'findall', '(', '"(?m)^ ..."', ',', 's', ')', ':', '\n',
'!INDENT',
'if', 'token', ':', '\n',
'!INDENT',
'if', 'token', '[', '0', ']', '==', "' '", ':', '\n',
'!INDENT',
'new_indent', '=', 'len', '(', 'token', ')', '/', '4', '\n',
'!DEDENT',
'else', ':', '\n',
'!INDENT',
'if', 'token', '!=', "'\\n'", ':', '\n',
'!INDENT',
'while', 'cur_indent', '<', 'new_indent', ':', '\n',
'!INDENT',
'tokens', '.', 'append', '(', "'!INDENT'", ')', '\n',
'cur_indent', '+=', '1', '\n',
'!DEDENT',
'while', 'cur_indent', '>', 'new_indent', ':', '\n',
'!INDENT',
'tokens', '.', 'append', '(', "'!DEDENT'", ')', '\n',
'cur_indent', '-=', '1', '\n',
'!DEDENT',
'!DEDENT',
'tokens', '.', 'append', '(', 'token', ')', '\n',
'!DEDENT',
'!DEDENT',
'!DEDENT',
'if', 'tokens', '[', '-', '1', ']', '!=', "'\\n'", ':', '\n',
'!INDENT',
'tokens', '.', 'append', '(', "'\\n'", ')', '\n',
'!DEDENT',
'while', 'cur_indent', '>', '0', ':', '\n',
'!INDENT',
'tokens', '.', 'append', '(', "'!DEDENT'", ')', '\n',
'cur_indent', '-=', '1', '\n',
'!DEDENT',
'return', 'tokens', '\n',
'!DEDENT']
Die vollständige Grammatik von Python findet man in Kapitel 9 der Sprachspezifikation. Sie beschreibt, wie Anweisungen und Ausdrücke gebildet werden. Jede Regel hat einen Namen, dem ein Doppelpunkt und die Beschreibung der Regel folgt. Durch einen senkrechten Strich getrennte Teilausdrücke bilden Alternativen. Ein Teilausdruck in eckigen Klammern ist ein optionaler Teil. Ein Teilausdruck in geschweiften Klammern kann beliebig oft wiederholt werden. Wörter in Anführungsstrichen stehen für sich, alle anderen Namen stehen für weitere Regeln. Runde Klammern können benutzt werden, um Teilausdrücke zu gruppieren.
Hier ist der Teil für Ausdrücke, so weit ich sie in meinem Python unterstützen will:
test: or_test ['if' or_test 'else' test]
or_test: and_test {'or' and_test}
and_test: not_test {'and' not_test}
not_test: 'not' not_test | comparison
comparison: expr [('<'|'>'|'=='|'>='|'<='|'!='|'in'|'not' 'in'|'is') expr]
expr: arith_expr
arith_expr: term {('+'|'-') term}
term: factor {('*'|'/'|'%') factor}
factor: ('+'|'-') factor | power
power: atom {trailer}
atom: '('[testlist]')' | '['[testlist]']' | '{'[dictorsetmaker]'}' | NAME | NUMBER | STRING+
trailer: '(' [testlist] ')' | '[' subscriptlist ']' | '.' NAME
subscriptlist: subscript {',' subscript} [',']
subscript: test | [test] ':' [test] [':' [test]]
testlist: test {',' test} [',']
dictorsetmaker: (test ':' test {',' test ':' test} [',']) | testlist
Im Gegensatz zu Original-Python habe ich lambda, Bit-Operationen, **, yield und Comprehensions bzw. Generatorausdrücke weggelassen. Argumente von Funktions- und Methodenaufrufen können keine Schlüsselwörter und keine *- und **-Ausdrücke enthalten. Außerdem gibt es kein ... innerhalb von []-Operationen.
Bevor ich zeige, wie ich die einzelnen Regeln der Grammatik in Python-Methoden übersetze, stelle ich hier meine Klasse Parser vor. Sie zerlegt ein Programm es mit Hilfe der Funktion tokenize aus dem ersten Teil in Token. Sie erlaubt den Zugriff auf das aktuelle Token, kann das nächste Token zum aktuellen machen und stellt mit at, atsel und expect Methoden bereit, um bequem die Syntax zu prüfen.
class Parser:
def __init__(self, source):
self.tokens = tokenize(source)
self.index = 0
def token(self):
"Return the current token or '' if there is no token."
return self.tokens[self.index] if self.index < len(self.tokens) else ''
def advance(self):
"Make next token the current token."
self.index += 1
def at(self, token):
"If current token is given one, advance to next token and return True."
if self.token() == token:
self.advance()
return True
def atsel(self, dct):
"If current token is one of the keys of the given dict, return associated value."
for k, v in dct.items():
if self.at(k):
return v
def expect(self, token):
"Raise a syntax error if the current token isn't the expected one."
if not self.at(token):
raise SyntaxError, 'expected %r but found %r' % (token, self.token())
Los geht es mit der Regel test. Dies ist ein Ausdruck, dem optional ein if folgen kann. So ein if-Ausdruck wird durch die AST-Klasse If repräsentiert, die den Ausdruck für die Bedingung und die beiden Ausdrücke für den then-Fall und den else-Fall zusammenfasst:
# test: or_test ['if' or_test 'else' test]
def parse_test(self):
expr = self.parse_or_test()
if self.at('if'):
then_expr = expr
cond_expr = self.parse_or_test()
self.expect('else')
return If(cond_expr, then_expr, self.parse_test())
return expr
class If(Expr):
def __init__(self, cond_expr, then_expr, else_expr):
self.cond_expr, self.then_expr, self.else_expr = cond_expr, then_expr, else_expr
def __str__(self):
return '%s if %s else %s' % (self.then_expr, self.cond_expr, self.else_expr)
Wie man sieht, wird jede Referenz einer Regel zu einem entsprechenden Methodenaufruf. Ich lasse alle Methoden, die Regeln implementieren, mit dem Präfix parse_ beginnen. Ein optionaler Regelteil in [ ] wird zu einem if. Beginnt der optionale Teil mit einem Schlüsselwort, kann ich dieses mit at() prüfen. Syntaktischer Zucker, also Syntax die nicht zwingend erforderlich ist, um zu entscheiden, welcher Teilausdruck gewählt werden soll, prüfe ich mit expect().
Danach folgt or_test, ein Ausdruck, dem optional mit or ein weiterer Ausdruck folgen kann. Die AST-Klasse Or ist eine von vielen Unterklassen von Bin, einer abstrakten AST-Klasse, die für binäre Ausdrücke steht und jeweils den Ausdruck für die linke Seite und die rechte Seite der Operation zusammenfasst:
# or_test: and_test {'or' and_test}
def parse_or_test(self):
expr = self.parse_and_test()
while self.at('or'):
expr = Or(expr, self.parse_and_test())
return expr
class Bin(Expr):
op = '?'
def __init__(self, left_expr, right_expr):
self.left_expr, self.right_expr = left_expr, right_expr
def __str__(self):
return '(%s %s %s)' % (self.left_expr, self.op, self.right_expr)
class Or(Bin):
op = 'or'
Eine Wiederholung mit { } in einer Regel wird zu einer while-Schleife in der Methode. Auch hier hilft es, wenn der zu wiederholende Regelteil mit einem Schlüsselwort beginnt, denn das kann ich dann wieder mit at() prüfen. Zu beachten ist, dass alle Operatoren soweit nicht anders erwähnt, linksassoziativ sind, d.h. a op b op c wird als (a op b) op c übersetzt.
Die and_test-Regel funktioniert analog zu or_test und benutzt die AST-Klasse And:
# and_test: not_test {'and' not_test}
def parse_and_test(self):
expr = self.parse_not_test()
while self.at('and'):
expr = And(expr, self.parse_not_test())
return expr
class And(Bin):
op = 'and'
Die nächste Regel not_test erlaubt ein optionales not vor einem Ausdruck:
# not_test: 'not' not_test | comparison
def parse_not_test(self):
if self.at('not'):
return Not(self.parse_not_test())
return self.parse_comparison()
class Unary(Expr):
op = '?'
def __init__(self, expr):
self.expr = expr
def __str__(self):
return '%s%s' % (self.op, self.expr)
class Not(Unary):
op = 'not '
AST-Klassen für unäre Operationen erben von der abstrakten AST-Klasse Unary, die die Operation und den Ausdruck kennt. Die Alternative | prüfe ich mit if anhand des ersten Schlüsselworts des Teilausdrucks.
Um eine Grammatik in einen sogenannten rekursiv absteigenden LL(1)-Parser zu übersetzen (die Eins bedeutet, dass ich immer nur ein Token anschauen muss, um zu entscheiden, wie es weitergeht; dies ist die einfachste Form einer Grammatik), wende ich folgende Entwurfsmuster an:
# Keyword
a: 'k'
=>
def parse_a(self):
self.expect('k')
# Rule
a: b
=>
def parse_a(self):
self.parse_b()
# Sequence
a: b c
=>
def parse_a(self):
self.parse_b()
self.parse_c()
# Alternative
a: 'c' d | e
=>
def parse_a(self):
if self.at('c'):
self.parse_d()
else:
self.parse_e()
# Option
a: ['b' c]
=>
def parse_a(self):
if self.at('b'):
self.parse_c()
# Repetition
a: {'b' c}
=>
def parse_a(self):
while self.at('b'):
self.parse_c()
Als nächstes kommen die Vergleichsoperationen. Im Gegensatz zum Original-Python erlaube ich keine Reihung der Art 0 < a < 2, was die Auswertung vereinfacht. Mit atsel kann ich zu einem Operator die passende AST-Klasse wählen. Diese Klassen erben alle von Bin und sind bis auf den Namen des jeweiligen Operators identisch.
# comparison: expr [('<'|'>'|'=='|'>='|'<='|'!='|'in'|'not' 'in'|'is' ['not']) expr]
def parse_comparison(self):
expr = self.parse_expr()
kind = self.atsel({'<': Lt, '>': Gt, '==': Eq, '>=': Ge, '<=': Le, '!=': Ne,
'in': In, 'not': NotIn, 'is': Is})
if kind:
if kind is NotIn:
self.expect('in')
if kind is Is and self.at('not'):
kind = IsNot
return kind(expr, self.parse_expr())
return expr
class Lt(Bin):
op = '<'
class Gt(Bin):
op = '>'
class Le(Bin):
op = '<='
class Ge(Bin):
op = '>='
class Eq(Bin):
op = '=='
class Ne(Bin):
op = '!='
class In(Bin):
op = 'in'
class NotIn(Bin):
op = 'not in'
class Is(Bin):
op = 'is'
class IsNot(Bin):
op = 'is not'
Die Regel expr macht eigentlich gar nichts, weil ich an dieser Stelle die Bit-Operationen gestrichen habe. Daher geht es sofort mit arith_expr weiter, die Regel für Addition und Subtraktion. Da ich in Python in der Bedingung von while keine Variable zuweisen kann, gleichzeitig aber wissen muss, ob + oder - ausgewählt wurde, muss ich eine recht hässliche while True-Schleife mit einem break bauen. Die Alternative wäre, die Zuweisung zu kind zweimal zu machen, was aber dem DRY-Prinzip widersprechen würde. Die Operationen sind links-assoziativ.
# expr: arith_expr
def parse_expr(self):
return self.parse_arith_expr()
# arith_expr: term {('+'|'-') term}
def parse_arith_expr(self):
expr = self.parse_term()
while True:
kind = self.atsel({'+': Add, '-': Sub})
if not kind: break
expr = kind(expr, self.parse_term())
return expr
class Add(Bin):
op = '+'
class Sub(Bin):
op = '-'
Für *, / und % funktioniert es analog. Alle Regeln sind entsprechend der Bindungsstärke der Operationen sortiert. Daher kommt zuerst die Regel arith_expr für additive Operationen und dann term für multiplikative Operationen, da diese stärker binden. Auch diese Operationen sind links-assoziativ.
# term: factor {('*'|'/'|'%') factor}
def parse_term(self):
expr = self.parse_factor()
while True:
kind = self.atsel({'*': Mul, '/': Div, '%': Mod})
if not kind: break
expr = kind(expr, self.parse_factor())
return expr
class Mul(Bin):
op = '*'
class Div(Bin):
op = '/'
class Mod(Bin):
op = '%'
Noch stärker bindet das unäre Plus oder Minus als Vorzeichen. Dies ist daher die nächste Regel:
# factor: ('+'|'-') factor | power
def parse_factor(self):
kind = self.atsel({'+': Pos, '-': Neg})
if kind:
return kind(self.parse_factor())
return self.parse_power()
class Pos(Unary):
op = '+'
class Neg(Unary):
op = '-'
Die Regel power definiert, dass einem Ausdruck eine Liste von Argumenten in runden Klammern folgen kann, was ihn zu einem Funktions- oder Methodenaufruf macht; oder dass dem Ausdruck ein Indexoperator (eckige Klammern) oder ein Attributzugriff folgen kann. Alle Operationen sind links-assoziativ.
# power: atom {trailer}
def parse_power(self):
expr = self.parse_atom()
# trailer: '(' [testlist] ')' | '[' subscriptlist ']' | '.' NAME
while True:
if self.at('('):
expr = Call(expr, self.parse_testlist_opt())
self.expect(')')
elif self.at('['):
expr = Index(expr, self.parse_subscriptlist())
self.expect(']')
elif self.at('.'):
expr = Attr(expr, self.parse_name())
else:
break
return expr
class Call(Expr):
def __init__(self, expr, arguments):
self.expr, self.arguments = expr, arguments
def __str__(self):
return '%s(%s)' % (self.expr, join_str(self.arguments))
class Index(Expr):
def __init__(self, expr, slices):
self.expr, self.slices = expr, slices
def __str__(self):
return '%s[%s]' % (self.expr, join_str(self.slices))
class Attr(Expr):
def __init__(self, expr, name):
self.expr, self.name = expr, name
def __str__(self):
return '%s.%s' % (self.expr, self.name)
Schauen wir uns jetzt atom an. Hier werden Tupel, Listen, Dictionaries und Sets beschrieben. Außerdem kann ein Bezeichner als Variable vorkommen oder eine Zahl oder eine Folge von Strings, beides als Literale.
Bei Tupel besteht das Problem, dass bei einem Argument ohne Komma einfach nur eine Gruppierung vorliegt. Dieser Fall geht leider nicht direkt aus der Grammatik hervor.
Die abstrakte AST-Klasse Ctr für Konstruktor bildet die Oberklasse für TupleCtr, ListCtr, DictCtr und SetCtr. Ob ein Ausdruck in geschweiften Klammern ein Set oder ein Dictionary ist, kann leider erst nach dem ersten Ausdruck an dem : erkannt werden. Diese Unterscheidung trifft dictorsetmaker.
Bei Strings muss ich noch \n, \', \" oder \\ in das jeweilige Zeichen umwandeln. Dies mache ich mit einer Kette von replace()-Aufrufen. Außerdem gehören natürlich die umschließenden Anführungsstriche nicht zum String. Python will es, dass mehrere aufeinander folgende String-Token zu einem String-Literal werden. Das macht die Auswertung auch nicht gerade einfacher.
# atom: '('[testlist]')' | '['[testlist]']' | '{'[dictorsetmaker]'}' | NAME | NUMBER | STRING+
def parse_atom(self):
if self.at('('):
if self.at(')'):
return TupleCtr([])
e = self.parse_test()
if self.at(')'):
return e # just a grouping of expressions; no tuple constructor
self.expect(',')
es = [e] + self.parse_testlist_opt()
self.expect(')')
return TupleCtr(es)
if self.at('['):
es = self.parse_testlist_opt()
self.expect(']')
return ListCtr(es)
if self.at('{'):
return self.parse_dictorsetmaker()
token = self.token()
if token:
if token[0].isdigit():
self.advance()
return Lit(int(token))
if token[0].isalpha() or token[0] == '_':
self.advance()
return Var(token)
if token[0] == '"' or token[0] == "'":
s = ''
while token and (token[0] == '"' or token[0] == "'"):
s += token[1:-1].replace('\\n', '\n').replace("\\'", "'")\
.replace('\\"', '"').replace('\\\\', '\\')
self.advance()
token = self.token()
return Lit(s)
raise SyntaxError, "expected (, [, {, NAME, NUMBER or STRING but found %r" % token
# dictorsetmaker: test ':' test {',' test ':' test} [','] | testlist
def parse_dictorsetmaker(self):
if self.at('}'):
return DictCtr([])
expr = self.parse_test()
if self.at(':'):
# it's a dict, not a set
exprs = [(expr, self.parse_test())]
while self.at(','):
if self.at('}'):
break
k = self.parse_test()
self.expect(':')
v = self.parse_test()
exprs.append((k, v))
else:
self.expect('}')
return DictCtr(exprs)
else:
# it must be a set
exprs = [expr]
while self.at(','):
if self.at('}'):
break
exprs.append(self.parse_test())
else:
self.expect('}')
return SetCtr(exprs)
class Ctr(Expr):
def __init__(self, exprs):
self.exprs = exprs
def to_s(self):
return join_str(self.exprs)
class TupleCtr(Ctr):
def __str__(self):
return '(%s)' % self.to_s()
def to_s(self):
s = Ctr.to_s(self)
if len(self.exprs) == 1:
s += ','
return s
class ListCtr(Ctr):
def __str__(self):
return '[%s]' % self.to_s()
class SetCtr(Ctr):
def __str__(self):
return '{%s}' % self.to_s()
class DictCtr(Ctr):
def __str__(self):
return '{%s}' % self.to_s()
def to_s(self):
s = ''
for e in self.exprs:
if s:
s += ', '
s += str(e[0]) + ': ' + str(e[1])
return s
class Lit(Expr):
def __init__(self, value):
self.value = value
def __str__(self):
return repr(self.value)
class Var(Expr):
def __init__(self, name):
self.name = name
def __str__(self):
return self.name
Ein Ausdruck in Klammern kann optional eine Liste aus durch Komma getrennte Ausdrücken enthalten. Dieses regelt testlist, genauer die Methode parse_testlist_opt, die auch eine leere Liste von Ausdrücken liefern kann.
# testlist: test {',' test} [',']
def parse_testlist_opt(self):
exprs = []
if self.has_test():
exprs.append(self.parse_test())
while self.at(','):
if not self.has_test():
break
exprs.append(self.parse_test())
return exprs
Da die Regel so wie angegeben, nicht mit einem rekursiv absteigenden LL(1)-Parser, wie ich ihn hier baue, erkannt werden kann, sieht die while-Schleife etwas komplizierter aus. Wenn ich auf ein Komma treffe, weiß ich nicht, ob danach ein test folgt und ich somit in dem Teil der Regel bin, der sich wiederholt, oder ob ich das letzte optionale Komma vorliegen habe. Ich beende daher die while-Schleife, wenn nach dem Komma kein test folgt. Dann muss es wohl das letzte optionale Komma gewesen sein.
Die Methode has_test prüft, ob das aktuelle Token der Anfang eines Ausdrucks ist. Schaut man sich die Grammatik an, beginnt ein test wie or_test, der beginnt wie and_test und der wie not_test. Diese Regel beginnt entweder mit dem Schlüsselwort not oder wie comparison, die wie expr beginnt, die wie arith_expr, wie term, wie factor. Dort kann ein + oder - auftauchen, oder die Regel beginnt wie power, die wie atom beginnt. Hier können es Klammern, ein Name, eine Zahl oder ein String sein. Also prüfe ich, ob das aktuelle Token mit einem Buchstaben oder einer Zahl beginnt oder eine Klammer ist oder Plus oder Minus oder ein einfacher oder doppelter Anführungsstrich:
def has_test(self):
token = self.token()
return token and (token[0].isalnum() or token[0] in '+-([{\'"_')
Manchmal will man auch sicherstellen, dass testlist garantiert ein Element hat:
# testlist: test {',' test} [',']
def parse_testlist(self):
exprs = self.parse_testlist_opt()
if not exprs:
raise SyntaxError, "list must not be empty"
return exprs
Muss das aktuelle Token ein Bezeichner sein, prüft dies die folgende Methode. In der Grammatik findet man sie so nicht direkt, denn im Gegensatz zu meinem Ansatz kann man Namen dort direkt im Scanner erkennen. Streng genommen müsste ich noch sicherstellen, dass der Name kein Schlüsselwort ist. Das spare ich mir hier:
def parse_name(self):
token = self.token()
if token and (token[0].isalpha() or token[0] == '_'):
self.advance()
return token
raise SyntaxError, "expected NAME but found %r" % token
Der Index eines []-Operators kann recht kompliziert aufgebaut sein. Die beiden folgenden Methoden übersetzen diese eine Liste von Ausdrücken oder Slice-Objekten, wie sie dann auch erzeugt werden, wenn die __getitem__-Methode eines Typs, der [] unterstützt, aufgerufen wird.
# subscriptlist: subscript {',' subscript} [',']
def parse_subscriptlist(self):
ss = [self.parse_subscript()]
while self.at(','):
if not self.has_test() and self.token() != ':':
break
ss.append(self.parse_subscript())
return ss
# subscript: test | [test] ':' [test] [':' [test]]
def parse_subscript(self):
if self.has_test():
start = self.parse_test()
if not self.at(':'):
return start
else:
start = None
self.expect(':')
if self.has_test():
stop = self.parse_test()
else:
stop = None
if self.at(':'):
if self.has_test():
step = self.parse_test()
else:
step = None
else:
step = None
return Slice(start, stop, step)
class Slice:
def __init__(self, start, stop, step):
self.start, self.stop, self.step = start, stop, step
def __str__(self):
def nn(v): return '' if v is None else v
return '%s:%s:%s' % (nn(self.start), nn(self.stop), nn(self.step))
Damit sind alle Regeln der Grammatik in Methoden den Klasse Parser übersetzt und der Parser kann nun Python-Ausdrücke in Exemplare der AST-Klassen übersetzen.
Hier sind einige Tests:
print Parser('1+2*3').parse_test()
print Parser('(1+2)*3').parse_test()
print Parser('call(1, None, "a" "b")').parse_test()
print Parser('foo[1, :2, ::].bar').parse_test()
print Parser('-a < +4 if b is "c" else []').parse_test()
print Parser('({}, {1}, {1, 2}, {3:4, 5:6})').parse_test()
Neben Ausdrücken gibt es in Python noch Anweisungen. Die Grammatik unterscheidet hier zwei Arten: Einfache Anweisungen und zusammengesetzte Anweisungen, die jeweils wieder (einfache oder zusammengesetzte) Anweisungen in Form einer "Suite" enthalten können. Eine "Suite" wird entweder durch Einrückung gebildet oder besteht aus einer durch ; getrennten Folge einfacher Anweisungen, die alle in der selben Zeile stehen müssen.
stmt: simple_stmt | compound_stmt
simple_stmt: small_stmt {';' small_stmt} [';'] NEWLINE
small_stmt: expr_stmt | print_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | assert_stmt
expr_stmt: testlist [('+=' | '-=' | '*=' | '/=' | '%=' | '=') testlist]
print_stmt: 'print' [ test {',' test} [','] ]
pass_stmt: 'pass'
flow_stmt: break_stmt | return_stmt | raise_stmt
break_stmt: 'break'
return_stmt: 'return' [testlist]
raise_stmt: 'raise' [test [',' test]]
import_stmt: import_name | import_from
import_name: 'import' dotted_as_names
import_from: 'from' dotted_name 'import' ('*' | import_as_names)
import_as_name: NAME ['as' NAME]
dotted_as_name: dotted_name ['as' NAME]
import_as_names: import_as_name {',' import_as_name}
dotted_as_names: dotted_as_name {',' dotted_as_name}
dotted_name: NAME {'.' NAME}
global_stmt: 'global' NAME {',' NAME}
assert_stmt: 'assert' test [',' test]
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef
if_stmt: 'if' test ':' suite {'elif' test ':' suite} ['else' ':' suite]
while_stmt: 'while' test ':' suite ['else' ':' suite]
for_stmt: 'for' exprlist 'in' testlist ':' suite ['else' ':' suite]
try_stmt: 'try' ':' suite (except_clause {except_clause} | 'finally' ':' suite)
except_clause: 'except' [test ['as' NAME]] ':' suite
suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT
funcdef: 'def' NAME parameters ':' suite
parameters: '(' [NAME {',' NAME} [',']] ')'
classdef: 'class' NAME ['(' [testlist] ')'] ':' suite
Ich habe del, yield, continue, exec und with aus der Grammatik entfernt. Es gibt außerdem keine Mehrfachzuweisungen. Bei print verbiete ich >> zur Ausgabeumlenkung. Bei raise lasse ich das dritte Argument weg, bei except nutze ich as. Auch Parameterlisten habe ich vereinfacht und es gibt keine Schlüsselwortparameter und keine *- und **-Parameter. Decorators sind ebenfalls aus der Grammatik verschwunden.
Ich beginne mit der Regel stmt. Da simple_stmt eine Liste von Anweisungen liefern kann, definiere ich, dass auch parse_stmt eine Liste von Exemplaren von Unterklassen der abstrakten AST-Klasse Stmt liefert. Daher ist es einfacher, finde ich, zunächst auf die zusammengesetzten Anweisungen zu prüfen. Die Methode parse_compound_stmt liefert None statt eines Fehlers, wenn sie keine zusammengesetzte Anweisung erkennt.
# stmt: simple_stmt | compound_stmt
def parse_stmt(self):
stmt = self.parse_compound_stmt()
if stmt:
return [stmt]
return self.parse_simple_stmt()
Weiter geht es erst einmal mit simple_stmt. Auch hier ist es leider nicht möglich, mit einem rekursiv absteigenden LL(1)-Parser zu entscheiden, wie bei einem ; zu verfahren ist. Ich muss daher die while-Schleife abbrechen, wenn nach dem ; ein Zeilenumbruch folgt, da ich dann offensichtlich das letzte optionale Semikolon erwischt habe. Endet die while-Schleife ohne break, greift der else-Fall der Schleife und ich erwarte ein Zeilenende.
# simple_stmt: small_stmt {';' small_stmt} [';'] NEWLINE
def parse_simple_stmt(self):
stmts = [self.parse_small_stmt()]
while self.at(';'):
if self.at('\n'):
break
stmts.append(self.parse_small_stmt())
else:
self.expect('\n')
return stmts
Die Regel small_stmt zählt alle möglichen Anweisungen auf. Die Regeln flow_stmt und import_stmt habe ich an dieser Stelle gleich integriert. Die zusammengesetzten Anweisungen habe ich ja schon zuvor ausgeschlossen. Treffe ich also hier auf etwas, dass ich nicht kenne, ist es ein Fehler, falls es keine Ausdruckanweisung (z.B. ein Funktionsaufruf) oder Zuweisung ist. Dies prüfe ich ohne besonderen Grund zum Schluss.
# small_stmt: expr_stmt | print_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | assert_stmt
# flow_stmt: break_stmt | return_stmt | raise_stmt
# import_stmt: import_name | import_from
def parse_small_stmt(self):
if self.at('print'):
return self.parse_print_stmt()
if self.at('pass'):
return self.parse_pass_stmt()
if self.at('break'):
return self.parse_break_stmt()
if self.at('return'):
return self.parse_return_stmt()
if self.at('raise'):
return self.parse_raise_stmt()
if self.at('import'):
return self.parse_import_name()
if self.at('from'):
return self.parse_import_from()
if self.at('global'):
return self.parse_global_stmt()
if self.at('assert'):
return self.parse_assert_stmt()
if self.has_test():
# expr_stmt: testlist [('+=' | '-=' | '*=' | '/=' | '%=' | '=') testlist]
expr = self.parse_testlist_as_tuple()
kind = self.atsel({'=': AssignStmt, '+=': AddAssignStmt, '-=': SubAssignStmt})
if kind:
return kind(expr, self.parse_testlist_as_tuple())
return ExprStmt(expr)
raise SyntaxError, 'expected statement, expression or assignment'
class AssignStmt(Stmt):
op = '='
def __init__(self, lhs, rhs):
self.lhs, self.rhs = lhs, rhs
def __str__(self):
return '%s %s %s' % (self.lhs, self.op, self.rhs)
class AddAssignStmt(AssignStmt): op = '+='
class SubAssignStmt(AssignStmt): op = '-='
class ExprStmt(Stmt):
def __init__(self, expr):
self.expr = expr
def __str__(self):
return str(self.expr)
Die Methode parse_testlist_as_tuple erläutere ich später. Sie sorgt dafür, dass ein einzelner Ausdruck zu einem Ausdruck wird, folgt jedoch ein Komma (oder sind es mehr als ein Ausdruck), wird es zu einem Tupel-Konstruktor.
Nun kommen die Regeln für die einzelnen Anweisungen. Beginnen wir mit print_stmt. Hier ist zu beachten, dass ein Komma am Ende bedeutet, dass kein Zeilenumbruch nach der Ausgabe folgen soll. Ich kann hier daher leider nicht einfach parse_testlist_opt benutzen, sondern muss die Argumente von print per Hand analysieren:
# print_stmt: 'print' [ test {',' test} [','] ]
def parse_print_stmt(self):
if self.has_test():
exprs = [self.parse_test()]
while self.at(','):
if not self.has_test():
no_nl = True
break
exprs.append(self.parse_test())
else:
no_nl = False
return PrintStmt(exprs, no_nl)
return PrintStmt([], False)
class PrintStmt(Stmt):
def __init__(self, exprs, no_nl):
self.exprs, self.no_nl = exprs, no_nl
def __str__(self):
if self.exprs:
s = join_str(self.exprs)
if self.no_nl:
s += ', '
return 'print %s' % s
return 'print'
Zu pass_stmt und break_stmt ist nichts weiter zu sagen:
# pass_stmt: 'pass'
def parse_pass_stmt(self):
return PassStmt()
# break_stmt: 'break'
def parse_break_stmt(self):
return BreakStmt()
class PassStmt(Stmt):
def __str__(self):
return 'pass'
class BreakStmt(Stmt):
def __str__(self):
return 'break'
Bei return_stmt gilt ähnliches wie bei print. Die Grammatik-Regel suggeriert hier zwar, dass ich einfach parse_testlist_opt benutzen kann, doch hier gibt es den Sonderfall, dass ein einzelnes Argument ohne Komma einfach nur ein Argument, ein einzelnes Argument mit Komma jedoch ein Tupel-Konstruktor ist. Bei mehr als einem Argument ist es einfach, da ist es immer ein Tupel-Konstruktor. Ein return ohne Argument entspricht einem return None.
# return_stmt: 'return' [testlist]
def parse_return_stmt(self):
expr = self.parse_testlist_opt_as_tuple()
return ReturnStmt(expr if expr else Lit(None))
def parse_testlist_opt_as_tuple(self):
if self.has_test():
expr = self.parse_test()
if not self.at(','):
return expr
exprs = [expr]
if not self.has_test():
return TupleCtr(exprs)
return TupleCtr(exprs + self.parse_testlist_opt())
return None
def parse_testlist_as_tuple(self):
expr = self.parse_testlist_opt_as_tuple()
if not expr:
raise SyntaxError, 'expression expected'
class ReturnStmt(Stmt):
def __init__(self, expr):
self.expr = expr
def __str__(self):
return 'return %s' % self.expr
raise_stmt definiert die drei Varianten von raise: Keine Argumente, ein Argument oder zwei Argumente. Das erste Argument ist entweder ein Klassen-Objekt oder Exemplar eine Klasse, das zweite Argument im Falle, dass das erste eine Klasse ist, das Argument für dessen Konstruktor. Warum mache ich mir eigentlich die Mühe, diese komische Syntax so abzubilden?
# raise_stmt: 'raise' [test [',' test]]
def parse_raise_stmt(self):
if self.has_test():
exception = self.parse_test()
if self.at(','):
message = self.parse_test()
else:
message = None
else:
exception = None
message = None
return RaiseStmt(exception, message)
class RaiseStmt(Stmt):
def __init__(self, exception, message):
self.exception, self.message = exception, message
def __str__(self):
if self.exception:
if self.message:
return 'raise %s, %s' % (self.exception, self.message)
return 'raise %s' % self.exception
return 'raise'
Relativ kompliziert sind die beiden Varianten von import. Ich habe im Gegensatz zu Python relative mit . oder .. beginnende Imports aus der Grammatik entfernt. Bei import kann eine Liste von Modul-Namen folgen, die aus jeweils durch Punkte getrennten Namen bestehen. Außerdem kann optional mit as ein Alias-Name angegeben werden. Bei from import gibt es nur einen Modul-Namen (ohne Möglichkeit für ein Alias), nach dem import dann aber entweder ein Sternchen oder eine Liste von einfachen Namen, denen optional mit as ein Alias-Name folgt.
# import_name: 'import' dotted_as_names
def parse_import_name(self):
return ImportStmt(self.parse_dotted_as_names())
# import_from: 'from' dotted_name 'import' ('*' | import_as_names)
def parse_import_from(self):
dotted_name = self.parse_dotted_name()
self.expect('import')
if self.at('*'):
return FromImportStmt(dotted_name, [])
return FromImportStmt(dotted_name, self.parse_import_as_names())
# dotted_as_names: dotted_as_name {',' dotted_as_name}
def parse_dotted_as_names(self):
dotted_names = [self.parse_dotted_as_name()]
while self.at(','):
dotted_names.append(self.parse_dotted_as_name())
return dotted_names
# dotted_as_name: dotted_name ['as' NAME]
def parse_dotted_as_name(self):
dotted_name = self.parse_dotted_name()
if self.at('as'):
alias = self.parse_name()
else:
alias = dotted_name[-1]
return dotted_name, alias
# dotted_name: NAME {'.' NAME}
def parse_dotted_name(self):
dotted_name = [self.parse_name()]
while self.at('.'):
dotted_name.append(self.parse_name())
return dotted_name
# import_as_names: import_as_name {',' import_as_name}
def parse_import_as_names(self):
names = [self.parse_import_as_name()]
while self.at(','):
names.append(self.parse_import_as_name())
return names
# import_as_name: NAME ['as' NAME]
def parse_import_as_name(self):
name = self.parse_name()
if self.at('as'):
alias = self.parse_name()
else:
alias = name
return name, alias
class ImportStmt(Stmt):
def __init__(self, dotted_names):
self.dotted_names = dotted_names
def __str__(self):
s = ''
for dotted_name in self.dotted_names:
if s:
s += ', '
s += '.'.join(dotted_name[0])
s += ' as '
s += dotted_name[1]
return 'import %s' % s
class FromImportStmt(Stmt):
def __init__(self, dotted_name, names):
self.dotted_name, self.names = dotted_name, names
def __str__(self):
if self.names:
s = ''
for name in self.names:
if s:
s += ', '
s += name[0]
s += ' as '
s += name[1]
else:
s = '*'
return 'from %s import %s' % ('.'.join(self.dotted_name), s)
Die nächsten beiden Anweisungen sind dafür wieder einfacher strukturiert. Tatsächlich sollte sich global gar nicht im AST direkt widerspiegeln sondern beeinflussen, ob ein Bezeichner als lokale oder globale Variable gewertet wird. Dies kann mein Parser allerdings (noch) nicht. Bei assert gibt es ein oder zwei Argumente, den Test und das optionale Argument für den AssertionError.
# global_stmt: 'global' NAME {',' NAME}
def parse_global_stmt(self):
names = [self.parse_name()]
while self.at(','):
names.append(self.parse_name())
return GlobalStmt(names)
# assert_stmt: 'assert' test [',' test]
def parse_assert_stmt(self):
test = self.parse_test()
if self.at(','):
message = self.parse_test()
else:
message = None
return AssertStmt(test, message)
class GlobalStmt(Stmt):
def __init__(self, names):
self.names = names
def __str__(self):
return 'global %s' % ', '.join(self.names)
class AssertStmt(Stmt):
def __init__(self, expr, message):
self.expr, self.message = expr, message
def __str__(self):
if self.message:
return 'assert %s, %s' % (self.expr, self.message)
return 'assert %s' % self.expr
Dies waren alle einfachen Anweisungen.
Die zusammengesetzten Anweisungen unterscheide ich wie folgt:
# compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef
def parse_compound_stmt(self):
if self.at('if'):
return self.parse_if_stmt()
if self.at('while'):
return self.parse_while_stmt()
if self.at('for'):
return self.parse_for_stmt()
if self.at('try'):
return self.parse_try_stmt()
if self.at('def'):
return self.parse_funcdef()
if self.at('class'):
return self.parse_classdef()
Für die if-Anweisung war es praktisch, mit einer lokalen Funktion zu arbeiten, die sich um das Übersetzen der elif-Teile kümmert. Da ich meinen Parser ja mit sich selbst übersetzen will, habe ich mir eingebrockt, jetzt also lokale Funktionen unterstützen zu müssen. Die lokale Funktion könnte allerdings genauso gut auch eine weitere Methode sein.
# if_stmt: 'if' test ':' suite {'elif' test ':' suite} ['else' ':' suite]
def parse_if_stmt(self):
def parse_if_stmt():
if self.at('elif'):
test = self.parse_test()
self.expect(':')
return IfStmt(test, self.parse_suite(), parse_if_stmt())
elif self.at('else'):
self.expect(':')
return self.parse_suite()
return None
test = self.parse_test()
self.expect(':')
return IfStmt(test, self.parse_suite(), parse_if_stmt())
class IfStmt(Stmt):
def __init__(self, test_expr, then_suite, else_suite):
self.test_expr, self.then_suite, self.else_suite = test_expr, then_suite, else_suite
def __str__(self):
return 'if %s:\n%s\nelse:\n%s' % (self.test_expr, self.then_suite, self.else_suite)
Zu while_stmt fällt mir nichts ein. Inzwischen sollte klar sein, wie Anweisungen übersetzt werden.
# while_stmt: 'while' test ':' suite ['else' ':' suite]
def parse_while_stmt(self):
test = self.parse_test()
self.expect(':')
suite = self.parse_suite()
if self.at('else'):
self.expect(':')
else_suite = self.parse_suite()
else:
else_suite = None
return WhileStmt(test, suite, else_suite)
class WhileStmt(Stmt):
def __init__(self, test_expr, while_suite, else_suite):
self.test_expr, self.while_suite, self.else_suite = test_expr, while_suite, else_suite
def __str__(self):
return 'while %s:\n%s\nelse:%s' % (self.test_expr, self.while_suite, self.else_suite)
Bei for_stmt finden wir eine neue Regel exprlist statt testlist wie üblich. Ein test könnte ja eine comparison-Regel sein und diese könnte in benutzen und das würde zu einem Konflikt mit dem in bei for führen. Daher darf die erste List nur expr sein, so sagt die Grammatik. Eigentlich darf es noch weniger sein, denn wie bei der Zuweisung weiter oben diskutiert muss es etwas sein, das auf der linken Seite eines = stehen darf: Eine Variable, eine Index-Operation oder ein Attributzugriff. Für die Liste nach in benutze ich die selbe Methode wie bei return, denn auch hier gilt: Ein einzelnes Argument ist einfach ein Argument, doch folgt ein Komma, wird es zu einem Tupel. Zwei oder mehr Argumente werde ebenfalls zu einem Tupel.
# for_stmt: 'for' exprlist 'in' testlist ':' suite ['else' ':' suite]
def parse_for_stmt(self):
lhs = self.parse_exprlist_as_tuple()
self.expect('in')
items_expr = self.parse_testlist_as_tuple()
self.expect(':')
for_suite = self.parse_suite()
if self.at('else'):
self.expect(':')
else_suite = self.parse_suite()
else:
else_suite = None
return ForStmt(lhs, items_expr, for_suite, else_suite)
# exprlist: expr {',' expr} [',']
def parse_exprlist_as_tuple(self):
expr = self.parse_expr()
if not self.at(','):
return expr
exprs = [expr]
while self.has_test() and self.token() != 'in':
exprs.append(self.parse_expr())
if not self.at(','):
break
return TupleCtr(exprs)
class ForStmt(Stmt):
def __init__(self, lhs, expr, for_suite, else_suite):
self.lhs, self.expr, self.for_suite, self.else_suite = lhs, expr, for_suite, else_suite
def __str__(self):
return 'for %s in %s:\n%s\nelse:\n%s' % (self.lhs, self.expr, self.for_suite, self.else_suite)
Bei try habe ich die Grammatik so umgeschrieben, dass nur try-finally oder try-except, aber nicht sowohl except als auch finally vorkommen darf. Das else habe ich gestrichen, da mir gerade dessen Semantik entfallen ist.
# try_stmt: 'try' ':' suite (except_clause {except_clause} | 'finally' ':' suite)
def parse_try_stmt(self):
self.expect(':')
try_suite = self.parse_suite()
if self.at('finally'):
self.expect(':')
return TryFinallyStmt(try_suite, self.parse_suite())
self.expect('except')
excepts = [self.parse_except_clause()]
while self.at('except'):
excepts.append(self.parse_except_clause())
return TryExceptStmt(try_suite, excepts)
# except_clause: 'except' [test ['as' NAME]] ':' suite
def parse_except_clause(self):
if self.has_test():
exception = self.parse_test()
if self.at('as'):
name = self.parse_name()
else:
name = None
else:
exception = None
name = None
self.expect(':')
return exception, name, self.parse_suite()
class TryFinallyStmt(Stmt):
def __init__(self, try_suite, finally_suite):
self.try_suite, self.finally_suite = try_suite, finally_suite
def __str__(self):
return 'try:\n%s\nfinally:\n%s' % (self.try_suite, self.finally_suite)
class TryExceptStmt(Stmt):
def __init__(self, try_suite, excepts):
self.try_suite, self.excepts = try_suite, excepts
def __str__(self):
s = ''
for e in self.excepts:
s += '\nexcept'
if e[0]:
s += ' '
s += str(e[0])
if e[1]:
s += ' as '
s += e[1]
s += ':\n'
s += str(e[2])
return 'try:\n%s%s' % (self.try_suite, s)
Die Regel funcdef gibt an, wie neue Funktionen oder Methoden definiert werden:
# funcdef: 'def' NAME parameters ':' suite
# parameters: '(' [NAME {',' NAME} [',']] ')'
def parse_funcdef(self):
name = self.parse_name()
params = []
self.expect('(')
if not self.at(')'):
params.append(self.parse_name())
while self.at(','):
if self.at(')'):
break
params.append(self.parse_name())
else:
self.expect(')')
self.expect(':')
return DefStmt(name, params, self.parse_suite())
class DefStmt(Stmt):
def __init__(self, name, params, suite):
self.name, self.params, self.suite = name, params, suite
def __str__(self):
return 'def %s(%s):\n%s' % (self.name, ', '.join(self.params), self.suite)
Und schlussendlich definiert classdef, wie neue Klassen in Python angelegt werden:
# classdef: 'class' NAME ['(' [testlist] ')'] ':' suite
def parse_classdef(self):
name = self.parse_name()
if self.at('('):
super_exprs = self.parse_testlist_opt()
self.expect(')')
else:
super_exprs = []
self.expect(':')
return ClassStmt(name, super_exprs, self.parse_suite())
class ClassStmt(Stmt):
def __init__(self, name, super_exprs, suite):
self.name, self.super_exprs, self.suite = name, super_exprs, suite
def __str__(self):
return 'class %s(%s):\n%s' % (self.name, join_str(self.super_exprs), self.suite)
Die Regel suite kam schon diverse Male vor. Hier ist ihre Implementierung. Eine Suite ist entweder eine durch ; getrennte Folge von einfachen Anweisungen, die alle in einer Zeile stehen müssen, oder aber ein eingerückter Block von (einfachen oder zusammengesetzten) Anweisungen:
# suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT
def parse_suite(self):
if self.at('\n'):
self.expect('!INDENT')
stmts = []
while not self.at('!DEDENT'):
stmts.extend(self.parse_stmt())
return Suite(stmts)
return Suite(self.parse_simple_stmt())
Nun fehlt noch eine letzte Regel, die benutzt wird, um eine komplette Datei einzulesen. Da auch dies eine Liste von Anweisungen ist, gebe ich hier eine Suite zurück. Ich glaube, mein Scanner kann gar keine zusätzlichen \n erzeugen, eigentlich könnte ich daher die Regel etwas vereinfachen, aber ist auch egal.
# file_input: {NEWLINE | stmt} ENDMARKER
def parse_file(self):
stmts = []
while self.token():
if not self.at('\n'):
stmts.extend(self.parse_stmt())
return Suite(stmts)
Hier ist ein Test, der zeigt, wie ich mit dem Parser die Datei mit dem Parser übersetze:
print Parser(open('parser.py').read()).parse_file()
Meine __str__-Funktionen lassen die Einrückung unter den Tisch fallen, aber wenn ich diese wieder manuell ergänze, sieht der Anfang von parser.py wie folgt aus:
from scanner import tokenize as tokenize
from ast import *
class Parser():
def __init__(self, source):
self.tokens = tokenize(source)
self.index = 0
def token(self):
"Return the current token or '' if there is no token."
return self.tokens[self.index] if (self.index < len(self.tokens)) else ''
def advance(self):
'Make next token the current token.'
self.index += 1
def at(self, token):
'If current token is given one, advance to next token and return True.'
if (self.token() == token):
self.advance()
return True
else:
None
def atsel(self, dct):
for k, v in dct.items():
if self.at(k):
return v
else:
None
else:
None
def expect(self, token):
"Raise a syntax error if the current token isn't the expected one."
if not self.at(token):
raise SyntaxError, ('expected %r but found %r' % (token, self.token()))
else:
None
Wie geht es weiter? Aus dem AST kann ich nun mit rekursiven Methoden compile Maschinencode für eine virtuelle Maschine erzeugen. Dann muss ich einen Interpreter für diese virtuelle Maschine bauen, ein Laufzeitsystem für Python entwerfen und habe meinen eigenen Python-Interpreter, der sich selbst ausführen kann.
Alternativ kann ich für jede AST-Klasse eine Methode eval implementieren und auf diese Weise einen einfachen rekursiven Interpreter für Python in Python schreiben. Um es einfacher aufzuschreiben, definiere ich alle Methoden in einer Klasse und benenne die Methoden nach dem Schema Klasse_method. Mit dem folgenden Programm kann ich dann die Methoden den Klassen zuordnen:
for name, method in Interpreter.__dict__.items():
if name[0] != '_':
class_name, method_name = name.split('_', 1)
setattr(globals()[class_name], method_name, method)
Alle AST-Knoten werden im Kontext eines Frame ausgewertet, der lokale und globale Variablen kennt:
class Frame:
def __init__(self, locls, globls):
self.locals, self.globals = locls, globls
def get(self, name):
try:
return self.locals[name]
except KeyError:
try:
return self.globals[name]
except KeyError:
return getattr(self.globals['__builtins__'], name)
def set(self, name, value):
self.locals[name] = value
Die eval-Methoden für Ausdrücke sind Routine. Alle Operationen kann ich eins-zu-eins auf die Python-Operationen zurückführen. Bei Index spare ich mir den Aufwand, mehr als ein Argument zu unterstützen. Bei den Konstruktoren für Tupel, Listen, Sets und Dictionaries ist auch nichts weiter zu beachten.
Einzig zu Call ist etwas zu sagen: Ich unterscheide benutzerdefinierte Funktionen (oder Methoden) von eingebauten dadurch, dass ein Attribut params vorhanden sein muss, welches eine Liste mit den Namen der Parameter enthält, damit ich den passenden Frame bauen kann. Eingebaute Funktionen rufe ich einfach mittels apply auf. Hier wäre praktisch, ein * für Funktionsargumente zu haben, doch das hatte ich ja aus meinem Subset von Python heraus definiert. Hat die Funktion ein Attribut im_func, habe ich eine gebundene oder ungebundene Methode vorliegen, die ich dann wieder auspacke und ggf. den Namen self in meinem Frame an das in der Methode gebundene Exemplar binde.
Für einige AST-Klassen gibt es auch set-Methoden, um sie auf der linken Seite einer Zuweisung benutzen zu können. Dies gilt für Var, Attr, Index und TupleCtr. Letzterer bildet die linke Seite, wenn dort mehrere durch Komma getrennte Ausdrücke standen. Das Original-Python erlaubt hier auch Listen. Das halte ich aber für entbehrlich.
class Interpreter:
def If_eval(self, f):
return (self.then_expr if self.test_expr.eval(f) else self.else_expr).eval(f)
def Or_eval(self, f):
return self.left_expr.eval(f) or self.right_expr.eval(f)
def And_eval(self, f):
return self.left_expr.eval(f) and self.right_expr.eval(f)
def Lt_eval(self, f):
return self.left_expr.eval(f) < self.right_expr.eval(f)
def Gt_eval(self, f):
return self.left_expr.eval(f) > self.right_expr.eval(f)
def Le_eval(self, f):
return self.left_expr.eval(f) <= self.right_expr.eval(f)
def Ge_eval(self, f):
return self.left_expr.eval(f) >= self.right_expr.eval(f)
def Eq_eval(self, f):
return self.left_expr.eval(f) == self.right_expr.eval(f)
def Ne_eval(self, f):
return self.left_expr.eval(f) != self.right_expr.eval(f)
def In_eval(self, f):
return self.left_expr.eval(f) in self.right_expr.eval(f)
def NotIn_eval(self, f):
return self.left_expr.eval(f) not in self.right_expr.eval(f)
def Is_eval(self, f):
return self.left_expr.eval(f) is self.right_expr.eval(f)
def IsNot_eval(self, f):
return self.left_expr.eval(f) is not self.right_expr.eval(f)
def Add_eval(self, f):
return self.left_expr.eval(f) + self.right_expr.eval(f)
def Sub_eval(self, f):
return self.left_expr.eval(f) - self.right_expr.eval(f)
def Mul_eval(self, f):
return self.left_expr.eval(f) * self.right_expr.eval(f)
def Div_eval(self, f):
return self.left_expr.eval(f) / self.right_expr.eval(f)
def Mod_eval(self, f):
return self.left_expr.eval(f) % self.right_expr.eval(f)
def Not_eval(self, f):
return not self.expr.eval(f)
def Pos_eval(self, f):
return +self.expr.eval(f)
def Neg_eval(self, f):
return -self.expr.eval(f)
def Call_eval(self, f):
func = self.expr.eval(f)
values = f.eval_list(self.arguments)
if hasattr(func, 'params'):
locals = {}
if hasattr(func, 'im_func'):
if func.im_self:
values.insert(0, func.im_self)
func = func.im_func
for param, value in zip(func.params, values):
locals[param] = value
return func(Frame(locals, func.globals))
return apply(func, values)
def Index_eval(self, f):
if len(self.slices) != 1: raise UnsupportedOperationError
return self.expr.eval(f)[self.slices[0].eval(f)]
def Index_set(self, f, value):
if len(self.slices) != 1: raise UnsupportedOperationError
self.expr.eval(f)[self.slices[0].eval(f)] = value
def Slice_eval(self, f):
return slice(self.start.eval(f), self.stop.eval(f), self.step.eval(f))
def Attr_eval(self, f):
return getattr(self.expr.eval(f), self.name)
def Attr_set(self, f, value):
setattr(self.expr.eval(f), self.name, value)
def TupleCtr_eval(self, f):
return tuple(f.eval_list(self.exprs))
def TupleCtr_set(self, f, value):
if len(value) < len(self.exprs):
raise ValueError, "need more values to unpack"
if len(value) > len(self.exprs):
raise ValueError, "too many values to unpack"
for expr, value in zip(self.exprs, value):
expr.set(f, value)
def ListCtr_eval(self, f):
return list(f.eval_list(self.exprs))
def SetCtr_eval(self, f):
return set(f.eval_list(self.exprs))
def DictCtr_eval(self, f):
values = []
for expr in self.exprs:
values.append((expr[0].eval(f), expr[1].eval(f)))
return dict(values)
def Lit_eval(self, f):
return self.value
def Var_eval(self, f):
return f.get(self.name)
def Var_set(self, f, value):
f.set(self.name, value)
Mehr passiert bei Anweisungen. Ich würde deren Methoden gerne exec statt eval nennen, doch das ist leider ein Schlüsselwort in Python, sodass ich execute benutze.
Beginnen wir mit PrintStmt. Hier mache ich es mir einfach, und unterstütze nur print-Befehle mit einem Argument. Ich wüsste auf Anhieb nicht, wie mehr als ein Argument unterstützen kann und immer noch print benutzen kann. Wahrscheinlich müsste man auf sys.stdout.write() ausweichen.
def PrintStmt_execute(self, f):
if self.exprs:
if len(self.exprs) != 1: raise UnsupportedOperationError
if self.no_nl:
print self.exprs[0].eval(f),
else:
print self.exprs[0].eval(f)
else:
print
Die wohl einfachste Anweisung ist PassStmt. Es passiert einfach nichts:
def PassStmt_execute(self, f):
pass
Für BreakStmt benutze ich eine BreakException, die ich in for- und while-Schleifen explizit abfange und sie so abbrechen kann:
def BreakStmt_execute(self, f):
raise BreakException
class BreakException(Exception): pass
Den selben Trick benutze ich für ReturnStmt. Auch hier muss ich die Ausführung des Programms abbrechen und die aktuelle Funktion (oder Methode) beenden. Das mache ich mit einer ReturnException. Diesmal übergebe ich aber auch noch den Rückgabewert als Argument für die Exception:
def ReturnStmt_execute(self, f):
raise ReturnException(self.expr.eval(f))
class ReturnException(Exception): pass
Für RaiseStmt habe ich mir nichts weiter überlegt. Ich glaube, es ist nicht okay, einfach die Exception zu werfen, aber ausprobieren kann ich's ja. Glücklicherweise braucht mein Parser Exceptions nur, um Fehlerfälle anzuzeigen:
def RaiseStmt_execute(self, f):
if self.message:
raise self.exception.eval(f), self.message.eval(f)
raise self.exception.eval(f)
Auch die ImportStmt-Anweisung habe ich schnell so hingehackt, ohne es wirklich auszuprobieren. Ich nutze die eingebaute Funktion __import__, um den Import auszuführen, binde dann aber die Variablen in meinem Frame:
def ImportStmt_execute(self, f):
for dotted_name in self.dotted_names:
f.set(dotted_name[1], __import__('.'.join(dotted_name[0])))
Für FromImportStmt lade ich das Modul und picke mir dann die Objekte mit getattr aus dem Modul-Objekt. Falls ich die *-Form vorliegen habe, hoffe ich darauf, dass es ein __all__ mit den Namen gibt. Sonst extrahiere ich alle Namen, die nicht mit einem _ beginnen und nehme diese.
def FromImportStmt_execute(self, f):
m = __import__('.'.join(self.dotted_name))
if self.names:
for name in self.names:
f.set(name[1], getattr(m, name[0]))
else:
try:
names = getattr(m, '__all__')
except AttributeError:
names = []
for n in m.__dict__.keys():
if n[0] != '_':
names.append(n)
for name in names:
f.set(name, getattr(m, name))
GlobalStmt ignoriere ich einfach. Eigentlich müsste ich vor dem Ausführen des AST einmal über den kompletten AST laufen, und für jede Variable entscheiden, ob sie eine lokale Variable ist oder eine globale oder ob das nicht entscheidbar ist und ich mit beidem rechnen muss. Das spare ich mir und nehme immer den letzten Fall an, was es mir unmöglich macht, einer globalen Variable etwas zuweisen zu können. Glücklicherweise brauche ich das bei meinem Parser auch nicht.
def GlobalStmt_execute(self, f):
pass
AssertStmt ist wieder einfach. Auch hier hoffe ich, es ist okay, einfach die Python-Exceptions (AssertionError) direkt zu benutzen und nicht eigene Exceptions zu haben. Aber ich nutze ja auch int, str, list und die anderen Typen von Python direkt für mein Laufzeitsystem.
def AssertStmt_execute(self, f):
if self.message:
assert self.expr.eval(f), self.message.eval(f)
else:
assert self.expr.eval(f)
Zuweisungen nutzen die set-Methoden, die ich für einige Unterklassen von Expr definiert habe. Tatsächlich ist es ein Laufzeitfehler in Python (und wird nicht vom Compiler erkannt), wenn man versucht, z.B. einer Konstanten etwas zuzuweisen. So falsch kann daher meine Implementierung gar nicht sein:
def AssignStmt_execute(self, f):
self.lhs.set(f, self.rhs.eval(f))
def Expr_set(self, f):
raise SyntaxError, "can't assign to literal or operator"
Für += und -= mache ich's glaube ich falsch, wenn ich werte zweimal die linke Seite aus. Dies zu korrigieren (und auch die speziellen Methoden __iadd__ und __isub__ so vorhanden zu benutzen) überlasse ich dem geneigten Leser.
def AddAssignStmt_execute(self, f):
self.lhs.set(f, self.lhs.eval(f) + self.rhs.eval(f))
def SubAssignStmt_execute(self, f):
self.lhs.set(f, self.lhs.eval(f) - self.rhs.eval(f))
Die letzte einfache Anweisung ist ExprStmt, welche einfach den Ausdruck des Seiteneffekts wegen auswertet. Sind es mehrere Ausdrücke in Form eines Tupels, wird auch dieses erzeugt und weggeschmissen. Könnte man effizienter machen -- oder auch nicht.
def ExprStmt_execute(self, f):
self.expr.eval(f)
Kommen wir zu den zusammengesetzten Anweisungen. Hier wäre es praktisch gewesen, würde ich im Parser, wenn ein optionaler else-Zweig fehlt, stattdessen PassStmt eintragen. Dann müsste ich jetzt keine Sonderfälle berücksichtigen:
def IfStmt_execute(self, f):
if self.test_expr.eval(f):
self.then_suite.execute(f)
else:
if self.else_suite:
self.else_suite.execute(f)
Bei WhileStmt und BreakStmt sieht man, wie BreakException benutzt wird, um die Schleife abzubrechen. Bei for muss für jedes Element, über das iteriert wird, noch die Variablen binden:
def WhileStmt_execute(self, f):
while self.test_expr.eval(f):
try:
self.while_suite.execute(f)
except BreakException:
break
else:
if self.else_suite:
self.else_suite.execute(f)
def ForStmt_execute(self, f):
for item in self.items_expr.eval(f):
self.lhs.set(f, item)
try:
self.for_suite.execute(f)
except BreakException:
break
else:
if self.else_suite:
self.else_suite.execute(f)
Während TryFinally direkt auf try/finally abgebildet werden kann, bin ich mir nicht sicher, ob ich in TryExceptStmt mit der Implementierung von except richtig liege. Ich prüfe die Exception der Reihe nach gegen das, wozu der Ausdruck hinter except auswertet, in der Hoffnung, dass ist eine Unterklasse von Exception. Dann binde ich die Exception an den optionalen Namen und werte die "Suite" aus. Passt keine der übergebenen Ausdrücke, werfe ich erneut die Exception.
def TryFinallyStmt_execute(self, f):
try:
self.try_suite.execute(f)
finally:
self.finally_suite.execute(f)
def TryExceptStmt_execute(self, f):
try:
self.try_suite.execute(f)
except Exception as e:
for expr, name, suite in self.excepts:
if expr is None or isinstance(e, expr.eval(f)):
if name:
f.set(name, e)
suite.execute(f)
break
else:
raise e
Eine benutzerdefinierte Funktion ist eine, die ein Attribut params hat, siehe Call. Außerdem muss ich mir die aktuellen globalen Variablen merken. Dann kann ich die Funktion in meinem Frame an eine lokale Variable binden. Die Funktion selbst muss auf ReturnException achten (siehe ReturnStmt).
def DefStmt_execute(self, f):
def userfunc(f):
try:
self.suite.execute(f)
except ReturnException as e:
return e.args[0]
userfunc.__name__ = self.name
userfunc.params = self.params
userfunc.globals = f.globals
f.set(self.name, userfunc)
Eine Klasse definiere ich, indem ich zunächst den Rumpf in einem neuen Frame auswerte und dann dessen locals-Dictionary als Dictionary der Klasse benutze, wenn ich die Klasse mit type erzeuge:
def ClassStmt_execute(self, f):
if self.super_exprs:
supers = tuple(f.eval_list(self.super_exprs))
else:
supers = (object,)
locals = {}
self.suite.execute(Frame(locals, f.globals))
f.set(self.name, type(self.name, supers, locals))
Bleibt noch das Auswerten einer Suite:
def Suite_execute(self, f):
for stmt in self.stmts:
stmt.execute(f)
Der Interpreter ist fertig. Hier ein paar Tests:
def run(s):
globls = {'__builtins__': __builtins__}
frame = Frame(globls, globls)
Parser(s).parse_file().execute(frame)
run("3+4")
run("for i in 1, 2, 3: print i")
run("def a(n): return n * n\nprint a(3)")
run("for x, y in zip(range(2, 5), 'abc'): print x * y")
run("class A:\n def m(self): return 3\nprint A().m()")
Theoretisch müsste er sich jetzt selbst ausführen können -- leider habe ich ein Problem: Erzeuge ich eine neue Klasse, wird automatisch __init__ aufgerufen und diese Methode hat jetzt als benutzerdefinierte Funktion die falsche Argument-Liste. Wie ich das reparieren kann, fällt mir gerade nicht ein. Wahrscheinlich kann ich nicht einfach vorhandene Klassen-Objekte benutzen.
Ich empfand es als äußerst schmerzlich, keine List-Comprehensions zu haben. Hier ist die geänderte Grammatik. Um zu entscheiden, ob innerhalb der eckigen Klammern eine Liste von Ausdrücken oder ein Ausdruck, dem ein for folgt, steht, muss die alte Regel testlist aufgebrochen werden. Auch die Elemente, über die das for iterieren soll, können nicht der test-Regel folgen, weil diese auch ein nachgestelltes if erlauben würde, was zu Verwechslungen mit list_if führen würde. Daher gibt es die neue Regel testlist_safe.
atom: ... | '[' [listmaker] ']' | ...
listmaker: test ( list_for | {',' test} [','] )
list_for: 'for' exprlist 'in' testlist_safe [list_iter]
list_iter: list_for | list_if
list_if: 'if' or_test [list_iter]
testlist_safe: or_test {',' or_test} [',']
Die Übersetzung der Regeln in Python ist nicht weiter schwer. Der neue AST-Knoten ListCompr fasst den auszuwertenden Ausdruck und die for-Schleife, repräsentiert als Exemplar von ComprFor zusammen. Da sich for und if beliebig schachteln lassen, kann jedes ComprFor- bzw. ComprIf-Exemplar wieder ein weiteres Exemplar enthalten.
# listmaker: test ( list_for | {',' test} [','] )
def parse_listmaker(self):
expr = self.parse_test()
if self.at('for'):
return ListCompr(expr, self.parse_list_for())
exprs = [expr]
while self.at(','):
if not self.has_test():
break
exprs.append(self.parse_test())
return exprs
# list_for: 'for' exprlist 'in' testlist_safe [list_iter]
def parse_list_for(self):
lhs = self.parse_exprlist_as_tuple()
self.expect('in')
items_expr = self.parse_testlist_safe_as_tuple()
return ComprFor(lhs, items_expr, self.parse_list_iter_opt())
# list_iter: list_for | list_if
def parse_list_iter_opt(self):
if self.at('for'):
return self.parse_list_for()
if self.at('if'):
return self.parse_list_if()
return None
# list_if: 'if' or_test [list_iter]
def parse_list_if(self):
return ComprIf(self.parse_or_test(), self.parse_list_iter_opt())
# testlist_safe: or_test {',' or_test} [',']
def parse_testlist_safe_as_tuple(self):
expr = self.parse_or_test()
if not self.at(','):
return expr
exprs = [expr]
while self.has_test() and self.token() != 'in':
exprs.append(self.parse_or_test())
if not self.at(','):
break
return TupleCtr(exprs)
class ListCompr(Expr):
def __init__(self, expr, compr):
self.expr, self.compr = expr, compr
def __str__(self):
return '[%s %s]' % (self.expr, self.compr)
def eval(self, f):
result = []
self.compr.doit(f, self.expr, result)
return result
class ComprFor:
def __init__(self, lhs, items_expr, compr):
self.lhs, self.items_expr, self.compr = lhs, items_expr, compr
def __str__(self):
return 'for %s in %s %s' % (self.lhs, self.items_expr, self.compr)
def doit(self, f, expr, result):
for item in self.items_expr.eval(f):
self.lhs.set(f, item)
if self.compr:
self.compr.doit(f, expr, result)
else:
result.append(expr.eval(f))
class ComprIf:
def __init__(self, test_expr, compr):
self.test_expr, self.compr = test_expr, compr
def __str__(self):
return 'if %s %s' % (self.test_expr, self.compr)
def doit(self, f, expr, result):
if self.test_expr.eval(f):
if self.compr:
self.compr.doit(f, expr, result)
else:
result.append(expr.eval(f))
Die Auswertung einer List-Comprehension habe ich auch gleich direkt in der Klasse ListCompr implementiert. Der für jedes Element der Schleife zu berechnende Ausdruck wird zusammen mit der Liste, in der die Ergebnisse gesammelt werden, an ComprFor bzw. ComprIf übergeben. Diese machen in der Methode doit ihr Ding und delegieren das Berechnen des Ausdrucks entweder an ein weiteres ComprFor bzw. ComprIf-Exemplar oder führen die Berechnung aus.
Der Original-Python-Interpreter kann mehrere Zeilen, die auf \ enden, zu einer logischen Zeile zusammenfassen. Dies erlaubt es, lange Zeilen, wie die folgende, auf mehr als eine Zeile aufzuteilen:
KEYWORDS = set(\
"and,as,assert,break,class,continue,def,del,elif,else,except,exec,"\
"finally,for,from,global,if,import,in,is,lambda,not,or,pass,print,"\
"raise,return,try,while,with,yield".split(','))
Ein einfaches replace ist alles, was es braucht:
...
for token in findall(..., s.replace('\\\n', '')):
...
Nun kann ich auch den vollständigen regulären Ausdruck für findall zeigen:
for token in findall(\
"(?m)^ *(?:#.*)?\n|#.*$|(^ +|\n|\\w+|[()\\[\\]{}:.,;]|[+\\-*/%<>=]=?|"\
"!=|'(?:\\\\[n'\"\\\\]|[^'])*'|\"(?:\\\\[n'\"\\\\]|[^\"])*\")| +", \
s.replace('\\\n', '')):
Die Variable KEYWORDS ist wiederum praktisch, um in parse_name sicherzustellen, dass Schlüsselwörter nicht als Bezeichner benutzt werden:
class Parser...
def parse_name(self):
token = self.token()
if token and (token[0].isalpha() or token[0] == '_') and token not in KEYWORDS:
self.advance()
return token
raise SyntaxError, "expected NAME but found %r" % token
Python ignoriert innerhalb einer geöffneten runden, eckigen oder geschweiften Klammer die Einrückung bis zur passenden schließenden Klammer. Dies ist ein weiterer Weg, lange Ausdrücke in mehr als einer Zeile unterzubringen.
Ich zähle die Anzahl der geöffneten Klammern in der Variable level. Gibt es geöffnete Klammern, bestimme ich zwar nach wie vor die Einrückung, passe sie aber nie an. Außerdem unterdrücke ich alle Zeilenumbrüche.
def tokenize(s):
...
level = 0
for ...
if token:
if token[0] == ' ':
...
else:
if level > 0 or token == '\n':
new_indent = 0
else:
...
if token in '([{':
level += 1
if token in '}])':
level -= 1
if level == 0 or token != '\n':
tokens.append(token)
...
Jetzt wären noch mehrzeilige Strings praktisch. Der angepasste reguläre Ausdruck sähe so aus: '("""(?:.|\n)*?"""|\'\'\'(?:.|\n)*?\'\'\')'. Er muss vor den einfachsten Strings stehen. Um dem Parser die Arbeit zu ersparen, diese Strings gesondert zu behandeln, baue ich noch folgendes in tokenize ein:
def tokenize(s):
...
for ...
if token:
# normalize strings
if token[:3] == '"""' or token[:3] == "'''":
token = token[2:-2]
if token[0] == '"':
token = "'%s'" % token[1:-1]
if token[0] == "'":
token = token.replace('\\n', '\n').replace("\\'", "'")\
.replace('\\"', '"').replace('\\\\', '\\')
Dreifach-Strings mache ich zu einfachen Strings. Alle Strings kann man an einem einfachen Anführungsstrich erkennen. Innerhalb des Strings ersetze ich \n, \', \" oder \\.
Der Parser kann dann wie folgt vereinfacht werden:
def parse_atom(self):
...
if token:
if token[0] == "'":
s = ''
while token and token[0] == "'":
s += token[1:-1]
self.advance()
token = self.token()
return Lit(s)