Blame view

fsabuilder/morfeuszbuilder/segrules/rulesNFA.py 4.35 KB
Michał Lenart authored
1
2
3
4
5
6
'''
Created on 24 sty 2014

@author: mlenart
'''
Michał Lenart authored
7
from morfeuszbuilder.segrules.rulesFSA import RulesFSA, RulesState
Michał Lenart authored
8
9
10

class RulesNFAState(object):
Michał Lenart authored
11
12
    statesCounter = 0
Michał Lenart authored
13
14
    def __init__(self, rule, initial=False, final=False, weak=False):
        self.rule = rule
Michał Lenart authored
15
        self.transitionsMap = {}
Michał Lenart authored
16
#         self.transitionsDataMap = {}
Michał Lenart authored
17
18
        self.initial = initial
        self.final = final
Michał Lenart authored
19
20
21
22
23
        self.weak = weak
        self.idx = RulesNFAState.statesCounter
        RulesNFAState.statesCounter += 1

    def addTransition(self, label, targetState):
Michał Lenart authored
24
        assert label is None or len(label) == 2
Michał Lenart authored
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
Michał Lenart authored
38
Michał Lenart authored
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:
Michał Lenart authored
45
                    for state1 in state.dfs(visitedStates):
Michał Lenart authored
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)]
Michał Lenart authored
53
54
55

class RulesNFA(object):
Michał Lenart authored
56
    def __init__(self):
Michał Lenart authored
57
        self.initialState = RulesNFAState(rule=None, initial=True)
Michał Lenart authored
58
Michał Lenart authored
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:
Michał Lenart authored
64
65
66
#                     transitionData = nfaState.transitionsDataMap[label]
                    segnum, shiftOrth = label
                    res.setdefault((segnum, shiftOrth), set())
Michał Lenart authored
67
                    for nextNFAState in nextStates:
Michał Lenart authored
68
                        res[(segnum, shiftOrth)] |= nextNFAState.getClosure(set())
Michał Lenart authored
69
70
71
        return res

    def _doConvertState(self, dfaState, nfaStates, nfaSubset2DFAState):
Michał Lenart authored
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)
Michał Lenart authored
77
        weak = any(map(lambda state: state.weak and state.final, nfaStates))
Michał Lenart authored
78
        final = any(map(lambda state: state.final, nfaStates))
Michał Lenart authored
79
#         assert not weak or not final
Michał Lenart authored
80
81
82
        if final:
            # dfaState should be final
            # and contain info about weakness
Michał Lenart authored
83
84
85
            dfaState.setAsAccepting(weak=weak)
#             dfaState.encodedData = bytearray([1 if weak else 0])
        for (segnum, shiftOrth), nextNFAStates in self._groupOutputByLabels(nfaStates).iteritems():
Michał Lenart authored
86
87
88
89
            key = frozenset(nextNFAStates)
            if key in nfaSubset2DFAState:
                nextDFAState = nfaSubset2DFAState[key]
            else:
Michał Lenart authored
90
                nextDFAState = RulesState()
Michał Lenart authored
91
92
                nfaSubset2DFAState[key] = nextDFAState
                self._doConvertState(nextDFAState, nextNFAStates, nfaSubset2DFAState)
Michał Lenart authored
93
94
            dfaState.setTransition((segnum, shiftOrth), nextDFAState)
#             dfaState.setTransitionData(label, transitionData)
Michał Lenart authored
95
96

    def convertToDFA(self):
Michał Lenart authored
97
        dfa = RulesFSA()
Michał Lenart authored
98
        startStates = self.initialState.getClosure(set())
Michał Lenart authored
99
        assert not any(filter(lambda s: s.final, startStates))
Michał Lenart authored
100
        dfa.initialState = RulesState()
Michał Lenart authored
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()
Michał Lenart authored
107
108
109
110
111
112

class InconsistentStateWeaknessException(Exception):

    def __init__(self, weakState, nonWeakState):
        self.weakState = weakState
        self.nonWeakState = nonWeakState