|
1
2
3
4
5
6
|
'''
Created on 24 sty 2014
@author: mlenart
'''
|
|
7
|
from morfeuszbuilder.segrules.rulesFSA import RulesFSA, RulesState
|
|
8
9
10
|
class RulesNFAState(object):
|
|
11
12
|
statesCounter = 0
|
|
13
14
|
def __init__(self, rule, initial=False, final=False, weak=False):
self.rule = rule
|
|
15
|
self.transitionsMap = {}
|
|
16
|
# self.transitionsDataMap = {}
|
|
17
18
|
self.initial = initial
self.final = final
|
|
19
20
21
22
23
|
self.weak = weak
self.idx = RulesNFAState.statesCounter
RulesNFAState.statesCounter += 1
def addTransition(self, label, targetState):
|
|
24
|
assert label is None or len(label) == 2
|
|
25
26
27
28
29
30
31
32
33
34
35
36
37
|
self.transitionsMap.setdefault(label, set())
self.transitionsMap[label].add(targetState)
def getClosure(self, visited):
if self in visited:
return set()
else:
visited.add(self)
res = set()
res.add(self)
for nextState in self.transitionsMap.get(None, []):
res |= nextState.getClosure(visited)
return res
|
|
38
|
|
|
39
40
41
42
43
44
|
def dfs(self, visitedStates=set()):
if not self in visitedStates:
visitedStates.add(self)
yield self
for _, nextStates in self.transitionsMap.iteritems():
for state in nextStates:
|
|
45
|
for state1 in state.dfs(visitedStates):
|
|
46
47
48
49
50
51
52
|
yield state1
def debug(self):
print '----------------'
print 'STATE:', self.idx
for label, nextStates in self.transitionsMap.iteritems():
print label, '-->', [s.idx for s in sorted(nextStates, key=lambda s: s.idx)]
|
|
53
54
55
|
class RulesNFA(object):
|
|
56
|
def __init__(self):
|
|
57
|
self.initialState = RulesNFAState(rule=None, initial=True)
|
|
58
|
|
|
59
60
61
62
63
|
def _groupOutputByLabels(self, nfaStates):
res = {}
for nfaState in nfaStates:
for label, nextStates in nfaState.transitionsMap.iteritems():
if label is not None:
|
|
64
65
66
|
# transitionData = nfaState.transitionsDataMap[label]
segnum, shiftOrth = label
res.setdefault((segnum, shiftOrth), set())
|
|
67
|
for nextNFAState in nextStates:
|
|
68
|
res[(segnum, shiftOrth)] |= nextNFAState.getClosure(set())
|
|
69
70
71
|
return res
def _doConvertState(self, dfaState, nfaStates, nfaSubset2DFAState):
|
|
72
73
74
75
76
|
if not all(map(lambda state: state.weak, filter(lambda state: state.final, nfaStates))) \
and any(map(lambda state: state.weak, filter(lambda state: state.final, nfaStates))):
weakState = list(filter(lambda state: state.final and state.weak, nfaStates))[0]
nonWeakState = list(filter(lambda state: state.final and not state.weak, nfaStates))[0]
raise InconsistentStateWeaknessException(weakState, nonWeakState)
|
|
77
|
weak = any(map(lambda state: state.weak and state.final, nfaStates))
|
|
78
|
final = any(map(lambda state: state.final, nfaStates))
|
|
79
|
# assert not weak or not final
|
|
80
81
82
|
if final:
# dfaState should be final
# and contain info about weakness
|
|
83
84
85
|
dfaState.setAsAccepting(weak=weak)
# dfaState.encodedData = bytearray([1 if weak else 0])
for (segnum, shiftOrth), nextNFAStates in self._groupOutputByLabels(nfaStates).iteritems():
|
|
86
87
88
89
|
key = frozenset(nextNFAStates)
if key in nfaSubset2DFAState:
nextDFAState = nfaSubset2DFAState[key]
else:
|
|
90
|
nextDFAState = RulesState()
|
|
91
92
|
nfaSubset2DFAState[key] = nextDFAState
self._doConvertState(nextDFAState, nextNFAStates, nfaSubset2DFAState)
|
|
93
94
|
dfaState.setTransition((segnum, shiftOrth), nextDFAState)
# dfaState.setTransitionData(label, transitionData)
|
|
95
96
|
def convertToDFA(self):
|
|
97
|
dfa = RulesFSA()
|
|
98
|
startStates = self.initialState.getClosure(set())
|
|
99
|
assert not any(filter(lambda s: s.final, startStates))
|
|
100
|
dfa.initialState = RulesState()
|
|
101
102
103
104
105
106
|
self._doConvertState(dfa.initialState, startStates, {frozenset(startStates): dfa.initialState})
return dfa
def debug(self):
for state in self.initialState.dfs():
state.debug()
|
|
107
108
109
110
111
112
|
class InconsistentStateWeaknessException(Exception):
def __init__(self, weakState, nonWeakState):
self.weakState = weakState
self.nonWeakState = nonWeakState
|