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