一天时间用python写门语言

标签: 一天 时间 python | 发表时间:2011-07-26 10:53 | 作者:机械唯物主义 way
出处:http://server.linjunhalida.com/blog/
http://www.hrsolutionsinc.com/engagementcalculator/calculator.jpg

今天我在广州加班, 上午其他同事去干活我一个人在旅店, 没事做就又练习写计算器程序了. 本来打算用python来写一个简单的支持加减乘除括号的计算器, 后来有加上了变量复制, 比较符, 条件判断, 循环, 最后还加上了函数, 几乎可以说是一个简单的语言了. 以后我也可以说写过一门语言了哈哈.

回到正题. 这里面整理一下这个简单的程序用到的方法, 代码在: https://bitbucket.org/linjunhalida/code-example/src/tip/python/calculator/

一开始, 我希望实现一个简单的支持加减乘除括号的计算器, 我不打算用python自带的方式(eval), 而是自己写一个. 虽然有种种取巧的方式, 我还是采用教科书般的方法, 首先词法分析, 然后语法分析+计算结果.

词法分析

词法分析的函数是syntax_analysis, 输入一个字符串, 拆分成一个个的词, 解析整型和浮点. 比如: "2 * 3 + 1" 就拆分成 [2, '*', 3, '+', 1], 没什么好说的, 从头开始解析即可. 没有用到状态机, 只是简单的根据字符串的首字母做条件判断, 然后一个个往下读, 根据状况拆分.

语法分析

我采用的方法是从the C++ programming language里面那个计算机程序学来的方法: 首先写出基本的语法, 然后每个语法模块写一个函数, 然后通过函数的递归调用来模拟语法树的生成和解析, 不需要显式地生成语法树.

我用了一个类Caculator来保存词法分析后的list, 以及当前处理到的符号位置, 变量表等东西, 语法模块都是这个类的方法, 这样写起来方便一点.

我们一部分一部分来吧. 首先我先实现加减乘除括号. 整理基本的语法:

l0 = (ltop) | n | - n
l1 = l1 * l0 | l1 / l0 | l0
l2 = l2 + l1 | l2 - l1 | l1
ltop = l2

n 是数字. 里面l0, l1, l2, 是根据优先级做了分割, 保证优先级高的操作首先执行. ltop的目的是为了方便扩充新的运算符号.

l2函数如下, 整体的逻辑是, 当发现下一个符号是'+-'的时候, 就一直解析和计算v, 然后返回v. self.ls是词法分析后的词列表, self.p是表示当前处理到的词位置. inc()表示解析下一个词, get()获取下一个词, has_next()判断下面还有没有.

所有的函数都类似这样的方式, 不传参数进去, 解析词列表, 返回计算后的结果.

def l2(self):
    v = self.l1()
    while (self.has_next()
           and self.isstr(self.get())
           and self.get() in '+-'):
        if self.get() == '+':
            self.inc()
            v2 = self.l1()
            v += v2
        elif self.get() == '-':
            self.inc()
            v2 = self.l1()
            v -= v2
    return v

赋值

然后我开始实现赋值功能, 同时考虑扩展成为能够解析多个表达式的语法, 这个基本也是抄the C++ programming language的方法, 改了几点:

  • 加了program, exp_list, exp, 更像一个语言了.
  • l0加上NAME, 能够获取NAME对应变量的值.
  • assignment赋值的操作. 为了通用, 赋值也是有返回值的.
l0 = (ltop) | n | NAME

program = END | exp_list END
exp_list = exp_list ; exp
exp = ltop | assignment

assignment = NAME = exp

赋值和计算都是exp的一种, 代码是这样写的:

def exp(self):
    if self.has_next(1):
        if self.get(1) == '=':
            return self.assignment()
        ...

    return self.ltop()

我在Caculator类里面加了一个values的dict, 用来保存赋值的值, 赋值和获取值的代码:

def assignment(self):
    name = self.get()
    self.inc()
    self.inc()
    v = self.exp()
    self.values[name] = v
    return v

def l0(self):
    g = self.get()
    ...
    elif self.issymbol(g):
        self.inc()
        return self.values[g]

条件判断

