Mercurial > hg > Members > shinya > pyrect
changeset 6:168d60b03e2c
add dotTranslator(Translator), that can translate from DFA or NFA into Dot-file(Dot is graph generater using tex.)
author | ryoma <shinya@firefly.cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 02 Jul 2010 02:43:28 +0900 (2010-07-01) |
parents | 11fba907c0af |
children | 8f0b12676238 |
files | code/graph/makepdf.sh code/graph/makepng.sh code/graph/reg.dot code/graph/regdfa.dot code/graph/regdfa.dot.pdf code/graph/regdfa.pdf code/graph/regnfa.dot code/graph/regnfa.pdf src/cTranslator.py src/cbcTranslator.py src/dotTranslator.py src/translator.py |
diffstat | 12 files changed, 130 insertions(+), 28 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/code/graph/makepdf.sh Fri Jul 02 02:43:28 2010 +0900 @@ -0,0 +1,7 @@ +#!/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
--- a/code/graph/makepng.sh Thu Jul 01 00:40:51 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
--- a/code/graph/reg.dot Thu Jul 01 00:40:51 2010 +0900 +++ b/code/graph/reg.dot Fri Jul 02 02:43:28 2010 +0900 @@ -3,7 +3,7 @@ d2ttikzedgelabels = true; d2tstyleonly = true; d2tdocpreamble = "\usetikzlibrary{automata}"; - d2tfigpreamble = " ikzstyle{every state}= [draw=blue!50, shape=circle, very thick,fill=blue!20]"; + d2tfigpreamble = " ikzstyle{every state}= [draw=blue!50, shape=circle, very thick,fill=blue!20]"; edge [lblstyle="fill=blue!20", style="arrows=->", topath="bend left"]; node [shape="circle", style="state"];
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/code/graph/regdfa.dot Fri Jul 02 02:43:28 2010 +0900 @@ -0,0 +1,18 @@ +digraph G{ + d2tdocpreamble = "\usetikzlibrary{automata}"; + d2tfigpreamble = "\tikzstyle{every state}= \ + [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"] +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/code/graph/regnfa.dot Fri Jul 02 02:43:28 2010 +0900 @@ -0,0 +1,20 @@ +digraph G{ + d2tdocpreamble = "\usetikzlibrary{automata}"; + d2tfigpreamble = "\tikzstyle{every state}= \ + [draw=blue!50,very thick,shape=circle, fill=blue!20]"; + node [style="state"]; + edge [lblstyle="fill=blue!20", style="arrows=->", topath="bend left"]; + s6 [style="state, initial"] + s8 [style="state, accepting"] + s1 -> s2 [texlbl="A"] + s3 -> s4 [texlbl="B"] + s2 -> s5 [texlbl="$\varepsilon$"] + s2 -> s7 [texlbl="$\varepsilon$"] + s5 -> s1 [texlbl="$\varepsilon$"] + s5 -> s3 [texlbl="$\varepsilon$"] + s4 -> s5 [texlbl="$\varepsilon$"] + s4 -> s7 [texlbl="$\varepsilon$"] + s7 -> s8 [texlbl="C"] + s6 -> s5 [texlbl="$\varepsilon$"] + s6 -> s7 [texlbl="$\varepsilon$"] +}
--- a/src/cTranslator.py Thu Jul 01 00:40:51 2010 +0900 +++ b/src/cTranslator.py Fri Jul 02 02:43:28 2010 +0900 @@ -1,12 +1,14 @@ #!/usr/bin/env python -import sys from dfareg import Regexp, CallGraph from translator import Translator class CTranslator(Translator): """ CTranslator + This Calss can translate from DFA or NFA into C source code. + DFA: A simple state transition as tail call (also can implement with CbC). + NFA: using stack, deepening depth-first search. >>> string = \"(A|B)*C\" >>> reg = Regexp(string) >>> dfacg = CallGraph(reg.dfa) @@ -14,20 +16,22 @@ >>> CTranslator(string, dfacg).translate() >>> CTranslator(string, nfacg).translate() """ - def __init__(self, regexp, cg, stream=sys.stdout): + def __init__(self, regexp, cg): self.regexp = regexp self.cg = cg - self.stream = stream + self.stream = None self.funType = 'void ' self.callType = '' self.breakStatement = '\t\t\tbreak;' self.debug = False def translateFromCallGraph(self): + def prefix(string): + return "state_"+string # self.emit C-source code self.emit("#include <stdio.h>\n") for k in self.cg.map.iterkeys(): - self.emit(self.funType + "state_" + k + "(char* s);\n") + self.emit(self.funType + prefix(k) + "(char* s);\n") self.emit(self.funType + 'accept(char* s);\n') self.emit(self.funType + 'reject(char* s);\n') self.emit(""" @@ -36,14 +40,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, "state_"+self.cg.start)) +""" % (self.regexp, len(self.cg.states), self.callType, prefix(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 + "state_" + k + "(char* s) {\n") + self.emit(self.funType + prefix(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" @@ -51,7 +55,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, "state_"+s, sLocal)) + self.emit("\t%s%s(%s);\n" % (self.callType, prefix(s), sLocal)) else: sLocal = "s" @@ -61,7 +65,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, "state_"+nextState, sLocal)) + self.emit("\t\t\t%s%s(%s);\n" % (self.callType, prefix(nextState), sLocal)) if self.breakStatement != '' : self.emit(self.breakStatement+'\n') if k in self.cg.accepts : @@ -81,7 +85,7 @@ \tprintf(\"\\nstring does not match regexp. \\n\\n\"); }\n""" % self.funType) -def main(): +def test(): import doctest doctest.testmod() ''' @@ -90,4 +94,4 @@ ct.translate() ''' -if __name__ == '__main__' : main() +if __name__ == '__main__' : test()
--- a/src/cbcTranslator.py Thu Jul 01 00:40:51 2010 +0900 +++ b/src/cbcTranslator.py Fri Jul 02 02:43:28 2010 +0900 @@ -1,6 +1,5 @@ #!/usr/bin/env python -import sys from dfareg import Regexp, CallGraph from cTranslator import CTranslator @@ -8,19 +7,25 @@ pass class CbCTranslator(CTranslator): - def __init__(self, regexp, cg, stream=sys): + """ + CbCTranslator + >>> string = \"(A|B)*C\" + >>> reg = Regexp(string) + >>> dfacg = CallGraph(reg.dfa) + >>> CbCTranslator(string, dfacg).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 = stream + self.stream = None self.funType = '__code ' self.callType = 'goto ' self.breakStatement = '' self.debug = False -def main(): - reg = Regexp("(A|B)*C") - cbct = CbCTranslator(reg.regexp, CallGraph(reg.dfa)) - cbct.translate() +def test(): + import doctest + doctest.testmod() -if __name__ == '__main__' : main() +if __name__ == '__main__' : test()
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/dotTranslator.py Fri Jul 02 02:43:28 2010 +0900 @@ -0,0 +1,55 @@ +#!/usr/bin/env python + +import re +from translator import Translator +from dfareg import CallGraph, Regexp + +class DotTranslator(Translator): + """ + DotToranslator + This Class can translate from DFA or NFA into Dot + Dot is Graph-generater using TeX. + --code/graph/makepdf.sh is generate graph script. + >>> string = \"(A|B)*C\" + >>> reg = Regexp(string) + >>> dfacg = CallGraph(reg.dfa) + >>> nfacg = CallGraph(reg.nfa) + >>> DotTranslator(string, dfacg).translate() + >>> DotTranslator(string, nfacg).translate() + """ + def translateFromCallGraph(self): + def prefix(string): + return "s"+re.sub("_", "", string) + self.emit(''' +digraph G{ +\td2tdocpreamble = "\\usetikzlibrary{automata}"; +\td2tfigpreamble = "\\tikzstyle{every state}= \\ +\t[draw=blue!50,very thick,shape=circle, fill=blue!20]"; +\tnode [style="state"]; +\tedge [lblstyle="fill=blue!20", style="arrows=->", topath="bend left"]; +''') + + self.emit("\t%s [style=\"state, initial\"]\n" % (prefix(self.cg.start))) + for accept in self.cg.accepts: + self.emit("\t%s [style=\"state, accepting\"]\n" % (prefix(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.emit("}") + + +def test(): + import doctest + doctest.testmod() + ''' + reg = Regexp("(A|B)*C") + ct = CTranslator(reg.regexp, CallGraph(reg.dfa)) + ct.translate() + ''' + +if __name__ == '__main__' : test()
--- a/src/translator.py Thu Jul 01 00:40:51 2010 +0900 +++ b/src/translator.py Fri Jul 02 02:43:28 2010 +0900 @@ -3,10 +3,10 @@ import sys class Translator(object): - def __init__(self, regexp, cg, stream=sys.stdout): + def __init__(self, regexp, cg): self.regexp = regexp self.cg = cg - self.stream = stream + self.stream = None def emit(self, string): self.stream.write(string)