source: proto/charsetcompiler/charset_compiler.py @ 699

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

Add JSON Value and String follow sets.

File size: 30.6 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                               
205                                # String
206                                CharDef('Lex.DQuote','\"'),
207                                CharDef('Lex.RSolidus','\\'),
208                                #CharDef('Lex.Solidus','/'),
209                                #CharDef('Lex.b','b'),
210                                #CharDef('Lex.f','f'),
211                                #CharDef('Lex.n','n'),
212                                #CharDef('Lex.r','r'),
213                                #CharDef('Lex.t','t'),
214                                CharDef('Lex.u','u'),
215                                CharSetDef('Lex.Escape', ['\"','\\','/','b','f','n','r','t','u']),
216                                CharSetDef('Lex.HexDigit', ['0-9','a-f','A-F']),
217                                                               
218                                # WS
219                                CharSetDef('Lex.WS', ['\x0D', '\x0A', '\x09', ' ']),
220                               
221                                # true
222                                CharDef('Lex.t','t'),
223                                CharDef('Lex.r','r'),
224                                #CharDef('Lex.u','\"'),
225                                CharDef('Lex.e','e'),
226                               
227                                # false
228                                CharDef('Lex.f','f'),
229                                CharDef('Lex.a','a'),
230                                CharDef('Lex.l','l'),
231                                CharDef('Lex.s','s'),
232                                #CharDef('Lex.e','\"'),
233                               
234                                # null
235                                CharDef('Lex.n','n'),
236                                #CharDef('Lex.u','\"'),
237                                #CharDef('Lex.l','\"'),
238                                #CharDef('Lex.l','\"')                         
239                               
240                                # Follow Sets
241                                CharSetDef('Lex.ValueFollowSet',[',','}',']']),
242                                CharSetDef('Lex.StringFollowSet',[',','}',']',':'])                             
243]
244
245
246DefinitionSet['JSON'] = DefinitionSet['UTF8'] + DefinitionSet['JSON_Control'] + DefinitionSet['JSON_Lexical'] 
247
248#
249# Following definitions for the parabix2 unbounded bitstream prototype
250#
251# First all the special characters in the XML delimiters.
252
253xml_marks =    [CharDef('lex.RefStart', '&'),
254                CharDef('lex.Semicolon', ';'),
255                CharDef('lex.LAngle', '<'),
256                CharDef('lex.RAngle', '>'),
257                CharDef('lex.LBracket', '['),
258                CharDef('lex.RBracket', ']'),
259                CharDef('lex.Exclam', '!'),
260                CharDef('lex.QMark', '?'),
261                CharDef('lex.Hyphen', '-'),
262                CharDef('lex.Equals', "="),
263                CharDef('lex.SQuote', "'"),
264                CharDef('lex.DQuote', '"'),
265                CharDef('lex.Slash', '/'),
266                CharDef('lex.Hash', '#'),
267                CharDef('lex.x', 'x'),
268                CharDef('lex.Colon', ':')
269                ]
270#
271# NameFollow: all characters that may legally follow an XML name, plus
272# any others that may not be used in names.
273# 1. All non-WS characters that may legally follow an XML name.
274namefollow = [CharSetDef('lex.NameFollow', [';', '=', '/', '>', '?', ')', '[', '|', '?', '*', '+', ','])]
275#
276# NameScan: all ASCII characters that may legally occur in a Name,
277# plus all UTF-8 prefix and suffix bytes.
278namescan = [CharSetDef('lex.NameScan', ['_', '-', '.', '0-:', 'A-Z', 'a-z', '\x80-\xFF'])]
279
280#
281namelex = [CharSetDef('lex.ASCII_name_start', ['_', ':', 'A-Z', 'a-z']),
282           CharSetDef('lex.ASCII_name_char', ['_', '-', '.', '0-:', 'A-Z', 'a-z']),
283           CharSetDef('lex.NameScan', ['_', '-', '.', '0-:', 'A-Z', 'a-z', '\x80-\xFF'])]
284
285#
286UTF8_BOM_bytes = [CharDef('u8.xEF', '\xEF'), CharDef('u8.xBF', '\xBF'), CharDef('u8.xBE', '\xBE')]
287
288DefinitionSet['parabix2'] = (xml_marks + namelex + DefinitionSet['WS_Control_10']
289                             + DefinitionSet['Digit_and_Hex'] + DefinitionSet['UTF8'] + UTF8_BOM_bytes)
290
291DefinitionSet['CSV'] = [CharDef('BackSlash', '\\'),
292                        CharDef('DQuote', '"'),
293                        CharDef('SQuote', '\''),
294                        CharDef('CR', '\x0D'),
295                        CharDef('LF', '\x0A'),
296                        CharDef('Comma', ','),
297                        CharDef('HT', '\x09'),
298                        CharDef('Period', '.')]
299
300
301#
302# Symbolic Representations of Boolean Expressions
303#
304
305class BoolExpr:
306   """The BoolExpr class and its subclasses provide a symbolic
307      representation of Boolean expressions.
308   """
309   pass
310
311class Var(BoolExpr):
312    def __init__(self, varname):
313        self.varname = varname
314    def show(self): return 'Var("' + self.varname + '")'
315
316class TrueLiteral(BoolExpr):
317    def __init__(self):
318        self.value = True
319    def show(self): return 'T'
320
321class FalseLiteral(BoolExpr):
322    def __init__(self):
323        self.value = False
324    def show(self): return 'F'
325
326class Not(BoolExpr):
327    def __init__(self, expr):
328        self.operand = expr
329    def show(self): return 'Not(%s)' % (self.operand.show())
330
331class And(BoolExpr):
332    def __init__(self, expr1, expr2):
333        self.operand1 = expr1
334        self.operand2 = expr2
335    def show(self): return 'And(%s, %s)' % (self.operand1.show(), self.operand2.show())
336
337class Or(BoolExpr):
338    def __init__(self, expr1, expr2):
339        self.operand1 = expr1
340        self.operand2 = expr2
341    def show(self): return 'Or(%s, %s)' % (self.operand1.show(), self.operand2.show())
342
343class Xor(BoolExpr):
344    def __init__(self, expr1, expr2):
345        self.operand1 = expr1
346        self.operand2 = expr2
347    def show(self): return 'Xor(%s, %s)' % (self.operand1.show(), self.operand2.show())
348
349class Sel(BoolExpr):
350    def __init__(self, expr1, expr2, expr3):
351        self.sel = expr1
352        self.true_branch = expr2
353        self.false_branch = expr3
354    def show(self): return 'Sel(%s, %s, %s)' % (self.sel.show(), self.true_branch.show(), self.false_branch.show())
355
356
357#
358# Optimizing Constructors for Boolean Expressions
359# - Maintaining Assembler Instruction Form:
360#   - All boolean algebraic rules involving true/false applied.
361#   - Negations restricted:
362#       - no negations within or (DeMorgan's to nand)
363#       - at most one negation within and
364#
365
366def make_not(expr):
367    if isinstance(expr, TrueLiteral):
368        return FalseLiteral()
369    elif isinstance(expr, FalseLiteral):
370        return TrueLiteral()
371    elif isinstance(expr, Not):
372        return expr.operand
373    else: return Not(expr)
374
375def make_and(expr1, expr2):
376    if isinstance(expr1, TrueLiteral):
377        return expr2
378    elif isinstance(expr2, TrueLiteral):
379        return expr1
380    elif isinstance(expr1, FalseLiteral):
381        return FalseLiteral()
382    elif isinstance(expr2, FalseLiteral):
383        return FalseLiteral()
384    elif equal_exprs(expr1, expr2): return expr1
385    elif isinstance(expr1, Not):
386        if isinstance(expr2, Not):
387            return make_not(make_or(expr1.operand, expr2.operand))
388        elif equal_exprs(expr1.operand, expr2): return FalseLiteral()
389        else: return And(expr1, expr2)
390    elif isinstance(expr2, Not):
391        if equal_exprs(expr1, expr2.operand): return FalseLiteral()
392        else: return And(expr1, expr2)
393    else: return And(expr1, expr2)
394
395def make_or(expr1, expr2):
396    if isinstance(expr1, FalseLiteral):
397        return expr2
398    elif isinstance(expr2, FalseLiteral):
399        return expr1
400    elif isinstance(expr1, TrueLiteral):
401        return TrueLiteral()
402    elif isinstance(expr2, TrueLiteral):
403        return TrueLiteral()
404    elif isinstance(expr1, Not):
405        return make_not(make_and(expr1.operand, make_not(expr2)))
406    elif isinstance(expr2, Not):
407        return make_not(make_and(make_not(expr1), expr2.operand))
408    elif equal_exprs(expr1, expr2): return expr1
409    elif isinstance(expr1, And) and isinstance(expr2, And):
410        # These optimizations factor out common components that
411        # can occur when sets are formed by union (e.g., union of
412        # [a-z] and [A-Z].
413        if equal_exprs(expr1.operand1, expr2.operand1):
414            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2))
415        elif equal_exprs(expr1.operand2, expr2.operand2):
416            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1))
417        elif equal_exprs(expr1.operand1, expr2.operand2):
418            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1))
419        elif equal_exprs(expr1.operand2, expr2.operand1):
420            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2))
421        else: return Or(expr1, expr2)
422    else: return Or(expr1, expr2)
423
424def make_sel(if_expr, T_expr, F_expr):
425    if isinstance(if_expr, TrueLiteral):
426        return T_expr
427    elif isinstance(if_expr, FalseLiteral):
428        return F_expr
429    elif isinstance(T_expr, TrueLiteral):
430        # if x then T else y = x or y
431        return make_or(if_expr, F_expr) 
432    elif isinstance(T_expr, FalseLiteral):
433        # if x then F else y = not(x) and y
434        return make_and(make_not(if_expr), F_expr) 
435    elif isinstance(F_expr, FalseLiteral):
436        # if x then y else F = x and y
437        return make_and(if_expr, T_expr) 
438    elif isinstance(F_expr, TrueLiteral):
439        # if x then y else T = not(x) or y
440        return make_or(make_not(if_expr), T_expr)
441    elif equal_exprs(T_expr, F_expr):
442        return T_expr
443    else: return Sel(if_expr, T_expr, F_expr)
444
445
446def make_xor(expr1, expr2):
447    if isinstance(expr1, FalseLiteral):
448        return expr2
449    elif isinstance(expr1, FalseLiteral):
450        return expr1
451    elif isinstance(expr1, TrueLiteral):
452        return make_not(expr2)
453    elif isinstance(expr2, TrueLiteral):
454        return make_not(expr1)
455    elif isinstance(expr1, Not) and isinstance(expr2, Not):
456        return make_xor(expr1.operand, expr2.operand)
457    else: return Xor(expr1, expr2)
458
459def equal_exprs(e1, e2):
460    if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral)
461    elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral)
462    elif isinstance(e1, Var) and isinstance(e2, Var):
463        return e1.varname == e2.varname
464    elif isinstance(e1, Not) and isinstance(e2, Not):
465        return equal_exprs(e1.operand, e2.operand)
466    elif isinstance(e1, And) and isinstance(e2, And):
467        if equal_exprs(e1.operand1, e2.operand1):
468            return equal_exprs(e1.operand2, e2.operand2)
469        elif equal_exprs(e1.operand1, e2.operand2):
470            return equal_exprs(e1.operand2, e2.operand1)
471        else: return False
472    elif isinstance(e1, Or) and isinstance(e2, Or):
473        if equal_exprs(e1.operand1, e2.operand1):
474            return equal_exprs(e1.operand2, e2.operand2)
475        elif equal_exprs(e1.operand1, e2.operand2):
476            return equal_exprs(e1.operand2, e2.operand1)
477        else: return False
478    elif isinstance(e1, Xor) and isinstance(e2, Xor):
479        if equal_exprs(e1.operand1, e2.operand1):
480            return equal_exprs(e1.operand2, e2.operand2)
481        elif equal_exprs(e1.operand1, e2.operand2):
482            return equal_exprs(e1.operand2, e2.operand1)
483        else: return False
484    elif isinstance(e1, Sel) and isinstance(e2, Sel):
485        if equal_exprs(e1.sel, e2.sel):
486             if equal_exprs(e1.true_branch, e2.true_branch):
487                 return equal_exprs(e1.false_branch, e2.false_branch)
488             else: return False
489        else: return False
490
491
492#
493#
494#  Boolean Expressions for Character Class Definitions
495#
496
497def bit_var(n):
498    return 'bit[%i]' % n
499def make_bitv(n):
500    return Var(bit_var(n))
501
502# Deprecated
503def make_2bit_test(var1, var2, bit_pattern):
504  if bit_pattern == 0: 
505    return make_not(make_or(var1, var2))
506  elif bit_pattern == 1:
507    return make_and(make_not(var1), var2)
508  elif bit_pattern == 2:
509    return make_and(var1, make_not(var2))
510  else: return make_and(var1, var2)
511
512# Deprecated
513def make_8bit_test(bit_pattern):
514  return make_and(make_and(make_2bit_test(make_bitv(0), make_bitv(1), (bit_pattern >> 6) & 3),
515                           make_2bit_test(make_bitv(2), make_bitv(3), (bit_pattern >> 4) & 3)),
516                  make_and(make_2bit_test(make_bitv(4), make_bitv(5), (bit_pattern >> 2) & 3),
517                           make_2bit_test(make_bitv(6), make_bitv(7), (bit_pattern) & 3)))
518
519
520def make_bit_test(pattern, bit_count):
521    bit_terms = []
522    test_bit = 2**(bit_count - 1)
523    for i in range(0, bit_count):
524        if (pattern & test_bit) == 0:
525            bit_terms.append(make_not(make_bitv(i)))
526        else: bit_terms.append(make_bitv(i))
527        test_bit >>= 1
528    while len(bit_terms) > 1:
529        new_terms = []
530        for i in range(0, len(bit_terms)/ 2):
531            new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
532        if len(bit_terms) % 2 == 1:
533            new_terms.append(bit_terms[-1])
534        bit_terms = new_terms
535    return bit_terms[0]
536
537
538def char_test_expr(ch):
539    return make_bit_test(ord(ch), 8)
540    #return make_8bit_test(ord(ch))
541
542def GE_Range(N, n):
543    if N == 0: return TrueLiteral()
544    elif N % 2 == 0 and (n >> (N - 2)) == 0:
545        return make_or(make_or(make_bitv(8-N), make_bitv(9-N)),
546                        GE_Range(N - 2, n))
547    elif N % 2 == 0 and (n >> (N - 2)) == 3:   # >= 11xxxx
548        return make_and(make_and(make_bitv(8-N), make_bitv(9-N)),
549                        GE_Range(N - 2, n - (3 << (N-2))))
550    elif N >= 1:
551        hi_bit = n & (1 << (N-1))
552        lo_bits = n - hi_bit
553        lo_range = GE_Range(N-1, lo_bits)
554        if hi_bit == 0:
555            # If the hi_bit of n is not set, then whenever the corresponding bit
556            # is set in the target, the target will certainly be >=.  Otherwise,
557            # the value of GE_range(N-1, lo_bits) is required.
558            return make_or(make_bitv(8-N), lo_range)
559        else: 
560            # If the hi_bit of n is set, then the corresponding bit must be set
561            # in the target for >= and GE_range(N-1, lo_bits) must also be true.
562            return make_and(make_bitv(8-N), lo_range)
563
564def LE_Range(N, n):
565    # If an N-bit pattern is all ones, then it is always
566    # true that any n-bit value is LE this pattern.
567    # Handling this as a special case avoids an overflow
568    # issue with n+1 requiring more than N bits.
569    if n+1 == 2 ** N:
570        return TrueLiteral()
571    else:
572        return make_not(GE_Range(N, n+1))
573
574BadRange = Exception()
575
576
577def Make_Range(n1, n2):  # require n2 >= n1
578    diff_bits = n1 ^ n2
579    diff_count = 0
580    while diff_bits > 0:
581        diff_count += 1
582        diff_bits >>= 1
583    if n2 < n1 or diff_count > 8: raise BadRange()
584    common = make_bit_test(n1 >> diff_count, 8 - diff_count)
585    if diff_count == 0: return common
586    mask = 2**(diff_count-1) - 1
587    lo_test = GE_Range(diff_count-1, n1 & mask)
588    hi_test = LE_Range(diff_count-1, n2 & mask)
589    return make_and(common, make_sel(make_bitv(8-diff_count), hi_test, lo_test))
590
591# Deprecated   
592def Inclusive_Range(N, n1, n2):  # require n2 >= n1
593    if N == 0: return TrueLiteral()
594    elif n1 >= 2**(N-1):
595        return make_and(make_bitv(8-N), Inclusive_Range(N-1, n1 - 2**(N-1), n2 - 2**(N-1)))
596    elif n2 < 2**(N-1):
597        return make_and(make_not(make_bitv(8-N)), Inclusive_Range(N-1, n1, n2))
598    else:
599        n2_lo = n2 - 2**(N-1)
600        lo_test = GE_Range(N-1, n1)
601        hi_test = LE_Range(N-1, n2_lo)
602        # special optimization?
603        # if n2_lo + 1 == n1: return make_xor(make_bit_test(8-N), lo_test)
604        return make_sel(make_bitv(8-N), lo_test, hi_test)
605
606
607
608
609BadCharSetItem = Exception()
610
611def char_or_range_expr(charset_item):
612    if len(charset_item) == 1:
613        return char_test_expr(charset_item[0])
614    elif len(charset_item) == 3:
615        if charset_item[1] == '-' and ord(charset_item[0]) <= ord(charset_item[2]):
616             return Make_Range(ord(charset_item[0]), ord(charset_item[2]))
617             #  return Inclusive_Range(8, ord(charset_item[0]), ord(charset_item[2]))
618    print charset_item
619    raise BadCharSetItem
620
621def charset_expr(chardef):
622    e1 = char_or_range_expr(chardef.items[0])
623    for i in range(1, len(chardef.items)):
624        e1 = make_or(e1, char_or_range_expr(chardef.items[i]))
625    if chardef.complemented: return make_not(e1)
626    else: return e1
627
628
629
630#
631#
632#  Code Generation
633#
634class CodeGenObject:
635    def __init__(self, predeclared, typedecl='BitBlock '):
636        self.gensym_template = 'temp%i'
637        self.gensym_counter = 0
638        self.generated_code = []
639        self.common_expression_map = {}
640        for sym in predeclared: self.common_expression_map[sym] = sym
641        self.typedecl = typedecl
642    def add_assignment(self, varname, expr):
643        self.common_expression_map[expr] = varname
644        self.generated_code.append(%s%s = %s;\n' % (self.typedecl, varname, expr))
645    def expr_string_to_variable(self, expr_string):
646        if self.common_expression_map.has_key(expr_string): 
647            return self.common_expression_map[expr_string]
648        else:
649            self.gensym_counter += 1
650            sym = self.gensym_template % self.gensym_counter
651            self.add_assignment(sym, expr_string)
652            return sym
653    def showcode(self):
654        s = ''
655        for stmt in self.generated_code: s += stmt
656        return s
657
658
659
660def expr2simd(genobj, expr):
661    """Translate a Boolean expression into three-address Altivec code
662       using code generator object genobj.
663    """
664    if isinstance(expr, TrueLiteral): return 'simd_const_1(1)'
665    elif isinstance(expr, FalseLiteral): return 'simd_const_1(0)'
666    elif isinstance(expr, Var): return expr.varname
667    elif isinstance(expr, Not):
668       e = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand))
669       return 'simd_andc(simd_const_1(1), %s)' % (e)
670    elif isinstance(expr, Or):
671       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
672       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
673       return 'simd_or(%s, %s)' % (e1, e2)
674    elif isinstance(expr, Xor):
675       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
676       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
677       return 'simd_xor(%s, %s)' % (e1, e2)
678    elif isinstance(expr, And):
679       if isinstance(expr.operand1, Not):
680           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1.operand))
681           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
682           return 'simd_andc(%s, %s)' % (e2, e1)
683       elif isinstance(expr.operand2, Not):
684           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
685           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2.operand))
686           return 'simd_andc(%s, %s)' % (e1, e2)
687       else:
688           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
689           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
690           return 'simd_and(%s, %s)' % (e1, e2)
691    elif isinstance(expr, Sel):
692       sel = genobj.expr_string_to_variable(expr2simd(genobj, expr.sel))
693       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.true_branch))
694       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.false_branch))
695       return 'simd_if(%s, %s, %s)' %(sel, e1, e2)
696
697def chardef2simd(genobj, chardef):
698    genobj.add_assignment(chardef.name, expr2simd(genobj, charset_expr(chardef)))
699
700def chardeflist2simd(chardeflist):
701    cgo = CodeGenObject([bit_var(i) for i in range(0,8)])
702    for d in chardeflist:
703        chardef2simd(cgo, d)
704    return cgo.showcode()
705
706
707
708def expr2py(genobj, expr):
709    """Translate a Boolean expression into three-address python code
710       using code generator object genobj.
711    """
712    if isinstance(expr, TrueLiteral): return '-1'
713    elif isinstance(expr, FalseLiteral): return '0'
714    elif isinstance(expr, Var): return expr.varname
715    elif isinstance(expr, Not):
716       e = genobj.expr_string_to_variable(expr2py(genobj, expr.operand))
717       return '(~%s)' % (e)
718    elif isinstance(expr, Or):
719       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
720       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
721       return '(%s | %s)' % (e1, e2)
722    elif isinstance(expr, Xor):
723       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
724       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
725       return '(%s ^ %s)' % (e1, e2)
726    elif isinstance(expr, And):
727       if isinstance(expr.operand1, Not):
728           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1.operand))
729           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
730           return '(%s &~ %s)' % (e2, e1)
731       elif isinstance(expr.operand2, Not):
732           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
733           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2.operand))
734           return '(%s &~ %s)' % (e1, e2)
735       else:
736           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
737           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
738           return '(%s & %s)' % (e1, e2)
739    elif isinstance(expr, Sel):
740       sel = genobj.expr_string_to_variable(expr2py(genobj, expr.sel))
741       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.true_branch))
742       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.false_branch))
743       return '((%s & %s)|(~(%s) & %s))' %(sel, e1, sel, e2)
744
745def chardef2py(genobj, chardef):
746    genobj.add_assignment(chardef.name, expr2py(genobj, charset_expr(chardef)))
747
748
749def py_chardefmap(chardeflist):
750    defs = ["'%s' : %s" % (d.name,d.name) for d in chardeflist]
751    return  '{%s}' % string.join(defs, ',\n\t')
752
753def chardeflist2py(chardeflist):
754    cgo = CodeGenObject([bit_var(i) for i in range(0,8)],'')
755    for d in chardeflist:
756        chardef2py(cgo, d) 
757    return cgo.showcode()# + "  return "+ py_chardefmap(chardeflist) + "\n"
758
759
760def code_gen_for_transcode(transcode_tbl_h, transcode_tbl_l):
761  cgo = CodeGenObject([bit_var(i) for i in range(0,8)])
762  xor_tbl_l = [transcode_tbl_l[code] ^ code for code in range(256)]
763  code_gen_for_transcode_8bit(cgo, "x16h", transcode_tbl_h)
764  code_gen_for_transcode_8bit(cgo, "x16l", xor_tbl_l)
765  return cgo.showcode()
766
767def code_gen_for_transcode_8bit(cgo, pfx, tbl):
768  for bit in range(8):
769    bit_mask = 256 >> bit
770    in_run = False
771    first_expr_found = False
772    bit_expr = FalseLiteral()
773    for code in range(256):
774      if tbl[code] & bit_mask != 0:
775        if not in_run:
776          in_run = True
777          run_start = code
778      else:
779        if in_run:
780          if run_start == code-1:
781            e1 = char_test_expr(chr(code - 1))
782          else:
783            e1 = Make_Range(run_start, code - 1)
784          if first_expr_found:
785            bit_expr = make_or(bit_expr, e1)
786          else:
787            first_expr_found = True
788            bit_expr = e1
789    if first_expr_found:
790      cgo.add_assignment("%s[%i]" % (pfx, bit), expr2simd(cgo, bit_expr))
791
792# Work with tables from
793# /home/cameron/glibc-2.3.5/localedata/charmaps/
794
795charmap_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")
796
797def read_char_map(file):
798  f = open(file)
799  lines = f.readlines()
800  matches = [charmap_line_RE.match(l) for l in lines]
801  u16hi = [ord(binascii.unhexlify(m.group(1))) for m in matches if m]
802  u16lo = [ord(binascii.unhexlify(m.group(2))) for m in matches if m]
803  codes = [ord(binascii.unhexlify(m.group(3))) for m in matches if m]
804  codes_OK = [c for c in range(256) if codes[c] == c]
805  if len(codes_OK) != 256:
806    print("Code map failure reading %s" % file)
807  return (u16hi, u16lo)
808
809import codecs
810def ascii2ebcdic_chardeflist(defs):
811        encoder = codecs.getencoder('cp037')
812        return [xlate_chardef(d, encoder) for d in defs]
813
814def xlate_char_or_range(charset_item, encoder):
815    if len(charset_item) == 1:
816        return encoder(charset_item[0])
817    elif len(charset_item) == 3:
818        if charset_item[1] == '-' and ord(charset_item[0]) <= ord(charset_item[2]):
819             return Make_Range(ord(charset_item[0]), ord(charset_item[2]))
820             #  return Inclusive_Range(8, ord(charset_item[0]), ord(charset_item[2]))
821    print charset_item
822    raise BadCharSetItem
823       
824def xlate_chardef(chardef, encoder):
825  if isinstance(chardef, CharDef):
826    return CharDef(chardef.name, encoder(chardef.items[0])[0], chardef.complemented)
827  else:
828    cdefs = []
829    for item in chardef.items:
830        if len(item) == 1: cdefs.append(encoder(item)[0])
831        elif len(item) == 3:
832          for v in range(ord(item[0]), ord(item[-1])+1):
833            cdefs.append(encoder(chr(v))[0])
834        else: raise BadCharSetItem
835    return CharSetDef(chardef.name, cdefs, chardef.complemented)
836
837import charset_input_parser
838def input_chardef(filename):
839    """
840    Returns a list of declared CharSet from the declarations in the input file
841    """
842    defs = []
843    charset_declaration_list = charset_input_parser.processCharsetInput(filename)
844   
845    for charset_declaration in charset_declaration_list:
846        defs.append(CharSetDef (charset_declaration[0], charset_declaration[1]))
847
848    return defs
849                                 
850import sys
851def main():
852    if len(sys.argv) == 2:
853        # if the specified argument is not in the DefinitionSet, then assume that it's a filename
854        if sys.argv[1] not in DefinitionSet:
855            #define the characters in the list
856            defs = input_chardef(sys.argv[1])
857            #print chardeflist2simd(defs)
858            print chardeflist2py(defs)
859        else:
860            #print chardeflist2simd(DefinitionSet[sys.argv[1]])
861            print chardeflist2py(DefinitionSet[sys.argv[1]])
862    elif len(sys.argv) == 3 and sys.argv[2] == 'EBCDIC':
863        defs = ascii2ebcdic_chardeflist(DefinitionSet[sys.argv[1]])
864        print chardeflist2simd(defs)
865    else:
866        print "Usage python charset_compiler.py <name> [EBCDIC]"
867        for k in DefinitionSet.keys(): print k
868
869if __name__ == "__main__": main()
Note: See TracBrowser for help on using the repository browser.