现在我的简单语法变得有点像一门真正的语言了, 但是还缺少很多必要的东西, 我思考如何实现条件判断. 首先实现判断语句, 语法:

l3 = l2 < l2 | l2 > l2 | l2 == l2 | l2
ltop = l3

实现很简单, 判断下一个符号是什么而已, 为了简单, 我没有加上True/False, 而是统一用1/0的方式来做, 真返回1, 假返回0.

def l3(self):
    v = self.l2()

    if not self.has_next():
        return v

    if self.get() == '<':
        self.inc()
        v2 = self.l2()
        if v < v2: return 1
        else: return 0
    elif self.get() == '>':
        self.inc()
        v2 = self.l2()
        if v > v2: return 1
        else: return 0
    elif self.get() == '==':
        self.inc()
        v2 = self.l2()
        if v == v2: return 1
        else: return 0

    return v

然后实现条件判断. 语法如下:

exp = ltop | assignment | condition
condition = if ltop {exp_list} else {exp_list}

exp里面判断第一个词是不是if, 然后跳转到condition函数(循环, 函数也采用类似的方法来判断), 然后解析条件判断的值, 如果大于一, 解析第一个exp_list, 不然解析第2个exp_list. 里面做了一些语法错误的判断. 还有else部分是可选的, 为了简单没有实现elif的方式. 对于不需要解析的exp_list, 我利用goto_next_block来跳转, 要注意的是处理嵌套{}的问题.

def exp(self):
    if self.has_next(1):
        if self.get(1) == '=':
            return self.assignment()
        elif self.get() == 'if':
            return self.condition()
        ...

def condition(self):
    self.inc()
    v = self.ltop()
    if self.get() != '{':
        self.error('exp error : no {')
    self.inc()

    if v > 0:
        v = self.exp_list()
    else:
        self.goto_next_block()

    if self.get() != '}':
        self.error('exp error : not }')
    self.inc()

    if self.has_next() and self.get() == 'else':
        self.inc()
        if self.get() != '{':
            self.error('exp error : no {')
        self.inc()

        if v <= 0:
            v = self.exp_list()
        else:
            self.goto_next_block()

        if self.get() != '}':
            self.error('exp error : not }')
        self.inc()
    return v

def goto_next_block(self):
    count = 1
    while self.has_next():
        if self.get() == '}':
            count -= 1
            if count <= 0: break
        elif self.get() == '{':
            count += 1
        self.inc()

循环

好了, 条件判断实现了, 下面该是循环了. 语法:

exp = ltop | assignment | condition | loop
loop = while ltop {exp_list}

具体实现上, 我缓存了loop开始的位置, 先判断ltop, 如果发现满足, 执行exp_list, 然后设置self.p为loop开始, 然后继续判断ltop. 不满足的话就跳出来.. 比我现象中的容易实现.

def loop(self):
    self.inc()
    p = self.p
    while True:
        v = self.ltop()

        if self.get() != '{':
            self.error('exp error : no {')
        self.inc()

        if v > 0:
            v = self.exp_list()
        else:
            self.goto_next_block()

        if self.get() != '}':
            self.error('exp error : not }')
        self.inc()

        if v <= 0:
            break
        else:
            self.p = p

    return v

函数

好了, 没有函数的语言是不完整的. 为了实现函数, 需要做很多工作.

先看语法, l0上面加的是调用函数, function_args是函数调用的参数, exp里面加上函数定义的部分, function_args_names是形参.

l0 = (ltop) | n | NAME | - n | NAME ( function_args )

exp = ltop | assignment | condition | loop | function

function = def NAME(function-args-names){exp_list}
function_args_names = function_args , NAME | NAME  | None
function_args = function_args , exp | exp | None

根据我看SICP学来的经验, 函数可以采用环境来实现. 所谓环境的概念, 就是函数本身是嵌套的, 每个函数内部就是一个环境, 保存有一些局部变量, 只在函数内部有效. 传给函数的参数就是在函数的环境里面做对应的赋值.

比如: def f1(a, b) {...}; f1(1, 2) , f1的环境是env1, f2的环境是env2, 在调用f1的时候, 执行到f1内部时, Caculator的self.env是env1, env1.values含有a, b 2个变量, 值分别是调用f1(1, 2)时传进来的1和2.

