补全：把 VM 的环境当根

👁️ 2 人浏览 💬 0 人评论 ❤️ 添加收藏

（每道题开头都有同一段：06 的词法/语法/show、Env、RunError；本条加的 compile_expr / compile_stmt / compile_block / compile_program（树 → 指令列表）、listing(code)（把指令列表打成「序号:指令操作数|…」）、Code（函数值：名、参数、代码、定义时的环境）、run_code(code, env, out)（栈式 VM，交回执行的指令条数）、run_vm(src)。）

把运行时和 VM 连起来：补全 live_names(env)——从一个 Env 出发，沿父链收集所有变量名（这些就是「根」）；再补 closure_env_count(env)：值里有几个 Code（每个 Code 都拴着一个环境，那个环境也活着）。

提交你的答案

请登录后提交答案。

去登录

← 补全：从根出发标记 Python 和本条的对应 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

KEYWORDS = ("let", "if", "else", "while", "fn", "return", "print")
CMP = (">=", "<=", "==", "!=", "<", ">")

def T(src):
    toks = []
    ln, pos = 1, 0
    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("print"):
            self.advance()
            e = self.expr()
            self.expect(";")
            return ("print", e, t[2], t[3])
        if self.at("return"):
            self.advance()
            e = self.expr()
            self.expect(";")
            return ("return", e, t[2], t[3])
        if self.at("fn"):
            self.advance()
            name = self.expect_kind("IDENT")
            self.expect("(")
            params = []
            while not self.at(")"):
                params.append(self.expect_kind("IDENT")[1])
                if self.at(","):
                    self.advance()
            self.expect(")")
            return ("fn", name[1], params, self.block(), t[2], t[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()
            if self.at("("):
                self.advance()
                args = []
                while not self.at(")"):
                    args.append(self.expr())
                    if self.at(","):
                        self.advance()
                self.expect(")")
                return ("call", t[1], args, t[2], t[3])
            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] == "call":
        return n[1] + "(" + ",".join(show(a) for a in n[2]) + ")"
    if n[0] == "let":
        return "let:" + n[1] + "=" + show(n[2])
    if n[0] == "assign":
        return n[1] + "=" + show(n[2])
    if n[0] == "print":
        return "print:" + show(n[1])
    if n[0] == "return":
        return "return:" + show(n[1])
    if n[0] == "fn":
        return "fn:" + n[1] + "(" + ",".join(n[2]) + "){" + ";".join(show(x) for x in n[3]) + "}"
    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 RunError(Exception):
    def __init__(self, msg, line, col, stack=None):
        super().__init__(msg + "@" + str(line) + ":" + str(col))
        self.msg, self.line, self.col = msg, line, col
        self.stack = list(stack) if stack else ["main"]

def where(self):
        return ">".join(self.stack)

class Env:
    def __init__(self, parent=None):
        self.vars = {}
        self.parent = parent

def define(self, name, value):
        self.vars[name] = value

def find(self, name):
        e = self
        while e is not None:
            if name in e.vars:
                return e
            e = e.parent
        return None

def get(self, name, line, col, stack):
        e = self.find(name)
        if e is None:
            raise RunError("未定义「" + name + "」", line, col, stack)
        return e.vars[name]

def set(self, name, value, line, col, stack):
        e = self.find(name)
        if e is None:
            raise RunError("未定义「" + name + "」", line, col, stack)
        e.vars[name] = value

class Closure:
    def __init__(self, name, params, body, env):
        self.name, self.params, self.body, self.env = name, params, body, env

class ReturnSignal(Exception):
    def __init__(self, value):
        self.value = value

def compile_expr(n, code):
    if n[0] == "num" or n[0] == "str":
        code.append(("PUSH", n[1]))
    elif n[0] == "var":
        code.append(("LOAD", n[1], n[2], n[3]))
    elif n[0] == "bin":
        compile_expr(n[2], code)
        compile_expr(n[3], code)
        code.append(("BIN", n[1], n[4], n[5]))
    elif n[0] == "call":
        for a in n[2]:
            compile_expr(a, code)
        code.append(("CALL", n[1], len(n[2]), n[3], n[4]))

def compile_stmt(n, code):
    if n[0] == "let":
        compile_expr(n[2], code)
        code.append(("DEFINE", n[1]))
    elif n[0] == "assign":
        compile_expr(n[2], code)
        code.append(("STORE", n[1], n[3], n[4]))
    elif n[0] == "print":
        compile_expr(n[1], code)
        code.append(("PRINT",))
    elif n[0] == "expr":
        compile_expr(n[1], code)
        code.append(("POP",))
    elif n[0] == "return":
        compile_expr(n[1], code)
        code.append(("RETURN",))
    elif n[0] == "fn":
        body = compile_block(n[3])
        body.append(("PUSH", 0))
        body.append(("RETURN",))
        code.append(("MAKE_FN", n[1], n[2], body))
    elif n[0] == "if":
        compile_expr(n[1], code)
        jf = len(code)
        code.append(("JUMP_IF_FALSE", None))
        code.append(("ENTER",))
        for s in n[2]:
            compile_stmt(s, code)
        code.append(("LEAVE",))
        if n[3] is None:
            code[jf] = ("JUMP_IF_FALSE", len(code))
        else:
            je = len(code)
            code.append(("JUMP", None))
            code[jf] = ("JUMP_IF_FALSE", len(code))
            code.append(("ENTER",))
            for s in n[3]:
                compile_stmt(s, code)
            code.append(("LEAVE",))
            code[je] = ("JUMP", len(code))
    elif n[0] == "while":
        top = len(code)
        compile_expr(n[1], code)
        jf = len(code)
        code.append(("JUMP_IF_FALSE", None))
        code.append(("ENTER",))
        for s in n[2]:
            compile_stmt(s, code)
        code.append(("LEAVE",))
        code.append(("JUMP", top))
        code[jf] = ("JUMP_IF_FALSE", len(code))

def compile_block(stmts):
    code = []
    for s in stmts:
        compile_stmt(s, code)
    return code

def compile_program(tree):
    return compile_block(tree[1])

def listing(code):
    return "|".join(str(i) + ":" + ":".join(str(x) for x in ins[:2]) for i, ins in enumerate(code))

class Code:
    def __init__(self, name, params, code, env):
        self.name, self.params, self.code, self.env = name, params, code, env

HOOK = None      # 调试钩子：每次压帧之后调 HOOK(frames)

def run_code(code, env, out):
    frames = [[code, 0, env, [], "main"]]
    steps = 0
    while frames:
        f = frames[-1]
        if f[1] >= len(f[0]):
            frames.pop()
            continue
        ins = f[0][f[1]]
        f[1] += 1
        steps += 1
        op = ins[0]
        stack = f[3]
        names = [x[4] for x in frames]
        if op == "PUSH":
            stack.append(ins[1])
        elif op == "LOAD":
            stack.append(f[2].get(ins[1], ins[2], ins[3], names))
        elif op == "DEFINE":
            f[2].define(ins[1], stack.pop())
        elif op == "STORE":
            f[2].set(ins[1], stack.pop(), ins[2], ins[3], names)
        elif op == "BIN":
            r = stack.pop()
            l = stack.pop()
            opr = ins[1]
            if opr in CMP:
                stack.append({">=": l >= r, "<=": l <= r, "==": l == r, "!=": l != r, "<": l < r, ">": l > r}[opr])
            elif opr == "+":
                if type(l) != type(r):
                    raise RunError("类型不匹配", ins[2], ins[3], names)
                stack.append(l + r)
            elif type(l) is not int or type(r) is not int:
                raise RunError("类型不匹配", ins[2], ins[3], names)
            elif opr == "-":
                stack.append(l - r)
            elif opr == "*":
                stack.append(l * r)
            else:
                if r == 0:
                    raise RunError("除以零", ins[2], ins[3], names)
                stack.append(l // r)
        elif op == "PRINT":
            v = stack.pop()
            out.append(("true" if v else "false") if isinstance(v, bool) else str(v))
        elif op == "POP":
            stack.pop()
        elif op == "JUMP":
            f[1] = ins[1]
        elif op == "JUMP_IF_FALSE":
            if not stack.pop():
                f[1] = ins[1]
        elif op == "ENTER":
            f[2] = Env(f[2])
        elif op == "LEAVE":
            f[2] = f[2].parent
        elif op == "MAKE_FN":
            f[2].define(ins[1], Code(ins[1], ins[2], ins[3], f[2]))
        elif op == "CALL":
            fn = f[2].get(ins[1], ins[3], ins[4], names)
            if not isinstance(fn, Code):
                raise RunError("不是函数「" + ins[1] + "」", ins[3], ins[4], names)
            if ins[2] != len(fn.params):
                raise RunError("参数个数不对「" + fn.name + "」", ins[3], ins[4], names)
            if len(frames) > 50:
                raise RunError("调用太深「" + fn.name + "」", ins[3], ins[4], names)
            args = [stack.pop() for _ in fn.params][::-1]
            local = Env(fn.env)
            for p, a in zip(fn.params, args):
                local.define(p, a)
            frames.append([fn.code, 0, local, [], fn.name])
            if HOOK is not None:
                HOOK(frames)
        elif op == "RETURN":
            v = stack.pop()
            frames.pop()
            if frames:
                frames[-1][3].append(v)
        else:
            raise RunError("不认识的指令「" + op + "」", 0, 0, names)
    return steps

def run_vm(src):
    out = []
    run_code(compile_program(parse(src)), Env(), out)
    return "|".join(out)

def run_vm_safe(src):
    out = []
    try:
        run_code(compile_program(parse(src)), Env(), out)
    except RunError as e:
        out.append("错误:" + e.msg + "@" + str(e.line) + ":" + str(e.col) + " 调用栈 " + e.where())
    except ParseError as e:
        out.append("语法错误 " + str(e))
    return "|".join(out)

def live_names(env):
    # TODO
    return set()

def closure_env_count(env):
    # TODO
    return 0

g = Env()
out = []
run_code(compile_program(parse("let x = 1 ;\nfn make ( ) { let n = 0 ; fn inc ( ) { n = n + 1 ; return n ; } return inc ; }\nlet c = make ( ) ;\nlet d = make ( ) ;")), g, out)
print(",".join(sorted(live_names(g))) + "/" + str(closure_env_count(g)) + "/" + str(g.vars["c"].env is g.vars["d"].env))

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

全部评论