python 写一个scheme 解释器（二）——简单求值器内核

浏览数：24 / 时间：2015年06月08日

这一篇开始正式完成求值器，首先本着一个基本原则：

先将整个流程实现，才逐步细化每个过程，最终扩充比较难的特性。

一、词法分析

def tokenAnalysis(strings):
    return strings.replace(‘(‘,‘ ( ‘).replace(‘)‘,‘ ) ‘).split()

将字符串流按照空白字符分割成一个个子串，split 和 replace 函数的更多用法可以查阅python手册。

示例：

（cons 1 2）

拆分结果：’(’ ‘cons’ ‘1’ ‘2’ ‘)’

注意，replace用于在（和其它字符之间添加空白字符，这样才可以正确的将括号和cons 分割开来，因为scheme语法中(和其它字符是可以连着写的

二、语法分析

语法的分析原则见上一篇博文，简单来说：就是将每一个子表达式做成一个list，直至没有更小的表达式为止，这个过程显然是递归的，我们处理的时候也采用递归的方式来做。

def parse(tokens):
    first_token=tokens.pop(0)
    if first_token==‘(‘:
        expr=[]
        while tokens[0] != ‘)‘:
            expr.append(parse(tokens))
            tokens.pop(0)
            return expr
    elif first_token==‘)‘:
        raise SyntaxError("there need left bracket!")
    else :
        return parse_constant_value(first_token)
        


def parse_constant_value(token):
    try:
        return int(token)
    except ValueError:
        try:
            return float(token)
        except ValueError:
            return Symbol(token)

1. 首先我们取出tokens中的第一个token，它要么是可直接求值的类型，要么是‘(’ ；

2. 如果它是可求值的类型，对应最后一个else：语句，转到parse_constant_value 处处理，处理的时候采用异常抛出的方式，分别对应int float str类型；

3. 如果是左括号开始的语句，则不断读取tokens，直至末元素为‘）’，注意给exor中添加新token的时候采用递归的方式加入，这样可以保证任何程度的表达式嵌套都可以正确的处理

三 . eval 内核

def eval(stat, env=global_env):
    while (True):

        if isinstance(stat, Symbol):
            return eval_var(stat, env)

        elif not isinstance(stat, List):
            return eval_constant(stat)

        elif is_arit_expr(stat):
            return eval_arit_expr(stat, env)

stat为statement的所写,env 是求值环境，和用racket来实现的时候如出一辙。

注意一点：这里eval里面有一条while(True)：，这其实是为了尾递归优化而做的改变，这里可以不考虑这一句，因为每个子项都会直接返回。

env的定义：

class Env(dict):
    def find(self, var):
        return self if (var in self) else self.outer.find(var)

    def __init__(self, parms=(), args=(), outer=None):
        self.update(zip(parms, args))
        self.outer = outer

很简单的一个类，有2个函数可用，一个是初始化构建新的环境所用的__init__，另一个是在环境中由里到外递归查找var对应的value

也就是说，我们构建env的时候是将新的var-value键对加入新的Env（）对象，并且这个对象的outer是旧的环境。这也满足我们对于求值环境的接口约定，而我们知道，只要满足这样的接口约定的都是合法的

Symbol = str

List =list

上面是两个简单类型的定义，左边是scheme中的类型，右边是对应的python类型。

eval_var eval_constant 都十分容易，这里看看简易求值器的计算器部分：

operator = [‘+‘, ‘-‘, ‘*‘, ‘/‘, ‘>‘, ‘<‘, ‘=‘, ‘>=‘, ‘<=‘]


def is_arit_expr(stat):
    if stat[0] in operator:
        return True
    else:
        return False

def eval_arit_expr(stat, env):
    (op, first, second) = stat
    first = eval(first, env)
    second = eval(second, env)
    if op == ‘+‘:
        return first + second
    elif op == ‘-‘:
        return first - second
    elif op == ‘*‘:
        return first * second
    elif op == ‘/‘:
        if second == 0:
            print("Wrong , the divide number cannot be zero!")
            return None
        else:
            return first / second
    elif op == ‘>‘:
        return first > second
    elif op == ‘<‘:
        return first < second
    elif op == ‘=‘:
        return first == second
    elif op == ‘<=‘:
        return first <= second
    elif op == ‘>=‘:
        return first >= second

非常简单，就不再赘述了。

以上是变量、常量、数学运算的部分。

        elif is_begin_with(stat, ‘quote‘):
            return eval_quote(stat)

        elif is_begin_with(stat, ‘if‘):
            (_, test, if_part, else_part) = stat
            stat = (if_part if eval(test, env) else else_part)
        elif is_begin_with(stat, ‘define‘):
            return eval_define(stat, env)

以上的quote 、 if、 define 也很容易添加

注意这里的if其实是优化尾递归之后的版本，我们没有直接return ，而是将待求值的表达式赋值为if中满足条件该执行的表达式。

四、交互环境和输出：

def REPL(program=";;;GD-interpreter >"):
    while True:
        result = eval(parse(tokenAnalysis(input(program))))
        my_print(result)


def my_print(value):
    if value is True:
        print("#t")
    elif value is False:
        print("#f")
    elif value is None:
        pass
    else:
        print (value)