Compiler_Principle/fa.py at master · comzyh/Compiler_Principle · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author: Comzyh
# @Date:   2015-06-02 17:38:36
# @Last Modified by:   Comzyh
# @Last Modified time: 2015-06-04 22:55:19

Epsilon = 0


class NFANode(object):

    """Node of NFA"""

    def __init__(self, nfa=None, index=0, transfer=None, data=None):
        super(NFANode, self).__init__()
        if not isinstance(index, int):
            raise Exception('id must be integer, got %s' % index)
        if transfer is None:
            transfer = {}  # 坑, 使用默认参数的话全局都指向一个dictionary了..
        self.index = index  # 标号
        self.transfer = transfer  # 转移表
        self.NFA = nfa
        self.alphabet = nfa.alphabet
        self.data = data

    def add_transfer(self, char, dest):
        if char not in self.transfer:
            self.transfer[char] = []
        self.transfer[char].append(dest)

    def get_transfer(self, char):
        if char in self.transfer:
            return self.transfer[char]
        else:
            return []

    def __str__(self):
        s = ''
        s += '--------------\n'
        s += 'index:%s\n' % self.index
        for key, arr in self.transfer.items():
            s += '%s :' % key
            s += str([state.index for state in arr])
            s += '\n'
        return s

    def show_transfer(self, char):
        print '--------------'
        print 'index:%s' % self.index
        if char in self.transfer:
            print char, ':',
            print[state.index for state in self.transfer[char]]


class NFA(object):

    """Nondeterministic Finite Automaton"""

    def __init__(self, alphabet):
        super(NFA, self).__init__()
        self.states = []  # 状态集
        self.alphabet = alphabet
        self.S = self.create_node()
        self.final_state = set()
        self.name_to_state_dict = None

    def create_node(self):
        node = NFANode(self, len(self.states))
        self.states.append(node)
        return node

    def add_transfer(self, u, char, v):
        if (not (u in self.states) or not (v in self.states) or
                not (char in self.alphabet or char == Epsilon)):
            print 'u in self.states: %s\n' % (u in self.states)
            print 'v in self.states: %s\n' % (v in self.states)
            print 'chr in self.alphabet %s\n' % (char in self.alphabet)
            print 'char = ', char
            raise Exception('illigal transition')
        u.add_transfer(char, v)
        # print '%s ----%s----> %s' % (u.index, char, v.index)

    def __str__(self):
        s = ''
        for state in self.states:
            s += state.__str__()
        return s


class DFANode(object):

    """Node of DFA"""

    def __init__(self, dfa=None, index=0, transfer=None):
        super(DFANode, self).__init__()
        self.dfa = dfa
        self.index = index
        if transfer is None:
            transfer = {}
        self.transfer = transfer
        self.data = {}

    def add_transfer(self, char, dest):
        self.transfer[char] = dest

    def get_transfer(self, char):
        if char not in self.transfer:
            return None
        return self.transfer[char]


class DFA(object):

    """Deterministic Finite Automation"""

    def __init__(self, alphabet):
        super(DFA, self).__init__()
        self.states = []  # 状态集
        self.alphabet = alphabet
        self.S = self.create_node()
        self.final_state = set()
        self.name_to_state_dict = None

    def create_node(self):
        node = DFANode(self, len(self.states))
        self.states.append(node)
        return node

    def add_transfer(self, u, char, v):
        if (not (u in self.states) or not (v in self.states) or
                not (char in self.alphabet or char == Epsilon)):
            print 'u in self.states: %s\n' % (u in self.states)
            print 'v in self.states: %s\n' % (v in self.states)
            print 'chr in self.alphabet %s\n' % (char in self.alphabet)
            print 'char = ', char
            raise Exception('illigal transition')
        u.add_transfer(char, v)
        # print '%s ----%s----> %s' % (u.index, char, v.index)

    def get_transfer(self, u, char):
        if (u not in self.states or char not in self.alphabet):
            raise Exception('no such transfer')
        return u.get_transfer(char)