来自: 网络寻租 - FeedzShare
发布时间:2011年07月26日, 已有 2 人推荐
今天我在广州加班, 上午其他同事去干活我一个人在旅店, 没事做就又练习写计算器程序了. 本来打算用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的方法, 改了几点:
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)
我一开始没有想到能够写那么多的, 结果一个语法一个语法加下来就变成这样了... 虽然没有性能优化, 以及其他的错误处理什么的东西, 能够写出一个简单的语言, 还是让我很有成就感的. 我不是一个很强的程序员, 也能写出一个简单的语言, 相信你也可以写一个来玩玩!
下一步: 虚拟机+字节码+编译 方式的语言, 实现协程+原生同步!
