Changeset 3942 for proto


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

Refactor pulling out bitwise_expr module; prepare toAst method

Location:
proto/charsetcompiler
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • proto/charsetcompiler/charset_compiler.py

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