Mercurial > hg > Members > shinya > pyrect

annotate src/cTranslator.py @ 8:a28f87d353bb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Sat, 03 Jul 2010 01:40:36 +0900
parents 168d60b03e2c
children 973b596bd124
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
8
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
1 #!/Usr/bin/env python
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 from dfareg import Regexp, CallGraph
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 from translator import Translator
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 class CTranslator(Translator):
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 """
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 CTranslator
6
168d60b03e2c add dotTranslator(Translator), that can translate from DFA or NFA into Dot-file(Dot is graph generater using tex.)
ryoma <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
9 This Calss can translate from DFA or NFA into C source code.
168d60b03e2c add dotTranslator(Translator), that can translate from DFA or NFA into Dot-file(Dot is graph generater using tex.)
ryoma <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
10 DFA: A simple state transition as tail call (also can implement with CbC).
168d60b03e2c add dotTranslator(Translator), that can translate from DFA or NFA into Dot-file(Dot is graph generater using tex.)
ryoma <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
11 NFA: using stack, deepening depth-first search.
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 >>> string = \"(A|B)*C\"
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 >>> reg = Regexp(string)
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 >>> dfacg = CallGraph(reg.dfa)
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 >>> nfacg = CallGraph(reg.nfa)
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 >>> CTranslator(string, dfacg).translate()
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 >>> CTranslator(string, nfacg).translate()
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 """
6
168d60b03e2c add dotTranslator(Translator), that can translate from DFA or NFA into Dot-file(Dot is graph generater using tex.)
ryoma <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
19 def __init__(self, regexp, cg):
8
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
20 Translator.__init__(self, regexp, cg)
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 self.funType = 'void '
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 self.callType = ''
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 self.breakStatement = '\t\t\tbreak;'
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 self.debug = False
8
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
25 if self.cg.type is "DFA":
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
26 self.dfaStateNameHash = self.createDFAStateNameHash()
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
27
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
28 def modifyStateName(self, stateName):
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
29 if self.cg.type is "DFA":
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
30 return "state_"+self.dfaStateNameHash[stateName]
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
31 else:
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
32 return "state_"+stateName
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 def translateFromCallGraph(self):
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 # self.emit C-source code
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 self.emit("#include <stdio.h>\n")
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 for k in self.cg.map.iterkeys():
8
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
38 self.emit(self.funType + self.modifyStateName(k) + "(char* s);\n")
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 self.emit(self.funType + 'accept(char* s);\n')
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 self.emit(self.funType + 'reject(char* s);\n')
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 self.emit("""
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 int main(int argc, char* argv[]) {
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 \tputs(\"regexp: %s\");
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 \tputs(\"number of state: %d\");
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 \tprintf(\"string: %%s\\n\", argv[1]);
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 \t%s%s(argv[1]);
8
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
47 """ % (self.regexp, len(self.cg.states), self.callType, self.modifyStateName(self.cg.start)))
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 if self.cg.type is "NFA" : self.emit("\treject(argv[1]);\n")
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 self.emit("""
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 \treturn 0;
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 }\n\n""")
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 for k, v in self.cg.map.iteritems():
8
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
54 self.emit(self.funType + self.modifyStateName(k) + "(char* s) {\n")
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 if self.debug: self.emit("\tprintf(\"state: %s, input: %%s\\n\", s);\n" % (k))
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 if self.cg.type is "NFA":
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 sLocal = "s_local"
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 self.emit("\tchar* %s = s;\n" % (sLocal))
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 # epsilon-transition
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 for ss in (ss for i,ss in v.iteritems() if i == ''):
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 for s in ss:
8
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
62 self.emit("\t%s%s(%s);\n" % (self.callType, self.modifyStateName(s), sLocal))
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 else:
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 sLocal = "s"
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 self.emit("\tswitch(*%s++) {\n" % (sLocal))
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 for input, nextStates in v.iteritems():
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 if input != '':
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 self.emit("\t\tcase '%s': \n" % (input))
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 for nextState in nextStates:
8
a28f87d353bb simplify DFA state name. (in C/Dot Translator. ex: "1_2_3" -> "1")
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
72 self.emit("\t\t\t%s%s(%s);\n" % (self.callType, self.modifyStateName(nextState), sLocal))
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 if self.breakStatement != '' : self.emit(self.breakStatement+'\n')
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 if k in self.cg.accepts :
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 self.emit( """\t\tcase '\\0':\n\t\t\t%saccept(%s);\n%s\n""" % (self.callType, sLocal, self.breakStatement))
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 if self.cg.type is "DFA":
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 self.emit("\t\tdefault: %sreject(%s);\n\t}\n" % (self.callType, sLocal))
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 else:
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 self.emit("\t}\n")
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 self.emit("}\n\n")
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 self.emit ("""
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 %saccept(char* s) {
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 \tprintf(\"\\nstring matches regexp. \\n\\n\");
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 }\n""" % self.funType)
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 self.emit ("""
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 %sreject(char* s) {
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 \tprintf(\"\\nstring does not match regexp. \\n\\n\");
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 }\n""" % self.funType)
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91
6
168d60b03e2c add dotTranslator(Translator), that can translate from DFA or NFA into Dot-file(Dot is graph generater using tex.)
ryoma <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
92 def test():
5
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 import doctest
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 doctest.testmod()
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 '''
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 reg = Regexp("(A|B)*C")
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 ct = CTranslator(reg.regexp, CallGraph(reg.dfa))
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 ct.translate()
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 '''
11fba907c0af add Translater(object), that can translate C/CbC source code
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100
6
168d60b03e2c add dotTranslator(Translator), that can translate from DFA or NFA into Dot-file(Dot is graph generater using tex.)
ryoma <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
101 if __name__ == '__main__' : test()