source: proto/charsetcompiler/charset_compiler.py @ 676

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

Add JSON character class definitions.

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