Mercurial > hg > expressionparser

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
1 #!/usr/bin/env python
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
2
2
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
3 # Implements a top-down parser/evaluator for simple boolean expressions.
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
4 # ideas taken from http://effbot.org/zone/simple-top-down-parsing.htm
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
5 #
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
6 # Rough grammar:
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
7 # expr := literal
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
8 # | '(' expr ')'
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
9 # | expr '&&' expr
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
10 # | expr '||' expr
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
11 # | expr '==' expr
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
12 # | expr '!=' expr
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
13 # literal := BOOL
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
14 # | INT
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
15 # | STRING
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
16 # | IDENT
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
17 # BOOL := true|false
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
18 # INT := [0-9]+
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
19 # STRING := "[^"]*"
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
20 # IDENT := [A-Za-z_]\w*
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
21
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
22 # Identifiers take their values from a mapping dictionary passed as the second
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
23 # argument.
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
24
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
25 __all__ = ['parse', 'ParseError']
0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
26 import re, unittest
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
27
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
28 # token classes
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
29 class ident_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
30 def __init__(self, value):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
31 self.value = value
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
32 def nud(self, parser):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
33 # identifiers take their value from the value mappings passed
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
34 # to the parser
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
35 return parser.value(self.value)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
36
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
37 class int_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
38 def __init__(self, value):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
39 self.value = int(value)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
40 def nud(self, parser):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
41 return self.value
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
42
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
43 class bool_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
44 def __init__(self, value):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
45 self.value = {'true':True, 'false':False}[value]
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
46 def nud(self, parser):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
47 return self.value
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
48
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
49 class eq_op_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
50 "=="
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
51 lbp = 20
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
52 def led(self, parser, left):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
53 return left == parser.expression(self.lbp)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
54
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
55 class neq_op_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
56 "!="
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
57 lbp = 20
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
58 def led(self, parser, left):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
59 return left != parser.expression(self.lbp)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
60
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
61 class and_op_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
62 "&&"
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
63 lbp = 11
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
64 def led(self, parser, left):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
65 right = parser.expression(self.lbp)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
66 return left and right
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
67
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
68 class or_op_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
69 "||"
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
70 lbp = 10
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
71 def led(self, parser, left):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
72 right = parser.expression(self.lbp)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
73 return left or right
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
74
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
75 class lparen_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
76 "("
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
77 lbp = 50
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
78 def nud(self, parser):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
79 expr = parser.expression()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
80 parser.advance(rparen_token)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
81 return expr
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
82
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
83 class rparen_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
84 ")"
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
85 lbp = 0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
86
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
87 class string_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
88 def __init__(self, value):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
89 self.value = value
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
90 def nud(self, parser):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
91 return self.value
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
92
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
93 class end_token:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
94 # lowest left binding power, always ends parsing
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
95 lbp = 0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
96
2
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
97 class ParseError(Exception):
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
98 pass
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
99
0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
100 class ExpressionParser(object):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
101 def __init__(self, text, valuemapping):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
102 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
103 Initialize the parser with input |text|, and |valuemapping| as
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
104 a dict mapping identifier names to values.
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
105 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
106 self.text = text
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
107 self.valuemapping = valuemapping
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
108
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
109 def _tokenize(self):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
110 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
111 Lex the input text into tokens and yield them in sequence.
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
112 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
113 # scanner callbacks
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
114 def bool_(scanner, t): return bool_token(t)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
115 def identifier(scanner, t): return ident_token(t)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
116 def integer(scanner, t): return int_token(t)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
117 def eq(scanner, t): return eq_op_token()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
118 def neq(scanner, t): return neq_op_token()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
119 def or_(scanner, t): return or_op_token()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
120 def and_(scanner, t): return and_op_token()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
121 def lparen(scanner, t): return lparen_token()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
122 def rparen(scanner, t): return rparen_token()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
123 def string_(scanner, t): return string_token(t[1:-1])
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
124
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
125 scanner = re.Scanner([
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
126 (r"true|false", bool_),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
127 (r"[a-zA-Z_]\w*", identifier),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
128 (r"[0-9]+", integer),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
129 (r'"[^"]*"', string_),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
130 (r"==", eq),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
131 (r"!=", neq),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
132 (r"\|\|", or_),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
133 (r"&&", and_),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
134 (r"\(", lparen),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
135 (r"\)", rparen),
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
136 (r"\s+", None), # skip whitespace
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
137 ])
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
138 tokens, remainder = scanner.scan(self.text)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
139 for t in tokens:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
140 yield t
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
141 yield end_token()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
142
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
143 def value(self, ident):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
144 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
145 Look up the value of |ident| in the value mapping passed in the
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
146 constructor.
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
147 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
148 return self.valuemapping[ident]
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
149
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
150 def advance(self, expected):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
151 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
152 Assert that the next token is an instance of |expected|, and advance
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
153 to the next token.
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
154 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
155 if not isinstance(self.token, expected):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
156 raise Exception, "Unexpected token!"
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
157 self.token = self.iter.next()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
158
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
159 def expression(self, rbp=0):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
160 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
161 Parse and return the value of an expression until a token with
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
162 right binding power greater than rbp is encountered.
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
163 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
164 t = self.token
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
165 self.token = self.iter.next()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
166 left = t.nud(self)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
167 while rbp < self.token.lbp:
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
168 t = self.token
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
169 self.token = self.iter.next()
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
170 left = t.led(self, left)
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
171 return left
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
172
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
173 def parse(self):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
174 """
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
175 Parse and return the value of the expression in the text
2
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
176 passed to the constructor. Raises a ParseError if the expression
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
177 could not be parsed.
0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
178 """
2
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
179 try:
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
180 self.iter = self._tokenize()
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
181 self.token = self.iter.next()
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
182 return self.expression()
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
183 except:
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
184 raise ParseError
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
185
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
186 def parse(text, values):
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
187 """
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
188 Parse and evaluate a boolean expression in |text|. Use |values| to look
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
189 up the value of identifiers referenced in the expression. Returns the final
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
190 value of the expression. A ParseError will be raised if parsing fails.
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
191 """
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
192 return ExpressionParser(text, values).parse()
0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
193
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
194 class ExpressionParserUnittest(unittest.TestCase):
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
195 def test_BasicValues(self):
2
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
196 self.assertEqual(1, parse("1", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
197 self.assertEqual(100, parse("100", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
198 self.assertEqual(True, parse("true", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
199 self.assertEqual(False, parse("false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
200 self.assertEqual("", parse('""', {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
201 self.assertEqual("foo bar", parse('"foo bar"', {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
202 self.assertEqual(1, parse("foo", {'foo':1}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
203 self.assertEqual(True, parse("bar", {'bar':True}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
204 self.assertEqual("xyz", parse("abc123", {'abc123':"xyz"}))
0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
205
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
206 def test_Equality(self):
2
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
207 self.assertTrue(parse("true == true", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
208 self.assertTrue(parse("false == false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
209 self.assertTrue(parse("false == false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
210 self.assertTrue(parse("1 == 1", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
211 self.assertTrue(parse("100 == 100", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
212 self.assertTrue(parse('"some text" == "some text"', {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
213 self.assertTrue(parse("true != false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
214 self.assertTrue(parse("1 != 2", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
215 self.assertTrue(parse('"text" != "other text"', {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
216 self.assertTrue(parse("foo == true", {'foo': True}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
217 self.assertTrue(parse("foo == 1", {'foo': 1}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
218 self.assertTrue(parse('foo == "bar"', {'foo': 'bar'}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
219 self.assertTrue(parse("foo == bar", {'foo': True, 'bar': True}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
220 self.assertTrue(parse("true == foo", {'foo': True}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
221 self.assertTrue(parse("foo != true", {'foo': False}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
222 self.assertTrue(parse("foo != 2", {'foo': 1}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
223 self.assertTrue(parse('foo != "bar"', {'foo': 'abc'}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
224 self.assertTrue(parse("foo != bar", {'foo': True, 'bar': False}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
225 self.assertTrue(parse("true != foo", {'foo': False}))
0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
226
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
227 def test_Conjunctions(self):
2
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
228 self.assertTrue(parse("true && true", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
229 self.assertTrue(parse("true || false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
230 self.assertFalse(parse("false || false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
231 self.assertFalse(parse("true && false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
232 self.assertTrue(parse("true || false && false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
233
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
234 def test_Parens(self):
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
235 self.assertTrue(parse("(true)", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
236 self.assertEquals(10, parse("(10)", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
237 self.assertEquals('foo', parse('("foo")', {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
238 self.assertEquals(1, parse("(foo)", {'foo':1}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
239 self.assertTrue(parse("(true == true)", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
240 self.assertTrue(parse("(true != false)", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
241 self.assertTrue(parse("(true && true)", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
242 self.assertTrue(parse("(true || false)", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
243 self.assertTrue(parse("(true && true || false)", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
244 self.assertFalse(parse("(true || false) && false", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
245 self.assertTrue(parse("(true || false) && true", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
246 self.assertTrue(parse("true && (true || false)", {}))
94a293b914af add documentation, clean up interface slightly, tweak tests
Ted Mielczarek <ted.mielczarek@gmail.com>
parents: 1
diff changeset
247 self.assertTrue(parse("true && (true || false)", {}))
0
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
248
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
249 if __name__ == '__main__':
ae57e69e4b15 simple expression parser
Ted Mielczarek <ted.mielczarek@gmail.com>
parents:
diff changeset
250 unittest.main()