# HG changeset patch # User Ryoma SHINYA # Date 1292162959 -32400 # Node ID e327e93aeb3ab92780f9d3fbda3a23de3a85c60b # Parent 4d498b002de5a3bea3eb2d82da48ace6abc0ef5b remove callgraph and use Transition. diff -r 4d498b002de5 -r e327e93aeb3a pyrect/converter.py --- a/pyrect/converter.py Sun Dec 12 23:04:31 2010 +0900 +++ b/pyrect/converter.py Sun Dec 12 23:09:19 2010 +0900 @@ -1,7 +1,7 @@ #!/usr/bin/env python import sys -from pyrect.regexp import Regexp, CallGraph, DFATranslator, SuffixDFATranslator, SuffixTrieTranslator +from pyrect.regexp import Regexp, DFATranslator, SuffixDFATranslator, SuffixTrieTranslator from pyrect.regexp.nfa import SuffixNFA from pyrect.translator import * from optparse import OptionParser @@ -36,17 +36,14 @@ elif opts.snfa: fa = "SDFA" reg.nfa = SuffixNFA(reg.nfa) - reg.nfacg = CallGraph(reg.nfa) elif opts.sdfa: fa = "DFA" sdfa = SuffixDFATranslator().translate(reg.dfa) reg.dfa = sdfa - reg.dfacg = CallGraph(sdfa) elif opts.trie: fa = "DFA" trie = SuffixTrieTranslator().translate(reg.dfa) reg.dfa = trie - reg.dfacg = CallGraph(trie) else: fa = "DFA" diff -r 4d498b002de5 -r e327e93aeb3a pyrect/translator/c_translator.py --- a/pyrect/translator/c_translator.py Sun Dec 12 23:04:31 2010 +0900 +++ b/pyrect/translator/c_translator.py Sun Dec 12 23:09:19 2010 +0900 @@ -1,6 +1,6 @@ #!/Usr/bin/env python -from pyrect.regexp import Regexp +from pyrect.regexp import Regexp, DFA from pyrect.regexp.ast import * from translator import Translator @@ -14,10 +14,9 @@ >>> CTranslator(reg).translate() >>> CTranslator(reg).translate() """ - def __init__(self, regexp, fa="DFA"): + def __init__(self, regexp): Translator.__init__(self, regexp) - if fa == "DFA": - self.cg = regexp.dfacg + self.fa = regexp.dfa self.debug = False self.eols = (Character('\0'), Character('\n'), Character('\r')) self.special_rule = (Range, BegLine, MBCharacter) @@ -32,12 +31,12 @@ def emit_accept_state(self): self.emiti("int accept(unsigned char* s) {") self.emit( "return 1;") - self.emitd("}", 2) + self.demit("}", 2) def emit_reject_state(self): self.emiti("int reject(unsigned char* s) {") self.emit( "return 0;") - self.emitd("}", 2) + self.demit("}", 2) def emit_skip(self): self.emiti("const char skip_tbl[256] = {") @@ -50,20 +49,20 @@ self.emit("2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,") self.emit("3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,6,6,1,1,") self.emit("};") - self.emitd("#define SKIP(s) ((s) + skip_tbl[*(unsigned char *)s])", 2) + self.demit("#define SKIP(s) ((s) + skip_tbl[*(unsigned char *)s])", 2) def emit_driver(self): self.emiti("int main(int argc, unsigned char* argv[]) {") self.emit( 'buf = argv[1];') self.emit( 'puts("regexp: %s");' % self.regexp.regexp) - self.emit( 'puts("number of state: %d");' % len(self.cg.states)) + self.emit( 'puts("number of state: %d");' % len(self.fa.states)) self.emit( r'printf("string: %s\n", argv[1]);') - self.emit0( "if (%s(argv[1]))" % self.state_name(self.cg.start)) + self.emit0( "if (%s(argv[1]))" % self.state_name(self.fa.start)) self.emit( r'printf("accept: regexp matches string. \n\n");') self.emit0( "else ") self.emit( r'printf("reject: regexp not matches string. \n\n");') self.emit( "return 0;") - self.emitd("}", 2) + self.demit("}", 2) def emit_strcmp1(self, string, next): cmp_stmt = list() @@ -98,11 +97,10 @@ self.emit(" && ") self.emiti(")") self.emit ("return %s(s+%d);" % (self.state_name(next), offset)) - self.emitd() + self.demit() def emit_strcmp2(self, string, next): - self.indent() - self.emit ( "ls = s;") + self.iemit ( "ls = s;") # emit -> if (cmp_stmt && cmp_stmt && ...) self.emit0("if (") self.emit ("*ls++ == '%c'" % string[0]) @@ -110,13 +108,13 @@ self.emit0(" && *ls++ == '%c'" % char) self.emiti(")") self.emit ("return %s(ls);" % self.state_name(next)) - self.emitd() + self.demit() def emit_strcmp3(self, string, next): self.emit('static unsigned char* string = \"%s\";' % string) self.emiti("if (memcmp(string, s, %d) == 0)" % len(string)) self.emit("return %s(s+%d);" % (self.state_name(next), len(string))) - self.emitd() + self.demit() def emit_switch(self, case, default=None): if not case: @@ -128,14 +126,14 @@ self.trans_stmt.emit(case, self.state_name(next_)) if default: self.emit("default: return %s(s);" % default) - self.emitd("}") + self.demit("}") def emit_state(self, cur_state, transition): self.emiti("int %s(unsigned char* s) {" % self.state_name(cur_state)) if self.debug: self.emit(r'printf("state: %s, input: %%s\n", s);' % cur_state) - if self.cg.type == "NFA": + if type(self.fa) == DFA: default = None if '' in transition: epsilon_transition = transition.pop('') @@ -150,7 +148,7 @@ elif type(input_) is AnyChar: default = self.state_name(transition.pop(input_)) - if cur_state in self.cg.accepts: + if cur_state in self.fa.accepts: for eol in self.eols: transition[eol] = "accept" elif default != "reject": @@ -159,11 +157,11 @@ self.emit_switch(transition, default) - self.emitd("}", 2) + self.demit("}", 2) def emit_initialization(self): self.emit("#include ") - for state in self.cg.map.iterkeys(): + for state in self.fa.transition.iterkeys(): self.emit("int %s(unsigned char* s);" % self.state_name(state)) self.emit('int accept(unsigned char* s);') self.emit('int reject(unsigned char* s);') @@ -175,7 +173,7 @@ self.emit_initialization() self.emit_driver() - for cur_state, transition in self.cg.map.iteritems(): + for cur_state, transition in self.fa.transition.iteritems(): self.emit_state(cur_state, transition) self.emit_accept_state() diff -r 4d498b002de5 -r e327e93aeb3a pyrect/translator/dot_translator.py --- a/pyrect/translator/dot_translator.py Sun Dec 12 23:04:31 2010 +0900 +++ b/pyrect/translator/dot_translator.py Sun Dec 12 23:09:19 2010 +0900 @@ -4,7 +4,7 @@ from translator import Translator from pyrect.regexp import Regexp -from pyrect.regexp.dfa import SuffixDFA +from pyrect.regexp.dfa import SuffixDFA, DFA class DotTranslator(Translator): """ @@ -20,42 +20,42 @@ def __init__(self, regexp, fa="DFA"): Translator.__init__(self, regexp) if fa == "NFA": - self.cg = regexp.nfacg + self.fa = regexp.nfa else: - self.cg = regexp.dfacg + self.fa = regexp.dfa self.fill_color = "lightsteelblue1" self.frame_color = "navyblue" def state_name(self, name): - return "q"+name + return "q"+str(name) def emit_from_callgraph(self): color = "fillcolor=%s, style=filled, color = %s" % (self.fill_color, self.frame_color) - self.emit('digraph G{'), self.indent() + self.emiti('digraph G{') self.emit( 'rankdir=LR') self.emit( 'regex [shape=plaintext, label="%s"]' % self.regexp.regexp) # emit transition - for state in self.cg.states: - if state in self.cg.accepts: + for state in self.fa.states: + if state in self.fa.accepts: self.emit("%s [shape=doublecircle, %s]" % (self.state_name(state), color)) else: self.emit("%s [shape=circle, %s]" % (self.state_name(state), color)) # edge to start state self.emit("start [shape=point]") - self.emit("start -> %s" % self.state_name(self.cg.start), 2) + self.emit("start -> %s" % self.state_name(self.fa.start), 2) - for cur_state, trans in self.cg.map.iteritems(): + for cur_state, trans in self.fa.transition.iteritems(): for input, next_states in trans.iteritems(): - if self.cg.type == "DFA": + if type(self.fa) == DFA: next_states = [next_states] for next_state in next_states: self.emit("%s -> %s [label=\"%s\"]" % (self.state_name(cur_state), self.state_name(next_state), input)) - if type(self.regexp.dfa) == SuffixDFA: - sdfa = self.regexp.dfa + if type(self.fa) == SuffixDFA: + sdfa = self.fa pdfa = sdfa.pdfa color = "fillcolor=\"#99cc99\", style=filled, color = \"#000000\"" arrowstyle = "arrowhead = odot, dir = both" @@ -80,7 +80,7 @@ self.emit("%s_accept [shape=box,label=\"%s\", %s, %s]" % (self.state_name(str(s)), "\\n".join(msg), color, arrowstyle)) self.emit("%s -> %s_accept [label=\"acceptable\"]" % (self.state_name(str(s)), (self.state_name(str(s))))) - self.emitd("}", 2) + self.demit("}", 2) def test(): import doctest diff -r 4d498b002de5 -r e327e93aeb3a pyrect/translator/grep_translator.py --- a/pyrect/translator/grep_translator.py Sun Dec 12 23:04:31 2010 +0900 +++ b/pyrect/translator/grep_translator.py Sun Dec 12 23:09:19 2010 +0900 @@ -22,7 +22,7 @@ BASE_DIR = os.path.dirname(os.path.abspath(__file__)) def __init__(self, regexp): - CTranslator.__init__(self, regexp, fa="DFA") + CTranslator.__init__(self, regexp) self.__bufsize = 1024 * 1024 self.thread_dfa = 1 self.thread_line = 1 @@ -70,7 +70,7 @@ self.filter = False if not self.filter_only: - for state in self.cg.map.iterkeys(): + for state in self.cg.transition.iterkeys(): self.emit("void %s(%s);" % (self.state_name(state), self.interface)) self.emit()