用LL(1)递归下降语法器构造一个计算器

LL(1)

何为LL(1)？通俗来说就是向前看一个词法单元的自顶向下解析器。两个L都代表left-to-right，第一个L表示解析器按“从左到右”的顺序解析输入内容；第二个L表示下降解析时也是按“从左到右”的顺序遍历子节点。而(1)表示它使用一个向前看词法单元。

我们从一个简单的计算器来看看递归下降的语法器如何构造。

对于 2 + 3 * 5 的抽象语法树如下：

我们可以使用如下文法表示计算表达式：

 1 import tokenize, StringIO
 2 
 3 tokens = None
 4 cur_tok = None
 5 
 6 def scan(text):
 7     g = tokenize.generate_tokens(
 8         StringIO.StringIO(text).readline)
 9     return ((v[0], v[1]) for v in g)
10     
11 def get_token():
12     global tokens, cur_tok
13     cur_tok = tokens.next()
14     #print cur_tok
15     return cur_tok
16     
17 def match(type, val = ''):
18     global tokens, cur_tok
19     t, v = cur_tok
20     if t == type or t == tokenize.OP and v == val:
21         get_token()
22     else:
23         raise 
24 
25 def expr():
26     global cur_tok
27     tmp = term()
28     t, v = cur_tok
29     while v == '+' or v == '-':
30         match(tokenize.OP)
31         rhs = term()
32         e = str(tmp) + str(v) + str(rhs)
33         tmp = eval(e)
34         print e, '=', tmp
35         t, v = cur_tok
36     return tmp 
37 
38 def term():
39     global cur_tok
40     tmp = factor()
41     t, v = cur_tok
42     while v == '*' or v == '/':
43         match(tokenize.OP)
44         rhs = factor()
45         e = str(tmp) + str(v) + str(rhs)
46         tmp = eval(e)
47         print e, '=', tmp
48         t, v = cur_tok
49     return tmp
50 
51 def factor():
52     global cur_tok
53     t, v = cur_tok
54     if t == tokenize.NUMBER:
55         match(tokenize.NUMBER)
56         return int(v)
57     elif v == '(':
58         match(tokenize.OP, '(')
59         tmp = expr()
60         match(tokenize.OP, ')')
61         return tmp
62     else:
63         raise
64 
65 if __name__ == '__main__':
66     text = '12 + 2 * ( 5 + 6 )'
67     tokens = scan(text)
68     get_token()
69     res = expr()
70     print text, '=', res

对于12 + 2 * ( 5 + 6 )，运行结果如下：