source: proto/charsetcompiler/pablo_expr.py @ 3947

Last change on this file since 3947 was 3947, checked in by cameron, 5 years ago

Rename bitwise-expr to pablo-expr;add advance expression, pablo-stmt

File size: 8.4 KB
Line 
1#
2#  Pablo Expressions:  bitwise Boolean Expressions + Advance.
3#
4import ast
5
6class BitwiseExpr:
7   """The BitwiseExpr class and its subclasses provide a symbolic
8      representation of bitwise Boolean expressions.
9   """
10   pass
11
12class Var(BitwiseExpr):
13    def __init__(self, varname):
14        self.varname = varname
15    def __str__(self): return 'Var("' + self.varname + '")'
16    def toAST(self): return ast.Name(id=self.varname, ctx=ast.Load())
17
18class TrueLiteral(BitwiseExpr):
19    def __init__(self):
20        self.value = True
21    def __str__(self): return 'T'
22    def toAST(self): return ast.Name(id='True', ctx=ast.Load())
23
24class FalseLiteral(BitwiseExpr):
25    def __init__(self):
26        self.value = False
27    def __str__(self): return 'F'
28    def toAST(self): return ast.Name(id='False', ctx=ast.Load())
29
30class Not(BitwiseExpr):
31    def __init__(self, expr):
32        self.operand = expr
33    def __str__(self): return 'Not(%s)' % (self.operand.__str__())
34    def toAST(self): return ast.UnaryOp(ast.Not(), self.operand.toAST())
35
36class And(BitwiseExpr):
37    def __init__(self, expr1, expr2):
38        self.operand1 = expr1
39        self.operand2 = expr2
40    def __str__(self): return 'And(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
41    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitAnd(), self.operand2.toAST())
42
43class Or(BitwiseExpr):
44    def __init__(self, expr1, expr2):
45        self.operand1 = expr1
46        self.operand2 = expr2
47    def __str__(self): return 'Or(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
48    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitOr(), self.operand2.toAST())
49
50class Xor(BitwiseExpr):
51    def __init__(self, expr1, expr2):
52        self.operand1 = expr1
53        self.operand2 = expr2
54    def __str__(self): return 'Xor(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
55    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitXor(), self.operand2.toAST())
56
57class Sel(BitwiseExpr):
58    def __init__(self, expr1, expr2, expr3):
59        self.sel = expr1
60        self.true_branch = expr2
61        self.false_branch = expr3
62    def __str__(self): return 'Sel(%s, %s, %s)' % (self.sel.__str__(), self.true_branch.__str__(), self.false_branch.__str__())
63    def toAST(self): return ast.IfExpr(self.sel.toAST(), self.true_branch.toAST(), self.false_branch.toAST())
64
65class Adv(BitwiseExpr):
66    def __init__(self, expr, n):
67        self.operand = expr
68        self.offset = n
69    def __str__(self): return 'Advance(%s, %i)' % (self.operand.__str__(), self.offset)
70    def toAST(self): return ast.Call(ast.Attribute(ast.Name('pablo', ast.Load()), 'Advance', ast.Load()), [self.operand.toAST(), ast.Num(self.offset)])
71
72
73
74
75#
76# Optimizing Constructors for Boolean Expressions
77# - Maintaining Assembler Instruction Form:
78#   - All boolean algebraic rules involving true/false applied.
79#   - Negations restricted:
80#       - no negations within or (DeMorgan's to nand)
81#       - at most one negation within and
82#
83
84def make_not(expr):
85    if isinstance(expr, TrueLiteral):
86        return FalseLiteral()
87    elif isinstance(expr, FalseLiteral):
88        return TrueLiteral()
89    elif isinstance(expr, Not):
90        return expr.operand
91    else: return Not(expr)
92
93def make_and(expr1, expr2):
94    if isinstance(expr1, TrueLiteral):
95        return expr2
96    elif isinstance(expr2, TrueLiteral):
97        return expr1
98    elif isinstance(expr1, FalseLiteral):
99        return FalseLiteral()
100    elif isinstance(expr2, FalseLiteral):
101        return FalseLiteral()
102    elif equal_exprs(expr1, expr2): return expr1
103    elif isinstance(expr1, Not):
104        if isinstance(expr2, Not):
105            return make_not(make_or(expr1.operand, expr2.operand))
106        elif equal_exprs(expr1.operand, expr2): return FalseLiteral()
107        else: return And(expr1, expr2)
108    elif isinstance(expr2, Not):
109        if equal_exprs(expr1, expr2.operand): return FalseLiteral()
110        else: return And(expr1, expr2)
111    else: return And(expr1, expr2)
112
113def make_or(expr1, expr2):
114    if isinstance(expr1, FalseLiteral):
115        return expr2
116    elif isinstance(expr2, FalseLiteral):
117        return expr1
118    elif isinstance(expr1, TrueLiteral):
119        return TrueLiteral()
120    elif isinstance(expr2, TrueLiteral):
121        return TrueLiteral()
122    elif isinstance(expr1, Not):
123        return make_not(make_and(expr1.operand, make_not(expr2)))
124    elif isinstance(expr2, Not):
125        return make_not(make_and(make_not(expr1), expr2.operand))
126    elif equal_exprs(expr1, expr2): return expr1
127    elif isinstance(expr1, And) and isinstance(expr2, And):
128        # These optimizations factor out common components that
129        # can occur when sets are formed by union (e.g., union of
130        # [a-z] and [A-Z].
131        if equal_exprs(expr1.operand1, expr2.operand1):
132            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2))
133        elif equal_exprs(expr1.operand2, expr2.operand2):
134            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1))
135        elif equal_exprs(expr1.operand1, expr2.operand2):
136            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1))
137        elif equal_exprs(expr1.operand2, expr2.operand1):
138            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2))
139        else: return Or(expr1, expr2)
140    else: return Or(expr1, expr2)
141
142def make_sel(if_expr, T_expr, F_expr):
143    if isinstance(if_expr, TrueLiteral):
144        return T_expr
145    elif isinstance(if_expr, FalseLiteral):
146        return F_expr
147    elif isinstance(T_expr, TrueLiteral):
148        # if x then T else y = x or y
149        return make_or(if_expr, F_expr) 
150    elif isinstance(T_expr, FalseLiteral):
151        # if x then F else y = not(x) and y
152        return make_and(make_not(if_expr), F_expr) 
153    elif isinstance(F_expr, FalseLiteral):
154        # if x then y else F = x and y
155        return make_and(if_expr, T_expr) 
156    elif isinstance(F_expr, TrueLiteral):
157        # if x then y else T = not(x) or y
158        return make_or(make_not(if_expr), T_expr)
159    elif equal_exprs(T_expr, F_expr):
160        return T_expr
161    else: return Sel(if_expr, T_expr, F_expr)
162
163
164def make_xor(expr1, expr2):
165    if isinstance(expr1, FalseLiteral):
166        return expr2
167    elif isinstance(expr2, FalseLiteral):
168        return expr1
169    elif isinstance(expr1, TrueLiteral):
170        return make_not(expr2)
171    elif isinstance(expr2, TrueLiteral):
172        return make_not(expr1)
173    elif isinstance(expr1, Not) and isinstance(expr2, Not):
174        return make_xor(expr1.operand, expr2.operand)
175    else: return Xor(expr1, expr2)
176
177# Return True if e1 and e2 can be proven equivalent according
178# to some rules, False otherwise.   Note that False may
179# be returned in some cases when the exprs are equivalent.
180def equal_exprs(e1, e2):
181    if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral)
182    elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral)
183    elif isinstance(e1, Var) and isinstance(e2, Var):
184        return e1.varname == e2.varname
185    elif isinstance(e1, Not) and isinstance(e2, Not):
186        return equal_exprs(e1.operand, e2.operand)
187    elif isinstance(e1, And) and isinstance(e2, And):
188        if equal_exprs(e1.operand1, e2.operand1):
189            return equal_exprs(e1.operand2, e2.operand2)
190        elif equal_exprs(e1.operand1, e2.operand2):
191            return equal_exprs(e1.operand2, e2.operand1)
192        else: return False
193    elif isinstance(e1, Or) and isinstance(e2, Or):
194        if equal_exprs(e1.operand1, e2.operand1):
195            return equal_exprs(e1.operand2, e2.operand2)
196        elif equal_exprs(e1.operand1, e2.operand2):
197            return equal_exprs(e1.operand2, e2.operand1)
198        else: return False
199    elif isinstance(e1, Xor) and isinstance(e2, Xor):
200        if equal_exprs(e1.operand1, e2.operand1):
201            return equal_exprs(e1.operand2, e2.operand2)
202        elif equal_exprs(e1.operand1, e2.operand2):
203            return equal_exprs(e1.operand2, e2.operand1)
204        else: return False
205    elif isinstance(e1, Sel) and isinstance(e2, Sel):
206        if equal_exprs(e1.sel, e2.sel):
207             if equal_exprs(e1.true_branch, e2.true_branch):
208                 return equal_exprs(e1.false_branch, e2.false_branch)
209             else: return False
210        else: return False
211    elif isinstance(e1, Adv) and isinstance(e2, Adv):
212        if e1.offset == e2.offset: return equal_exprs(e1.operand(), e2.operand())
213        else: return False
214    else: return False
215
Note: See TracBrowser for help on using the repository browser.