|
9
|
1 #!/usr/bin/env python
|
|
|
2 # -*- encoding: utf-8 -*-
|
|
|
3
|
|
|
4 import copy
|
|
|
5 from pyrect.regexp.parser import Parser
|
|
|
6 from pyrect.regexp.nfa_translator import NFATranslator
|
|
|
7 from pyrect.regexp.dfa_translator import DFATranslator
|
|
|
8 from pyrect.regexp.dfa import DFA
|
|
|
9 from pyrect.regexp.nfa import NFA
|
|
|
10 from pyrect.regexp.ast import Character
|
|
|
11
|
|
|
12 # create call graph (as dictionary)
|
|
|
13 class CallGraph(object):
|
|
|
14 """CallGraph is State Transition Diagram.
|
|
|
15 it's can be create from DFA or DFA.
|
|
|
16 >>> prs = Parser()
|
|
|
17 >>> dfat = DFATranslator()
|
|
|
18 >>> cg = CallGraph(dfat.translate(prs.parse('(argv|argc|args|あれ|これ)')))
|
|
|
19 """
|
|
|
20
|
|
|
21 def __init__(self, fa):
|
|
|
22 self.fa = fa
|
|
|
23 if isinstance(fa, DFA):
|
|
|
24 self.type = "DFA"
|
|
|
25 else:
|
|
|
26 self.type = "NFA"
|
|
|
27 self.start = str(self.fa.start)
|
|
|
28 self.states = map(str, self.fa.states)
|
|
|
29 self.accepts = map(str, self.fa.accepts)
|
|
|
30 self.inputs = set()
|
|
|
31 self.map = self.create_call_graph(self.fa)
|
|
|
32
|
|
|
33 def create_call_graph(self, fa):
|
|
|
34 transitionCases = dict()
|
|
|
35 # transitionCases is hash table that binds a state and inputs,
|
|
|
36 # it's useful for transition definition
|
|
|
37 # fa is dfa or nfa
|
|
|
38 # dfa.map => {(1, 'C'): 2, (3, 'C'): 2, (0, 'A'): 1, ...}
|
|
|
39 # : 1 x 'C' -> 2
|
|
|
40 # nfa.map => {(6, ''): set([5, 7]), (1, 'A'): set([2]), ....}
|
|
|
41 # : 6 x '' -> set([5, 7])
|
|
|
42
|
|
|
43 for (state, input) in fa.map.iterkeys():
|
|
|
44 slot = transitionCases.setdefault(state, set())
|
|
|
45 slot.add(input)
|
|
|
46
|
|
|
47 callGraph = dict()
|
|
|
48
|
|
|
49 # create CallGraph
|
|
|
50 for state in self.states:
|
|
|
51 callGraph[str(state)] = dict()
|
|
|
52
|
|
|
53 for (state, input) in transitionCases.iteritems():
|
|
|
54 caseMap = dict()
|
|
|
55
|
|
|
56 for case in input:
|
|
|
57 self.inputs.add(case)
|
|
|
58 if self.type == "DFA":
|
|
|
59 caseMap[case] = str(fa.map[state, case])
|
|
|
60 else:
|
|
|
61 caseMap[case] = map(str, fa.map[state, case])
|
|
|
62 callGraph[str(state)] = caseMap
|
|
|
63 return callGraph
|
|
|
64
|
|
|
65 def test():
|
|
|
66 import doctest
|
|
|
67 doctest.testmod()
|
|
|
68
|
|
|
69 if __name__ == "__main__": test()
|
