Abhängig davon, wie kompliziert die Grammatik ist, kann man's auch einfach selbst machen. Eine EBNF-Grammatik hat ja gerade die Eigenschaft, dass man sie per Hand in einen rekursiv absteigenden LL(1) Parser verwandeln kann (zeigt Wirth als Erfinder dieser BNF-Variante sehr schön in seinem kleinen Compilierbau-Büchlein).
Beispiel: Gegeben sei folgende Grammatik:
Code: Alles auswählen
sexp = atom | list
atom = SYMBOL | NUMBER
list = "(" {sexp} ["." sexp] ")"
Dann kann ich wie folgt einen Parser dafür bauen. Ich baue ihn klassisch in zwei Teilen. Zunächst erkenne ich SYMBOL und NUMBER:
Code: Alles auswählen
class Parser:
def __init__(self, source):
self.source = source
def peek(self):
"Return the next char or the empty string."
return self.source[0] if self.source else ""
def consume(self):
"Return the next char, consuming it."
ch = self.peek()
self.source = self.source[1:]
return ch
def next_token(self):
"Return the next token (one of `().NS`) and (in case of `NS`) its value."
while self.peek() in "\n ": self.consume()
if self.peek() == "": return "", None
if self.peek() == "(": return self.consume(), None
if self.peek() == ")": return self.consume(), None
if self.peek() == ".": return self.consume(), None
s = self.consume()
while self.peek() and self.peek() not in "\n (.)":
s += self.consume()
if s.isdigit():
return "N", int(s)
else:
return "S", s
Testen wir schnell, ob `next_token` funktioniert:
Code: Alles auswählen
p = Parser("(defn fac (n) (? (= n 0) 1 (* n (fac (1- n)))))")
n, v = p.next_token()
while n:
print(n, v)
n, v = p.next_token()
( None
S defn
S fac
...
Nun kann ich den eigentlichen Parser beginnen. Als LL(1)-Parser muss ich immer Zugriff auf das nächste Symbol haben, bei mir ein Tupel aus Typ und Wert. In Python 3, was ich hier benutze, gibt es leider nicht mehr die IMHO praktische Möglichkeit, ein übergebenes Tupel sofort in der Argumentliste zu zerlegen. Daher muss ich hässlicherweise mit tv[0] und tv[1] arbeiten. Möglicherweise wären zwei Exemplarvariablen doch die bessere Modellierung gewesen.
Code: Alles auswählen
def parse(self):
return self.parse_sexp(self.next_token())
def parse_sexp(self, tv):
if tv[0] in "NS": return self.parse_atom(tv)
if tv[0] == "(": return self.parse_list(self.next_token())
raise SyntaxError
def parse_atom(self, tv):
return tv[1]
def parse_list(self, tv):
if tv[0] == ")": return None
if tv[0] == ".":
v = self.parse_sexp(self.next_token())
t, _ = self.next_token()
if t == ")": return v
raise SyntaxError
return (self.parse_sexp(tv), self.parse_list(self.next_token()))
Mein Parser wandet den Lisp S-Ausdruck in Cons-Zellen, repräsentiert durch Python-Tupel und Atome, repräsentiert durch Python Strings und Integers, um. Los geht's mit `parse`, welches die erste Regel, `parse_sex` mit dem ersten Token aufruft. In EBNF sieht diese Regel so aus: "sexp = atom | list". Die Theorie spricht jetzt von einer first(R)-Menge, die man für jede Regel R definieren kann und die jeweils die Token enthält, mit denen jede Alternative einer enthaltenen Regel beginnt bzw. die Token (aka Nichtterminalsymbole) selbst. Es ist schnell zu sehen, dass
Code: Alles auswählen
first(atom) = NUMBER, SYMBOL
first(list) = "("
first(sexp) = first(atom) + first(list)
Um also zu entscheiden, ob wir ein Atom oder eine Liste parsen wollen, müssen wir uns anschauen, welches Token wir vorliegen haben. Dann verzweigen wir zu `parse_atom` oder `parse_list`, wobei wir hier das ( konsumieren und die Methode mit den nächsten Token aufrufen. Bei `parse_atom` ist nichts weiter zu tun als einfach den Wert des Tokens zurückzugeben. Die Methode `next_token` (mein Scanner), macht das "zufällig" schon richtig.
Bei `parse_list` ist es wichtig, die rest(R)-Menge zu kennen. Was passiert, wenn weder das {} noch das [] zutrifft? Dann haben wir ein ")". In diesem Fall haben wir die komplette Liste erkannt. Das [] wird zu einem "if". Das {} wird in der Regel zu seinem "while", doch ich habe mich hinreißen lassen und die rekursive Struktur von aus Cons-Zellen bestehenden Lisp-Listen ausgenutzt und einen rekursiven Ansatz gewählt. Es funktioniert:
Code: Alles auswählen
p = Parser("(defn fac (n) (? (= n 0) 1 (* n (fac (1- n)))))")
print(p.parse())
('defn', ('fac', (('n', None), (('?', (('=', ('n', (0, None))), (1, (('*', ('n', (('fac', (('1-', ('n', None)), None)), None))), None)))), None))))
Da ich neben proper lists auch improper lists bzw. dotted pairs erkenne, kann ich nicht einfach eine Python-Liste als Repräsentation benutzen. Aber ich kann so tun und wenigstens den Parser dafür ohne Rekursion schreiben. Dadurch wird klarer, wie die Struktur der Grammatik eins zu eins in ein Programm umgewandelt werden kann:
Code: Alles auswählen
def parse_list(self, tv):
while tv[0] not in ".)":
self.parse_sexpr(tv)
tv = self.next_token()
if tv[0] == ".":
self.parse_sexpr(self.next_token())
tv = self.next_token()
if tv[0] == ")": return
raise SyntaxError
Stefan
)