1+ #!/usr/bin/env python
2+ # -*- encoding: utf-8 -*-
3+ """
4+ Topic: 下降解析器
5+ Desc :
6+ """
7+ import re
8+ import collections
9+
10+ # Token specification
11+ NUM = r'(?P<NUM>\d+)'
12+ PLUS = r'(?P<PLUS>\+)'
13+ MINUS = r'(?P<MINUS>-)'
14+ TIMES = r'(?P<TIMES>\*)'
15+ DIVIDE = r'(?P<DIVIDE>/)'
16+ LPAREN = r'(?P<LPAREN>\()'
17+ RPAREN = r'(?P<RPAREN>\))'
18+ WS = r'(?P<WS>\s+)'
19+
20+ master_pat = re .compile ('|' .join ([NUM , PLUS , MINUS , TIMES ,
21+ DIVIDE , LPAREN , RPAREN , WS ]))
22+ # Tokenizer
23+ Token = collections .namedtuple ('Token' , ['type' , 'value' ])
24+
25+
26+ def generate_tokens (text ):
27+ scanner = master_pat .scanner (text )
28+ for m in iter (scanner .match , None ):
29+ tok = Token (m .lastgroup , m .group ())
30+ if tok .type != 'WS' :
31+ yield tok
32+
33+
34+ # Parser
35+ class ExpressionEvaluator :
36+ '''
37+ Implementation of a recursive descent parser. Each method
38+ implements a single grammar rule. Use the ._accept() method
39+ to test and accept the current lookahead token. Use the ._expect()
40+ method to exactly match and discard the next token on on the input
41+ (or raise a SyntaxError if it doesn't match).
42+ '''
43+
44+ def parse (self , text ):
45+ self .tokens = generate_tokens (text )
46+ self .tok = None # Last symbol consumed
47+ self .nexttok = None # Next symbol tokenized
48+ self ._advance () # Load first lookahead token
49+ return self .expr ()
50+
51+ def _advance (self ):
52+ 'Advance one token ahead'
53+ self .tok , self .nexttok = self .nexttok , next (self .tokens , None )
54+
55+ def _accept (self , toktype ):
56+ 'Test and consume the next token if it matches toktype'
57+ if self .nexttok and self .nexttok .type == toktype :
58+ self ._advance ()
59+ return True
60+ else :
61+ return False
62+
63+ def _expect (self , toktype ):
64+ 'Consume next token if it matches toktype or raise SyntaxError'
65+ if not self ._accept (toktype ):
66+ raise SyntaxError ('Expected ' + toktype )
67+
68+ # Grammar rules follow
69+ def expr (self ):
70+ "expression ::= term { ('+'|'-') term }*"
71+ exprval = self .term ()
72+ while self ._accept ('PLUS' ) or self ._accept ('MINUS' ):
73+ op = self .tok .type
74+ right = self .term ()
75+ if op == 'PLUS' :
76+ exprval += right
77+ elif op == 'MINUS' :
78+ exprval -= right
79+ return exprval
80+
81+ def term (self ):
82+ "term ::= factor { ('*'|'/') factor }*"
83+ termval = self .factor ()
84+ while self ._accept ('TIMES' ) or self ._accept ('DIVIDE' ):
85+ op = self .tok .type
86+ right = self .factor ()
87+ if op == 'TIMES' :
88+ termval *= right
89+ elif op == 'DIVIDE' :
90+ termval /= right
91+ return termval
92+
93+ def factor (self ):
94+ "factor ::= NUM | ( expr )"
95+ if self ._accept ('NUM' ):
96+ return int (self .tok .value )
97+ elif self ._accept ('LPAREN' ):
98+ exprval = self .expr ()
99+ self ._expect ('RPAREN' )
100+ return exprval
101+ else :
102+ raise SyntaxError ('Expected NUMBER or LPAREN' )
103+
104+
105+ def descent_parser ():
106+ e = ExpressionEvaluator ()
107+ print (e .parse ('2' ))
108+ print (e .parse ('2 + 3' ))
109+ print (e .parse ('2 + 3 * 4' ))
110+ print (e .parse ('2 + (3 + 4) * 5' ))
111+ # print(e.parse('2 + (3 + * 4)'))
112+ # Traceback (most recent call last):
113+ # File "<stdin>", line 1, in <module>
114+ # File "exprparse.py", line 40, in parse
115+ # return self.expr()
116+ # File "exprparse.py", line 67, in expr
117+ # right = self.term()
118+ # File "exprparse.py", line 77, in term
119+ # termval = self.factor()
120+ # File "exprparse.py", line 93, in factor
121+ # exprval = self.expr()
122+ # File "exprparse.py", line 67, in expr
123+ # right = self.term()
124+ # File "exprparse.py", line 77, in term
125+ # termval = self.factor()
126+ # File "exprparse.py", line 97, in factor
127+ # raise SyntaxError("Expected NUMBER or LPAREN")
128+ # SyntaxError: Expected NUMBER or LPAREN
129+
130+
131+ if __name__ == '__main__' :
132+ descent_parser ()
0 commit comments