首页 > 代码库 > python 写一个scheme 解释器 （二）——简单求值器内核

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

2024-08-04 01:01:06   211人阅读

 

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

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

 

一、 词法分析

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)

运行的时候只要REPL()就可以了。my_print主要是为了让输出更加符合scheme的习惯，没有这个函数也无所谓。

 

最关键的lambda 函数和过程调用的支持和函数调用尾递归优化见下一篇。

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


联系
我们