Mercurial > hg > expressionparser

comparison expr.py @ 2:94a293b914af

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add documentation, clean up interface slightly, tweak tests
author Ted Mielczarek <ted.mielczarek@gmail.com>
date Thu, 02 Jun 2011 07:44:25 -0400
parents c45135ec8c13
children 5ac8eed85684
comparison
equal deleted inserted replaced
1:c45135ec8c13 2:94a293b914af
1 #!/usr/bin/env python 1 #!/usr/bin/env python
2 2
3 # Implements a top-down parser/evaluator for simple boolean expressions.
4 # ideas taken from http://effbot.org/zone/simple-top-down-parsing.htm
5 #
6 # Rough grammar:
7 # expr := literal
8 # | '(' expr ')'
9 # | expr '&&' expr
10 # | expr '||' expr
11 # | expr '==' expr
12 # | expr '!=' expr
13 # literal := BOOL
14 # | INT
15 # | STRING
16 # | IDENT
17 # BOOL := true|false
18 # INT := [0-9]+
19 # STRING := "[^"]*"
20 # IDENT := [A-Za-z_]\w*
21
22 # Identifiers take their values from a mapping dictionary passed as the second
23 # argument.
24
25 __all__ = ['parse', 'ParseError']
3 import re, unittest 26 import re, unittest
4 27
5 # ideas taken from http://effbot.org/zone/simple-top-down-parsing.htm
6 # token classes 28 # token classes
7 class ident_token: 29 class ident_token:
8 def __init__(self, value): 30 def __init__(self, value):
9 self.value = value 31 self.value = value
10 def nud(self, parser): 32 def nud(self, parser):
69 return self.value 91 return self.value
70 92
71 class end_token: 93 class end_token:
72 # lowest left binding power, always ends parsing 94 # lowest left binding power, always ends parsing
73 lbp = 0 95 lbp = 0
96
97 class ParseError(Exception):
98 pass
74 99
75 class ExpressionParser(object): 100 class ExpressionParser(object):
76 def __init__(self, text, valuemapping): 101 def __init__(self, text, valuemapping):
77 """ 102 """
78 Initialize the parser with input |text|, and |valuemapping| as 103 Initialize the parser with input |text|, and |valuemapping| as
146 return left 171 return left
147 172
148 def parse(self): 173 def parse(self):
149 """ 174 """
150 Parse and return the value of the expression in the text 175 Parse and return the value of the expression in the text
151 passed to the constructor. 176 passed to the constructor. Raises a ParseError if the expression
152 """ 177 could not be parsed.
153 self.iter = self._tokenize() 178 """
154 self.token = self.iter.next() 179 try:
155 return self.expression() 180 self.iter = self._tokenize()
181 self.token = self.iter.next()
182 return self.expression()
183 except:
184 raise ParseError
185
186 def parse(text, values):
187 """
188 Parse and evaluate a boolean expression in |text|. Use |values| to look
189 up the value of identifiers referenced in the expression. Returns the final
190 value of the expression. A ParseError will be raised if parsing fails.
191 """
192 return ExpressionParser(text, values).parse()
156 193
157 class ExpressionParserUnittest(unittest.TestCase): 194 class ExpressionParserUnittest(unittest.TestCase):
158 def parse(self, text, values):
159 return ExpressionParser(text, values).parse()
160
161 def test_BasicValues(self): 195 def test_BasicValues(self):
162 self.assertEqual(1, self.parse("1", {})) 196 self.assertEqual(1, parse("1", {}))
163 self.assertEqual(100, self.parse("100", {})) 197 self.assertEqual(100, parse("100", {}))
164 self.assertEqual(True, self.parse("true", {})) 198 self.assertEqual(True, parse("true", {}))
165 self.assertEqual(False, self.parse("false", {})) 199 self.assertEqual(False, parse("false", {}))
166 self.assertEqual("", self.parse('""', {})) 200 self.assertEqual("", parse('""', {}))
167 self.assertEqual("foo bar", self.parse('"foo bar"', {})) 201 self.assertEqual("foo bar", parse('"foo bar"', {}))
168 self.assertEqual(1, self.parse("foo", {'foo':1})) 202 self.assertEqual(1, parse("foo", {'foo':1}))
169 self.assertEqual(True, self.parse("bar", {'bar':True})) 203 self.assertEqual(True, parse("bar", {'bar':True}))
170 self.assertEqual("xyz", self.parse("abc123", {'abc123':"xyz"})) 204 self.assertEqual("xyz", parse("abc123", {'abc123':"xyz"}))
171 205
172 def test_Equality(self): 206 def test_Equality(self):
173 self.assertTrue(self.parse("true == true", {})) 207 self.assertTrue(parse("true == true", {}))
174 self.assertTrue(self.parse("false == false", {})) 208 self.assertTrue(parse("false == false", {}))
175 self.assertTrue(self.parse("false == false", {})) 209 self.assertTrue(parse("false == false", {}))
176 self.assertTrue(self.parse("1 == 1", {})) 210 self.assertTrue(parse("1 == 1", {}))
177 self.assertTrue(self.parse("100 == 100", {})) 211 self.assertTrue(parse("100 == 100", {}))
178 self.assertTrue(self.parse('"some text" == "some text"', {})) 212 self.assertTrue(parse('"some text" == "some text"', {}))
179 self.assertTrue(self.parse("true != false", {})) 213 self.assertTrue(parse("true != false", {}))
180 self.assertTrue(self.parse("1 != 2", {})) 214 self.assertTrue(parse("1 != 2", {}))
181 self.assertTrue(self.parse('"text" != "other text"', {})) 215 self.assertTrue(parse('"text" != "other text"', {}))
182 self.assertTrue(self.parse("foo == true", {'foo': True})) 216 self.assertTrue(parse("foo == true", {'foo': True}))
183 self.assertTrue(self.parse("foo == 1", {'foo': 1})) 217 self.assertTrue(parse("foo == 1", {'foo': 1}))
184 self.assertTrue(self.parse('foo == "bar"', {'foo': 'bar'})) 218 self.assertTrue(parse('foo == "bar"', {'foo': 'bar'}))
185 self.assertTrue(self.parse("foo == bar", {'foo': True, 'bar': True})) 219 self.assertTrue(parse("foo == bar", {'foo': True, 'bar': True}))
186 self.assertTrue(self.parse("true == foo", {'foo': True})) 220 self.assertTrue(parse("true == foo", {'foo': True}))
187 self.assertTrue(self.parse("foo != true", {'foo': False})) 221 self.assertTrue(parse("foo != true", {'foo': False}))
188 self.assertTrue(self.parse("foo != 2", {'foo': 1})) 222 self.assertTrue(parse("foo != 2", {'foo': 1}))
189 self.assertTrue(self.parse('foo != "bar"', {'foo': 'abc'})) 223 self.assertTrue(parse('foo != "bar"', {'foo': 'abc'}))
190 self.assertTrue(self.parse("foo != bar", {'foo': True, 'bar': False})) 224 self.assertTrue(parse("foo != bar", {'foo': True, 'bar': False}))
191 self.assertTrue(self.parse("true != foo", {'foo': False})) 225 self.assertTrue(parse("true != foo", {'foo': False}))
192 226
193 def test_Conjunctions(self): 227 def test_Conjunctions(self):
194 self.assertTrue(self.parse("true && true", {})) 228 self.assertTrue(parse("true && true", {}))
195 self.assertTrue(self.parse("true || false", {})) 229 self.assertTrue(parse("true || false", {}))
196 self.assertFalse(self.parse("false || false", {})) 230 self.assertFalse(parse("false || false", {}))
197 self.assertFalse(self.parse("true && false", {})) 231 self.assertFalse(parse("true && false", {}))
232 self.assertTrue(parse("true || false && false", {}))
233
234 def test_Parens(self):
235 self.assertTrue(parse("(true)", {}))
236 self.assertEquals(10, parse("(10)", {}))
237 self.assertEquals('foo', parse('("foo")', {}))
238 self.assertEquals(1, parse("(foo)", {'foo':1}))
239 self.assertTrue(parse("(true == true)", {}))
240 self.assertTrue(parse("(true != false)", {}))
241 self.assertTrue(parse("(true && true)", {}))
242 self.assertTrue(parse("(true || false)", {}))
243 self.assertTrue(parse("(true && true || false)", {}))
244 self.assertFalse(parse("(true || false) && false", {}))
245 self.assertTrue(parse("(true || false) && true", {}))
246 self.assertTrue(parse("true && (true || false)", {}))
247 self.assertTrue(parse("true && (true || false)", {}))
198 248
199 if __name__ == '__main__': 249 if __name__ == '__main__':
200 unittest.main() 250 unittest.main()