frozenset() 返回一个冻结的集合,冻结后集合不能再添加或删除任何元素

1
class FARule(object):
2
3
    def __init__(self, state, character, new_state):
4
        self.state = state
5
        self.character = character
6
        self.new_state = new_state
7
8
    def applies_to(self, state, character):
9
        return self.state == state and self.character == character
10
11
    def follow(self):
12
        return self.new_state
13
14
    def __str__(self):
15
        return "#<FARule {} -- {} --> {}>".format(self.state, self.character,
16
                                                  self.new_state)
17
18
19
class NFARulebook(object):
20
21
    def __init__(self, rules):
22
        self.rules = rules
23
24
    def next_state(self, states, character):
25
        n_states = []
26
        for state in states:
27
            s = self.follow_rules_for(state, character)
28
            n_states += s
29
        return set(n_states)
30
31
    def follow_rules_for(self, state, character):
32
        return [rule.follow() for rule in self.rule_for(state, character)]
33
34
    def rule_for(self, state, character):
35
        return [rule for rule in self.rules if rule.applies_to(state, character)]
36
37
    def follow_free_moves(self, states):
38
        more_states = self.next_state(states, None)
39
40
        if more_states.issubset(states):
41
            return states
42
        else:
43
            return self.follow_free_moves(more_states | states)
44
45
    def alphabet(self):
46
        return list(set([rule.character for rule in self.rules if
47
                         rule.character]))
48
49
class NFA(object):
50
    
51
    def __init__(self, current_state, accept_state, rulebook):
52
        self.accept_state = accept_state
53
        self.rulebook = rulebook
54
        self.current_state = frozenset(self.rulebook.follow_free_moves(current_state) )
55
56
    def accept(self):
57
        return bool(self.current_state & set(self.accept_state)) 
58
59
    def read_string(self, string):
60
        for s in string:
61
            self.read_character(s)
62
63
    def read_character(self, character):
64
        self.current_state = self.rulebook.next_state(self.current_state,
65
                                                      character)
66
        self.current_state = self.rulebook.follow_free_moves(self.current_state) 
67
68
69
class NFADesign(object):
70
71
    def __init__(self, start_state, accept_state, rulebook):
72
        self.start_state = start_state
73
        self.accept_state = accept_state
74
        self.rulebook = rulebook
75
76
    def is_accepting(self, string):
77
        nfa = self.to_nfa()
78
        nfa.read_string(string)
79
        return nfa.accept()
80
81
    def to_nfa(self, current_state=None):
82
        if not current_state:
83
            current_state = {self.start_state}
84
        return NFA(current_state, self.accept_state, self.rulebook)
85
86
87
class NFASimulation(object):
88
89
    def __init__(self, nfa_design):
90
        self.nfa_design = nfa_design 
91
92
    def next_state(self, state, character):
93
        nfa = self.nfa_design.to_nfa(state)
94
        nfa.read_character(character)
95
        return frozenset(nfa.current_state)
96
97
    def rules_for(self, state):
98
        return [FARule(state, character, self.next_state(state, character)) for
99
               character in self.nfa_design.rulebook.alphabet()]
100
101
    def discover_states_and_rules(self, states):
102
        rules = []
103
        for state in states:
104
            rules += self.rules_for(state)
105
        more_states = set([rule.follow() for rule in rules])
106
107
        if more_states.issubset(states):
108
            return [states, rules]
109
        else:
110
            return self.discover_states_and_rules(states | more_states)
111
112
if __name__ == "__main__":
113
    rulebook = NFARulebook(
114
        [
115
            FARule(1, 'a', 1), FARule(1, 'a', 2), FARule(1, None, 2),
116
            FARule(2, 'b', 3),
117
            FARule(3, 'b', 1), FARule(3, None, 2)
118
        ]
119
    )
120
121
    nfa_design = NFADesign(1, [3], rulebook)
122
    print(nfa_design)
123
    print(nfa_design.to_nfa().current_state)
124
    print(nfa_design.to_nfa({2}).current_state)
125
    print(nfa_design.to_nfa({3}).current_state)
126
127
    nfa = nfa_design.to_nfa({2, 3})
128
    nfa.read_character('b')
129
    print(nfa.current_state)
130
131
132
    print("-" * 100)
133
    simulation = NFASimulation(nfa_design)
134
    print(simulation.next_state({1, 2}, 'a'))
135
    print(simulation.next_state({1, 2}, 'b'))
136
    print(simulation.next_state({3, 2}, 'b'))
137
    print(simulation.next_state({1, 3, 2}, 'b'))
138
    print(simulation.next_state({1, 3, 2}, 'a'))
139
    print("-" * 100)
140
    print(rulebook.alphabet())
141
    rules = simulation.rules_for(frozenset({1, 2}))
142
    for r in rules:
143
        print(r)
144
    rules = simulation.rules_for(frozenset({3, 2}))
145
    for r in rules:
146
        print(r)
147
148
    print("-" * 100)
149
150
    start_state = nfa_design.to_nfa().current_state
151
    print(start_state)
152
    states, rules = simulation.discover_states_and_rules(set([start_state]))
153
    print(states)
154
    for r in rules:
155
        print(r)