← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to pypy/translator/pyrex/Pyrex/Plex/Transitions.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
pypy/translator/pyrex/Pyrex/Plex/Transitions.py
 
1
#
 
2
#   Plex - Transition Maps
 
3
#
 
4
#   This version represents state sets direcly as dicts
 
5
#   for speed.
 
6
#
 
7
 
 
8
from copy import copy
 
9
import string
 
10
from sys import maxint
 
11
from types import TupleType
 
12
 
 
13
class TransitionMap:
 
14
  """
 
15
  A TransitionMap maps an input event to a set of states.
 
16
  An input event is one of: a range of character codes, 
 
17
  the empty string (representing an epsilon move), or one 
 
18
  of the special symbols BOL, EOL, EOF.
 
19
  
 
20
  For characters, this implementation compactly represents 
 
21
  the map by means of a list:
 
22
  
 
23
    [code_0, states_0, code_1, states_1, code_2, states_2,
 
24
      ..., code_n-1, states_n-1, code_n]
 
25
    
 
26
  where |code_i| is a character code, and |states_i| is a 
 
27
  set of states corresponding to characters with codes |c|
 
28
  in the range |code_i| <= |c| <= |code_i+1|.
 
29
  
 
30
  The following invariants hold:
 
31
    n >= 1
 
32
    code_0 == -maxint
 
33
    code_n == maxint
 
34
    code_i < code_i+1 for i in 0..n-1
 
35
    states_0 == states_n-1
 
36
  
 
37
  Mappings for the special events '', BOL, EOL, EOF are
 
38
  kept separately in a dictionary.
 
39
  """
 
40
  
 
41
  map = None     # The list of codes and states
 
42
  special = None # Mapping for special events
 
43
  
 
44
  def __init__(self, map = None, special = None):
 
45
    if not map:
 
46
      map = [-maxint, {}, maxint]
 
47
    if not special:
 
48
      special = {}
 
49
    self.map = map
 
50
    self.special = special
 
51
    #self.check() ###
 
52
  
 
53
  def add(self, event, new_state,
 
54
    TupleType = TupleType):
 
55
    """
 
56
    Add transition to |new_state| on |event|.
 
57
    """
 
58
    if type(event) == TupleType:
 
59
      code0, code1 = event
 
60
      i = self.split(code0)
 
61
      j = self.split(code1)
 
62
      map = self.map
 
63
      while i < j:
 
64
        map[i + 1][new_state] = 1
 
65
        i = i + 2
 
66
    else:
 
67
      self.get_special(event)[new_state] = 1
 
68
 
 
69
  def add_set(self, event, new_set,
 
70
    TupleType = TupleType):
 
71
    """
 
72
    Add transitions to the states in |new_set| on |event|.
 
73
    """
 
74
    if type(event) == TupleType:
 
75
      code0, code1 = event
 
76
      i = self.split(code0)
 
77
      j = self.split(code1)
 
78
      map = self.map
 
79
      while i < j:
 
80
        map[i + 1].update(new_set)
 
81
        i = i + 2
 
82
    else:
 
83
      self.get_special(event).update(new_set)
 
84
  
 
85
  def get_epsilon(self,
 
86
    none = None):
 
87
    """
 
88
    Return the mapping for epsilon, or None.
 
89
    """
 
90
    return self.special.get('', none)
 
91
  
 
92
  def items(self,
 
93
    len = len):
 
94
    """
 
95
    Return the mapping as a list of ((code1, code2), state_set) and
 
96
    (special_event, state_set) pairs.
 
97
    """
 
98
    result = []
 
99
    map = self.map
 
100
    else_set = map[1]
 
101
    i = 0
 
102
    n = len(map) - 1
 
103
    code0 = map[0]
 
104
    while i < n:
 
105
      set = map[i + 1]
 
106
      code1 = map[i + 2]
 
107
      if set or else_set:
 
108
        result.append(((code0, code1), set))
 
109
      code0 = code1
 
110
      i = i + 2
 
111
    for event, set in self.special.items():
 
112
      if set:
 
113
        result.append((event, set))
 
114
    return result
 
115
  
 
116
  # ------------------- Private methods --------------------
 
117
 
 
118
  def split(self, code,
 
119
    len = len, maxint = maxint):
 
120
    """
 
121
    Search the list for the position of the split point for |code|, 
 
122
    inserting a new split point if necessary. Returns index |i| such 
 
123
    that |code| == |map[i]|.
 
124
    """
 
125
    # We use a funky variation on binary search.
 
