# HG changeset patch # User Ryoma SHINYA # Date 1278088836 -32400 # Node ID a28f87d353bbacd7195ec8309d573bc8adbc5a6d # Parent 8f0b1267623852c42cfa440024f699b041bc088b simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1") diff -r 8f0b12676238 -r a28f87d353bb code/graph/makegraph.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/code/graph/makegraph.sh Sat Jul 03 01:40:36 2010 +0900 @@ -0,0 +1,8 @@ +#!/bin/sh +neato -Txdot $1.dot | dot2tex -ftikz --tikzedgelabels -tmath --styleonly > $1.tex +platex $1.tex +platex $1.tex +dvips $1.dvi +dvipdf $1.dvi +convert $1.pdf $1.png +rm -f $1.dvi $1.tex $1.dvi $1.aux $1.ps $1.log diff -r 8f0b12676238 -r a28f87d353bb code/graph/makepdf.sh --- a/code/graph/makepdf.sh Fri Jul 02 03:27:58 2010 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,7 +0,0 @@ -#!/bin/sh -neato -Txdot $1.dot | dot2tex -ftikz --tikzedgelabels -tmath --styleonly > $1.tex -platex $1.tex -platex $1.tex -dvips $1.dvi -dvipdf $1.dvi -rm -f $1.dvi $1.tex $1.dvi $1.aux $1.ps $1.log diff -r 8f0b12676238 -r a28f87d353bb code/graph/regdfa.dot --- a/code/graph/regdfa.dot Fri Jul 02 03:27:58 2010 +0900 +++ b/code/graph/regdfa.dot Sat Jul 03 01:40:36 2010 +0900 @@ -4,15 +4,15 @@ [draw=blue!50,very thick,shape=circle, fill=blue!20]"; node [style="state"]; edge [lblstyle="fill=blue!20", style="arrows=->", topath="bend left"]; - s13567 [style="state, initial"] - s8 [style="state, accepting"] - s13567 -> s12357 [texlbl="A"] - s13567 -> s8 [texlbl="C"] - s13567 -> s13457 [texlbl="B"] - s13457 -> s12357 [texlbl="A"] - s13457 -> s8 [texlbl="C"] - s13457 -> s13457 [texlbl="B"] - s12357 -> s12357 [texlbl="A"] - s12357 -> s8 [texlbl="C"] - s12357 -> s13457 [texlbl="B"] + s1 [style="state, initial"] + s0 [style="state, accepting"] + s1 -> s3 [texlbl="A"] + s1 -> s0 [texlbl="C"] + s1 -> s2 [texlbl="B"] + s2 -> s3 [texlbl="A"] + s2 -> s0 [texlbl="C"] + s2 -> s2 [texlbl="B"] + s3 -> s3 [texlbl="A"] + s3 -> s0 [texlbl="C"] + s3 -> s2 [texlbl="B"] } diff -r 8f0b12676238 -r a28f87d353bb code/graph/regdfa.pdf Binary file code/graph/regdfa.pdf has changed diff -r 8f0b12676238 -r a28f87d353bb src/cTranslator.py --- a/src/cTranslator.py Fri Jul 02 03:27:58 2010 +0900 +++ b/src/cTranslator.py Sat Jul 03 01:40:36 2010 +0900 @@ -1,4 +1,4 @@ -#!/usr/bin/env python +#!/Usr/bin/env python from dfareg import Regexp, CallGraph from translator import Translator @@ -17,21 +17,25 @@ >>> CTranslator(string, nfacg).translate() """ def __init__(self, regexp, cg): - self.regexp = regexp - self.cg = cg - self.stream = None + Translator.__init__(self, regexp, cg) self.funType = 'void ' self.callType = '' self.breakStatement = '\t\t\tbreak;' self.debug = False + if self.cg.type is "DFA": + self.dfaStateNameHash = self.createDFAStateNameHash() + + def modifyStateName(self, stateName): + if self.cg.type is "DFA": + return "state_"+self.dfaStateNameHash[stateName] + else: + return "state_"+stateName def translateFromCallGraph(self): - def prefix(string): - return "state_"+string # self.emit C-source code self.emit("#include \n") for k in self.cg.map.iterkeys(): - self.emit(self.funType + prefix(k) + "(char* s);\n") + self.emit(self.funType + self.modifyStateName(k) + "(char* s);\n") self.emit(self.funType + 'accept(char* s);\n') self.emit(self.funType + 'reject(char* s);\n') self.emit(""" @@ -40,14 +44,14 @@ \tputs(\"number of state: %d\"); \tprintf(\"string: %%s\\n\", argv[1]); \t%s%s(argv[1]); -""" % (self.regexp, len(self.cg.states), self.callType, prefix(self.cg.start))) +""" % (self.regexp, len(self.cg.states), self.callType, self.modifyStateName(self.cg.start))) if self.cg.type is "NFA" : self.emit("\treject(argv[1]);\n") self.emit(""" \treturn 0; }\n\n""") for k, v in self.cg.map.iteritems(): - self.emit(self.funType + prefix(k) + "(char* s) {\n") + self.emit(self.funType + self.modifyStateName(k) + "(char* s) {\n") if self.debug: self.emit("\tprintf(\"state: %s, input: %%s\\n\", s);\n" % (k)) if self.cg.type is "NFA": sLocal = "s_local" @@ -55,7 +59,7 @@ # epsilon-transition for ss in (ss for i,ss in v.iteritems() if i == ''): for s in ss: - self.emit("\t%s%s(%s);\n" % (self.callType, prefix(s), sLocal)) + self.emit("\t%s%s(%s);\n" % (self.callType, self.modifyStateName(s), sLocal)) else: sLocal = "s" @@ -65,7 +69,7 @@ if input != '': self.emit("\t\tcase '%s': \n" % (input)) for nextState in nextStates: - self.emit("\t\t\t%s%s(%s);\n" % (self.callType, prefix(nextState), sLocal)) + self.emit("\t\t\t%s%s(%s);\n" % (self.callType, self.modifyStateName(nextState), sLocal)) if self.breakStatement != '' : self.emit(self.breakStatement+'\n') if k in self.cg.accepts : diff -r 8f0b12676238 -r a28f87d353bb src/cbcTranslator.py --- a/src/cbcTranslator.py Fri Jul 02 03:27:58 2010 +0900 +++ b/src/cbcTranslator.py Sat Jul 03 01:40:36 2010 +0900 @@ -12,17 +12,17 @@ >>> string = \"(A|B)*C\" >>> reg = Regexp(string) >>> dfacg = CallGraph(reg.dfa) - >>> CbCTranslator(string, dfacg).translate() + >>> ct = CbCTranslator(string, dfacg) + >>> ct.translate() + >>> ct.debug = True + >>> ct.translate() """ def __init__(self, regexp, cg): if cg.type is "NFA": raise CbCTranslateExeption("can't translate CbC from NFA") - self.regexp = regexp - self.cg = cg - self.stream = None + CTranslator.__init__(self, regexp, cg) self.funType = '__code ' self.callType = 'goto ' self.breakStatement = '' - self.debug = False def test(): import doctest diff -r 8f0b12676238 -r a28f87d353bb src/dotTranslator.py --- a/src/dotTranslator.py Fri Jul 02 03:27:58 2010 +0900 +++ b/src/dotTranslator.py Sat Jul 03 01:40:36 2010 +0900 @@ -17,9 +17,18 @@ >>> DotTranslator(string, dfacg).translate() >>> DotTranslator(string, nfacg).translate() """ + def __init__(self, regexp, cg): + Translator.__init__(self, regexp, cg) + if self.cg.type is "DFA": + self.dfaStateNameHash = self.createDFAStateNameHash() + + def modifyStateName(self, stateName): + if self.cg.type is "DFA": + return "s"+self.dfaStateNameHash[stateName] + else: + return "s"+stateName + def translateFromCallGraph(self): - def prefix(string): - return "s"+re.sub("_", "", string) self.emit(''' digraph G{ \td2tdocpreamble = "\\usetikzlibrary{automata}"; @@ -29,16 +38,16 @@ \tedge [lblstyle="fill=blue!20", style="arrows=->", topath="bend left"]; ''') - self.emit("\t%s [style=\"state, initial\"]\n" % (prefix(self.cg.start))) + self.emit("\t%s [style=\"state, initial\"]\n" % (self.modifyStateName(self.cg.start))) for accept in self.cg.accepts: - self.emit("\t%s [style=\"state, accepting\"]\n" % (prefix(accept))) + self.emit("\t%s [style=\"state, accepting\"]\n" % (self.modifyStateName(accept))) for curState, trans in self.cg.map.iteritems(): for input, nextStates in trans.iteritems(): if input is "" : input = "$\\varepsilon$" for nextState in nextStates: self.emit("\t%s -> %s [texlbl=\"%s\"]\n" - % (prefix(curState), prefix(nextState), input)) + % (self.modifyStateName(curState), self.modifyStateName(nextState), input)) self.emit("}") diff -r 8f0b12676238 -r a28f87d353bb src/translator.py --- a/src/translator.py Fri Jul 02 03:27:58 2010 +0900 +++ b/src/translator.py Sat Jul 03 01:40:36 2010 +0900 @@ -11,6 +11,16 @@ def emit(self, string): self.stream.write(string) + def createDFAStateNameHash(self): + dfaStateNameHash = dict() + states = list(self.cg.states) + for index in range(len(states)): + dfaStateNameHash[states[index]] = str(index) + return dfaStateNameHash + + def modifyStateName(self, stateName): + return stateName + def translateFromCallGraph(self): pass