答案是用Python实现Scheme解释器需解析S表达式、构建环境并实现求值规则。首先通过tokenize和parse将源码转为AST，再定义Env类管理作用域链，eval函数处理变量查找、条件、定义、lambda及函数调用，最后repl提供交互界面，整体涵盖词法分析、语法解析、环境模型与递归求值等核心机制。
用Python实现一个简单的Scheme解释器，核心是解析S表达式、构建求值环境，并实现基本的Lisp语义。这个过程能加深对函数式编程、递归求值和语言设计的理解。下面是一个基础但可运行的Python版Scheme子集实现。
1. 词法与语法分析（Tokenizer & Parser）
Scheme代码由括号、符号、数字和操作符组成。先将源码拆分为标记（token），再构造成抽象语法树（AST）。
Tokenizer 将输入字符串切分为基本单元：代码示例：
def tokenize(chars):
return chars.replace('(', ' ( ').replace(')', ' ) ').split()
Parser 将标记序列转换为嵌套列表结构（即AST）：
立即学习“Python免费学习笔记（深入）”；
def parse(tokens):
def read_from_tokens():
if len(tokens) == 0:
raise SyntaxError("意外结束")
token = tokens.pop(0)
if token == '(':
L = []
while tokens[0] != ')':
L.append(read_from_tokens())
tokens.pop(0) # 消耗 ')'
return L
elif token == ')':
raise SyntaxError("括号不匹配")
else:
return atom(token)
def atom(token):
try: return int(token)
except ValueError:
try: return float(token)
except ValueError:
return token # 符号如 x, +, lambda
return read_from_tokens()
2. 环境与求值器（Environment & Evaluator）
定义变量查找环境和表达式求值逻辑。环境是一个支持嵌套作用域的字典链。
class Env(dict):
def __init__(self, parms=(), args=(), outer=None):
self.update(zip(parms, args))
self.outer = outer
def find(self, var):
return self if var in self else self.outer.find(var) if self.outer else None
标准环境 包含常见函数如 +、-、*、/ 和比较操作：
import math
import operator as op
def standard_env():
env = Env()
env.update({
'+': op.add, '-': op.sub, '': op.mul, '/': op.truediv,
'>': op.gt, '<': op.lt, '>=': op.ge, '<=': op.le, '=': op.eq,
'abs': abs,
'pi': math.pi,
'sin': math.sin,
'cos': math.cos,
'sqrt': math.sqrt,
'pow': pow,
'begin': lambda x: x[-1],
})
return env
求值函数 根据表达式类型进行处理：
def eval(x, env):
if isinstance(x, str): # 变量引用
return env.find(x)[x]
elif not isinstance(x, list): # 字面量：数字
return x
elif x[0] == 'if': # 条件
_, test, conseq, alt = x
exp = conseq if eval(test, env) else alt
return eval(exp, env)
elif x[0] == 'define': # 变量定义
_, var, expr = x
env[var] = eval(expr, env)
elif x[0] == 'lambda': # 匿名函数
_, parms, body = x
return lambda *args: eval(body, Env(parms, args, env))
else: # 函数调用
proc = eval(x[0], env)
args = [eval(arg, env) for arg in x[1:]]
return proc(*args)
3. 顶层循环（REPL）
读取-求值-打印循环，让用户交互输入表达式。
def repl(prompt='lis.py> '):
env = standard_env()
while True:
try:
source = input(prompt)
if source.strip() == "quit":
break
val = eval(parse(tokenize(source)), env)
if val is not None:
print(schemestr(val))
except Exception as e:
print(f"错误: {e}")
def schemestr(exp):
if isinstance(exp, list):
return '(' + ' '.join(map(schemestr, exp)) + ')'
return str(exp)
4. 使用示例
启动解释器后可以输入如下内容：
lis.py> (+ 2 3)
5
lis.py> (define x 10)
lis.py> (* x x)
100
lis.py> ((lambda (x) (* x x)) 5)
25
lis.py> (if (> 3 2) 42 0)
42
这个实现涵盖了Scheme的核心机制：S表达式解析、词法作用域、闭包、条件和函数应用。虽然缺少宏、尾递归优化等高级特性，但已足够演示语言解释的基本原理。
基本上就这些。想扩展的话，可以加入let、quote、cons/car/cdr等特性，逐步逼近完整Scheme。
