)Code: Alles auswählen
sexp = atom | list
atom = SYMBOL | NUMBER
list = "(" {sexp} ["." sexp] ")"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", sCode: 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
...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()))Code: Alles auswählen
first(atom) = NUMBER, SYMBOL
first(list) = "("
first(sexp) = first(atom) + first(list)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))))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