source: proto/charsetcompiler/charset_compiler.py @ 2993

Last change on this file since 2993 was 2993, checked in by cameron, 6 years ago

Generate a Pablo skeleton

File size: 20.2 KB
Line 
1#
2#  Character Class Compiler
3#
4#  Version 0.8 - Feb. 17, 2012
5#     Add command-line option for specifying basis_pattern
6#  Copyright (c) 2007-12, Robert D. Cameron
7#  All rights reserved.
8#
9#  TO DO Notes
10#
11#  1.  Perhaps the character set definition should be extended to
12#      allow other set operations.   For example, the 'Restricted' set
13#      of XML might be defined as ['\x00-\x1f'] - ['\x09', '\x0a', '\x0d']
14#      This would require fewer operations to compute.
15#
16#  2.  The range logic generator should be modified to group
17#      bit variables the same way as the individual character logic
18#      generator (i.e., combining bits 0 and 1, 2 and 3, 4 and 5 and
19#      6 and 7 first.
20#
21#  3.  Extend for 16-bit and full Unicode character values.
22#
23#
24#--------------------------------------------------------------------------
25#
26#  Data types
27#  1. Character Set Definitions
28#  2. Boolean Expressions
29#  3. Code Generator Objects
30#
31import sys, optparse
32import re, binascii, string
33import EBCDIC
34
35import charset_def
36CharDef = charset_def.CharDef
37CharSetDef = charset_def.CharSetDef
38
39import charsets
40DefinitionSet = charsets.DefinitionSet
41
42import charset_input_parser
43
44#
45# Symbolic Representations of Boolean Expressions
46#
47
48class BoolExpr:
49   """The BoolExpr class and its subclasses provide a symbolic
50      representation of Boolean expressions.
51   """
52   pass
53
54class Var(BoolExpr):
55    def __init__(self, varname):
56        self.varname = varname
57    def show(self): return 'Var("' + self.varname + '")'
58
59class TrueLiteral(BoolExpr):
60    def __init__(self):
61        self.value = True
62    def show(self): return 'T'
63
64class FalseLiteral(BoolExpr):
65    def __init__(self):
66        self.value = False
67    def show(self): return 'F'
68
69class Not(BoolExpr):
70    def __init__(self, expr):
71        self.operand = expr
72    def show(self): return 'Not(%s)' % (self.operand.show())
73
74class 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
80class 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
86class 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
92class 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
109def 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
118def 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
138def 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
167def 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
189def 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.
205def 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#
242
243def bit_var(n):
244    global options
245#    return 'bit[%i]' % n
246    return options.basis_pattern % n
247def make_bitv(n):
248    return Var(bit_var(n))
249
250
251def make_bit_test(pattern, bit_count):
252    if bit_count == 0: return TrueLiteral()
253    bit_terms = []
254    test_bit = 2**(bit_count - 1)
255    for i in range(0, bit_count):
256        if (pattern & test_bit) == 0:
257            bit_terms.append(make_not(make_bitv(i)))
258        else: bit_terms.append(make_bitv(i))
259        test_bit >>= 1
260    while len(bit_terms) > 1:
261        new_terms = []
262        for i in range(0, len(bit_terms)/ 2):
263            new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
264        if len(bit_terms) % 2 == 1:
265            new_terms.append(bit_terms[-1])
266        bit_terms = new_terms
267    return bit_terms[0]
268
269
270def char_test_expr(ch):
271    return make_bit_test(ord(ch), 8)
272    #return make_8bit_test(ord(ch))
273
274def GE_Range(N, n):
275    if N == 0: return TrueLiteral()
276    elif N % 2 == 0 and (n >> (N - 2)) == 0:
277        return make_or(make_or(make_bitv(8-N), make_bitv(9-N)),
278                        GE_Range(N - 2, n))
279    elif N % 2 == 0 and (n >> (N - 2)) == 3:   # >= 11xxxx
280        return make_and(make_and(make_bitv(8-N), make_bitv(9-N)),
281                        GE_Range(N - 2, n - (3 << (N-2))))
282    elif N >= 1:
283        hi_bit = n & (1 << (N-1))
284        lo_bits = n - hi_bit
285        lo_range = GE_Range(N-1, lo_bits)
286        if hi_bit == 0:
287            # If the hi_bit of n is not set, then whenever the corresponding bit
288            # is set in the target, the target will certainly be >=.  Otherwise,
289            # the value of GE_range(N-1, lo_bits) is required.
290            return make_or(make_bitv(8-N), lo_range)
291        else: 
292            # If the hi_bit of n is set, then the corresponding bit must be set
293            # in the target for >= and GE_range(N-1, lo_bits) must also be true.
294            return make_and(make_bitv(8-N), lo_range)
295
296def LE_Range(N, n):
297    # If an N-bit pattern is all ones, then it is always
298    # true that any n-bit value is LE this pattern.
299    # Handling this as a special case avoids an overflow
300    # issue with n+1 requiring more than N bits.
301    if n+1 == 2 ** N:
302        return TrueLiteral()
303    else:
304        return make_not(GE_Range(N, n+1))
305
306BadRange = Exception()
307
308
309def Make_Range(n1, n2):  # require n2 >= n1
310    diff_bits = n1 ^ n2
311    diff_count = 0
312    while diff_bits > 0:
313        diff_count += 1
314        diff_bits >>= 1
315    if n2 < n1 or diff_count > 8: raise BadRange()
316    mask = 2**(diff_count-1) - 1
317    common = make_bit_test(n1 >> diff_count, 8 - diff_count)
318    if diff_count == 0: return common
319    mask = 2**(diff_count-1) - 1
320    lo_test = GE_Range(diff_count-1, n1 & mask)
321    hi_test = LE_Range(diff_count-1, n2 & mask)
322    return make_and(common, make_sel(make_bitv(8-diff_count), hi_test, lo_test))
323
324BadCharSetItem = Exception()
325
326def char_or_range_expr(charset_item):
327    if len(charset_item) == 1:
328        return char_test_expr(charset_item[0])
329    elif len(charset_item) == 3:
330        if charset_item[1] == '-' and ord(charset_item[0]) <= ord(charset_item[2]):
331             return Make_Range(ord(charset_item[0]), ord(charset_item[2]))
332    print charset_item
333    raise BadCharSetItem
334
335def charset_expr(chardef):
336    if chardef.items == []: return FalseLiteral()
337    e1 = char_or_range_expr(chardef.items[0])
338    for i in range(1, len(chardef.items)):
339        e1 = make_or(e1, char_or_range_expr(chardef.items[i]))
340    if chardef.complemented: return make_not(e1)
341    else: return e1
342
343#
344#
345#  Code Generation
346#
347class CodeGenObject:
348    def __init__(self, predeclared, typedecl='BitBlock '):
349        self.gensym_template = options.gensym_pattern
350        self.gensym_counter = 0
351        self.generated_code = []
352        self.common_expression_map = {}
353        for sym in predeclared: self.common_expression_map[sym] = sym
354        self.typedecl = typedecl
355    def add_assignment(self, varname, expr):
356        self.common_expression_map[expr] = varname
357        #self.generated_code.append('%s%s = %s;\n' % (self.typedecl, varname, expr))
358        self.generated_code.append('\t%s%s = %s\n' % (self.typedecl, varname, expr))
359    def expr_string_to_variable(self, expr_string):
360        if self.common_expression_map.has_key(expr_string): 
361            return self.common_expression_map[expr_string]
362        else:
363            self.gensym_counter += 1
364            sym = self.gensym_template % self.gensym_counter
365            self.add_assignment(sym, expr_string)
366            return sym
367    def showcode(self):
368        s = ''
369        for stmt in self.generated_code: s += stmt
370        return s
371
372def expr2simd(genobj, expr):
373    """Translate a Boolean expression into three-address Altivec code
374       using code generator object genobj.
375    """
376    if isinstance(expr, TrueLiteral): return 'simd_const_1(1)'
377    elif isinstance(expr, FalseLiteral): return 'simd_const_1(0)'
378    elif isinstance(expr, Var): return expr.varname
379    elif isinstance(expr, Not):
380       e = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand))
381       return 'simd_andc(simd_const_1(1), %s)' % (e)
382    elif isinstance(expr, Or):
383       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
384       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
385       return 'simd_or(%s, %s)' % (e1, e2)
386    elif isinstance(expr, Xor):
387       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
388       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
389       return 'simd_xor(%s, %s)' % (e1, e2)
390    elif isinstance(expr, And):
391       if isinstance(expr.operand1, Not):
392           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1.operand))
393           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
394           return 'simd_andc(%s, %s)' % (e2, e1)
395       elif isinstance(expr.operand2, Not):
396           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
397           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2.operand))
398           return 'simd_andc(%s, %s)' % (e1, e2)
399       else:
400           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
401           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
402           return 'simd_and(%s, %s)' % (e1, e2)
403    elif isinstance(expr, Sel):
404       sel = genobj.expr_string_to_variable(expr2simd(genobj, expr.sel))
405       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.true_branch))
406       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.false_branch))
407       return 'simd_if(%s, %s, %s)' %(sel, e1, e2)
408
409def chardef2simd(genobj, chardef):
410    genobj.add_assignment(chardef.name, expr2simd(genobj, charset_expr(chardef)))
411
412def chardeflist2simd(chardeflist):
413    cgo = CodeGenObject([bit_var(i) for i in range(0,8)])
414    for d in chardeflist:
415        chardef2simd(cgo, d)
416    return cgo.showcode()
417
418def expr2py(genobj, expr):
419    """Translate a Boolean expression into three-address python code
420       using code generator object genobj.
421    """
422    if isinstance(expr, TrueLiteral): return '-1'
423    elif isinstance(expr, FalseLiteral): return '0'
424    elif isinstance(expr, Var): return expr.varname
425    elif isinstance(expr, Not):
426       e = genobj.expr_string_to_variable(expr2py(genobj, expr.operand))
427       return '(~%s)' % (e)
428    elif isinstance(expr, Or):
429       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
430       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
431       return '(%s | %s)' % (e1, e2)
432    elif isinstance(expr, Xor):
433       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
434       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
435       return '(%s ^ %s)' % (e1, e2)
436    elif isinstance(expr, And):
437       if isinstance(expr.operand1, Not):
438           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1.operand))
439           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
440           return '(%s &~ %s)' % (e2, e1)
441       elif isinstance(expr.operand2, Not):
442           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
443           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2.operand))
444           return '(%s &~ %s)' % (e1, e2)
445       else:
446           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
447           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
448           return '(%s & %s)' % (e1, e2)
449    elif isinstance(expr, Sel):
450       sel = genobj.expr_string_to_variable(expr2py(genobj, expr.sel))
451       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.true_branch))
452       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.false_branch))
453       return '((%s & %s)|(~(%s) & %s))' %(sel, e1, sel, e2)
454
455def chardef2py(genobj, chardef):
456    genobj.add_assignment(chardef.name, expr2py(genobj, charset_expr(chardef)))
457
458
459def py_chardefmap(chardeflist):
460    defs = ["'%s' : %s" % (d.name,d.name) for d in chardeflist]
461    return  '{%s}' % string.join(defs, ',\n\t')
462
463def chardeflist2py(chardeflist):
464    cgo = CodeGenObject([bit_var(i) for i in range(0,8)],'')
465    for d in chardeflist:
466        chardef2py(cgo, d) 
467    return cgo.showcode()# + "  return "+ py_chardefmap(chardeflist) + "\n"
468
469
470
471def main():
472
473    global options
474    # Option definition
475    option_parser = optparse.OptionParser(usage='python %prog [options] <input file>', version='0.8')
476
477    option_parser.add_option('-b', '--basis_pattern', 
478                             dest='basis_pattern',
479                             type='string',
480                             default='basis_bits.bit_%i',
481                             help='pattern for basis bit streams; default: basis_bits.bit_%i',
482                             )
483    option_parser.add_option('-g', '--gensym_pattern', 
484                             dest='gensym_pattern',
485                             type='string',
486                             default='temp%i',
487                             help='pattern for generated temporaries; default: temp%i',
488                             )
489    option_parser.add_option('-E', '--EBCDIC', 
490                             dest='use_EBCDIC',
491                             action='store_true', 
492                             default=False,
493                             help='generate definitions for EBCDIC input',
494                             )
495    option_parser.add_option('-p', '--pablo', 
496                             dest='Pablo_skeleton',
497                             action='store_true', 
498                             default=False,
499                             help='generate pablo skeleton',
500                             )
501    options, args = option_parser.parse_args(sys.argv[1:])
502
503    # Positional arguments
504    if len(args) == 1:
505        # if the specified argument is not in the DefinitionSet, then assume that it's a filename
506        if args[0] not in DefinitionSet:
507            #define the characters in the list
508            defs = charset_input_parser.input_chardef(args[0])
509        else: defs = DefinitionSet[args[1]]
510        if options.use_EBCDIC:
511            defs = EBCDIC.ascii2ebcdic_chardeflist(defs)       
512        stmts = chardeflist2py(defs)
513        if options.Pablo_skeleton:
514          b = string.split(options.basis_pattern, ".")
515          if len(b) == 2: 
516            basis_struct = string.upper(b[0][0]) + b[0][1:]
517            basis_struct_var = b[0]
518            bit_pattern = b[1]
519          else: 
520            basis_struct = 'Bits'
521            basis_stuct_var = 'bits'
522            bit_pattern = bit[0]
523          struct_defs = "class %s():\n" % basis_struct
524          for i in range(8): struct_defs += "\t" + bit_pattern % i + " = 0\n"
525          struct_sets = {}
526          for d in defs:
527            n = string.split(d.name, ".")
528            if len(n) == 2:
529              if not n[0] in struct_sets.keys(): struct_sets[n[0]] = []
530              struct_sets[n[0]].append(n[1])
531          for k in struct_sets.keys():
532            struct_defs += "\nclass %s():\n" % (string.upper(k[0])+k[1:])
533            for f in struct_sets[k]: struct_defs += "\t" + f + " = 0\n"
534          print struct_defs
535          params = ", ".join([basis_struct_var] + struct_sets.keys())
536          print "\ndef Do_defs(%s):\n" % params
537          print stmts
538          print "\ndef main():\n\tDo_defs(%s)\n" % params
539        else: print stmts 
540
541    else:
542        option_parser.print_usage()
543
544if __name__ == "__main__": main()
545
Note: See TracBrowser for help on using the repository browser.