source: proto/charsetcompiler/charset_compiler.py @ 683

Last change on this file since 683 was 683, checked in by ksherdy, 9 years ago

Fix JSON String defintions.

File size: 30.1 KB
Line 
1# -*- coding: utf-8 -*-
2#
3#  Character Class Compiler
4#
5#  Version 0.7 - August 14, 2009
6#     Adding generation of Python code;  parabix 2 definitions
7#  Copyright (c) 2007, Robert D. Cameron
8#  All rights reserved.
9#
10#  TO DO Notes
11#
12#  1.  Perhaps the character set definition should be extended to
13#      allow other set operations.   For example, the 'Restricted' set
14#      of XML might be defined as ['\x00-\x1f'] - ['\x09', '\x0a', '\x0d']
15#      This would require fewer operations to compute.
16#
17#  2.  The range logic generator should be modified to group
18#      bit variables the same way as the individual character logic
19#      generator (i.e., combining bits 0 and 1, 2 and 3, 4 and 5 and
20#      6 and 7 first.
21#
22#  3.  Extend for 16-bit and full Unicode character values.
23#
24#
25#--------------------------------------------------------------------------
26#
27#  Data types
28#  1. Character Set Definitions
29#  2. Boolean Expressions
30#  3. Code Generator Objects
31#
32import re, binascii, string
33
34#
35#  Character sets are defined as lists of items that
36#  are either individual characters or ranges of contiguous
37#  characters.
38#
39class CharSetDef:
40    """Definitions of character sets.   Examples:
41    CharSetDef('alpha_', ['a-z', 'A-Z', '_'])
42    CharDef('semicolon', ';') (equiv. to CharSetDef('semicolon', [';']))
43    """
44    def __init__(self, name, items, invert = False):
45        self.name = name
46        self.items = items
47        self.complemented = invert
48    def show(self): 
49        if self.complemented:
50            return "CharSetDef(%s, %s, True)" % (self.name, self.items)
51        else: return "CharSetDef(%s, %s)" % (self.name, self.items)
52
53       
54class CharDef(CharSetDef):
55    def __init__(self, name, char, invert = False):
56        self.name = name
57        self.items = [char]
58        self.complemented = invert
59    def show(self): 
60        if self.complemented:
61            return "CharDef(%s, '\\%X', True)" % (self.name, ord(self.items[0]))
62        else: return "CharDef(%s, '\\%X')" % (self.name, ord(self.items[0]))
63
64
65#
66# UTF-8 bytes occurring in the additional XML 1.1 line break
67# characters NEL and LS.
68
69UTF8_XML11_WS_bytes = [CharDef('NEL1', chr(0xC2)),
70                        CharDef('NEL2', chr(0x85)),
71                        CharDef('LS1', chr(0xE2)),
72                        CharDef('LS2', chr(0x80)),
73                        CharDef('LS3', chr(0xA8))]
74           
75DefinitionSet = {}
76
77
78
79DefinitionSet['WS_Control_10'] = [CharSetDef('control.x00_x1F', ['\x00-\x1F']),
80                                  CharDef('control.CR', '\x0D'),
81                                  CharDef('control.LF', '\x0A'),
82                                  CharDef('control.HT', '\x09'),
83                                  CharDef('control.SP', ' '),
84                                  CharSetDef('lex.WS', ['\x0D', '\x0A', '\x09', ' '])]
85
86DefinitionSet['WS_Control_10_EBCDIC'] = [CharSetDef('Control', ['\x00-\x03', '\x37',
87                                                                '\x2d-\x2f', '\x16',
88                                                                '\x0b-\x13', '\x3c-\x3d',
89                                                                '\x32', '\x26-\x27',
90                                                                '\x18-\x19', '\x3f', 
91                                                                '\x1c-\x1f']),
92                                         CharDef('CR', '\x0D'),
93                                         CharDef('LF', '\x25'),
94                                         CharDef('HT', '\x05'),
95                                         CharDef('SP', '\x40')]
96
97DefinitionSet['WS_Control_11_EBCDIC'] = [CharSetDef('Control', ['\x00-\x3f']),
98                                         CharDef('CR', '\x0D'),
99                                         CharDef('LF', '\x25'),
100                                         CharDef('HT', '\x05'),
101                                         CharDef('SP', '\x40'),
102                                         CharDef('NEL', '\x15')]
103
104
105DefinitionSet['WS_Control_11_ISO8859'] = [CharSetDef('Control', ['\x00-\x1F', '\x7F', '\x80-\x9F']),
106                                          CharDef('CR', '\x0D'),
107                                          CharDef('LF', '\x0A'),
108                                          CharDef('HT', '\x09'),
109                                          CharDef('SP', ' '),
110                                          CharDef('NEL', '\x85')]
111
112DefinitionSet['Markup'] = [CharDef('RefStart', '&'),
113                           CharDef('Semicolon', ';'),
114                           CharDef('LAngle', '<'),
115                           CharDef('RAngle', '>'),
116                           CharDef('RBracket', ']'),
117                           CharDef('Hyphen', '-'),
118                           CharDef('QMark', '?'),
119                           CharDef('Equals', "="),
120                           CharDef('SQuote', "'"),
121                           CharDef('DQuote', '"'),
122                           CharDef('Slash', '/')
123                           ]
124
125DefinitionSet['Digit_and_Hex'] = [CharSetDef('Digit', ['0-9']),
126                                  CharSetDef('Hex', ['0-9', 'A-F', 'a-f'])]
127
128DefinitionSet['Markup2'] = DefinitionSet['Markup'] + DefinitionSet['Digit_and_Hex']
129
130DefinitionSet['LexicalItems'] = [CharSetDef('MarkupStart', ['<', '&']),
131                                 CharDef('RAngle', '>'),
132                                 CharDef('RBracket', ']'),
133                                 CharDef('Hyphen', '-'),
134                                 CharDef('QMark', '?'),
135                                 CharSetDef('Quote', ['"', "'", '<', '&']),
136                                 CharSetDef('NameFollow', [';', '=', '/', '>', '?', ')', '[', '|', '?', '*', '+', ','])
137                                 ]
138DefinitionSet['LexicalItems2'] = [CharSetDef('MarkupStart', ['<', '&']),
139                                 CharDef('RAngle', '>'),
140                                 CharDef('RBracket', ']'),
141                                 CharDef('Hyphen', '-'),
142                                 CharDef('QMark', '?'),
143                                 CharSetDef('Quote', ['"', "'", '<', '&']),
144                                 CharSetDef('NameFollow', [' -,', '/', ';-?', '[-^', '{-~'])
145                                 ]
146
147
148
149DefinitionSet['Digit_and_Hex'] = [CharSetDef('lex.Digit', ['0-9']),
150                                  CharSetDef('lex.Hex', ['0-9', 'A-F', 'a-f'])]
151                                 
152DefinitionSet['LexicalItems_with_Digit'] = DefinitionSet['LexicalItems2'] + DefinitionSet['Digit_and_Hex']
153
154DefinitionSet['LI_with_MarkupPass'] = DefinitionSet['LexicalItems_with_Digit'] + [CharSetDef('AmpHashSlash', ['&', '#', '/'])]
155
156#
157# Byte classifications in UTF-8 validation.
158DefinitionSet['UTF8'] =         [
159                                CharSetDef('u8.unibyte', ['\x00-\x7F']),
160                                CharSetDef('u8.prefix', ['\xC0-\xFF']),
161                                CharSetDef('u8.prefix2', ['\xC0-\xDF']),
162                                CharSetDef('u8.prefix3', ['\xE0-\xEF']),
163                                CharSetDef('u8.prefix4', ['\xF0-\xFF']),
164                                CharSetDef('u8.suffix', ['\x80-\xBF']),
165                                CharSetDef('u8.badprefix', ['\xC0-\xC1', '\xF5-\xFF']),
166                                CharDef('u8.xE0', '\xE0'),
167                                CharDef('u8.xED', '\xED'),
168                                CharDef('u8.xF0', '\xF0'),
169                                CharDef('u8.xF4', '\xF4'),
170                                CharSetDef('u8.xA0_xBF', ['\xA0-\xBF']),
171                                CharSetDef('u8.x80_x9F', ['\x80-\x9F']),
172                                CharSetDef('u8.x90_xBF', ['\x90-\xBF']),
173                                CharSetDef('u8.x80_x8F', ['\x80-\x8F']) 
174                                ]
175
176DefinitionSet['JSON_Control'] = [
177                                #Control characters
178                                CharSetDef('ctrl.x00_x1F', ['\x00-\x1F']),
179                                CharDef('ctrl.CR', '\x0D'),
180                                CharDef('ctrl.LF', '\x0A'),
181                                CharDef('ctrl.HT', '\x09'),
182                                CharDef('ctrl.SP', ' '),
183                                ]
184
185DefinitionSet['JSON_Lexical'] = [
186                                #Object
187                                CharDef('lex.LCurlyBrace','{'),
188                                CharDef('lex.Colon',':'),
189                                CharDef('lex.Comma',','),
190                                CharDef('lex.RCurlyBrace','}'),
191                               
192                                #Array
193                                CharDef('lex.LSquareBracket','['),
194                                CharDef('lex.RSquareBracket',']'),
195                               
196                                #Number
197                                CharDef('lex.Minus', '-'),
198                                CharDef('lex.Zero', '0'),
199                                CharSetDef('lex.Digit1_9', ['1-9']),
200                                CharSetDef('lex.Digit0_9', ['0-9']),
201                                CharDef('lex.DecimalPoint', '.'),
202                                CharSetDef('lex.Ee', ['E','e']),
203                                CharSetDef('lex.PlusMinus', ['+','-']),
204                                CharSetDef('lex.NumberFollowSet',[',','}',']']),
205                               
206                                #String
207                                CharDef('lex.DQuote','\"'),
208                                CharDef('lex.RSolidus','\\'),
209                                CharDef('lex.Solidus','/'),
210                                CharDef('lex.b','b'),
211                                CharDef('lex.f','f'),
212                                CharDef('lex.n','n'),
213                                CharDef('lex.t','t'),
214                                CharDef('lex.u','u'),
215                                CharSetDef('lex.HexDigit', ['0-9','a-f','A-F']),
216                               
217                                #WS
218                                CharSetDef('lex.WS', ['\x0D', '\x0A', '\x09', ' '])
219                                ]
220       
221DefinitionSet['JSON'] = DefinitionSet['UTF8'] + DefinitionSet['JSON_Control'] + DefinitionSet['JSON_Lexical'] 
222
223#
224# Following definitions for the parabix2 unbounded bitstream prototype
225#
226# First all the special characters in the XML delimiters.
227
228xml_marks =    [CharDef('lex.RefStart', '&'),
229                CharDef('lex.Semicolon', ';'),
230                CharDef('lex.LAngle', '<'),
231                CharDef('lex.RAngle', '>'),
232                CharDef('lex.LBracket', '['),
233                CharDef('lex.RBracket', ']'),
234                CharDef('lex.Exclam', '!'),
235                CharDef('lex.QMark', '?'),
236                CharDef('lex.Hyphen', '-'),
237                CharDef('lex.Equals', "="),
238                CharDef('lex.SQuote', "'"),
239                CharDef('lex.DQuote', '"'),
240                CharDef('lex.Slash', '/'),
241                CharDef('lex.Hash', '#'),
242                CharDef('lex.x', 'x'),
243                CharDef('lex.Colon', ':')
244                ]
245#
246# NameFollow: all characters that may legally follow an XML name, plus
247# any others that may not be used in names.
248# 1. All non-WS characters that may legally follow an XML name.
249namefollow = [CharSetDef('lex.NameFollow', [';', '=', '/', '>', '?', ')', '[', '|', '?', '*', '+', ','])]
250#
251# NameScan: all ASCII characters that may legally occur in a Name,
252# plus all UTF-8 prefix and suffix bytes.
253namescan = [CharSetDef('lex.NameScan', ['_', '-', '.', '0-:', 'A-Z', 'a-z', '\x80-\xFF'])]
254
255#
256namelex = [CharSetDef('lex.ASCII_name_start', ['_', ':', 'A-Z', 'a-z']),
257           CharSetDef('lex.ASCII_name_char', ['_', '-', '.', '0-:', 'A-Z', 'a-z']),
258           CharSetDef('lex.NameScan', ['_', '-', '.', '0-:', 'A-Z', 'a-z', '\x80-\xFF'])]
259
260#
261UTF8_BOM_bytes = [CharDef('u8.xEF', '\xEF'), CharDef('u8.xBF', '\xBF'), CharDef('u8.xBE', '\xBE')]
262
263DefinitionSet['parabix2'] = (xml_marks + namelex + DefinitionSet['WS_Control_10']
264                             + DefinitionSet['Digit_and_Hex'] + DefinitionSet['UTF8'] + UTF8_BOM_bytes)
265
266DefinitionSet['CSV'] = [CharDef('BackSlash', '\\'),
267                        CharDef('DQuote', '"'),
268                        CharDef('SQuote', '\''),
269                        CharDef('CR', '\x0D'),
270                        CharDef('LF', '\x0A'),
271                        CharDef('Comma', ','),
272                        CharDef('HT', '\x09'),
273                        CharDef('Period', '.')]
274
275
276#
277# Symbolic Representations of Boolean Expressions
278#
279
280class BoolExpr:
281   """The BoolExpr class and its subclasses provide a symbolic
282      representation of Boolean expressions.
283   """
284   pass
285
286class Var(BoolExpr):
287    def __init__(self, varname):
288        self.varname = varname
289    def show(self): return 'Var("' + self.varname + '")'
290
291class TrueLiteral(BoolExpr):
292    def __init__(self):
293        self.value = True
294    def show(self): return 'T'
295
296class FalseLiteral(BoolExpr):
297    def __init__(self):
298        self.value = False
299    def show(self): return 'F'
300
301class Not(BoolExpr):
302    def __init__(self, expr):
303        self.operand = expr
304    def show(self): return 'Not(%s)' % (self.operand.show())
305
306class And(BoolExpr):
307    def __init__(self, expr1, expr2):
308        self.operand1 = expr1
309        self.operand2 = expr2
310    def show(self): return 'And(%s, %s)' % (self.operand1.show(), self.operand2.show())
311
312class Or(BoolExpr):
313    def __init__(self, expr1, expr2):
314        self.operand1 = expr1
315        self.operand2 = expr2
316    def show(self): return 'Or(%s, %s)' % (self.operand1.show(), self.operand2.show())
317
318class Xor(BoolExpr):
319    def __init__(self, expr1, expr2):
320        self.operand1 = expr1
321        self.operand2 = expr2
322    def show(self): return 'Xor(%s, %s)' % (self.operand1.show(), self.operand2.show())
323
324class Sel(BoolExpr):
325    def __init__(self, expr1, expr2, expr3):
326        self.sel = expr1
327        self.true_branch = expr2
328        self.false_branch = expr3
329    def show(self): return 'Sel(%s, %s, %s)' % (self.sel.show(), self.true_branch.show(), self.false_branch.show())
330
331
332#
333# Optimizing Constructors for Boolean Expressions
334# - Maintaining Assembler Instruction Form:
335#   - All boolean algebraic rules involving true/false applied.
336#   - Negations restricted:
337#       - no negations within or (DeMorgan's to nand)
338#       - at most one negation within and
339#
340
341def make_not(expr):
342    if isinstance(expr, TrueLiteral):
343        return FalseLiteral()
344    elif isinstance(expr, FalseLiteral):
345        return TrueLiteral()
346    elif isinstance(expr, Not):
347        return expr.operand
348    else: return Not(expr)
349
350def make_and(expr1, expr2):
351    if isinstance(expr1, TrueLiteral):
352        return expr2
353    elif isinstance(expr2, TrueLiteral):
354        return expr1
355    elif isinstance(expr1, FalseLiteral):
356        return FalseLiteral()
357    elif isinstance(expr2, FalseLiteral):
358        return FalseLiteral()
359    elif equal_exprs(expr1, expr2): return expr1
360    elif isinstance(expr1, Not):
361        if isinstance(expr2, Not):
362            return make_not(make_or(expr1.operand, expr2.operand))
363        elif equal_exprs(expr1.operand, expr2): return FalseLiteral()
364        else: return And(expr1, expr2)
365    elif isinstance(expr2, Not):
366        if equal_exprs(expr1, expr2.operand): return FalseLiteral()
367        else: return And(expr1, expr2)
368    else: return And(expr1, expr2)
369
370def make_or(expr1, expr2):
371    if isinstance(expr1, FalseLiteral):
372        return expr2
373    elif isinstance(expr2, FalseLiteral):
374        return expr1
375    elif isinstance(expr1, TrueLiteral):
376        return TrueLiteral()
377    elif isinstance(expr2, TrueLiteral):
378        return TrueLiteral()
379    elif isinstance(expr1, Not):
380        return make_not(make_and(expr1.operand, make_not(expr2)))
381    elif isinstance(expr2, Not):
382        return make_not(make_and(make_not(expr1), expr2.operand))
383    elif equal_exprs(expr1, expr2): return expr1
384    elif isinstance(expr1, And) and isinstance(expr2, And):
385        # These optimizations factor out common components that
386        # can occur when sets are formed by union (e.g., union of
387        # [a-z] and [A-Z].
388        if equal_exprs(expr1.operand1, expr2.operand1):
389            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2))
390        elif equal_exprs(expr1.operand2, expr2.operand2):
391            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1))
392        elif equal_exprs(expr1.operand1, expr2.operand2):
393            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1))
394        elif equal_exprs(expr1.operand2, expr2.operand1):
395            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2))
396        else: return Or(expr1, expr2)
397    else: return Or(expr1, expr2)
398
399def make_sel(if_expr, T_expr, F_expr):
400    if isinstance(if_expr, TrueLiteral):
401        return T_expr
402    elif isinstance(if_expr, FalseLiteral):
403        return F_expr
404    elif isinstance(T_expr, TrueLiteral):
405        # if x then T else y = x or y
406        return make_or(if_expr, F_expr) 
407    elif isinstance(T_expr, FalseLiteral):
408        # if x then F else y = not(x) and y
409        return make_and(make_not(if_expr), F_expr) 
410    elif isinstance(F_expr, FalseLiteral):
411        # if x then y else F = x and y
412        return make_and(if_expr, T_expr) 
413    elif isinstance(F_expr, TrueLiteral):
414        # if x then y else T = not(x) or y
415        return make_or(make_not(if_expr), T_expr)
416    elif equal_exprs(T_expr, F_expr):
417        return T_expr
418    else: return Sel(if_expr, T_expr, F_expr)
419
420
421def make_xor(expr1, expr2):
422    if isinstance(expr1, FalseLiteral):
423        return expr2
424    elif isinstance(expr1, FalseLiteral):
425        return expr1
426    elif isinstance(expr1, TrueLiteral):
427        return make_not(expr2)
428    elif isinstance(expr2, TrueLiteral):
429        return make_not(expr1)
430    elif isinstance(expr1, Not) and isinstance(expr2, Not):
431        return make_xor(expr1.operand, expr2.operand)
432    else: return Xor(expr1, expr2)
433
434def equal_exprs(e1, e2):
435    if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral)
436    elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral)
437    elif isinstance(e1, Var) and isinstance(e2, Var):
438        return e1.varname == e2.varname
439    elif isinstance(e1, Not) and isinstance(e2, Not):
440        return equal_exprs(e1.operand, e2.operand)
441    elif isinstance(e1, And) and isinstance(e2, And):
442        if equal_exprs(e1.operand1, e2.operand1):
443            return equal_exprs(e1.operand2, e2.operand2)
444        elif equal_exprs(e1.operand1, e2.operand2):
445            return equal_exprs(e1.operand2, e2.operand1)
446        else: return False
447    elif isinstance(e1, Or) and isinstance(e2, Or):
448        if equal_exprs(e1.operand1, e2.operand1):
449            return equal_exprs(e1.operand2, e2.operand2)
450        elif equal_exprs(e1.operand1, e2.operand2):
451            return equal_exprs(e1.operand2, e2.operand1)
452        else: return False
453    elif isinstance(e1, Xor) and isinstance(e2, Xor):
454        if equal_exprs(e1.operand1, e2.operand1):
455            return equal_exprs(e1.operand2, e2.operand2)
456        elif equal_exprs(e1.operand1, e2.operand2):
457            return equal_exprs(e1.operand2, e2.operand1)
458        else: return False
459    elif isinstance(e1, Sel) and isinstance(e2, Sel):
460        if equal_exprs(e1.sel, e2.sel):
461             if equal_exprs(e1.true_branch, e2.true_branch):
462                 return equal_exprs(e1.false_branch, e2.false_branch)
463             else: return False
464        else: return False
465
466
467#
468#
469#  Boolean Expressions for Character Class Definitions
470#
471
472def bit_var(n):
473    return 'bit[%i]' % n
474def make_bitv(n):
475    return Var(bit_var(n))
476
477# Deprecated
478def make_2bit_test(var1, var2, bit_pattern):
479  if bit_pattern == 0: 
480    return make_not(make_or(var1, var2))
481  elif bit_pattern == 1:
482    return make_and(make_not(var1), var2)
483  elif bit_pattern == 2:
484    return make_and(var1, make_not(var2))
485  else: return make_and(var1, var2)
486
487# Deprecated
488def make_8bit_test(bit_pattern):
489  return make_and(make_and(make_2bit_test(make_bitv(0), make_bitv(1), (bit_pattern >> 6) & 3),
490                           make_2bit_test(make_bitv(2), make_bitv(3), (bit_pattern >> 4) & 3)),
491                  make_and(make_2bit_test(make_bitv(4), make_bitv(5), (bit_pattern >> 2) & 3),
492                           make_2bit_test(make_bitv(6), make_bitv(7), (bit_pattern) & 3)))
493
494
495def make_bit_test(pattern, bit_count):
496    bit_terms = []
497    test_bit = 2**(bit_count - 1)
498    for i in range(0, bit_count):
499        if (pattern & test_bit) == 0:
500            bit_terms.append(make_not(make_bitv(i)))
501        else: bit_terms.append(make_bitv(i))
502        test_bit >>= 1
503    while len(bit_terms) > 1:
504        new_terms = []
505        for i in range(0, len(bit_terms)/ 2):
506            new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
507        if len(bit_terms) % 2 == 1:
508            new_terms.append(bit_terms[-1])
509        bit_terms = new_terms
510    return bit_terms[0]
511
512
513def char_test_expr(ch):
514    return make_bit_test(ord(ch), 8)
515    #return make_8bit_test(ord(ch))
516
517def GE_Range(N, n):
518    if N == 0: return TrueLiteral()
519    elif N % 2 == 0 and (n >> (N - 2)) == 0:
520        return make_or(make_or(make_bitv(8-N), make_bitv(9-N)),
521                        GE_Range(N - 2, n))
522    elif N % 2 == 0 and (n >> (N - 2)) == 3:   # >= 11xxxx
523        return make_and(make_and(make_bitv(8-N), make_bitv(9-N)),
524                        GE_Range(N - 2, n - (3 << (N-2))))
525    elif N >= 1:
526        hi_bit = n & (1 << (N-1))
527        lo_bits = n - hi_bit
528        lo_range = GE_Range(N-1, lo_bits)
529        if hi_bit == 0:
530            # If the hi_bit of n is not set, then whenever the corresponding bit
531            # is set in the target, the target will certainly be >=.  Otherwise,
532            # the value of GE_range(N-1, lo_bits) is required.
533            return make_or(make_bitv(8-N), lo_range)
534        else: 
535            # If the hi_bit of n is set, then the corresponding bit must be set
536            # in the target for >= and GE_range(N-1, lo_bits) must also be true.
537            return make_and(make_bitv(8-N), lo_range)
538
539def LE_Range(N, n):
540    # If an N-bit pattern is all ones, then it is always
541    # true that any n-bit value is LE this pattern.
542    # Handling this as a special case avoids an overflow
543    # issue with n+1 requiring more than N bits.
544    if n+1 == 2 ** N:
545        return TrueLiteral()
546    else:
547        return make_not(GE_Range(N, n+1))
548
549BadRange = Exception()
550
551
552def Make_Range(n1, n2):  # require n2 >= n1
553    diff_bits = n1 ^ n2
554    diff_count = 0
555    while diff_bits > 0:
556        diff_count += 1
557        diff_bits >>= 1
558    if n2 < n1 or diff_count > 8: raise BadRange()
559    common = make_bit_test(n1 >> diff_count, 8 - diff_count)
560    if diff_count == 0: return common
561    mask = 2**(diff_count-1) - 1
562    lo_test = GE_Range(diff_count-1, n1 & mask)
563    hi_test = LE_Range(diff_count-1, n2 & mask)
564    return make_and(common, make_sel(make_bitv(8-diff_count), hi_test, lo_test))
565
566# Deprecated   
567def Inclusive_Range(N, n1, n2):  # require n2 >= n1
568    if N == 0: return TrueLiteral()
569    elif n1 >= 2**(N-1):
570        return make_and(make_bitv(8-N), Inclusive_Range(N-1, n1 - 2**(N-1), n2 - 2**(N-1)))
571    elif n2 < 2**(N-1):
572        return make_and(make_not(make_bitv(8-N)), Inclusive_Range(N-1, n1, n2))
573    else:
574        n2_lo = n2 - 2**(N-1)
575        lo_test = GE_Range(N-1, n1)
576        hi_test = LE_Range(N-1, n2_lo)
577        # special optimization?
578        # if n2_lo + 1 == n1: return make_xor(make_bit_test(8-N), lo_test)
579        return make_sel(make_bitv(8-N), lo_test, hi_test)
580
581
582
583
584BadCharSetItem = Exception()
585
586def char_or_range_expr(charset_item):
587    if len(charset_item) == 1:
588        return char_test_expr(charset_item[0])
589    elif len(charset_item) == 3:
590        if charset_item[1] == '-' and ord(charset_item[0]) <= ord(charset_item[2]):
591             return Make_Range(ord(charset_item[0]), ord(charset_item[2]))
592             #  return Inclusive_Range(8, ord(charset_item[0]), ord(charset_item[2]))
593    print charset_item
594    raise BadCharSetItem
595
596def charset_expr(chardef):
597    e1 = char_or_range_expr(chardef.items[0])
598    for i in range(1, len(chardef.items)):
599        e1 = make_or(e1, char_or_range_expr(chardef.items[i]))
600    if chardef.complemented: return make_not(e1)
601    else: return e1
602
603
604
605#
606#
607#  Code Generation
608#
609class CodeGenObject:
610    def __init__(self, predeclared, typedecl='BitBlock '):
611        self.gensym_template = 'temp%i'
612        self.gensym_counter = 0
613        self.generated_code = []
614        self.common_expression_map = {}
615        for sym in predeclared: self.common_expression_map[sym] = sym
616        self.typedecl = typedecl
617    def add_assignment(self, varname, expr):
618        self.common_expression_map[expr] = varname
619        self.generated_code.append(%s%s = %s;\n' % (self.typedecl, varname, expr))
620    def expr_string_to_variable(self, expr_string):
621        if self.common_expression_map.has_key(expr_string): 
622            return self.common_expression_map[expr_string]
623        else:
624            self.gensym_counter += 1
625            sym = self.gensym_template % self.gensym_counter
626            self.add_assignment(sym, expr_string)
627            return sym
628    def showcode(self):
629        s = ''
630        for stmt in self.generated_code: s += stmt
631        return s
632
633
634
635def expr2simd(genobj, expr):
636    """Translate a Boolean expression into three-address Altivec code
637       using code generator object genobj.
638    """
639    if isinstance(expr, TrueLiteral): return 'simd_const_1(1)'
640    elif isinstance(expr, FalseLiteral): return 'simd_const_1(0)'
641    elif isinstance(expr, Var): return expr.varname
642    elif isinstance(expr, Not):
643       e = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand))
644       return 'simd_andc(simd_const_1(1), %s)' % (e)
645    elif isinstance(expr, Or):
646       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
647       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
648       return 'simd_or(%s, %s)' % (e1, e2)
649    elif isinstance(expr, Xor):
650       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
651       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
652       return 'simd_xor(%s, %s)' % (e1, e2)
653    elif isinstance(expr, And):
654       if isinstance(expr.operand1, Not):
655           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1.operand))
656           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
657           return 'simd_andc(%s, %s)' % (e2, e1)
658       elif isinstance(expr.operand2, Not):
659           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
660           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2.operand))
661           return 'simd_andc(%s, %s)' % (e1, e2)
662       else:
663           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
664           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
665           return 'simd_and(%s, %s)' % (e1, e2)
666    elif isinstance(expr, Sel):
667       sel = genobj.expr_string_to_variable(expr2simd(genobj, expr.sel))
668       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.true_branch))
669       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.false_branch))
670       return 'simd_if(%s, %s, %s)' %(sel, e1, e2)
671
672def chardef2simd(genobj, chardef):
673    genobj.add_assignment(chardef.name, expr2simd(genobj, charset_expr(chardef)))
674
675def chardeflist2simd(chardeflist):
676    cgo = CodeGenObject([bit_var(i) for i in range(0,8)])
677    for d in chardeflist:
678        chardef2simd(cgo, d)
679    return cgo.showcode()
680
681
682
683def expr2py(genobj, expr):
684    """Translate a Boolean expression into three-address python code
685       using code generator object genobj.
686    """
687    if isinstance(expr, TrueLiteral): return '-1'
688    elif isinstance(expr, FalseLiteral): return '0'
689    elif isinstance(expr, Var): return expr.varname
690    elif isinstance(expr, Not):
691       e = genobj.expr_string_to_variable(expr2py(genobj, expr.operand))
692       return '(~%s)' % (e)
693    elif isinstance(expr, Or):
694       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
695       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
696       return '(%s | %s)' % (e1, e2)
697    elif isinstance(expr, Xor):
698       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
699       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
700       return '(%s ^ %s)' % (e1, e2)
701    elif isinstance(expr, And):
702       if isinstance(expr.operand1, Not):
703           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1.operand))
704           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
705           return '(%s &~ %s)' % (e2, e1)
706       elif isinstance(expr.operand2, Not):
707           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
708           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2.operand))
709           return '(%s &~ %s)' % (e1, e2)
710       else:
711           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
712           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
713           return '(%s & %s)' % (e1, e2)
714    elif isinstance(expr, Sel):
715       sel = genobj.expr_string_to_variable(expr2py(genobj, expr.sel))
716       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.true_branch))
717       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.false_branch))
718       return '((%s & %s)|(~(%s) & %s))' %(sel, e1, sel, e2)
719
720def chardef2py(genobj, chardef):
721    genobj.add_assignment(chardef.name, expr2py(genobj, charset_expr(chardef)))
722
723
724def py_chardefmap(chardeflist):
725    defs = ["'%s' : %s" % (d.name,d.name) for d in chardeflist]
726    return  '{%s}' % string.join(defs, ',\n\t')
727
728def chardeflist2py(chardeflist):
729    cgo = CodeGenObject([bit_var(i) for i in range(0,8)],'')
730    for d in chardeflist:
731        chardef2py(cgo, d) 
732    return cgo.showcode()# + "  return "+ py_chardefmap(chardeflist) + "\n"
733
734
735def code_gen_for_transcode(transcode_tbl_h, transcode_tbl_l):
736  cgo = CodeGenObject([bit_var(i) for i in range(0,8)])
737  xor_tbl_l = [transcode_tbl_l[code] ^ code for code in range(256)]
738  code_gen_for_transcode_8bit(cgo, "x16h", transcode_tbl_h)
739  code_gen_for_transcode_8bit(cgo, "x16l", xor_tbl_l)
740  return cgo.showcode()
741
742def code_gen_for_transcode_8bit(cgo, pfx, tbl):
743  for bit in range(8):
744    bit_mask = 256 >> bit
745    in_run = False
746    first_expr_found = False
747    bit_expr = FalseLiteral()
748    for code in range(256):
749      if tbl[code] & bit_mask != 0:
750        if not in_run:
751          in_run = True
752          run_start = code
753      else:
754        if in_run:
755          if run_start == code-1:
756            e1 = char_test_expr(chr(code - 1))
757          else:
758            e1 = Make_Range(run_start, code - 1)
759          if first_expr_found:
760            bit_expr = make_or(bit_expr, e1)
761          else:
762            first_expr_found = True
763            bit_expr = e1
764    if first_expr_found:
765      cgo.add_assignment("%s[%i]" % (pfx, bit), expr2simd(cgo, bit_expr))
766
767# Work with tables from
768# /home/cameron/glibc-2.3.5/localedata/charmaps/
769
770charmap_line_RE = re.compile("<U([0-9A-F][0-9A-F])([0-9A-Z][0-9A-Z])>\s+/x([0-9a-f][0-9a-f])\s")
771
772def read_char_map(file):
773  f = open(file)
774  lines = f.readlines()
775  matches = [charmap_line_RE.match(l) for l in lines]
776  u16hi = [ord(binascii.unhexlify(m.group(1))) for m in matches if m]
777  u16lo = [ord(binascii.unhexlify(m.group(2))) for m in matches if m]
778  codes = [ord(binascii.unhexlify(m.group(3))) for m in matches if m]
779  codes_OK = [c for c in range(256) if codes[c] == c]
780  if len(codes_OK) != 256:
781    print("Code map failure reading %s" % file)
782  return (u16hi, u16lo)
783
784import codecs
785def ascii2ebcdic_chardeflist(defs):
786        encoder = codecs.getencoder('cp037')
787        return [xlate_chardef(d, encoder) for d in defs]
788
789def xlate_char_or_range(charset_item, encoder):
790    if len(charset_item) == 1:
791        return encoder(charset_item[0])
792    elif len(charset_item) == 3:
793        if charset_item[1] == '-' and ord(charset_item[0]) <= ord(charset_item[2]):
794             return Make_Range(ord(charset_item[0]), ord(charset_item[2]))
795             #  return Inclusive_Range(8, ord(charset_item[0]), ord(charset_item[2]))
796    print charset_item
797    raise BadCharSetItem
798       
799def xlate_chardef(chardef, encoder):
800  if isinstance(chardef, CharDef):
801    return CharDef(chardef.name, encoder(chardef.items[0])[0], chardef.complemented)
802  else:
803    cdefs = []
804    for item in chardef.items:
805        if len(item) == 1: cdefs.append(encoder(item)[0])
806        elif len(item) == 3:
807          for v in range(ord(item[0]), ord(item[-1])+1):
808            cdefs.append(encoder(chr(v))[0])
809        else: raise BadCharSetItem
810    return CharSetDef(chardef.name, cdefs, chardef.complemented)
811
812import charset_input_parser
813def input_chardef(filename):
814    """
815    Returns a list of declared CharSet from the declarations in the input file
816    """
817    defs = []
818    charset_declaration_list = charset_input_parser.processCharsetInput(filename)
819   
820    for charset_declaration in charset_declaration_list:
821        defs.append(CharSetDef (charset_declaration[0], charset_declaration[1]))
822
823    return defs
824                                 
825import sys
826def main():
827    if len(sys.argv) == 2:
828        # if the specified argument is not in the DefinitionSet, then assume that it's a filename
829        if sys.argv[1] not in DefinitionSet:
830            #define the characters in the list
831            defs = input_chardef(sys.argv[1])
832            #print chardeflist2simd(defs)
833            print chardeflist2py(defs)
834        else:
835            #print chardeflist2simd(DefinitionSet[sys.argv[1]])
836            print chardeflist2py(DefinitionSet[sys.argv[1]])
837    elif len(sys.argv) == 3 and sys.argv[2] == 'EBCDIC':
838        defs = ascii2ebcdic_chardeflist(DefinitionSet[sys.argv[1]])
839        print chardeflist2simd(defs)
840    else:
841        print "Usage python charset_compiler.py <name> [EBCDIC]"
842        for k in DefinitionSet.keys(): print k
843
844if __name__ == "__main__": main()
Note: See TracBrowser for help on using the repository browser.