1#=======================================================================
2#
3#   Python Lexical Analyser
4#
5#   Classes for building NFAs and DFAs
6#
7#=======================================================================
8
9from __future__ import absolute_import
10
11import sys
12
13from .Transitions import TransitionMap
14
15try:
16    from sys import maxsize as maxint
17except ImportError:
18    from sys import maxint
19
20try:
21    unichr
22except NameError:
23    unichr = chr
24
25LOWEST_PRIORITY = -maxint
26
27
28class Machine(object):
29    """A collection of Nodes representing an NFA or DFA."""
30    states = None          # [Node]
31    next_state_number = 1
32    initial_states = None  # {(name, bol): Node}
33
34    def __init__(self):
35        self.states = []
36        self.initial_states = {}
37
38    def __del__(self):
39        #print "Destroying", self ###
40        for state in self.states:
41            state.destroy()
42
43    def new_state(self):
44        """Add a new state to the machine and return it."""
45        s = Node()
46        n = self.next_state_number
47        self.next_state_number = n + 1
48        s.number = n
49        self.states.append(s)
50        return s
51
52    def new_initial_state(self, name):
53        state = self.new_state()
54        self.make_initial_state(name, state)
55        return state
56
57    def make_initial_state(self, name, state):
58        self.initial_states[name] = state
59
60    def get_initial_state(self, name):
61        return self.initial_states[name]
62
63    def dump(self, file):
64        file.write("Plex.Machine:\n")
65        if self.initial_states is not None:
66            file.write("   Initial states:\n")
67            for (name, state) in sorted(self.initial_states.items()):
68                file.write("      '%s': %d\n" % (name, state.number))
69        for s in self.states:
70            s.dump(file)
71
72
73class Node(object):
74    """A state of an NFA or DFA."""
75    transitions = None      # TransitionMap
76    action = None           # Action
77    action_priority = None  # integer
78    number = 0              # for debug output
79    epsilon_closure = None  # used by nfa_to_dfa()
80
81    def __init__(self):
82        # Preinitialise the list of empty transitions, because
83        # the nfa-to-dfa algorithm needs it
84        #self.transitions = {'':[]}
85        self.transitions = TransitionMap()
86        self.action_priority = LOWEST_PRIORITY
87
88    def destroy(self):
89        #print "Destroying", self ###
90        self.transitions = None
91        self.action = None
92        self.epsilon_closure = None
93
94    def add_transition(self, event, new_state):
95        self.transitions.add(event, new_state)
96
97    def link_to(self, state):
98        """Add an epsilon-move from this state to another state."""
99        self.add_transition('', state)
100
101    def set_action(self, action, priority):
102        """Make this an accepting state with the given action. If
103        there is already an action, choose the action with highest
104        priority."""
105        if priority > self.action_priority:
106            self.action = action
107            self.action_priority = priority
108
109    def get_action(self):
110        return self.action
111
112    def get_action_priority(self):
113        return self.action_priority
114
115    def is_accepting(self):
116        return self.action is not None
117
118    def __str__(self):
119        return "State %d" % self.number
120
121    def dump(self, file):
122        # Header
123        file.write("   State %d:\n" % self.number)
124        # Transitions
125        #        self.dump_transitions(file)
126        self.transitions.dump(file)
127        # Action
128        action = self.action
129        priority = self.action_priority
130        if action is not None:
131            file.write("      %s [priority %d]\n" % (action, priority))
132
133    def __lt__(self, other):
134        return self.number < other.number
135
136
137class FastMachine(object):
138    """
139    FastMachine is a deterministic machine represented in a way that
140    allows fast scanning.
141    """
142    initial_states = None  # {state_name:state}
143    states = None          # [state]  where state = {event:state, 'else':state, 'action':Action}
144    next_number = 1        # for debugging
145
146    new_state_template = {
147        '': None, 'bol': None, 'eol': None, 'eof': None, 'else': None
148    }
149
150    def __init__(self):
151        self.initial_states = {}
152        self.states = []
153
154    def __del__(self):
155        for state in self.states:
156            state.clear()
157
158    def new_state(self, action=None):
159        number = self.next_number
160        self.next_number = number + 1
161        result = self.new_state_template.copy()
162        result['number'] = number
163        result['action'] = action
164        self.states.append(result)
165        return result
166
167    def make_initial_state(self, name, state):
168        self.initial_states[name] = state
169
170    def add_transitions(self, state, event, new_state, maxint=maxint):
171        if type(event) is tuple:
172            code0, code1 = event
173            if code0 == -maxint:
174                state['else'] = new_state
175            elif code1 != maxint:
176                while code0 < code1:
177                    state[unichr(code0)] = new_state
178                    code0 += 1
179        else:
180            state[event] = new_state
181
182    def get_initial_state(self, name):
183        return self.initial_states[name]
184
185    def dump(self, file):
186        file.write("Plex.FastMachine:\n")
187        file.write("   Initial states:\n")
188        for name, state in sorted(self.initial_states.items()):
189            file.write("      %s: %s\n" % (repr(name), state['number']))
190        for state in self.states:
191            self.dump_state(state, file)
192
193    def dump_state(self, state, file):
194        # Header
195        file.write("   State %d:\n" % state['number'])
196        # Transitions
197        self.dump_transitions(state, file)
198        # Action
199        action = state['action']
200        if action is not None:
201            file.write("      %s\n" % action)
202
203    def dump_transitions(self, state, file):
204        chars_leading_to_state = {}
205        special_to_state = {}
206        for (c, s) in state.items():
207            if len(c) == 1:
208                chars = chars_leading_to_state.get(id(s), None)
209                if chars is None:
210                    chars = []
211                    chars_leading_to_state[id(s)] = chars
212                chars.append(c)
213            elif len(c) <= 4:
214                special_to_state[c] = s
215        ranges_to_state = {}
216        for state in self.states:
217            char_list = chars_leading_to_state.get(id(state), None)
218            if char_list:
219                ranges = self.chars_to_ranges(char_list)
220                ranges_to_state[ranges] = state
221        ranges_list = ranges_to_state.keys()
222        ranges_list.sort()
223        for ranges in ranges_list:
224            key = self.ranges_to_string(ranges)
225            state = ranges_to_state[ranges]
226            file.write("      %s --> State %d\n" % (key, state['number']))
227        for key in ('bol', 'eol', 'eof', 'else'):
228            state = special_to_state.get(key, None)
229            if state:
230                file.write("      %s --> State %d\n" % (key, state['number']))
231
232    def chars_to_ranges(self, char_list):
233        char_list.sort()
234        i = 0
235        n = len(char_list)
236        result = []
237        while i < n:
238            c1 = ord(char_list[i])
239            c2 = c1
240            i += 1
241            while i < n and ord(char_list[i]) == c2 + 1:
242                i += 1
243                c2 += 1
244            result.append((chr(c1), chr(c2)))
245        return tuple(result)
246
247    def ranges_to_string(self, range_list):
248        return ','.join(map(self.range_to_string, range_list))
249
250    def range_to_string(self, range_tuple):
251        (c1, c2) = range_tuple
252        if c1 == c2:
253            return repr(c1)
254        else:
255            return "%s..%s" % (repr(c1), repr(c2))
256