126
    map = self.map
 
127
    hi = len(map) - 1
 
128
    # Special case: code == map[-1]
 
129
    if code == maxint:
 
130
      return hi
 
131
    # General case
 
132
    lo = 0
 
133
    # loop invariant: map[lo] <= code < map[hi] and hi - lo >= 2
 
134
    while hi - lo >= 4:
 
135
      # Find midpoint truncated to even index
 
136
      mid = ((lo + hi) / 2) & ~1
 
137
      if code < map[mid]:
 
138
        hi = mid
 
139
      else:
 
140
        lo = mid
 
141
    # map[lo] <= code < map[hi] and hi - lo == 2
 
142
    if map[lo] == code:
 
143
      return lo
 
144
    else:
 
145
      map[hi:hi] = [code, map[hi - 1].copy()]
 
146
      #self.check() ###
 
147
      return hi
 
148
  
 
149
  def get_special(self, event):
 
150
    """
 
151
    Get state set for special event, adding a new entry if necessary.
 
152
    """
 
153
    special = self.special
 
154
    set = special.get(event, None)
 
155
    if not set:
 
156
      set = {}
 
157
      special[event] = set
 
158
    return set
 
159
 
 
160
  # --------------------- Conversion methods -----------------------
 
161
  
 
162
  def __str__(self):
 
163
    map_strs = []
 
164
    map = self.map
 
165
    n = len(map)
 
166
    i = 0
 
167
    while i < n:
 
168
      code = map[i]
 
169
      if code == -maxint:
 
170
        code_str = "-inf"
 
171
      elif code == maxint:
 
172
        code_str = "inf"
 
173
      else:
 
174
        code_str = str(code)
 
175
      map_strs.append(code_str)
 
176
      i = i + 1
 
177
      if i < n:
 
178
        map_strs.append(state_set_str(map[i]))
 
179
      i = i + 1
 
180
    special_strs = {}
 
181
    for event, set in self.special.items():
 
182
      special_strs[event] = state_set_str(set)
 
183
    return "[%s]+%s" % (
 
184
      string.join(map_strs, ","), 
 
185
      special_strs
 
186
    )
 
187
  
 
188
  # --------------------- Debugging methods -----------------------
 
189
  
 
190
  def check(self):
 
191
    """Check data structure integrity."""
 
192
    if not self.map[-3] < self.map[-1]:
 
193
      print self
 
194
      assert 0
 
195
  
 
196
  def dump(self, file):
 
197
    map = self.map
 
198
    i = 0
 
199
    n = len(map) - 1
 
200
    while i < n:
 
201
      self.dump_range(map[i], map[i + 2], map[i + 1], file)
 
202
      i = i + 2
 
203
    for event, set in self.special.items():
 
204
      if set:
 
205
        if not event:
 
206
          event = 'empty'
 
207
        self.dump_trans(event, set, file)
 
208
  
 
209
  def dump_range(self, code0, code1, set, file):
 
210
    if set:
 
211
      if code0 == -maxint:
 
212
        if code1 == maxint:
 
213
          k = "any"
 
214
        else:
 
215
          k = "< %s" % self.dump_char(code1)
 
216
      elif code1 == maxint:
 
217
        k = "> %s" % self.dump_char(code0 - 1)
 
218
      elif code0 == code1 - 1:
 
219
        k = self.dump_char(code0)
 
220
      else:
 
221
        k = "%s..%s" % (self.dump_char(code0), 
 
222
          self.dump_char(code1 - 1))
 
223
      self.dump_trans(k, set, file)
 
224
  
 
225
  def dump_char(self, code):
 
226
    if 0 <= code <= 255:
 
227
      return repr(chr(code))
 
228
    else:
 
229
      return "chr(%d)" % code
 
230
  
 
231
  def dump_trans(self, key, set, file):
 
232
    file.write("      %s --> %s\n" % (key, self.dump_set(set)))
 
233
  
 
234
  def dump_set(self, set):
 
235
    return state_set_str(set)
 
236
 
 
237
#
 
238
#   State set manipulation functions
 
239
#
 
240
 
 
241
#def merge_state_sets(set1, set2):
 
242
#               for state in set2.keys():
 
243
#                       set1[state] = 1
 
244
 
 
245
def state_set_str(set):
 
246
  state_list = set.keys()
 
247
  str_list = []
 
248
  for state in state_list:
 
249
    str_list.append("S%d" % state.number)
 
250
  return "[%s]" % string.join(str_list, ",")
 
251
  
 
252
    
 
253