Ignore:
Timestamp:
Aug 1, 2014, 7:38:10 AM (5 years ago)
Author:
cameron
Message:

Refactor pulling out bitwise_expr module; prepare toAst method

File:
1 edited

Legend:

Unmodified
Added
Removed
  • proto/charsetcompiler/charset_compiler2.py

    r2997 r3942  
    4242import charset_input_parser
    4343
    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         # [a-z] and [A-Z].
    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 #
     44from bitwise_expr import *
    24245
    24346def bit_var(n):
Note: See TracChangeset for help on using the changeset viewer.