Changeset 3942 for proto/charsetcompiler/charset_compiler2.py
 Timestamp:
 Aug 1, 2014, 7:38:10 AM (5 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

proto/charsetcompiler/charset_compiler2.py
r2997 r3942 42 42 import charset_input_parser 43 43 44 # 45 # Symbolic Representations of Boolean Expressions 46 # 47 48 class BoolExpr: 49 """The BoolExpr class and its subclasses provide a symbolic 50 representation of Boolean expressions. 51 """ 52 pass 53 54 class Var(BoolExpr): 55 def __init__(self, varname): 56 self.varname = varname 57 def show(self): return 'Var("' + self.varname + '")' 58 59 class TrueLiteral(BoolExpr): 60 def __init__(self): 61 self.value = True 62 def show(self): return 'T' 63 64 class FalseLiteral(BoolExpr): 65 def __init__(self): 66 self.value = False 67 def show(self): return 'F' 68 69 class Not(BoolExpr): 70 def __init__(self, expr): 71 self.operand = expr 72 def show(self): return 'Not(%s)' % (self.operand.show()) 73 74 class And(BoolExpr): 75 def __init__(self, expr1, expr2): 76 self.operand1 = expr1 77 self.operand2 = expr2 78 def show(self): return 'And(%s, %s)' % (self.operand1.show(), self.operand2.show()) 79 80 class Or(BoolExpr): 81 def __init__(self, expr1, expr2): 82 self.operand1 = expr1 83 self.operand2 = expr2 84 def show(self): return 'Or(%s, %s)' % (self.operand1.show(), self.operand2.show()) 85 86 class Xor(BoolExpr): 87 def __init__(self, expr1, expr2): 88 self.operand1 = expr1 89 self.operand2 = expr2 90 def show(self): return 'Xor(%s, %s)' % (self.operand1.show(), self.operand2.show()) 91 92 class Sel(BoolExpr): 93 def __init__(self, expr1, expr2, expr3): 94 self.sel = expr1 95 self.true_branch = expr2 96 self.false_branch = expr3 97 def show(self): return 'Sel(%s, %s, %s)' % (self.sel.show(), self.true_branch.show(), self.false_branch.show()) 98 99 100 # 101 # Optimizing Constructors for Boolean Expressions 102 #  Maintaining Assembler Instruction Form: 103 #  All boolean algebraic rules involving true/false applied. 104 #  Negations restricted: 105 #  no negations within or (DeMorgan's to nand) 106 #  at most one negation within and 107 # 108 109 def make_not(expr): 110 if isinstance(expr, TrueLiteral): 111 return FalseLiteral() 112 elif isinstance(expr, FalseLiteral): 113 return TrueLiteral() 114 elif isinstance(expr, Not): 115 return expr.operand 116 else: return Not(expr) 117 118 def make_and(expr1, expr2): 119 if isinstance(expr1, TrueLiteral): 120 return expr2 121 elif isinstance(expr2, TrueLiteral): 122 return expr1 123 elif isinstance(expr1, FalseLiteral): 124 return FalseLiteral() 125 elif isinstance(expr2, FalseLiteral): 126 return FalseLiteral() 127 elif equal_exprs(expr1, expr2): return expr1 128 elif isinstance(expr1, Not): 129 if isinstance(expr2, Not): 130 return make_not(make_or(expr1.operand, expr2.operand)) 131 elif equal_exprs(expr1.operand, expr2): return FalseLiteral() 132 else: return And(expr1, expr2) 133 elif isinstance(expr2, Not): 134 if equal_exprs(expr1, expr2.operand): return FalseLiteral() 135 else: return And(expr1, expr2) 136 else: return And(expr1, expr2) 137 138 def make_or(expr1, expr2): 139 if isinstance(expr1, FalseLiteral): 140 return expr2 141 elif isinstance(expr2, FalseLiteral): 142 return expr1 143 elif isinstance(expr1, TrueLiteral): 144 return TrueLiteral() 145 elif isinstance(expr2, TrueLiteral): 146 return TrueLiteral() 147 elif isinstance(expr1, Not): 148 return make_not(make_and(expr1.operand, make_not(expr2))) 149 elif isinstance(expr2, Not): 150 return make_not(make_and(make_not(expr1), expr2.operand)) 151 elif equal_exprs(expr1, expr2): return expr1 152 elif isinstance(expr1, And) and isinstance(expr2, And): 153 # These optimizations factor out common components that 154 # can occur when sets are formed by union (e.g., union of 155 # [az] and [AZ]. 156 if equal_exprs(expr1.operand1, expr2.operand1): 157 return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2)) 158 elif equal_exprs(expr1.operand2, expr2.operand2): 159 return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1)) 160 elif equal_exprs(expr1.operand1, expr2.operand2): 161 return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1)) 162 elif equal_exprs(expr1.operand2, expr2.operand1): 163 return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2)) 164 else: return Or(expr1, expr2) 165 else: return Or(expr1, expr2) 166 167 def make_sel(if_expr, T_expr, F_expr): 168 if isinstance(if_expr, TrueLiteral): 169 return T_expr 170 elif isinstance(if_expr, FalseLiteral): 171 return F_expr 172 elif isinstance(T_expr, TrueLiteral): 173 # if x then T else y = x or y 174 return make_or(if_expr, F_expr) 175 elif isinstance(T_expr, FalseLiteral): 176 # if x then F else y = not(x) and y 177 return make_and(make_not(if_expr), F_expr) 178 elif isinstance(F_expr, FalseLiteral): 179 # if x then y else F = x and y 180 return make_and(if_expr, T_expr) 181 elif isinstance(F_expr, TrueLiteral): 182 # if x then y else T = not(x) or y 183 return make_or(make_not(if_expr), T_expr) 184 elif equal_exprs(T_expr, F_expr): 185 return T_expr 186 else: return Sel(if_expr, T_expr, F_expr) 187 188 189 def make_xor(expr1, expr2): 190 if isinstance(expr1, FalseLiteral): 191 return expr2 192 elif isinstance(expr2, FalseLiteral): 193 return expr1 194 elif isinstance(expr1, TrueLiteral): 195 return make_not(expr2) 196 elif isinstance(expr2, TrueLiteral): 197 return make_not(expr1) 198 elif isinstance(expr1, Not) and isinstance(expr2, Not): 199 return make_xor(expr1.operand, expr2.operand) 200 else: return Xor(expr1, expr2) 201 202 # Return True if e1 and e2 can be proven equivalent according 203 # to some rules, False otherwise. Note that False may 204 # be returned in some cases when the exprs are equivalent. 205 def equal_exprs(e1, e2): 206 if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral) 207 elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral) 208 elif isinstance(e1, Var) and isinstance(e2, Var): 209 return e1.varname == e2.varname 210 elif isinstance(e1, Not) and isinstance(e2, Not): 211 return equal_exprs(e1.operand, e2.operand) 212 elif isinstance(e1, And) and isinstance(e2, And): 213 if equal_exprs(e1.operand1, e2.operand1): 214 return equal_exprs(e1.operand2, e2.operand2) 215 elif equal_exprs(e1.operand1, e2.operand2): 216 return equal_exprs(e1.operand2, e2.operand1) 217 else: return False 218 elif isinstance(e1, Or) and isinstance(e2, Or): 219 if equal_exprs(e1.operand1, e2.operand1): 220 return equal_exprs(e1.operand2, e2.operand2) 221 elif equal_exprs(e1.operand1, e2.operand2): 222 return equal_exprs(e1.operand2, e2.operand1) 223 else: return False 224 elif isinstance(e1, Xor) and isinstance(e2, Xor): 225 if equal_exprs(e1.operand1, e2.operand1): 226 return equal_exprs(e1.operand2, e2.operand2) 227 elif equal_exprs(e1.operand1, e2.operand2): 228 return equal_exprs(e1.operand2, e2.operand1) 229 else: return False 230 elif isinstance(e1, Sel) and isinstance(e2, Sel): 231 if equal_exprs(e1.sel, e2.sel): 232 if equal_exprs(e1.true_branch, e2.true_branch): 233 return equal_exprs(e1.false_branch, e2.false_branch) 234 else: return False 235 else: return False 236 237 238 # 239 # 240 # Boolean Expressions for Character Class Definitions 241 # 44 from bitwise_expr import * 242 45 243 46 def bit_var(n):
Note: See TracChangeset
for help on using the changeset viewer.