最小的 parser 走一句
(每道题开头都有同一段:T() 是上一站 lexer 的替身——源码里 token 之间用空格分开,它切成 (kind, text, line, col);show() 把树写成一行:二元运算全加括号,语句之间用 |。)
一个只认「let 名字 = 值 ;」的最小 parser。看它走完一句之后交回什么、位置停在哪:
KEYWORDS = ("let", "if", "else", "while")
CMP = (">=", "<=", "==", "!=", "<", ">")
def T(src):
toks = []
for ln, line in enumerate(src.split("\n"), 1):
pos = 0
for w in line.split():
pos = line.index(w, pos)
if w in KEYWORDS:
k = "KEYWORD"
elif w[0] == '"':
k = "STRING"
elif w.isdigit():
k = "NUMBER"
elif w[0].isalpha() or w[0] == "_":
k = "IDENT"
else:
k = "OP"
toks.append((k, w, ln, pos + 1))
pos += len(w)
toks.append(("EOF", "", ln, pos + 1))
return toks
class ParseError(Exception):
def __init__(self, want, got, line, col):
super().__init__("期待「" + want + "」遇到「" + got + "」@" + str(line) + ":" + str(col))
self.want, self.got, self.line, self.col = want, got, line, col
def show(n):
if n[0] == "num" or n[0] == "var":
return str(n[1])
if n[0] == "str":
return '"' + n[1] + '"'
if n[0] == "bin":
return "(" + show(n[2]) + n[1] + show(n[3]) + ")"
if n[0] == "let":
return "let:" + n[1] + "=" + show(n[2])
if n[0] == "assign":
return n[1] + "=" + show(n[2])
if n[0] == "if":
s = "if[" + show(n[1]) + "]{" + ";".join(show(x) for x in n[2]) + "}"
if n[3] is not None:
s += "else{" + ";".join(show(x) for x in n[3]) + "}"
return s
if n[0] == "while":
return "while[" + show(n[1]) + "]{" + ";".join(show(x) for x in n[2]) + "}"
if n[0] == "program":
return "|".join(show(x) for x in n[1])
return "?"
class P:
def __init__(self, toks):
self.toks = toks
self.i = 0
def peek(self):
return self.toks[self.i]
def advance(self):
t = self.toks[self.i]
self.i += 1
return t
def at(self, text):
return self.peek()[1] == text
def expect(self, text):
t = self.peek()
if t[1] != text:
raise ParseError(text, t[1] or "文件结尾", t[2], t[3])
return self.advance()
def expect_kind(self, kind):
t = self.peek()
if t[0] != kind:
raise ParseError(kind, t[1] or "文件结尾", t[2], t[3])
return self.advance()
def value(self):
t = self.advance()
if t[0] == "NUMBER":
return ("num", int(t[1]))
if t[0] == "STRING":
return ("str", t[1][1:-1])
return ("var", t[1])
def let_stmt(self):
self.expect("let")
name = self.expect_kind("IDENT")[1]
self.expect("=")
v = self.value()
self.expect(";")
return ("let", name, v)
p = P(T("let rate = 12 ;"))
node = p.let_stmt()
print(show(node) + "/" + str(p.i))
全部评论