python实现的lisp解释器

作者: admin
更新: 8/28/2019, 11:36:02 AM

import math
import operator as op
def tokenize(s):
    "序列化,在字符串的括号两边加上空格,使得字符串变得标准化,以便split"
    return s.replace('(',' ( ').replace(')',' ) ').split()


def parse(program):
    return read_from_tokens(tokenize(program))


def atom(token):
    "对token进行转换"
    try: return int(token)
    except ValueError:
        try: return float(token)
        except ValueError:
            return str(token)
def read_from_tokens(tokens):
    "处理tokenize传送过来的token数组"
    if len(tokens) == 0:
        raise SyntaxError('unexpected EOF while reading')
    token = tokens.pop(0)#获取左边第一个元素
    if '(' == token:     #合法标记,继续
        arr = []
        while tokens[0] != ')':
            arr.append(read_from_tokens(tokens))#递归处理tokens
        tokens.pop(0)
        return arr
    elif ')' == token:
        raise SystemError('unexpected )')
    else :
        return  atom(token)


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 is not None else None


def standard_env():
    "标准环境,通过序对表示"
    env = Env()
    env.update(vars(math))#注入数学库
    env.update({
         '+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv, 
        '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 
        'abs':     abs,
        'append':  op.add,
        'begin':   lambda *x: x[-1],
        'car':     lambda x: x[0],
        'cdr':     lambda x: x[1:], 
        'cons':    lambda x,y: [x] + y,
        'eq?':     op.is_, 
        'equal?':  op.eq, 
        'length':  len, 
        'list':    lambda *x: list(x), 
        'list?':   lambda x: isinstance(x,list), 
        'map':     map,
        'max':     max,
        'min':     min,
        'not':     op.not_,
        'null?':   lambda x: x == [], 
        'number?': lambda x: isinstance(x, (int, float)),   
        'procedure?': callable,
        'round':   round,
        'symbol?': lambda x: isinstance(x, str),
    })
    return env


global_env = standard_env()



class Procedure(object):
    "过程和求值构成元循环"
    def __init__(self, parms, body, env):
        "函数参数, 函数体,环境"
        self.parms, self.body, self.env = parms, body, env
    def __call__(self, *args):
        return eval(self.body, Env(self.parms, args, self.env))


def eval(x, env= global_env):
    "重头戏,最关键的求值器"
    if isinstance(x, str):
        "获取拥有x环境(字典)中的x的值"
        return env.find(x)[x] if env.find(x) is not None else 'Error: ' + x + ' Not defined'
    elif not isinstance(x, list):
        "迭代器,直接返回"
        return x
    elif x[0] == 'quote':
        "引用,丢弃标记,直接返回引用的值"
        (_, exp) = x
        return exp
    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, exp) = x
        env[var] = eval(exp, env)
    elif x[0] == 'set!':
        "修改值"
        (_, var, exp) = x
        env.find(var)[var] = eval(exp, env)
    elif x[0] == 'lambda':
        (_, parms, body) = x
        return Procedure(parms, body, env)
    else:
        proc = eval(x[0], env)
        args = [eval(exp, env) for exp in x[1:]]
        return proc(*args)
def lispstr(exp):
    "转换python对象,以便打印"
    if isinstance(exp, list):
        return '(' + ' '.join(map(lispstr, exp)) + ')'
    else:
        return str(exp)
def repl(prompt='我的lisp> '):
    "循环求值器"
    while True:
        val = eval(parse(input(prompt)))
        if val is not None:
            print(lispstr(val))


if '__main__' == __name__:
    repl()

尝试一下

(define f (lambda (x) (if (< x 2) 1 (+ (f (- x 1) ) (f (- x 2) )))))


(f 5)
删除
修改
点击登陆评论