1 # Copyright (c) 1998-2000 John Aycock
3 # Permission is hereby granted, free of charge, to any person obtaining
4 # a copy of this software and associated documentation files (the
5 # "Software"), to deal in the Software without restriction, including
6 # without limitation the rights to use, copy, modify, merge, publish,
7 # distribute, sublicense, and/or sell copies of the Software, and to
8 # permit persons to whom the Software is furnished to do so, subject to
9 # the following conditions:
11 # The above copyright notice and this permission notice shall be
12 # included in all copies or substantial portions of the Software.
14 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 __version__ = 'SPARK-0.6.1'
27 def _namelist(instance):
28 namelist, namedict, classlist = [], {}, [instance.__class__]
33 if name not in namedict:
40 pattern = self.reflect()
41 self.re = re.compile(pattern, re.VERBOSE)
44 for name, number in self.re.groupindex.items():
45 self.index2func[number-1] = getattr(self, 't_' + name)
47 def makeRE(self, name):
48 doc = getattr(self, name).__doc__
49 rv = '(?P<%s>%s)' % (name[2:], doc)
54 for name in _namelist(self):
55 if name[:2] == 't_' and name != 't_default':
56 rv.append(self.makeRE(name))
58 rv.append(self.makeRE('t_default'))
61 def error(self, s, pos):
62 print "Lexical error at position %s" % pos
65 def tokenize(self, s):
69 m = self.re.match(s, pos)
74 for i in range(len(groups)):
75 if groups[i] and i in self.index2func:
76 self.index2func[i](groups[i])
79 def t_default(self, s):
84 def __init__(self, start):
89 self.startRule = self.augment(start)
96 # A hook for GenericASTBuilder and GenericASTMatcher.
98 def preprocess(self, rule, func): return rule, func
100 def addRule(self, doc, func):
104 for i in range(len(rules)):
105 if rules[i] == '::=':
107 index.append(len(rules))
109 for i in range(len(index)-1):
110 lhs = rules[index[i]]
111 rhs = rules[index[i]+2:index[i+1]]
112 rule = (lhs, tuple(rhs))
114 rule, fn = self.preprocess(rule, func)
116 if lhs in self.rules:
117 self.rules[lhs].append(rule)
119 self.rules[lhs] = [ rule ]
120 self.rule2func[rule] = fn
121 self.rule2name[rule] = func.__name__[2:]
122 self.ruleschanged = 1
124 def collectRules(self):
125 for name in _namelist(self):
127 func = getattr(self, name)
129 self.addRule(doc, func)
131 def augment(self, start):
133 # Tempting though it is, this isn't made into a call
134 # to self.addRule() because the start rule shouldn't
135 # be subject to preprocessing.
137 startRule = (self._START, ( start, self._EOF ))
138 self.rule2func[startRule] = lambda args: args[0]
139 self.rules[self._START] = [ startRule ]
140 self.rule2name[startRule] = ''
147 for rulelist in self.rules.values():
148 for lhs, rhs in rulelist:
149 if lhs not in self.first:
153 self.first[lhs][None] = 1
157 if sym not in self.rules:
158 self.first[lhs][sym] = 1
160 union[(sym, lhs)] = 1
164 for src, dest in union.keys():
165 destlen = len(self.first[dest])
166 self.first[dest].update(self.first[src])
167 if len(self.first[dest]) != destlen:
171 # An Earley parser, as per J. Earley, "An Efficient Context-Free
172 # Parsing Algorithm", CACM 13(2), pp. 94-102. Also J. C. Earley,
173 # "An Efficient Context-Free Parsing Algorithm", Ph.D. thesis,
174 # Carnegie-Mellon University, August 1968, p. 27.
177 def typestring(self, token):
180 def error(self, token):
181 print "Syntax error at or near `%s' token" % token
184 def parse(self, tokens):
186 tokens.append(self._EOF)
187 states = { 0: [ (self.startRule, 0, 0) ] }
189 if self.ruleschanged:
192 for i in xrange(len(tokens)):
197 self.buildState(tokens[i], states, i, tree)
199 #_dump(tokens, states)
201 if i < len(tokens)-1 or states[i+1] != [(self.startRule, 2, 0)]:
203 self.error(tokens[i-1])
204 rv = self.buildTree(tokens, tree, ((self.startRule, 2, 0), i+1))
208 def buildState(self, token, states, i, tree):
214 rule, pos, parent = item
218 # A -> a . (completer)
222 needsCompletion[lhs] = (item, i)
224 for pitem in states[parent]:
228 prule, ppos, pparent = pitem
231 if prhs[ppos:ppos+1] == (lhs,):
237 tree[(new, i)] = [(item, i)]
239 tree[(new, i)].append((item, i))
245 # A -> a . B (predictor)
247 if nextSym in self.rules:
249 # Work on completer step some more; for rules
250 # with empty RHS, the "parent state" is the
251 # current state we're adding Earley items to,
252 # so the Earley items the completer step needs
253 # may not all be present when it runs.
255 if nextSym in needsCompletion:
256 new = (rule, pos+1, parent)
257 olditem_i = needsCompletion[nextSym]
260 tree[(new, i)] = [olditem_i]
262 tree[(new, i)].append(olditem_i)
265 # Has this been predicted already?
267 if nextSym in predicted:
269 predicted[nextSym] = 1
271 ttype = token is not self._EOF and \
272 self.typestring(token) or \
274 if ttype is not None:
276 # Even smarter predictor, when the
277 # token's type is known. The code is
278 # grungy, but runs pretty fast. Three
279 # cases are looked for: rules with
280 # empty RHS; first symbol on RHS is a
281 # terminal; first symbol on RHS is a
282 # nonterminal (and isn't nullable).
284 for prule in self.rules[nextSym]:
291 if prhs0 not in self.rules:
297 first = self.first[prhs0]
298 if None not in first and \
304 for prule in self.rules[nextSym]:
306 # Smarter predictor, as per Grune &
307 # Jacobs' _Parsing Techniques_. Not
308 # as good as FIRST sets though.
311 if len(prhs) > 0 and \
312 prhs[0] not in self.rules and \
315 state.append((prule, 0, i))
318 # A -> a . c (scanner)
320 elif token == nextSym:
321 #assert new not in states[i+1]
322 states[i+1].append((rule, pos+1, parent))
324 def buildTree(self, tokens, tree, root):
326 self.buildTree_r(stack, tokens, -1, tree, root)
329 def buildTree_r(self, stack, tokens, tokpos, tree, root):
330 (rule, pos, parent), state = root
333 want = ((rule, pos, parent), state)
336 # Since pos > 0, it didn't come from closure,
337 # and if it isn't in tree[], then there must
338 # be a terminal symbol to the left of the dot.
339 # (It must be from a "scanner" step.)
343 stack.insert(0, tokens[tokpos])
347 # There's a NT to the left of the dot.
348 # Follow the tree pointer recursively (>1
349 # tree pointers from it indicates ambiguity).
350 # Since the item must have come about from a
351 # "completer" step, the state where the item
352 # came from must be the parent state of the
353 # item the tree pointer points to.
355 children = tree[want]
356 if len(children) > 1:
357 child = self.ambiguity(children)
361 tokpos = self.buildTree_r(stack,
365 (crule, cpos, cparent), cstate = child
369 result = self.rule2func[rule](stack[:len(rhs)])
370 stack[:len(rhs)] = [result]
373 def ambiguity(self, children):
375 # XXX - problem here and in collectRules() if the same
376 # rule appears in >1 method. But in that case the
377 # user probably gets what they deserve :-) Also
378 # undefined results if rules causing the ambiguity
379 # appear in the same method.
383 for i in range(len(children)):
384 ((rule, pos, parent), index) = children[i]
386 name = self.rule2name[rule]
387 sortlist.append((len(rhs), name))
390 list = map(lambda (a,b): b, sortlist)
391 return children[name2index[self.resolve(list)]]
393 def resolve(self, list):
395 # Resolve ambiguity in favor of the shortest RHS.
396 # Since we walk the tree from the top down, this
397 # should effectively resolve in favor of a "shift".
402 # GenericASTBuilder automagically constructs a concrete/abstract syntax tree
403 # for a given input. The extra argument is a class (not an instance!)
404 # which supports the "__setslice__" and "__len__" methods.
406 # XXX - silently overrides any user code in methods.
409 class GenericASTBuilder(GenericParser):
410 def __init__(self, AST, start):
411 GenericParser.__init__(self, start)
414 def preprocess(self, rule, func):
415 rebind = lambda lhs, self=self: \
416 lambda args, lhs=lhs, self=self: \
417 self.buildASTNode(args, lhs)
419 return rule, rebind(lhs)
421 def buildASTNode(self, args, lhs):
424 if isinstance(arg, self.AST):
427 children.append(self.terminal(arg))
428 return self.nonterminal(lhs, children)
430 def terminal(self, token): return token
432 def nonterminal(self, type, args):
434 rv[:len(args)] = args
438 # GenericASTTraversal is a Visitor pattern according to Design Patterns. For
439 # each node it attempts to invoke the method n_<node type>, falling
440 # back onto the default() method if the n_* can't be found. The preorder
441 # traversal also looks for an exit hook named n_<node type>_exit (no default
442 # routine is called if it's not found). To prematurely halt traversal
443 # of a subtree, call the prune() method -- this only makes sense for a
444 # preorder traversal. Node type is determined via the typestring() method.
447 class GenericASTTraversalPruningException:
450 class GenericASTTraversal:
451 def __init__(self, ast):
454 def typestring(self, node):
458 raise GenericASTTraversalPruningException
460 def preorder(self, node=None):
465 name = 'n_' + self.typestring(node)
466 if hasattr(self, name):
467 func = getattr(self, name)
471 except GenericASTTraversalPruningException:
477 name = name + '_exit'
478 if hasattr(self, name):
479 func = getattr(self, name)
482 def postorder(self, node=None):
489 name = 'n_' + self.typestring(node)
490 if hasattr(self, name):
491 func = getattr(self, name)
497 def default(self, node):
501 # GenericASTMatcher. AST nodes must have "__getitem__" and "__cmp__"
504 # XXX - makes assumptions about how GenericParser walks the parse tree.
507 class GenericASTMatcher(GenericParser):
508 def __init__(self, start, ast):
509 GenericParser.__init__(self, start)
512 def preprocess(self, rule, func):
513 rebind = lambda func, self=self: \
514 lambda args, func=func, self=self: \
515 self.foundMatch(args, func)
520 return (lhs, tuple(rhslist)), rebind(func)
522 def foundMatch(self, args, func):
526 def match_r(self, node):
527 self.input.insert(0, node)
532 self.input.insert(0, '(')
533 children = children + 1
537 self.input.insert(0, ')')
539 def match(self, ast=None):
545 self.parse(self.input)
547 def resolve(self, list):
549 # Resolve ambiguity in favor of the longest RHS.
553 def _dump(tokens, states):
554 for i in range(len(states)):
556 for (lhs, rhs), pos, parent in states[i]:
557 print '\t', lhs, '::=',
558 print ' '.join(rhs[:pos]),
560 print ' '.join(rhs[pos:]),
564 print 'token', str(tokens[i])