Mercurial > hg > Members > shinya > pyrect

comparison pyrect/regexp/dfa_translator.py @ 86:20a1c25d1fc9

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:13:05 +0900
parents fd3d0b8326fe
children 4d498b002de5
comparison
equal deleted inserted replaced
85:b34a900a3a0b 86:20a1c25d1fc9
1 #!/usr/bin/env python 1 #!/usr/bin/env python
2 #-*- encoding: utf-8 -*- 2 #-*- encoding: utf-8 -*-
3 3
4 from pyrect.regexp.parser import Parser 4 from pyrect.regexp.parser import Parser
5 from pyrect.regexp.ast import ASTWalker, AnyChar 5 from pyrect.regexp.ast import ASTWalker, AnyChar
6 from pyrect.regexp.nfa import NFA
7 from pyrect.regexp.nfa_translator import NFATranslator 6 from pyrect.regexp.nfa_translator import NFATranslator
8 from pyrect.regexp.dfa import DFA 7 from pyrect.regexp.nfa import NFA, SuffixNFA, SuffixTrieNFA
8 from pyrect.regexp.dfa import DFA, SuffixDFA
9 9
10 class DFATranslator(object): 10 class DFATranslator(object):
11 """ Create DFA from AST with Visitor-Pattern. 11 """ Create DFA from AST with Visitor-Pattern.
12 actually DFATranslator use NFATranslator and it convert NFA into DFA. 12 actually DFATranslator use NFATranslator and it convert NFA into DFA.
13 >>> prs = Parser() 13 >>> prs = Parser()
58 58
59 for v in map_.itervalues(): 59 for v in map_.itervalues():
60 if not v in done: 60 if not v in done:
61 que.add(frozenset(v)) 61 que.add(frozenset(v))
62 62
63 name_hash = dict() 63 assoc = dict()
64 states = set() 64 states = set()
65 65
66 states.add(nfa.epsilon_expand(frozenset([nfa.start]))) 66 states.add(nfa.epsilon_expand(frozenset([nfa.start])))
67 for state in map_.itervalues(): 67 for state in map_.itervalues():
68 states.add(frozenset(state)) 68 states.add(frozenset(state))
69 for index, state in enumerate(states): 69 for index, state in enumerate(states):
70 name_hash[frozenset(state)] = index 70 assoc[frozenset(state)] = index
71 states = list() 71 states = list()
72 for state in name_hash.itervalues(): 72 for state in assoc.itervalues():
73 states.append(state) 73 states.append(state)
74 74
75 start = name_hash[nfa.epsilon_expand(frozenset([nfa.start]))] 75 start = assoc[nfa.epsilon_expand(frozenset([nfa.start]))]
76 76
77 accepts = list() 77 accepts = list()
78 for state in name_hash.iterkeys(): 78 for state in assoc.iterkeys():
79 if state & set(nfa.accepts): 79 if state & set(nfa.accepts):
80 accepts.append(name_hash[state]) 80 accepts.append(assoc[state])
81 81
82 map__ = dict() 82 map__ = dict()
83 for key, value in map_.iteritems(): 83 for (s, c), v in map_.iteritems():
84 map__[(name_hash[frozenset(key[0])],key[1])] = name_hash[frozenset(value)] 84 map__[(assoc[frozenset(s)], c)] = assoc[frozenset(v)]
85 for k, v in assoc.items():
86 assoc[v] = k
85 87
86 return DFA( 88 return DFA(
87 start, 89 start,
88 accepts, 90 accepts,
89 map__, 91 map__,
90 states 92 states,
93 assoc
91 ) 94 )
95
96 class SuffixDFATranslator(DFATranslator):
97 def __init__(self):
98 self.sdfa = None
99
100 def translate(self, fa=None):
101 if fa:
102 self.sdfa = SuffixDFA(DFATranslator.translate(self, SuffixNFA(fa)), fa)
103 return self.sdfa
104
105 class SuffixTrieTranslator(DFATranslator):
106 def __init__(self):
107 self.trie = None
108
109 def translate(self, fa=None):
110 if fa:
111 self.trie = DFATranslator().translate(SuffixTrieNFA(fa))
112 return self.trie
92 113
93 def test(): 114 def test():
94 import doctest 115 import doctest
95 doctest.testmod() 116 doctest.testmod()
96 117