« back to all changes in this revision
Viewing changes to pymeta/runtime.py
- browse files at revision 40
- compare with another revision
- download diff
- download tarball
- view history from revision 40
- Committer: Allen Short
- Date: 2008-07-11 19:08:37 UTC
- Revision ID: washort@divmod.com-20080711190837-i2n635hhl5mvlx2v
JS-style input buffer. Seems slightly faster.
- files modified:
- pymeta/boot.py
added
removed
pymeta/runtime.py
29
29
"""
30
30
raise TypeError("Characters are not iterable")
31
31
32
class IterBuffer(object):
32
class InputStream(object):
33
33
"""
34
Wrapper for an iterable that allows pushing items onto it. The basic input
35
mechanism used by OMeta grammars.
34
The basic input mechanism used by OMeta grammars.
36
35
"""
37
36
38
def __init__(self, iterable):
37
def fromIterable(cls, iterable):
39
38
"""
40
39
@param iterable: Any iterable Python object.
41
40
"""
42
self.original = iterable
43
41
if isinstance(iterable, str):
44
self.iterable = (character(c) for c in iterable)
42
data = [character(c) for c in iterable]
45
43
elif isinstance(iterable, unicode):
46
self.iterable = (unicodeCharacter(c) for c in iterable)
44
data = [unicodeCharacter(c) for c in iterable]
47
45
else:
48
self.iterable = iter(iterable)
49
self.buffer = []
50
self.markBuffers = []
51
self.markPositions = []
52
self.position = 0
46
data = list(iterable)
47
return cls(data, 0)
48
fromIterable = classmethod(fromIterable)
49
50
def __init__(self, data, position):
51
self.data = data
52
self.position = position
53
53
self.memo = {}
54
self.args = []
55
56
57
def getMemo(self, name):
58
"""
59
Returns the memo record for the named rule.
60
@param name: A rule name.
61
"""
62
m = self.memo.get(self.position, None)
63
if m:
64
return m.get(name, None)
65
66
67
def setMemo(self, pos, name, rec):
68
"""
69
Store a memo record for the given value and position for the given
70
rule.
71
@param pos: A position in the input.
72
@param name: A rule name.
73
@param rec: A memo record.
74
"""
75
self.memo.setdefault(pos, {})[name] = rec
76
return rec
77
78
79
def __iter__(self):
80
return self
81
82
83
def next(self):
84
"""
85
Fetch the next item in the stream.
86
"""
87
if self.args:
88
val = self.args.pop()
89
else:
90
if self.buffer:
91
val = self.buffer.pop()
92
else:
93
val = self.iterable.next()
94
for buf in self.markBuffers:
95
buf.append(val)
96
self.position += 1
97
self.lastThing = val
98
return val
99
54
55
def head(self):
56
if self.position >= len(self.data):
57
raise IndexError("out of range")
58
return self.data[self.position]
59
60
def tail(self):
61
return InputStream(self.data, self.position+1)
100
62
101
63
def prev(self):
102
"""
103
Rewind by a single item.
104
"""
105
self.buffer.append(self.lastThing)
106
for buf in self.markBuffers:
107
if buf:
108
del buf[-1]
109
self.position -= 1
110
del self.lastThing
111
112
def push(self, obj):
113
"""
114
Push an object onto the stream, such that it will be returned on the
115
next call to next().
116
"""
117
self.position -= 1
118
self.args.append(obj)
119
if self.position in self.memo:
120
self.memo[self.position] = {}
121
122
def mark(self):
123
"""
124
Mark a position in the stream.
125
"""
126
self.markPositions.append(self.position)
127
self.markBuffers.append([])
128
return len(self.markBuffers)-1
129
130
131
def unmark(self, mark):
132
"""
133
Register disinterest in returning to a previously marked stream
134
position.
135
"""
136
del self.markBuffers[mark:]
137
del self.markPositions[mark:]
138
139
140
def rewind(self, mark):
141
"""
142
Return to a previously marked position in the stream.
143
"""
144
saved = self.markBuffers[mark][::-1]
145
self.buffer.extend(saved)
146
self.position = self.markPositions[mark]
147
self.unmark(mark)
148
if len(saved) > 0:
149
for buf in self.markBuffers:
150
del buf[-len(saved):]
151
152
153
def seekForwardTo(self, position):
154
"""
155
Advance until the input reaches the requested position.
156
"""
157
while position > self.position:
158
self.next()
64
return InputStream(self.data, self.position-1)
65
66
def getMemo(self, name):
67
"""
68
Returns the memo record for the named rule.
69
@param name: A rule name.
70
"""
71
return self.memo.get(name, None)
72
73
74
def setMemo(self, name, rec):
75
"""
76
Store a memo record for the given value and position for the given
77
rule.
78
@param name: A rule name.
79
@param rec: A memo record.
80
"""
81
self.memo[name] = rec
82
return rec
83
84
class ArgInput(object):
85
def __init__(self, arg, parent):
86
self.arg = arg
87
self.parent = parent
88
self.memo = {}
89
90
def head(self):
91
return self.arg
92
93
def tail(self):
94
return self.parent
95
96
97
def getMemo(self, name):
98
"""
99
Returns the memo record for the named rule.
100
@param name: A rule name.
101
"""
102
return self.memo.get(name, None)
103
104
105
def setMemo(self, name, rec):
106
"""
107
Store a memo record for the given value and position for the given
108
rule.
109
@param name: A rule name.
110
@param rec: A memo record.
111
"""
112
self.memo[name] = rec
113
return rec
114
159
115
160
116
class LeftRecursion(object):
161
117
"""
176
132
@param globals: A dictionary of names to objects, for use in evaluating
177
133
embedded Python expressions.
178
134
"""
179
self.input = IterBuffer(string)
135
self.input = InputStream.fromIterable(string)
180
136
self.locals = {}
181
137
if self.globals is None:
182
138
if globals is None:
193
149
"""
194
150
r = getattr(super(self.__class__, self), "rule_"+ruleName, None)
195
151
if r is not None:
196
self.input.setMemo(self.input.position, ruleName, None)
152
self.input.setMemo(ruleName, None)
197
153
return self._apply(r, ruleName, args)
198
154
else:
199
155
raise NameError("No rule named '%s'" %(ruleName,))
207
163
r = getattr(self, "rule_"+ruleName, None)
208
164
if r is not None:
209
165
return self._apply(r, ruleName, args)
166
210
167
else:
211
168
raise NameError("No rule named '%s'" %(ruleName,))
212
169
221
178
if args:
222
179
if rule.func_code.co_argcount - 1 != len(args):
223
180
for arg in args[::-1]:
224
self.input.push(arg)
181
self.input = ArgInput(arg, self.input)
225
182
return rule()
226
183
else:
227
184
return rule(*args)
228
185
memoRec = self.input.getMemo(ruleName)
229
186
if memoRec is None:
230
m = self.input.mark()
231
oldPosition = self.input.position
187
oldPosition = self.input
232
188
lr = LeftRecursion()
233
memoRec = self.input.setMemo(self.input.position, ruleName, lr)
189
memoRec = self.input.setMemo(ruleName, lr)
234
190
235
memoRec = self.input.setMemo(self.input.position, ruleName,
236
[rule(), self.input.position])
191
memoRec = self.input.setMemo(ruleName,
192
[rule(), self.input])
237
193
if lr.detected:
238
sentinel = self.input.position
239
self.input.rewind(m)
194
sentinel = self.input
240
195
while True:
241
196
try:
242
m = self.input.mark()
197
self.input = oldPosition
243
198
ans = rule()
244
if (self.input.position == sentinel):
199
if (self.input == sentinel):
245
200
break
246
201
247
memoRec = self.input.setMemo(oldPosition, ruleName,
248
[ans, self.input.position])
249
self.input.rewind(m)
202
memoRec = oldPosition.setMemo(ruleName,
203
[ans, self.input])
250
204
except ParseError:
251
205
break
252
self.input.unmark(m)
206
self.input = oldPosition
253
207
254
208
elif isinstance(memoRec, LeftRecursion):
255
209
memoRec.detected = True
256
210
raise ParseError()
257
self.input.seekForwardTo(memoRec[1])
211
self.input = memoRec[1]
258
212
return memoRec[0]
259
213
260
214
263
217
Match a single item from the input of any kind.
264
218
"""
265
219
try:
266
return self.input.next()
267
except StopIteration:
220
h = self.input.head()
221
self.input = self.input.tail()
222
return h
223
except IndexError:
268
224
raise ParseError()
269
225
270
226
def exactly(self, wanted):
273
229
274
230
@param wanted: What to match.
275
231
"""
232
i = self.input
276
233
try:
277
val = self.input.next()
278
except StopIteration:
234
val = self.input.head()
235
self.input = self.input.tail()
236
except IndexError:
279
237
raise ParseError()
280
238
if wanted == val:
281
239
return wanted
282
240
else:
283
self.input.prev()
241
self.input = i
284
242
raise ParseError()
285
243
286
244
rule_exactly = exactly
296
254
ans = list(initial)
297
255
while True:
298
256
try:
299
m = self.input.mark()
257
m = self.input
300
258
ans.append(fn())
301
259
except ParseError:
302
self.input.rewind(m)
260
self.input = m
303
261
break
304
else:
305
self.input.unmark(m)
306
262
return ans
307
263
308
264
def _or(self, fns):
314
270
"""
315
271
for f in fns:
316
272
try:
317
m = self.input.mark()
273
m = self.input
318
274
ret = f()
319
self.input.unmark(m)
320
275
return ret
321
276
except ParseError:
322
self.input.rewind(m)
277
self.input = m
323
278
raise ParseError()
324
279
325
280
def _not(self, fn):
328
283
329
284
@param fn: A callable of no arguments.
330
285
"""
331
m = self.input.mark()
286
m = self.input
332
287
try:
333
288
fn()
334
289
except ParseError:
335
self.input.rewind(m)
290
self.input = m
336
291
return True
337
292
else:
338
293
raise ParseError()
341
296
"""
342
297
Consume input until a non-whitespace character is reached.
343
298
"""
344
for c in self.input:
345
if not c.isspace():
346
self.input.prev()
299
while True:
300
try:
301
c = self.input.head()
302
except IndexError:
303
break
304
t = self.input.tail()
305
if c.isspace():
306
self.input = t
307
else:
347
308
break
348
309
return True
349
310
rule_spaces = eatWhitespace
366
327
367
328
@param expr: A callable of no arguments.
368
329
"""
330
v = self.rule_anything()
369
331
oldInput = self.input
370
m = self.input.mark()
371
332
try:
372
try:
373
v = self.rule_anything()
374
list = IterBuffer(v)
375
self.input = list
376
except TypeError:
377
oldInput.rewind(m)
378
raise ParseError()
379
else:
380
oldInput.unmark(m)
381
r = expr()
382
self.end()
383
return v
384
finally:
385
self.input = oldInput
333
self.input = InputStream.fromIterable(v)
334
except TypeError:
335
raise ParseError()
336
r = expr()
337
self.end()
338
self.input = oldInput
339
return v
386
340
387
341
388
342
def end(self):
401
355
@param f: A callable of no arguments.
402
356
"""
403
357
try:
404
m = self.input.mark()
358
m = self.input
405
359
x = f()
406
360
return x
407
361
finally:
408
self.input.rewind(m)
362
self.input = m
409
363
410
364
411
365
def token(self, tok):
412
366
"""
413
367
Match and return the given string, consuming any preceding whitespace.
414
368
"""
415
m = self.input.mark()
369
m = self.input
416
370
try:
417
371
self.eatWhitespace()
418
372
for c in tok:
419
373
self.exactly(c)
420
self.input.unmark(m)
421
374
return tok
422
375
except ParseError:
423
self.input.rewind(m)
376
self.input = m
424
377
raise
425
378
426
379
rule_token = token
430
383
Match a single letter.
431
384
"""
432
385
try:
433
x = self.input.next()
386
x = self.input.head()
434
387
if x.isalpha():
388
self.input = self.input.tail()
435
389
return x
436
390
else:
437
self.input.prev()
438
raise ParseError
439
except StopIteration:
440
raise ParseError
391
raise ParseError()
392
except IndexError:
393
raise ParseError()
441
394
442
395
rule_letter = letter
443
396
446
399
Match a single alphanumeric character.
447
400
"""
448
401
try:
449
x = self.input.next()
450
except StopIteration:
402
x = self.input.head()
403
except IndexError:
451
404
raise ParseError()
452
405
if x.isalnum() or x == '_':
406
self.input = self.input.tail()
453
407
return x
454
408
else:
455
self.input.prev()
456
409
raise ParseError()
457
410
458
411
rule_letterOrDigit = letterOrDigit
462
415
Match a single digit.
463
416
"""
464
417
try:
465
x = self.input.next()
466
except StopIteration:
418
x = self.input.head()
419
except IndexError:
467
420
raise ParseError()
468
421
if x.isdigit():
422
self.input = self.input.tail()
469
423
return x
470
424
else:
471
self.input.prev()
472
425
raise ParseError()
473
426
474
427
rule_digit = digit
483
436
delimiters = { "(": ")", "[": "]", "{": "}"}
484
437
stack = []
485
438
expr = []
486
for c in self.input:
439
while True:
440
try:
441
c = self.rule_anything()
442
except ParseError:
443
endchar = None
444
break
487
445
if c in endChars and len(stack) == 0:
488
446
endchar = c
489
447
break
496
454
elif c in delimiters.values():
497
455
raise ParseError()
498
456
elif c in "\"'":
499
for strc in self.input:
457
while True:
458
strc = self.rule_anything()
500
459
expr.append(strc)
501
460
if strc == c:
502
461
break
503
else:
504
endchar = None
505
462
if len(stack) > 0:
506
463
raise ParseError()
507
464
return ''.join(expr).strip(), endchar
Loggerhead is a web-based interface for Breezy
Version: 2.0.1