source: proto/REgen/REbuild.py @ 2996

Last change on this file since 2996 was 892, checked in by cameron, 9 years ago

REgen: regexp generator for ABNF

File size: 20.1 KB
Line 
1#
2#
3# REbuild - A package for building regular expressions.
4#
5#
6#  Robert D. Cameron, May 5, 2003
7#
8import string, re, binascii;
9
10std_hex_escape_re = re.compile(r'[\x00-\x1f\x7f]')
11
12def hex_escape(ch):
13    r"Return the hex-escape representation (\xhh) of a character."
14    return '\\x' + binascii.b2a_hex(ch)
15
16nonprintable_re = re.compile(r'[\x00-\x1f\x7f-\xff]')
17
18def hex_escape_nonprintable(string_val):
19    r"Replace nonprintable characters with escaped (\xhh) characters."
20    escaper = lambda match: hex_escape(match.group(0))
21    return nonprintable_re.sub(escaper, string_val)
22
23class StringConstructionSyntax:
24    """A StringConstruction class encodes the syntactic conventions for
25    constructing string values in a particular programming language or
26    system.   The StringConstructionSyntax class is both the virtual
27    class for all such (sub)classes, as well as the particular class
28    encoding suitable conventions for Python.
29    """
30    string_special_re = re.compile(r'([\"])')
31
32    def mk_literal(self, string_val):
33        lit1 = self.string_special_re.sub(r"\\\1", string_val)
34        return '"' + hex_escape_nonprintable(lit1) + '"'
35
36    def mk_var(self, varname):
37        return re.compile('[^A-Za-z0-9_]').sub('_', varname)
38
39    def literal_cat_SE(self, string_val, SE):
40        lit1 = self.string_special_re.sub(r"\\\1", string_val)
41        lit1 = hex_escape_nonprintable(lit1)
42        if SE[0] == '"':
43            return '"' + lit1 + SE[1:]
44        else: return '"' + lit1 + '" + ' + SE
45
46    def SE_cat_literal(self, SE, string_val):
47        lit1 = self.string_special_re.sub(r"\\\1", string_val)
48        lit1 = hex_escape_nonprintable(lit1)
49        if SE[-1] == '"': return SE[:-1] + lit1 + '"'
50        else: return SE + ' + "' + lit1 + '"'
51
52    def join(self, SE1, SE2):
53        if SE1[-1] == '"' and SE2[0] == '"':
54            return SE1[:-1] + SE2[1:]
55        else: return SE1 + " + " + SE2
56
57    def mk_assignment(self, var, SE):
58        return var + " = " + SE + '\n'
59
60
61class RegularExpressionSyntax:
62    """A RegularExpressionSyntax subclass encodes the syntactic conventions for
63    constructing regular expression values in a particular programming language
64    or system.   The RegularExpressionSyntax class is both the virtual
65    class for all such subclasses, as well as the particular subclass
66    encoding suitable conventions for Python.
67    """
68
69    def __init__(self, string_syntax_object):
70        self.sgen = string_syntax_object
71    metacharacter_re = re.compile(r"([][(){}|*+?.$^\\])")
72    def mk_literal(self, literal_string):
73        escaped = self.metacharacter_re.sub(r"\\\1", literal_string)
74        return self.sgen.mk_literal(escaped)
75    setmetacharacter_re = re.compile(r"([-\\\]^])")
76    range_min_length = 6
77    def char_subrange(self, firstch, lastch):
78        f = self.setmetacharacter_re.sub(r"\\\1", firstch)
79        l = self.setmetacharacter_re.sub(r"\\\1", lastch)
80        return f + '-' + l           
81    def mk_charset(self, charset_string, complemented = False):
82        if len(charset_string) == 0:
83            if complemented: return self.sgen.mk_literal('.')
84            else: return self.sgen.mk_literal('[]')
85        elif len(charset_string) == 1 and not complemented:
86            return self.sgen.mk_literal(charset_string)
87        range_start_index = 0
88        if complemented: set_string = '[^'
89        else: set_string = '['
90        for i in range(1, len(charset_string)):
91            if ord(charset_string[i]) != ord(charset_string[i-1]) + 1:
92                if i - range_start_index < self.range_min_length:
93                    range_chars = charset_string[range_start_index:i]
94                    set_string += self.setmetacharacter_re.sub(r"\\\1", range_chars)
95                else:
96                    set_string += self.char_subrange(charset_string[range_start_index],
97                                                     charset_string[i-1])
98                range_start_index = i
99        if len(charset_string) - range_start_index < self.range_min_length:
100            range_chars = charset_string[range_start_index:]
101            set_string += self.setmetacharacter_re.sub(r"\\\1", range_chars)
102        else:
103            set_string += self.char_subrange(charset_string[range_start_index],
104                                             charset_string[-1])
105        return self.sgen.mk_literal(set_string + ']')
106    def mk_range(self, first, last, complemented = False):
107        if complemented: set_start = '[^'
108        else: set_start = '['
109        return self.sgen.mk_literal(set_start + self.char_subrange(first, last) + ']')
110    def mk_var(self, varname):
111        return self.sgen.mk_var(varname)
112
113    def concatenation(self, RE_SE1, RE_SE2):
114        return self.sgen.join(RE_SE1, RE_SE2)
115    def alternation(self, RE_SE1, RE_SE2):
116        return self.sgen.join(RE_SE1, self.sgen.literal_cat_SE('|', RE_SE2))
117    def repetition(self, RE_SE, mincount, bound):
118        """Build a repetition expression denoting at least mincount
119        occurrences of the given RE, with a specified bound.  The value
120        of bound may be -1 to denote unbounded repetition, or a positive
121        value to denote an upper limit on the number of occurrences.
122        """
123        if bound == -1:  # unbounded repetition
124            if mincount == 0: suffix = '*'
125            elif mincount == 1: suffix = '+'
126            else: suffix = '{' + str(mincount) + ',}'
127        elif mincount == 0 and bound == 1: suffix = '?'
128        elif mincount == bound: suffix = '{' + str(mincount) + '}'
129        else: suffix = '{' + str(mincount) + ',' + str(bound) + '}'
130        return self.sgen.SE_cat_literal(RE_SE, suffix)
131    def group(self, RE_SE):
132        return self.sgen.literal_cat_SE('(?:', self.sgen.SE_cat_literal(RE_SE, ')'))
133    def selection_group(self, RE_SE):
134        return self.sgen.literal_cat_SE('(', self.sgen.SE_cat_literal(RE_SE, ')'))
135    def definition(self, varname, RE_SE):
136        return self.sgen.mk_assignment(varname, RE_SE)
137       
138                                       
139
140
141
142
143
144class RE:
145    """The RE class and its subclasses provide an abstract syntax
146    for regular expressions.
147    """
148    pass
149
150class Var(RE):
151    def __init__(self, varname):
152        self.varname = varname
153    def show(self): return 'Var("' + self.varname + '")'
154
155class Literal(RE):
156    def __init__(self, string):
157        self.literal_val = string
158    def show(self): return 'Literal("' + self.literal_val + '")'
159
160def anycase_Literal(str):
161    subexps = []
162    current = ''
163    for c in str:
164        if c in string.ascii_letters:
165            if current != '': subexps.append(Literal(current))
166            subexps.append(CharSet(c + string.swapcase(c)))
167            current = ''
168        else: current += c
169    if current != '': subexps.append(Literal(current))
170    if len(subexps) > 1: return JoinList(subexps)
171    else: return subexps[0]
172
173
174class CharSet(RE):
175    def __init__(self, char_list):
176        self.char_list = char_list
177        self.complemented = False
178    def show(self): return 'CharSet("' + self.char_list + '")'
179
180class NegSet(CharSet):
181    def __init__(self, char_list):
182        self.char_list = char_list
183        self.complemented = True
184    def show(self): return 'NegSet("' + self.char_list + '")'
185
186class CharRange(RE):
187    def __init__(self, first, last, complemented=False):
188        self.first_char = first
189        self.last_char = last
190        self.complemented = complemented
191    def show(self):
192        return 'CharRange(%s,%s)' % (self.first_char, self.last_char)
193
194class JoinList(RE):
195    def __init__(self, RE_list):
196        self.RE_list = RE_list
197    def show(self):
198        return 'JoinList([' + string.join(map(lambda r: r.show(), self.RE_list), ',') + '])'
199   
200class AltList(RE):
201    def __init__(self, RE_list):
202        self.RE_list = RE_list
203    def show(self):
204        return 'AltList([' + string.join(map(lambda r: r.show(), self.RE_list), ',') + '])'
205
206class Repeat(RE):
207    def __init__(self, re, mincount, bound):
208        self.repeated_RE = re
209        self.mincount = mincount
210        self.bound = bound
211    def show(self):
212        return 'Repeat(%s,%i,%i)' % (self.repeated_RE.show(), self.mincount, self.bound)
213
214class Opt(Repeat):
215    def __init__(self, re):
216        self.repeated_RE = re
217        self.mincount = 0
218        self.bound = 1
219    def show(self): return 'Opt(' + self.repeated_RE.show() + ')'
220
221class Star(Repeat):
222    def __init__(self, re):
223        self.repeated_RE = re
224        self.mincount = 0
225        self.bound = -1
226    def show(self): return 'Star(' + self.repeated_RE.show() + ')'
227
228class Plus(Repeat):
229    def __init__(self, re):
230        self.repeated_RE = re
231        self.mincount = 1
232        self.bound = -1
233    def show(self): return 'Plus(' + self.repeated_RE.show() + ')'
234
235#
236class Group(RE):
237    def __init__(self, re):
238        self.inner_RE = re
239    def show(self): return 'Group(' + self.inner_RE.show() + ')'
240
241class Rule(RE):
242    def __init__(self, name, re):
243        self.defined_name = name
244        self.defining_RE = re
245    def show(self):
246        return 'Rule(' + self.defined_name.show() + ', ' + self.defining_RE.show() + ')'
247
248def get_defn(grmr, NT):
249    for rule in grmr:
250        if rule.defined_name.varname == NT: return rule.defining_RE
251    return None
252   
253def is_joinable(regexp, grmr):
254    if regexp == None: return False
255    elif isinstance(regexp, Var):
256        return is_joinable(get_defn(grmr, regexp.varname), grmr)
257    else:
258        return not isinstance(regexp, AltList)
259
260def is_repeatable(regexp, grmr):
261    if regexp == None: return False
262    elif isinstance(regexp, Var):
263        return is_repeatable(get_defn(grmr, regexp.varname), grmr)
264    elif isinstance(regexp, Literal):
265        return len(regexp.literal_val) == 1
266    elif isinstance(regexp, CharSet): return True
267    elif isinstance(regexp, CharRange): return True
268    else: return isinstance(regexp, Group)
269
270def gen(regexp, grmr, syntax):
271    if isinstance(regexp, Var):
272        return syntax.mk_var(regexp.varname)
273    elif isinstance(regexp, Literal):
274        return syntax.mk_literal(regexp.literal_val)
275    elif isinstance(regexp, CharSet):
276        return syntax.mk_charset(regexp.char_list, regexp.complemented)
277    elif isinstance(regexp, CharRange):
278        return syntax.mk_range(regexp.first_char, regexp.last_char, regexp.complemented)
279    elif isinstance(regexp, JoinList):
280        generated_list = []
281        for x in regexp.RE_list:
282            if is_joinable(x, grmr):
283                generated_list.append(gen(x, grmr, syntax))
284            else:
285                generated_list.append(gen(Group(x), grmr, syntax))
286        return reduce(syntax.concatenation, generated_list)
287    elif isinstance(regexp, AltList):
288        generated_list = map(lambda x: gen(x, grmr, syntax), regexp.RE_list)
289        return reduce(syntax.alternation, generated_list)
290    elif isinstance(regexp, Repeat):
291        repeated = regexp.repeated_RE
292        if not is_repeatable(repeated, grmr):
293#            print repeated.show()
294            repeated = Group(repeated)
295        return syntax.repetition(gen(repeated, grmr, syntax),
296                                 regexp.mincount, regexp.bound)
297    elif isinstance(regexp, Group):
298        return syntax.group(gen(regexp.inner_RE, grmr, syntax))
299
300
301def grammar_gen(grmr, syntax):
302    generated = ''
303    for rule in grmr:
304        generated += syntax.definition(gen(rule.defined_name, grmr, syntax),
305                                       gen(rule.defining_RE, grmr, syntax))
306    return generated
307   
308def simplify(regexp, grmr):
309    if isinstance(regexp, Var): return regexp
310    elif isinstance(regexp, Literal): return regexp
311    elif isinstance(regexp, CharSet): return regexp
312    elif isinstance(regexp, CharRange): return regexp
313    elif isinstance(regexp, JoinList):
314        return JoinList(map(lambda e: simplify(e, grmr), regexp.RE_list))
315    elif isinstance(regexp, AltList):
316        simplified_alts = map(lambda e: simplify(e, grmr), regexp.RE_list)
317        singleton_list = filter(lambda a: reduces_to_charset(a, grmr), simplified_alts)
318        if len(singleton_list) > 0:
319            nonsingleton_list = filter(lambda x: not reduces_to_charset(x, grmr), simplified_alts)
320            singleton_list = map(lambda a: canonical_charset(a, grmr), singleton_list)
321            merged = reduce(union_charsets, singleton_list)
322            if len(nonsingleton_list) == 0: return merged
323            else: return AltList([merged] + nonsingleton_list)
324        elif len(simplified_alts) == 1: return simplified_alts[0]
325        else: return AltList(simplified_alts)
326#        singleton_list = filter(is_singleton, simplified_alts)
327#        if len(singleton_list) > 0:
328#            merged = reduce(merge_singletons, singleton_list)
329#            nonsingleton_list = filter(lambda x: not is_singleton(x), simplified_alts)
330#            return AltList([merged] + nonsingleton_list)
331#        else: return AltList(simplified_alts)
332    elif isinstance(regexp, Repeat):
333        repeated = simplify(regexp.repeated_RE, grmr)
334        if isinstance(repeated, Group) and is_repeatable(repeated.inner_RE, grmr):
335            repeated = repeated.inner_RE
336        if regexp.mincount == 0 and regexp.bound == -1:
337            return Star(repeated)
338        elif regexp.mincount == 1 and regexp.bound == -1:
339            return Plus(repeated)
340        elif regexp.mincount == 0 and regexp.bound == 1:
341            return Opt(repeated)
342        else: return Repeat(repeated, regexp.mincount, regexp.bound)
343    elif isinstance(regexp, Group):
344        return Group(simplify(regexp.inner_RE, grmr))
345
346#
347# Auxiliary functions for simplification of alternations involving
348# singletons (single characters and character sets).
349#
350def is_singleton(re):
351    if isinstance(re, Literal): return len(re.literal_val) == 1
352    else: return isinstance(re, CharSet)
353
354def merge_singletons(re1, re2):
355    resultset = ''
356    if isinstance(re1, Literal): resultset += re1.literal_val
357    elif isinstance(re1, CharSet): resultset += re1.char_list
358    if isinstance(re2, Literal): resultset += re2.literal_val
359    elif isinstance(re2, CharSet): resultset += re2.char_list
360    return CharSet(resultset)
361   
362def singleton_alt(singleton, other):
363    if is_singleton(other):
364        return merge_singletons(singleton, other)
365    elif isinstance(other, Alt) and is_singleton(other.RE1):
366        return Alt(merge_singletons(singleton, other.RE1), other.RE2)
367    else: return Alt(singleton, other)
368   
369pySyntax = RegularExpressionSyntax(StringConstructionSyntax());
370     
371
372def merge_NT_lists(NT_list1, NT_list2):
373    merged = NT_list1[:]
374    for NT in NT_list2:
375        if NT not in merged: merged.append(NT)
376    return merged
377
378def subtract_NT_lists(NT_list1, NT_list2):
379    diff = []
380    for NT in NT_list1:
381        if NT not in NT_list2: diff.append(NT)
382    return diff
383
384def RE_nonterminals(regexp):
385    if isinstance(regexp, Var): return [regexp.varname]
386    elif isinstance(regexp, Literal): return []
387    elif isinstance(regexp, CharSet): return []
388    elif isinstance(regexp, CharRange): return []
389    elif isinstance(regexp, JoinList) or isinstance(regexp, AltList):
390        return reduce(merge_NT_lists,
391               map(RE_nonterminals, regexp.RE_list))
392    elif isinstance(regexp, Repeat):
393        return RE_nonterminals(regexp.repeated_RE)
394    elif isinstance(regexp, Group):
395        return RE_nonterminals(regexp.inner_RE)
396
397def rule_nonterminals_in_list(rule, NTlist):
398    for NT in RE_nonterminals(rule.defining_RE):
399        if not NT in NTlist: return False
400    return True
401
402
403
404def partition(predicate, list):
405    return (filter(predicate, list),
406            filter(lambda x: not predicate(x), list))
407   
408def regular_subgrammar(grmr):
409    r"""Given a grammar, return the regular subgrammar, in
410    define-before-use order."""
411    NTlist = []
412    subrules = []
413    def rule_nonterminals_in_NTlist(rule):
414        for NT in RE_nonterminals(rule.defining_RE):
415            if not NT in NTlist: return False
416        return True
417    found, pending = partition(rule_nonterminals_in_NTlist, grmr)
418    while found != []:
419        subrules += found
420        NTlist += map(lambda r: r.defined_name.varname, found)
421        found, pending = partition(rule_nonterminals_in_NTlist, pending)
422    return subrules
423           
424           
425def recursive_subgrammar(grmr):
426    r"""Given a grammar, return the recursive subgrammar."""
427    NTlist = []
428    subrules = []
429    def rule_nonterminals_in_NTlist(rule):
430        for NT in RE_nonterminals(rule.defining_RE):
431            if not NT in NTlist: return False
432        return True
433    found, pending = partition(rule_nonterminals_in_NTlist, grmr)
434    while found != []:
435        subrules += found
436        NTlist += map(lambda r: r.defined_name.varname, found)
437        found, pending = partition(rule_nonterminals_in_NTlist, pending)
438    return pending
439           
440def reduces_to_charset(regexp, reg_grmr):
441    r"""Determine whether a regexp reduces to a charset.
442    May only be applied to rules in the regular subgrammar -
443    infinite recursion otherwise."""
444    if regexp == None: return False
445    elif isinstance(regexp, Var):
446        defn = get_defn(reg_grmr, regexp.varname)
447        if defn == None: return False
448        else: return reduces_to_charset(defn, reg_grmr)
449    elif isinstance(regexp, Literal):
450        return len(regexp.literal_val) == 1
451    elif isinstance(regexp, CharSet): return True
452    elif isinstance(regexp, CharRange): return True
453    elif isinstance(regexp, Group):
454        return reduces_to_charset(regexp.inner_RE, reg_grmr)
455    elif isinstance(regexp, AltList):
456        for alt in regexp.RE_list:
457            if reduces_to_charset(alt, reg_grmr): continue
458            else: return False
459        return True
460    else: return False
461
462def canonical_charset(regexp, grmr):
463    r"""Determine the canonical CharSet of a regular expression.
464    >>> gen(canonical_charset(NegSet('cab'), []), [], pySyntax)
465    '"[^abc]"'
466    >>> s = AltList([NegSet('cab'), CharSet('dcef')])
467    >>> gen(canonical_charset(s, []), [], pySyntax)
468    '"[^ab]"'
469    >>>
470    >>> gen(canonical_charset(AltList([Literal("d"), CharRange('e', 'x'), Literal('-')]), []), [], pySyntax)
471    '"[\\-d-x]"'
472    >>>
473    """
474    if isinstance(regexp, Var):
475        return canonical_charset(get_defn(grmr, regexp.varname), grmr)
476    elif isinstance(regexp, Literal):
477        return CharSet(regexp.literal_val)
478    elif isinstance(regexp, CharSet):
479        result_chars = ''
480        for c in range(0, 256):
481            if chr(c) in regexp.char_list:
482                result_chars += chr(c)
483        if regexp.complemented: return NegSet(result_chars)
484        else: return CharSet(result_chars)
485    elif isinstance(regexp, CharRange):
486        result_chars = ''
487        for c in range(ord(regexp.first_char), ord(regexp.last_char)+1):
488            result_chars += chr(c)
489        if regexp.complemented: return NegSet(result_chars)
490        else: return CharSet(result_chars)
491    elif isinstance(regexp, Group):
492        return canonical_charset(regexp.inner_RE, grmr)
493    elif isinstance(regexp, AltList):
494        sets = map(lambda alt: canonical_charset(alt, grmr), regexp.RE_list)
495        return reduce(union_charsets, sets)
496   
497   
498def union_charsets(set1, set2):
499    result_chars = ''
500    if set1.complemented:
501        if set2.complemented:
502            for c in set1.char_list:
503                if c in set2.char_list: result_chars += c
504            return NegSet(result_chars)
505        else:
506            for c in set1.char_list:
507                if c not in set2.char_list: result_chars += c
508            return NegSet(result_chars)
509    elif set2.complemented: return union_charsets(set2, set1)
510    else:
511        i1 = 0
512        i2 = 0
513        while i1 < len(set1.char_list) and i2 < len(set2.char_list):
514            if set1.char_list[i1] < set2.char_list[i2]:
515                result_chars += set1.char_list[i1]
516                i1 += 1
517            else:
518                result_chars += set2.char_list[i2]
519                i2 += 1
520        if i1 < len(set1.char_list):
521            result_chars += set1.char_list[i1:]
522        elif i2 < len(set2.char_list):
523            result_chars += set2.char_list[i2:]
524        return CharSet(result_chars)
525
526
527def simplify_rule(rule, grmr):
528    return Rule(rule.defined_name, simplify(rule.defining_RE, grmr))
529
530def simplify_grammar(grmr):
531    reg_grmr = regular_subgrammar(grmr)
532    return map(lambda r: simplify_rule(r, reg_grmr), grmr)
533
534
535
536def _test():
537    import doctest, REbuild
538    return doctest.testmod(REbuild)
539
540if __name__ == "__main__":
541    _test()
542
Note: See TracBrowser for help on using the repository browser.