Codewars:从逆波兰表达式到Three-Pass编译器(2)

在这里我想说的第二道题,我把它理解成一次对逆波兰表达式的运用和延伸。关于逆波兰表达式的相关知识,可以在前一篇博客中读到 : Codewars:从逆波兰表达式到Three-Pass编译器(1)

和前一题相比,这道题的题面就要复杂多了。

我们有一种如下的语法规则的编程语言:

 [ a b ] a*a + b*b

这里我们定义了一个函数,这个函数有两个参数(a 和 b),函数功能是计算 a 和 b 的平方和。

现在,请为该语言实现一个简单的语法编译器。编译过程可以拆分为三个步骤:

1.将函数解析为一个抽象语法树(AST

AST有如下规则:

    { 'op': '+', 'a': a, 'b': b }    // add subtree a to subtree b
    { 'op': '-', 'a': a, 'b': b }    // subtract subtree b from subtree a
    { 'op': '*', 'a': a, 'b': b }    // multiply subtree a by subtree b
    { 'op': '/', 'a': a, 'b': b }    // divide subtree a from subtree b
    { 'op': 'arg', 'n': n }          // reference to n-th argument, n integer
    { 'op': 'imm', 'n': n }          // immediate value n, n integer

那么, 例如 [ x y ] ( x + y ) / 2 这样的一个函数,我们需要将其解析为如下结构:

 { 'op': '/', 'a': { 'op': '+', 'a': { 'op': 'arg', 'n': 0 },
                                   'b': { 'op': 'arg', 'n': 1 } },
                 'b': { 'op': 'imm', 'n': 2 } }

2.优化AST,提前计算其中可以计算的项, 比如 [ x ] x + 2*5 这个函数,在经过第二步的优化后,将转化为如下结构:

   { 'op': '+', 'a': { 'op': 'arg', 'n': 0 },
                 'b': { 'op': 'imm', 'n': 10 } }

3.第三步则是将优化后的AST转化为类似汇编语言的底层代码,具体规则如下:

    "IM n"     // load the constant value n into R0
    "AR n"     // load the n-th input argument into R0
    "SW"       // swap R0 and R1
    "PU"       // push R0 onto the stack
    "PO"       // pop the top value off of the stack into R0
    "AD"       // add R1 to R0 and put the result in R0
    "SU"       // subtract R1 from R0 and put the result in R0
    "MU"       // multiply R0 by R1 and put the result in R0
    "DI"       // divide R0 by R1 and put the result in R0

那么,上面的例子经过转化后,一种可能的形式是: [ "IM 10", "SW", "AR 0", "AD" ] 。因为解析算法的不同,第三步得到的指令列表可能不尽相同,但只要最后的执行结果正确即可。

转换成以上形式后,题目提供了以下函数来执行这个指令列表:

def simulate(asm, argv):  
    r0, r1 = None, None
    stack = []
    for ins in asm:
        if ins[:2] == 'IM' or ins[:2] == 'AR':
            ins, n = ins[:2], int(ins[2:])
        if ins == 'IM':   r0 = n
        elif ins == 'AR': r0 = argv[n]
        elif ins == 'SW': r0, r1 = r1, r0
        elif ins == 'PU': stack.append(r0)
        elif ins == 'PO': r0 = stack.pop()
        elif ins == 'AD': r0 += r1
        elif ins == 'SU': r0 -= r1
        elif ins == 'MU': r0 *= r1
        elif ins == 'DI': r0 /= r1
    return r0

最后返回计算结果。

原题地址 :

https://www.codewars.com/kata/tiny-three-pass-compiler/train/python  

对于我这样不是科班出身也没学过编译原理这门课的程序员,解这道题的整个过程可以说是一次非常棒的实验课。这不正是编译器将一门高级编程语言编译成汇编代码的一个生动的例子吗!

幸好有了上一篇逆波兰表达式的基础,这道也变得不是那么的无从下手了,下面就讲讲我的思路:

第一步,首先需要对题目语言中的符号进行处理,比如 [] 表示函数的形参。 之后要处理的就是函数体中的表达式,我的思路是先将表达式转换逆波兰表达式,再使用计算逆波兰表达式的方法,构造AST。

第二步,递归遍历这棵树,计算其中两个节点均为标量的部分。

第三步,递归遍历优化后的AST,得到指令列表。

最后就是具体的实现代码了 :

import re

class Compiler(object):

    def compile(self, program):
        return self.pass3(self.pass2(self.pass1(program)))

    def tokenize(self, program):
        """Turn a program string into an array of tokens.  Each token
           is either '[', ']', '(', ')', '+', '-', '*', '/', a variable
           name or a number (as a string)"""
        token_iter = (m.group(0) for m in re.finditer(r'[-+*/()[\]]|[A-Za-z]+|\d+', program))
        return [tok for tok in token_iter]

    def pass1(self, program):
        tokens = self.tokenize(program)
        args = []
        list = []
        operators = []
        arg = False
        for t in tokens:
            if t == '[':
                arg = True
                continue

            if t == ']':
                arg = False
                continue

            if arg:
                args.append(t)
                continue

            if t in '+-*/':
                while(len(operators) != 0):
                    if operators[-1] != '(' and not (t in '*/' and operators[-1] in '+-'):
                        list.append(operators.pop())
                    else:
                        break
                operators.append(t)
            elif t == '(':
                operators.append(t)
            elif t == ')':
                while True:
                    x = operators.pop()
                    if x != '(' :
                        list.append(x)
                    else:
                        break
            else:
                list.append(t)

        stack = []
        for x in list + operators[::-1]:
            if x not in '+-*/':
                stack.append(x)
            else:
                b = self.build_val(stack.pop(), args)
                a = self.build_val(stack.pop(), args)
                stack.append({'op': x, 'a': a, 'b': b})

        return stack.pop()

    def build_val(self, val, args):
        if type(val) is dict:
            return val
        elif val in args:
            return {'op': 'arg', 'n': args.index(val)}
        elif val.isdigit():
            return {'op': 'imm', 'n': int(val)}

    def pass2(self, ast):
        if ast['op'] in '+-*/':
            if ast['a']['op'] in '+-*/':
                ast['a'] = self.pass2(ast['a'])
            if ast['b']['op'] in '+-*/':
                ast['b'] = self.pass2(ast['b'])
            if ast['a']['op'] == 'imm' and ast['b']['op'] == 'imm':
                ast = {'op': 'imm', 'n': eval(str(ast['a']['n']) + ast['op'] + str(ast['b']['n']))}

        return ast                

    def pass3(self, ast):
        op_dict = {
            '+': 'AD',
            '-': 'SU',
            '*': 'MU',
            '/': 'DI',
        }
        if ast['op'] in '+-*/':
            return (self.pass3(ast['a']) + self.pass3(ast['b'])) + ['PO', 'SW', 'PO', op_dict.get(ast['op']), 'PU']
        elif ast['op'] == 'arg':
            return ['AR ' + str(ast['n']), 'PU']
        elif ast['op'] == 'imm':
            return ['IM ' + str(ast['n']), 'PU']
Show Comments