Blame view

fsabuilder/morfeuszbuilder/segrules/rulesNFA.py 3.88 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
13
    statesCounter = 0

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

    def addTransition(self, label, targetState):
Michał Lenart authored
23
        assert label is None or len(label) == 2
Michał Lenart authored
24
25
26
27
28
29
30
31
32
33
34
35
36
        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
37
Michał Lenart authored
38
39
40
41
42
43
    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
44
                    for state1 in state.dfs(visitedStates):
Michał Lenart authored
45
46
47
48
49
50
51
                        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
52
53
54

class RulesNFA(object):
Michał Lenart authored
55
    def __init__(self):
Michał Lenart authored
56
57
        self.initialState = RulesNFAState(initial=True)
Michał Lenart authored
58
59
60
61
62
    def _groupOutputByLabels(self, nfaStates):
        res = {}
        for nfaState in nfaStates:
            for label, nextStates in nfaState.transitionsMap.iteritems():
                if label is not None:
Michał Lenart authored
63
64
65
#                     transitionData = nfaState.transitionsDataMap[label]
                    segnum, shiftOrth = label
                    res.setdefault((segnum, shiftOrth), set())
Michał Lenart authored
66
                    for nextNFAState in nextStates:
Michał Lenart authored
67
                        res[(segnum, shiftOrth)] |= nextNFAState.getClosure(set())
Michał Lenart authored
68
69
70
        return res

    def _doConvertState(self, dfaState, nfaStates, nfaSubset2DFAState):
Michał Lenart authored
71
72
73
        assert all(map(lambda state: state.weak, filter(lambda state: state.final, nfaStates))) \
            or not any(map(lambda state: state.weak, filter(lambda state: state.final, nfaStates)))
        weak = any(map(lambda state: state.weak and state.final, nfaStates))
Michał Lenart authored
74
        final = any(map(lambda state: state.final, nfaStates))
Michał Lenart authored
75
#         assert not weak or not final
Michał Lenart authored
76
77
78
        if final:
            # dfaState should be final
            # and contain info about weakness
Michał Lenart authored
79
80
81
            dfaState.setAsAccepting(weak=weak)
#             dfaState.encodedData = bytearray([1 if weak else 0])
        for (segnum, shiftOrth), nextNFAStates in self._groupOutputByLabels(nfaStates).iteritems():
Michał Lenart authored
82
83
84
85
            key = frozenset(nextNFAStates)
            if key in nfaSubset2DFAState:
                nextDFAState = nfaSubset2DFAState[key]
            else:
Michał Lenart authored
86
                nextDFAState = RulesState()
Michał Lenart authored
87
88
                nfaSubset2DFAState[key] = nextDFAState
                self._doConvertState(nextDFAState, nextNFAStates, nfaSubset2DFAState)
Michał Lenart authored
89
90
            dfaState.setTransition((segnum, shiftOrth), nextDFAState)
#             dfaState.setTransitionData(label, transitionData)
Michał Lenart authored
91
92

    def convertToDFA(self):
Michał Lenart authored
93
        dfa = RulesFSA()
Michał Lenart authored
94
        startStates = self.initialState.getClosure(set())
Michał Lenart authored
95
        assert not any(filter(lambda s: s.final, startStates))
Michał Lenart authored
96
        dfa.initialState = RulesState()
Michał Lenart authored
97
98
99
100
101
102
        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
103