Python使用spark模块构造计算器

Spark简介

Spark 解析器与 EBNF 语法有一些共同之处，但它将解析／处理过程分成了比传统的 EBNF 语法所允许的更小的组件。Spark 的优点在于，它对整个过程中每一步操作的控制都进行了微调，还提供了将定制代码插入到过程中的能力。

Spark的最新版是10年前发布的，真是非常的长寿，可见设计精良。其中的采用的设计模式有Reflection Pattern、Visitor Pattern、Pipes and Filters Pattern和Strategy Pattern。

初识Spark

第一次知道Spark这个模块是在IBM的网站[3]上看到的。

第一次激起我学习这个模块的兴趣是在看Python源码的时候，发现Python的编译器是用The Zephyr Abstract Syntax Description Language(Parser/Python.asdl)来定义的语法，然后通过(Parser/asdl.py、Parser/asdl_c.py、Parser/spark.py)根据Parser/Python.asdl生成C语言解析器。其中仅用了1000多行就实现了一个yacc。这个是非常地强大。

计算器

对于计算器的构造，我们在上文中使用LL(1)递归下降的方法构造了一个。但是Spark更加强大，Spark是用Earley语法分析算法，能够解析所有的上下文无关文法，这比LL和LR要更强，当然代价是更慢。

我们来看用Spark实现的计算器

 1 from spark import GenericParser, GenericScanner
 2 
 3 class Token(object):
 4     def __init__(self, type, attr=''):
 5         self.type = type
 6         self.attr = attr
 7     def __cmp__(self, o):
 8         return cmp(self.type, o)
 9     def __str__(self):
10         return self.type
11     def __repr__(self):
12         return str(self)
13 
14 class SimpleScanner(GenericScanner, object):
15     def __init__(self):
16         GenericScanner.__init__(self)
17 
18     def tokenize(self, input):
19         self.rv = []
20         GenericScanner.tokenize(self, input)
21         return self.rv
22 
23     def t_whitespace(self, s):
24         r' \s+ '
25         pass
26 
27     def t_op(self, s):
28         r' \+ | \- | \* | / | \( | \) '
29         self.rv.append(Token(type=s))
30 
31     def t_number(self, s):
32         r' \d+ '
33         self.rv.append(Token(type='number', attr=s))
34 
35 class ExprParser(GenericParser):
36     def __init__(self, start='expr'):
37         GenericParser.__init__(self, start)
38 
39     def p_expr_term_0(self, (lhs, op, rhs)):
40         '''
41             expr ::= expr addop term 
42             term ::= term mulop factor
43         '''
44         return eval(str(lhs) + str(op) + str(rhs))
45 
46     def p_expr_term_factor_1(self, (v, )):
47         '''
48             expr ::= term
49             term ::= factor
50         '''
51         return v
52 
53     def p_factor_1(self, (n, )):
54         ' factor ::= number '
55         return int(n.attr)
56 
57     def p_factor_2(self, (_0, expr, _1)):
58         ' factor ::= ( expr ) '
59         return expr
60 
61     def p_addop_mulop(self, (op, )):
62         ''' 
63             addop ::= +
64             addop ::= -
65             mulop ::= *
66             mulop ::= /
67         '''
68         return op
69 
70 
71 def scan(code):
72     scanner = SimpleScanner()
73     return scanner.tokenize(code)
74 
75 def parse(tokens):
76     parser = ExprParser()
77     return parser.parse(tokens)
78 
79 if __name__ == '__main__':
80     text = ' 7 + (1 + 3) * 5'
81     print parse(scan(text))
82