我们看Env类的定义. 现在我们删除掉Caculator的values, 让Env的 get_value()和set_value来获取和设置变量. Env是嵌套的, 因为函数调用的时候, 也可以访问上层赋值过的变量.

class Env():
    def __init__(self, parent=None):
        self.values = {}
        self.parent = parent

    def get_value(self, v):
        if v in self.values:
            return self.values[v]

        if not self.parent:
            raise Exception('cannot find value: %s, current_values: %s' % (v, str(self.values)))

        return self.parent.get_value(v)

    def set_value(self, name, v):
        self.values[name] = v

然后是函数赋值, 我把函数抽象成了一个类, 保存函数名, 开始位置, 以及缓存词列表, 因为caculator类是可以执行多次代码的. 最后我利用赋值的方式把函数保存下来.

class Func():
    pass

def function(self):
    func = Func()

    self.inc()

    name = self.get()
    if not self.issymbol(name):
        self.error('function error name : %s' % name)
    self.inc()
    func.name = name

    if self.get() != '(':
        self.error('function error not (')
    self.inc()

    func.arg_names = self.function_args_names()

    if self.get() != ')':
        self.error('function error not )')
    self.inc()

    if self.get() != '{':
        self.error('function error not {')
    self.inc()

    func.p = self.p
    func.ls = self.ls

    self.goto_next_block()

    if self.get() != '}':
        self.error('function error not }')
    self.inc()

    self.env.set_value(func.name, func)
    return 0

然后是函数执行的部分了. l0里面根据语法识别到函数调用, 然后执行function_all, 里面首先生成一个新的环境, 然后在新的环境里面, 把实际参数赋值给形参, 然后保存现在的ls, p, env, 然后执行函数体, 然后回复ls, p, env. function_args解析和返回实际参数列表, function_args_names解析和返回形参名称, 保存在Func.names里面, 都比较简单就不列出来了.

def l0(self):
    g = self.get()
    ...
    elif (self.has_next(2)
          and self.issymbol(g)
          and self.get(1) == '('):
        func = self.env.get_value(g)
        self.inc()
        self.inc()
        args = self.function_args()

        if not self.get() == ')':
            self.error('l0 function call error')
        self.inc()

        return self.function_call(func, args)

def function_call(self, func, args):
    env = Env(self.env)
    for name, v in zip(func.arg_names, args):
        env.set_value(name, v)

    self.push_p(env, func.p, func.ls)

    v = self.exp_list()

    return v

def push_p(self, env, p, ls):
    self.env = env
    self.pre_p = self.p
    self.p = p
    self.pre_ls = self.ls
    self.ls = ls

def pop_p(self):
    if self.env.parent == None:
        self.error('pop_p: no parent for env!')
    self.env = self.env.parent
    self.p = self.pre_p
    self.ls = self.pre_ls

写完后才知道, 真的... 不复杂!

函数可以返回

现在函数还是一直执行到结尾才返回, 我希望能够支持return语句, 原本考虑了半天, 不知道如何通过重重的函数调用, 返回到最上面, 后来经过 岚临 同学的提醒, 用抛出异常, 在上层捕捉的方式实现了, 加的代码只有4行!

语法:

exp = ltop | assignment | condition | loop | function | return
return_exp = return ltop

进到return_exp里面后, 会抛出ReturnException, 在function_call里面捕捉, 正好是当前调用函数的部分.

class ReturnException(Exception):
    """for implement return expression"""
    def __init__(self, v):
        Exception.__init__(self)
        self.value = v

def function_call(self, func, args):
    try:
        v = self.exp_list()
        self.pop_p()
    except ReturnException as e:
        v = e.value

def exp(self):
    if self.has_next(1):
        ...
        elif self.get() == 'return':
            return self.return_exp()

def return_exp(self):
    self.inc()
    v = self.exp()
    self.pop_p()
    raise ReturnException(v)

结论

