前三句的装饰树
（每道题开头都有同一段：上一站的 parser（多记了位置）、show()，和错误类 SemError——错误写成一行「原因@行:列」。）
贯穿的源码：
let rate = 12 ;
let msg = "hi" ;
let total = rate * 3 ;
if ( total >= 30 ) { let big = 1 ; total = total - big ; } else { total = 0 ; }对贯穿源码的前三句 let 逐句 annotate 并登记，再用 show_t 打出来：
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))
class Parser:
def __init__(self, toks):
self.toks, self.i = toks, 0
def peek(self):
return self.toks[self.i]
def advance(self):
self.i += 1
return self.toks[self.i - 1]
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 program(self):
stmts = []
while self.peek()[0] != "EOF":
stmts.append(self.stmt())
return ("program", stmts)
def stmt(self):
t = self.peek()
if self.at("let"):
self.advance()
name = self.expect_kind("IDENT")
self.expect("=")
e = self.expr()
self.expect(";")
return ("let", name[1], e, name[2], name[3])
if self.at("if"):
self.advance()
self.expect("(")
c = self.expr()
self.expect(")")
body = self.block()
alt = None
if self.at("else"):
self.advance()
alt = self.block()
return ("if", c, body, alt, t[2], t[3])
if self.at("while"):
self.advance()
self.expect("(")
c = self.expr()
self.expect(")")
return ("while", c, self.block(), t[2], t[3])
name = self.expect_kind("IDENT")
self.expect("=")
e = self.expr()
self.expect(";")
return ("assign", name[1], e, name[2], name[3])
def block(self):
self.expect("{")
stmts = []
while not self.at("}"):
if self.peek()[0] == "EOF":
self.expect("}")
stmts.append(self.stmt())
self.expect("}")
return stmts
def expr(self):
left = self.sum_()
if self.peek()[1] in CMP:
t = self.advance()
return ("bin", t[1], left, self.sum_(), t[2], t[3])
return left
def sum_(self):
left = self.term()
while self.peek()[1] in ("+", "-"):
t = self.advance()
left = ("bin", t[1], left, self.term(), t[2], t[3])
return left
def term(self):
left = self.factor()
while self.peek()[1] in ("*", "/"):
t = self.advance()
left = ("bin", t[1], left, self.factor(), t[2], t[3])
return left
def factor(self):
t = self.peek()
if t[0] == "NUMBER":
self.advance()
return ("num", int(t[1]))
if t[0] == "STRING":
self.advance()
return ("str", t[1][1:-1])
if t[0] == "IDENT":
self.advance()
return ("var", t[1], t[2], t[3])
if t[1] == "(":
self.advance()
e = self.expr()
self.expect(")")
return e
raise ParseError("表达式", t[1] or "文件结尾", t[2], t[3])
def parse(src):
return Parser(T(src)).program()
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 SemError(Exception):
def __init__(self, msg, line, col):
super().__init__(msg + "@" + str(line) + ":" + str(col))
self.msg, self.line, self.col = msg, line, col
class Scope:
def __init__(self, parent=None):
self.vars = {}
self.parent = parent
def declare(self, name, typ, line, col):
if name in self.vars:
raise SemError("重复声明「" + name + "」", line, col)
self.vars[name] = typ
def lookup(self, name):
s = self
while s is not None:
if name in s.vars:
return s.vars[name]
s = s.parent
return None
def annotate(n, scope, ann):
if n[0] in ("num", "str"):
t = n[0]
elif n[0] == "var":
t = scope.lookup(n[1])
if t is None:
raise SemError("未定义「" + n[1] + "」", n[2], n[3])
else:
l, r = annotate(n[2], scope, ann), annotate(n[3], scope, ann)
if l != r:
raise SemError("类型不匹配「" + l + "」「" + r + "」", n[4], n[5])
t = "bool" if n[1] in CMP else l
ann[id(n)] = t
return t
def show_t(n, ann):
if n[0] == "num" or n[0] == "var":
return str(n[1]) + ":" + ann[id(n)]
if n[0] == "str":
return '"' + n[1] + '":' + ann[id(n)]
if n[0] == "bin":
return "(" + show_t(n[2], ann) + n[1] + show_t(n[3], ann) + "):" + ann[id(n)]
if n[0] == "let":
return "let:" + n[1] + "=" + show_t(n[2], ann)
if n[0] == "assign":
return n[1] + "=" + show_t(n[2], ann)
return "?"
SRC = ('let rate = 12 ;\nlet msg = "hi" ;\nlet total = rate * 3 ;\n'
'if ( total >= 30 ) { let big = 1 ; total = total - big ; } else { total = 0 ; }')
p = parse(SRC)
sc = Scope()
ann = {}
for s in p[1][:3]:
sc.declare(s[1], annotate(s[2], sc, ann), s[3], s[4])
print("|".join(show_t(s, ann) for s in p[1][:3]))
全部评论