网络寻租

Programmer, Gamer, Hacker

一天时间用python写门语言

| Comments

image

今天我在广州加班, 上午其他同事去干活我一个人在旅店, 没事做就又练习写计算器程序了. 本来打算用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()判断下面还有没有.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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的一种, 代码是这样写的:

1
2
3
4
5
6
7

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

    return self.ltop()

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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来跳转, 要注意的是处理嵌套{}的问题.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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. 不满足的话就跳出来.. 比我现象中的容易实现.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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是嵌套的, 因为函数调用的时候, 也可以访问上层赋值过的变量.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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类是可以执行多次代码的. 最后我利用赋值的方式把函数保存下来.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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里面, 都比较简单就不列出来了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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里面捕捉, 正好是当前调用函数的部分.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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)

结论

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

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

Comments