我一开始没有想到能够写那么多的, 结果一个语法一个语法加下来就变成这样了... 虽然没有性能优化, 以及其他的错误处理什么的东西, 能够写出一个简单的语言, 还是让我很有成就感的. 我不是一个很强的程序员, 也能写出一个简单的语言, 相信你也可以写一个来玩玩!

下一步: 虚拟机+字节码+编译 方式的语言, 实现协程+原生同步!

相关 [一天 时间 python] 推荐:

一天时间用python写门语言

- way - 网络寻租
今天我在广州加班, 上午其他同事去干活我一个人在旅店, 没事做就又练习写计算器程序了. 本来打算用python来写一个简单的支持加减乘除括号的计算器, 后来有加上了变量复制, 比较符, 条件判断, 循环, 最后还加上了函数, 几乎可以说是一个简单的语言了. 以后我也可以说写过一门语言了哈哈.. 这里面整理一下这个简单的程序用到的方法, 代码在: https://bitbucket.org/linjunhalida/code-example/src/tip/python/calculator/.

dropbox讲python

- chuang - Initiative
dropbox定制优化CPython虚拟机,自己搞了个malloc调度算法. 那个 !!!111cos(0). 期待这次PyCon China 2011.

Python调试

- - 企业架构 - ITeye博客
原文地址: http://blog.csdn.net/xuyuefei1988/article/details/19399137. 1、下面网上收罗的资料初学者应该够用了,但对比IBM的Python 代码调试技巧:. IBM:包括 pdb 模块、利用 PyDev 和 Eclipse 集成进行调试、PyCharm 以及 Debug 日志进行调试:.

Python WSGI 初探

- - 坚实的幻想
在构建 Web 应用时,通常会有 Web Server 和 Application Server 两种角色. 其中 Web Server 主要负责接受来自用户的请求,解析 HTTP 协议,并将请求转发给 Application Server,Application Server 主要负责处理用户的请求,并将处理的结果返回给 Web Server,最终 Web Server 将结果返回给用户.

Python实现逻辑回归(Logistic Regression in Python)

- - 神刀安全网
Logistic Regression in Python ,作了中文翻译,并相应补充了一些内容. 本文并不研究逻辑回归具体算法实现,而是使用了一些算法库,旨在帮助需要用Python来做逻辑回归的训练和预测的读者快速上手. 逻辑回归是一项可用于预测二分类结果(binary outcome)的统计技术,广泛应用于金融、医学、犯罪学和其他社会科学中.

python 下载文件

- Eric - python相关的python 教程和python 下载你可以在老王python里寻觅
之前给大家分享的python 多线程抓取网页,我觉的大家看了以后,应该会对python 抓取网页有个很好的认识,不过这个只能用python 来抓取到网页的源代码,如果你想用做python 下载文件的话,上面的可能就不适合你了,最近我在用python 做文件下载的时候就遇到这个问题了,不过最终得以解决,为了让大家以后碰过这个问题有更好的解决办法,我把代码发出来:.

python代码调试

- - 阿里古古
【转自: http://blog.csdn.net/luckeryin/article/details/4477233】. 本文讨论在没有方便的IDE工具可用的情况下,使用pdb调试python程序. 例如,有模拟税收计算的程序:. debug_demo函数计算4500的入账所需的税收. 在需要插入断点的地方,加入红色部分代码:如果_DEBUG值为True,则在该处开始调试(加入_DEBUG的原因是为了方便打开/关闭调试).

python编程规范

- - 互联网 - ITeye博客
@FileName: @Author:xx@ic.net.cn @Create date: @description:用一行文字概述模块或脚本,用句号结尾. 不影响编码的效率,不与大众习惯冲突.. 使代码的逻辑更清晰,更易于理解..   *所有的 Python 脚本文件都应在文件头标上如下标识或其兼容格式的标识.

《Dive into Python 3》中文版

- hama - Wow! Ubuntu
Dive Into Python 是一份很知名的 Python 入门教程,由 Mark Pilgrim 编写,用户可以免费获取电子版本,而中文版则由啄木鸟社区翻译发布 [ 英文版 / 中文版 ]. 前阵子,Mark Pilgrim 又发布了 《Dive into Python 3》,此版本的内容涵盖了 Python 3 及其与 Python 2 的区别.