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

 

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

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

 

一、 词法分析

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 函数和过程调用的支持和函数调用尾递归优化见下一篇。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。