Mercurial > hg > Members > shinya > pyrect

annotate pyrect/regexp/dfa.py @ 87:d23f12ce0369

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Sun, 14 Nov 2010 04:16:12 +0900
parents 83c69d42faa8
children 4d498b002de5
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #!/usr/bin/env python
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 import curses.ascii as ascii
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
4 import copy, collections
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 from fa import FA
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 class DFA(FA):
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
8 def __init__(self, start, accepts, map_, states, assoc):
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 def transition(state, input):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 return map_[state, input]
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 FA.__init__(self, transition, start, accepts, map_, states)
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
12 self.assoc = assoc
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
13
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
14 def copy_from(self, dfa):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
15 self.start = dfa.start
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
16 self.map = copy.deepcopy(dfa.map)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
17 self.accepts = copy.deepcopy(dfa.accepts)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
18 self.states = copy.deepcopy(dfa.states)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
19 self.assoc = copy.deepcopy(dfa.assoc)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
20
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
21 @classmethod
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
22 def copy(cls, dfa_):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
23 dfa = DFA(dfa_)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
24 dfa.copy_from(dfa)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
25 return dfa
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 def get_runtime(self):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 return DFARuntime(self)
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
30 class SuffixDFA(DFA):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
31 def __init__(self, dfa, pdfa):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
32 self.copy_from(dfa)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
33 self.pdfa = pdfa
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
34 self.acceptable = dict()
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
35 self.make_acceptable()
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
36
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
37 def setdict(self):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
38 return collections.defaultdict(set)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
39
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
40 def make_acceptable(self):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
41 self.acceptable = collections.defaultdict(self.setdict)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
42
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
43 def search_acceptable(pcur, scur, searched, history, pstart):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
44 for (pcur_, i), pnext in self.pdfa.map.iteritems():
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
45 if pcur_ != pcur or (pnext, i) in searched: continue
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
46 searched_ = searched + [(pnext, i)]
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
47 snext = self.map[(scur, i)]
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
48 if scur not in history:
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
49 history_ = history + (scur,)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
50 else:
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
51 history_ = history
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
52 if pnext in self.pdfa.accepts:
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
53 self.acceptable[snext][history_].add(pstart)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
54 search_acceptable(pnext, snext, searched_, history_, pstart)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
55
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
56 for s in self.pdfa.states:
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
57 search_acceptable(s, self.start, [], (), s)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
58
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 class DFARuntime(object):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 def __init__(self, DFA):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 self.DFA = DFA
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 self.curState = self.DFA.start
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 def do_transition(self, char):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 self.curState = self.DFA.transition(
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 self.curState, char)
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 def is_accept_state(self):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 return self.curState in self.DFA.accepts
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 def accept(self, string):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 try:
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 for alphabet in string:
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 self.do_transition(alphabet)
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 except KeyError:
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 return False
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 return self.is_accept_state()