+++ /dev/null
-# Copyright (c) 1998-2002 John Aycock\r
-#\r
-# Permission is hereby granted, free of charge, to any person obtaining\r
-# a copy of this software and associated documentation files (the\r
-# "Software"), to deal in the Software without restriction, including\r
-# without limitation the rights to use, copy, modify, merge, publish,\r
-# distribute, sublicense, and/or sell copies of the Software, and to\r
-# permit persons to whom the Software is furnished to do so, subject to\r
-# the following conditions:\r
-#\r
-# The above copyright notice and this permission notice shall be\r
-# included in all copies or substantial portions of the Software.\r
-#\r
-# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
-# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
-# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.\r
-# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY\r
-# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,\r
-# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE\r
-# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\r
-\r
-__version__ = 'SPARK-0.7 (pre-alpha-5)'\r
-\r
-import re\r
-import string\r
-\r
-def _namelist(instance):\r
- namelist, namedict, classlist = [], {}, [instance.__class__]\r
- for c in classlist:\r
- for b in c.__bases__:\r
- classlist.append(b)\r
- for name in c.__dict__.keys():\r
- if not namedict.has_key(name):\r
- namelist.append(name)\r
- namedict[name] = 1\r
- return namelist\r
-\r
-class GenericScanner:\r
- def __init__(self, flags=0):\r
- pattern = self.reflect()\r
- self.re = re.compile(pattern, re.VERBOSE|flags)\r
-\r
- self.index2func = {}\r
- for name, number in self.re.groupindex.items():\r
- self.index2func[number-1] = getattr(self, 't_' + name)\r
-\r
- def makeRE(self, name):\r
- doc = getattr(self, name).__doc__\r
- rv = '(?P<%s>%s)' % (name[2:], doc)\r
- return rv\r
-\r
- def reflect(self):\r
- rv = []\r
- for name in _namelist(self):\r
- if name[:2] == 't_' and name != 't_default':\r
- rv.append(self.makeRE(name))\r
-\r
- rv.append(self.makeRE('t_default'))\r
- return string.join(rv, '|')\r
-\r
- def error(self, s, pos):\r
- print "Lexical error at position %s" % pos\r
- raise SystemExit\r
-\r
- def tokenize(self, s):\r
- pos = 0\r
- n = len(s)\r
- while pos < n:\r
- m = self.re.match(s, pos)\r
- if m is None:\r
- self.error(s, pos)\r
-\r
- groups = m.groups()\r
- for i in range(len(groups)):\r
- if groups[i] and self.index2func.has_key(i):\r
- self.index2func[i](groups[i])\r
- pos = m.end()\r
-\r
- def t_default(self, s):\r
- r'( . | \n )+'\r
- print "Specification error: unmatched input"\r
- raise SystemExit\r
-\r
-#\r
-# Extracted from GenericParser and made global so that [un]picking works.\r
-#\r
-class _State:\r
- def __init__(self, stateno, items):\r
- self.T, self.complete, self.items = [], [], items\r
- self.stateno = stateno\r
-\r
-class GenericParser:\r
- #\r
- # An Earley parser, as per J. Earley, "An Efficient Context-Free\r
- # Parsing Algorithm", CACM 13(2), pp. 94-102. Also J. C. Earley,\r
- # "An Efficient Context-Free Parsing Algorithm", Ph.D. thesis,\r
- # Carnegie-Mellon University, August 1968. New formulation of\r
- # the parser according to J. Aycock, "Practical Earley Parsing\r
- # and the SPARK Toolkit", Ph.D. thesis, University of Victoria,\r
- # 2001, and J. Aycock and R. N. Horspool, "Practical Earley\r
- # Parsing", unpublished paper, 2001.\r
- #\r
-\r
- def __init__(self, start):\r
- self.rules = {}\r
- self.rule2func = {}\r
- self.rule2name = {}\r
- self.collectRules()\r
- self.augment(start)\r
- self.ruleschanged = 1\r
-\r
- _NULLABLE = '\e_'\r
- _START = 'START'\r
- _BOF = '|-'\r
-\r
- #\r
- # When pickling, take the time to generate the full state machine;\r
- # some information is then extraneous, too. Unfortunately we\r
- # can't save the rule2func map.\r
- #\r
- def __getstate__(self):\r
- if self.ruleschanged:\r
- #\r
- # XXX - duplicated from parse()\r
- #\r
- self.computeNull()\r
- self.newrules = {}\r
- self.new2old = {}\r
- self.makeNewRules()\r
- self.ruleschanged = 0\r
- self.edges, self.cores = {}, {}\r
- self.states = { 0: self.makeState0() }\r
- self.makeState(0, self._BOF)\r
- #\r
- # XXX - should find a better way to do this..\r
- #\r
- changes = 1\r
- while changes:\r
- changes = 0\r
- for k, v in self.edges.items():\r
- if v is None:\r
- state, sym = k\r
- if self.states.has_key(state):\r
- self.goto(state, sym)\r
- changes = 1\r
- rv = self.__dict__.copy()\r
- for s in self.states.values():\r
- del s.items\r
- del rv['rule2func']\r
- del rv['nullable']\r
- del rv['cores']\r
- return rv\r
-\r
- def __setstate__(self, D):\r
- self.rules = {}\r
- self.rule2func = {}\r
- self.rule2name = {}\r
- self.collectRules()\r
- start = D['rules'][self._START][0][1][1] # Blech.\r
- self.augment(start)\r
- D['rule2func'] = self.rule2func\r
- D['makeSet'] = self.makeSet_fast\r
- self.__dict__ = D\r
-\r
- #\r
- # A hook for GenericASTBuilder and GenericASTMatcher. Mess\r
- # thee not with this; nor shall thee toucheth the _preprocess\r
- # argument to addRule.\r
- #\r
- def preprocess(self, rule, func): return rule, func\r
-\r
- def addRule(self, doc, func, _preprocess=1):\r
- fn = func\r
- rules = string.split(doc)\r
-\r
- index = []\r
- for i in range(len(rules)):\r
- if rules[i] == '::=':\r
- index.append(i-1)\r
- index.append(len(rules))\r
-\r
- for i in range(len(index)-1):\r
- lhs = rules[index[i]]\r
- rhs = rules[index[i]+2:index[i+1]]\r
- rule = (lhs, tuple(rhs))\r
-\r
- if _preprocess:\r
- rule, fn = self.preprocess(rule, func)\r
-\r
- if self.rules.has_key(lhs):\r
- self.rules[lhs].append(rule)\r
- else:\r
- self.rules[lhs] = [ rule ]\r
- self.rule2func[rule] = fn\r
- self.rule2name[rule] = func.__name__[2:]\r
- self.ruleschanged = 1\r
-\r
- def collectRules(self):\r
- for name in _namelist(self):\r
- if name[:2] == 'p_':\r
- func = getattr(self, name)\r
- doc = func.__doc__\r
- self.addRule(doc, func)\r
-\r
- def augment(self, start):\r
- rule = '%s ::= %s %s' % (self._START, self._BOF, start)\r
- self.addRule(rule, lambda args: args[1], 0)\r
-\r
- def computeNull(self):\r
- self.nullable = {}\r
- tbd = []\r
-\r
- for rulelist in self.rules.values():\r
- lhs = rulelist[0][0]\r
- self.nullable[lhs] = 0\r
- for rule in rulelist:\r
- rhs = rule[1]\r
- if len(rhs) == 0:\r
- self.nullable[lhs] = 1\r
- continue\r
- #\r
- # We only need to consider rules which\r
- # consist entirely of nonterminal symbols.\r
- # This should be a savings on typical\r
- # grammars.\r
- #\r
- for sym in rhs:\r
- if not self.rules.has_key(sym):\r
- break\r
- else:\r
- tbd.append(rule)\r
- changes = 1\r
- while changes:\r
- changes = 0\r
- for lhs, rhs in tbd:\r
- if self.nullable[lhs]:\r
- continue\r
- for sym in rhs:\r
- if not self.nullable[sym]:\r
- break\r
- else:\r
- self.nullable[lhs] = 1\r
- changes = 1\r
-\r
- def makeState0(self):\r
- s0 = _State(0, [])\r
- for rule in self.newrules[self._START]:\r
- s0.items.append((rule, 0))\r
- return s0\r
-\r
- def finalState(self, tokens):\r
- #\r
- # Yuck.\r
- #\r
- if len(self.newrules[self._START]) == 2 and len(tokens) == 0:\r
- return 1\r
- start = self.rules[self._START][0][1][1]\r
- return self.goto(1, start)\r
-\r
- def makeNewRules(self):\r
- worklist = []\r
- for rulelist in self.rules.values():\r
- for rule in rulelist:\r
- worklist.append((rule, 0, 1, rule))\r
-\r
- for rule, i, candidate, oldrule in worklist:\r
- lhs, rhs = rule\r
- n = len(rhs)\r
- while i < n:\r
- sym = rhs[i]\r
- if not self.rules.has_key(sym) or \\r
- not self.nullable[sym]:\r
- candidate = 0\r
- i = i + 1\r
- continue\r
-\r
- newrhs = list(rhs)\r
- newrhs[i] = self._NULLABLE+sym\r
- newrule = (lhs, tuple(newrhs))\r
- worklist.append((newrule, i+1,\r
- candidate, oldrule))\r
- candidate = 0\r
- i = i + 1\r
- else:\r
- if candidate:\r
- lhs = self._NULLABLE+lhs\r
- rule = (lhs, rhs)\r
- if self.newrules.has_key(lhs):\r
- self.newrules[lhs].append(rule)\r
- else:\r
- self.newrules[lhs] = [ rule ]\r
- self.new2old[rule] = oldrule\r
-\r
- def typestring(self, token):\r
- return None\r
-\r
- def error(self, token):\r
- print "Syntax error at or near `%s' token" % token\r
- raise SystemExit\r
-\r
- def parse(self, tokens):\r
- sets = [ [(1,0), (2,0)] ]\r
- self.links = {}\r
-\r
- if self.ruleschanged:\r
- self.computeNull()\r
- self.newrules = {}\r
- self.new2old = {}\r
- self.makeNewRules()\r
- self.ruleschanged = 0\r
- self.edges, self.cores = {}, {}\r
- self.states = { 0: self.makeState0() }\r
- self.makeState(0, self._BOF)\r
-\r
- for i in xrange(len(tokens)):\r
- sets.append([])\r
-\r
- if sets[i] == []:\r
- break\r
- self.makeSet(tokens[i], sets, i)\r
- else:\r
- sets.append([])\r
- self.makeSet(None, sets, len(tokens))\r
-\r
- #_dump(tokens, sets, self.states)\r
-\r
- finalitem = (self.finalState(tokens), 0)\r
- if finalitem not in sets[-2]:\r
- if len(tokens) > 0:\r
- self.error(tokens[i-1])\r
- else:\r
- self.error(None)\r
-\r
- return self.buildTree(self._START, finalitem,\r
- tokens, len(sets)-2)\r
-\r
- def isnullable(self, sym):\r
- #\r
- # For symbols in G_e only. If we weren't supporting 1.5,\r
- # could just use sym.startswith().\r
- #\r
- return self._NULLABLE == sym[0:len(self._NULLABLE)]\r
-\r
- def skip(self, (lhs, rhs), pos=0):\r
- n = len(rhs)\r
- while pos < n:\r
- if not self.isnullable(rhs[pos]):\r
- break\r
- pos = pos + 1\r
- return pos\r
-\r
- def makeState(self, state, sym):\r
- assert sym is not None\r
- #\r
- # Compute \epsilon-kernel state's core and see if\r
- # it exists already.\r
- #\r
- kitems = []\r
- for rule, pos in self.states[state].items:\r
- lhs, rhs = rule\r
- if rhs[pos:pos+1] == (sym,):\r
- kitems.append((rule, self.skip(rule, pos+1)))\r
- core = kitems\r
-\r
- core.sort()\r
- tcore = tuple(core)\r
- if self.cores.has_key(tcore):\r
- return self.cores[tcore]\r
- #\r
- # Nope, doesn't exist. Compute it and the associated\r
- # \epsilon-nonkernel state together; we'll need it right away.\r
- #\r
- k = self.cores[tcore] = len(self.states)\r
- K, NK = _State(k, kitems), _State(k+1, [])\r
- self.states[k] = K\r
- predicted = {}\r
-\r
- edges = self.edges\r
- rules = self.newrules\r
- for X in K, NK:\r
- worklist = X.items\r
- for item in worklist:\r
- rule, pos = item\r
- lhs, rhs = rule\r
- if pos == len(rhs):\r
- X.complete.append(rule)\r
- continue\r
-\r
- nextSym = rhs[pos]\r
- key = (X.stateno, nextSym)\r
- if not rules.has_key(nextSym):\r
- if not edges.has_key(key):\r
- edges[key] = None\r
- X.T.append(nextSym)\r
- else:\r
- edges[key] = None\r
- if not predicted.has_key(nextSym):\r
- predicted[nextSym] = 1\r
- for prule in rules[nextSym]:\r
- ppos = self.skip(prule)\r
- new = (prule, ppos)\r
- NK.items.append(new)\r
- #\r
- # Problem: we know K needs generating, but we\r
- # don't yet know about NK. Can't commit anything\r
- # regarding NK to self.edges until we're sure. Should\r
- # we delay committing on both K and NK to avoid this\r
- # hacky code? This creates other problems..\r
- #\r
- if X is K:\r
- edges = {}\r
-\r
- if NK.items == []:\r
- return k\r
-\r
- #\r
- # Check for \epsilon-nonkernel's core. Unfortunately we\r
- # need to know the entire set of predicted nonterminals\r
- # to do this without accidentally duplicating states.\r
- #\r
- core = predicted.keys()\r
- core.sort()\r
- tcore = tuple(core)\r
- if self.cores.has_key(tcore):\r
- self.edges[(k, None)] = self.cores[tcore]\r
- return k\r
-\r
- nk = self.cores[tcore] = self.edges[(k, None)] = NK.stateno\r
- self.edges.update(edges)\r
- self.states[nk] = NK\r
- return k\r
-\r
- def goto(self, state, sym):\r
- key = (state, sym)\r
- if not self.edges.has_key(key):\r
- #\r
- # No transitions from state on sym.\r
- #\r
- return None\r
-\r
- rv = self.edges[key]\r
- if rv is None:\r
- #\r
- # Target state isn't generated yet. Remedy this.\r
- #\r
- rv = self.makeState(state, sym)\r
- self.edges[key] = rv\r
- return rv\r
-\r
- def gotoT(self, state, t):\r
- return [self.goto(state, t)]\r
-\r
- def gotoST(self, state, st):\r
- rv = []\r
- for t in self.states[state].T:\r
- if st == t:\r
- rv.append(self.goto(state, t))\r
- return rv\r
-\r
- def add(self, set, item, i=None, predecessor=None, causal=None):\r
- if predecessor is None:\r
- if item not in set:\r
- set.append(item)\r
- else:\r
- key = (item, i)\r
- if item not in set:\r
- self.links[key] = []\r
- set.append(item)\r
- self.links[key].append((predecessor, causal))\r
-\r
- def makeSet(self, token, sets, i):\r
- cur, next = sets[i], sets[i+1]\r
-\r
- ttype = token is not None and self.typestring(token) or None\r
- if ttype is not None:\r
- fn, arg = self.gotoT, ttype\r
- else:\r
- fn, arg = self.gotoST, token\r
-\r
- for item in cur:\r
- ptr = (item, i)\r
- state, parent = item\r
- add = fn(state, arg)\r
- for k in add:\r
- if k is not None:\r
- self.add(next, (k, parent), i+1, ptr)\r
- nk = self.goto(k, None)\r
- if nk is not None:\r
- self.add(next, (nk, i+1))\r
-\r
- if parent == i:\r
- continue\r
-\r
- for rule in self.states[state].complete:\r
- lhs, rhs = rule\r
- for pitem in sets[parent]:\r
- pstate, pparent = pitem\r
- k = self.goto(pstate, lhs)\r
- if k is not None:\r
- why = (item, i, rule)\r
- pptr = (pitem, parent)\r
- self.add(cur, (k, pparent),\r
- i, pptr, why)\r
- nk = self.goto(k, None)\r
- if nk is not None:\r
- self.add(cur, (nk, i))\r
-\r
- def makeSet_fast(self, token, sets, i):\r
- #\r
- # Call *only* when the entire state machine has been built!\r
- # It relies on self.edges being filled in completely, and\r
- # then duplicates and inlines code to boost speed at the\r
- # cost of extreme ugliness.\r
- #\r
- cur, next = sets[i], sets[i+1]\r
- ttype = token is not None and self.typestring(token) or None\r
-\r
- for item in cur:\r
- ptr = (item, i)\r
- state, parent = item\r
- if ttype is not None:\r
- k = self.edges.get((state, ttype), None)\r
- if k is not None:\r
- #self.add(next, (k, parent), i+1, ptr)\r
- #INLINED --v\r
- new = (k, parent)\r
- key = (new, i+1)\r
- if new not in next:\r
- self.links[key] = []\r
- next.append(new)\r
- self.links[key].append((ptr, None))\r
- #INLINED --^\r
- #nk = self.goto(k, None)\r
- nk = self.edges.get((k, None), None)\r
- if nk is not None:\r
- #self.add(next, (nk, i+1))\r
- #INLINED --v\r
- new = (nk, i+1)\r
- if new not in next:\r
- next.append(new)\r
- #INLINED --^\r
- else:\r
- add = self.gotoST(state, token)\r
- for k in add:\r
- if k is not None:\r
- self.add(next, (k, parent), i+1, ptr)\r
- #nk = self.goto(k, None)\r
- nk = self.edges.get((k, None), None)\r
- if nk is not None:\r
- self.add(next, (nk, i+1))\r
-\r
- if parent == i:\r
- continue\r
-\r
- for rule in self.states[state].complete:\r
- lhs, rhs = rule\r
- for pitem in sets[parent]:\r
- pstate, pparent = pitem\r
- #k = self.goto(pstate, lhs)\r
- k = self.edges.get((pstate, lhs), None)\r
- if k is not None:\r
- why = (item, i, rule)\r
- pptr = (pitem, parent)\r
- #self.add(cur, (k, pparent),\r
- # i, pptr, why)\r
- #INLINED --v\r
- new = (k, pparent)\r
- key = (new, i)\r
- if new not in cur:\r
- self.links[key] = []\r
- cur.append(new)\r
- self.links[key].append((pptr, why))\r
- #INLINED --^\r
- #nk = self.goto(k, None)\r
- nk = self.edges.get((k, None), None)\r
- if nk is not None:\r
- #self.add(cur, (nk, i))\r
- #INLINED --v\r
- new = (nk, i)\r
- if new not in cur:\r
- cur.append(new)\r
- #INLINED --^\r
-\r
- def predecessor(self, key, causal):\r
- for p, c in self.links[key]:\r
- if c == causal:\r
- return p\r
- assert 0\r
-\r
- def causal(self, key):\r
- links = self.links[key]\r
- if len(links) == 1:\r
- return links[0][1]\r
- choices = []\r
- rule2cause = {}\r
- for p, c in links:\r
- rule = c[2]\r
- choices.append(rule)\r
- rule2cause[rule] = c\r
- return rule2cause[self.ambiguity(choices)]\r
-\r
- def deriveEpsilon(self, nt):\r
- if len(self.newrules[nt]) > 1:\r
- rule = self.ambiguity(self.newrules[nt])\r
- else:\r
- rule = self.newrules[nt][0]\r
- #print rule\r
-\r
- rhs = rule[1]\r
- attr = [None] * len(rhs)\r
-\r
- for i in range(len(rhs)-1, -1, -1):\r
- attr[i] = self.deriveEpsilon(rhs[i])\r
- return self.rule2func[self.new2old[rule]](attr)\r
-\r
- def buildTree(self, nt, item, tokens, k):\r
- state, parent = item\r
-\r
- choices = []\r
- for rule in self.states[state].complete:\r
- if rule[0] == nt:\r
- choices.append(rule)\r
- rule = choices[0]\r
- if len(choices) > 1:\r
- rule = self.ambiguity(choices)\r
- #print rule\r
-\r
- rhs = rule[1]\r
- attr = [None] * len(rhs)\r
-\r
- for i in range(len(rhs)-1, -1, -1):\r
- sym = rhs[i]\r
- if not self.newrules.has_key(sym):\r
- if sym != self._BOF:\r
- attr[i] = tokens[k-1]\r
- key = (item, k)\r
- item, k = self.predecessor(key, None)\r
- #elif self.isnullable(sym):\r
- elif self._NULLABLE == sym[0:len(self._NULLABLE)]:\r
- attr[i] = self.deriveEpsilon(sym)\r
- else:\r
- key = (item, k)\r
- why = self.causal(key)\r
- attr[i] = self.buildTree(sym, why[0],\r
- tokens, why[1])\r
- item, k = self.predecessor(key, why)\r
- return self.rule2func[self.new2old[rule]](attr)\r
-\r
- def ambiguity(self, rules):\r
- #\r
- # XXX - problem here and in collectRules() if the same rule\r
- # appears in >1 method. Also undefined results if rules\r
- # causing the ambiguity appear in the same method.\r
- #\r
- sortlist = []\r
- name2index = {}\r
- for i in range(len(rules)):\r
- lhs, rhs = rule = rules[i]\r
- name = self.rule2name[self.new2old[rule]]\r
- sortlist.append((len(rhs), name))\r
- name2index[name] = i\r
- sortlist.sort()\r
- list = map(lambda (a,b): b, sortlist)\r
- return rules[name2index[self.resolve(list)]]\r
-\r
- def resolve(self, list):\r
- #\r
- # Resolve ambiguity in favor of the shortest RHS.\r
- # Since we walk the tree from the top down, this\r
- # should effectively resolve in favor of a "shift".\r
- #\r
- return list[0]\r
-\r
-#\r
-# GenericASTBuilder automagically constructs a concrete/abstract syntax tree\r
-# for a given input. The extra argument is a class (not an instance!)\r
-# which supports the "__setslice__" and "__len__" methods.\r
-#\r
-# XXX - silently overrides any user code in methods.\r
-#\r
-\r
-class GenericASTBuilder(GenericParser):\r
- def __init__(self, AST, start):\r
- GenericParser.__init__(self, start)\r
- self.AST = AST\r
-\r
- def preprocess(self, rule, func):\r
- rebind = lambda lhs, self=self: \\r
- lambda args, lhs=lhs, self=self: \\r
- self.buildASTNode(args, lhs)\r
- lhs, rhs = rule\r
- return rule, rebind(lhs)\r
-\r
- def buildASTNode(self, args, lhs):\r
- children = []\r
- for arg in args:\r
- if isinstance(arg, self.AST):\r
- children.append(arg)\r
- else:\r
- children.append(self.terminal(arg))\r
- return self.nonterminal(lhs, children)\r
-\r
- def terminal(self, token): return token\r
-\r
- def nonterminal(self, type, args):\r
- rv = self.AST(type)\r
- rv[:len(args)] = args\r
- return rv\r
-\r
-#\r
-# GenericASTTraversal is a Visitor pattern according to Design Patterns. For\r
-# each node it attempts to invoke the method n_<node type>, falling\r
-# back onto the default() method if the n_* can't be found. The preorder\r
-# traversal also looks for an exit hook named n_<node type>_exit (no default\r
-# routine is called if it's not found). To prematurely halt traversal\r
-# of a subtree, call the prune() method -- this only makes sense for a\r
-# preorder traversal. Node type is determined via the typestring() method.\r
-#\r
-\r
-class GenericASTTraversalPruningException:\r
- pass\r
-\r
-class GenericASTTraversal:\r
- def __init__(self, ast):\r
- self.ast = ast\r
-\r
- def typestring(self, node):\r
- return node.type\r
-\r
- def prune(self):\r
- raise GenericASTTraversalPruningException\r
-\r
- def preorder(self, node=None):\r
- if node is None:\r
- node = self.ast\r
-\r
- try:\r
- name = 'n_' + self.typestring(node)\r
- if hasattr(self, name):\r
- func = getattr(self, name)\r
- func(node)\r
- else:\r
- self.default(node)\r
- except GenericASTTraversalPruningException:\r
- return\r
-\r
- for kid in node:\r
- self.preorder(kid)\r
-\r
- name = name + '_exit'\r
- if hasattr(self, name):\r
- func = getattr(self, name)\r
- func(node)\r
-\r
- def postorder(self, node=None):\r
- if node is None:\r
- node = self.ast\r
-\r
- for kid in node:\r
- self.postorder(kid)\r
-\r
- name = 'n_' + self.typestring(node)\r
- if hasattr(self, name):\r
- func = getattr(self, name)\r
- func(node)\r
- else:\r
- self.default(node)\r
-\r
-\r
- def default(self, node):\r
- pass\r
-\r
-#\r
-# GenericASTMatcher. AST nodes must have "__getitem__" and "__cmp__"\r
-# implemented.\r
-#\r
-# XXX - makes assumptions about how GenericParser walks the parse tree.\r
-#\r
-\r
-class GenericASTMatcher(GenericParser):\r
- def __init__(self, start, ast):\r
- GenericParser.__init__(self, start)\r
- self.ast = ast\r
-\r
- def preprocess(self, rule, func):\r
- rebind = lambda func, self=self: \\r
- lambda args, func=func, self=self: \\r
- self.foundMatch(args, func)\r
- lhs, rhs = rule\r
- rhslist = list(rhs)\r
- rhslist.reverse()\r
-\r
- return (lhs, tuple(rhslist)), rebind(func)\r
-\r
- def foundMatch(self, args, func):\r
- func(args[-1])\r
- return args[-1]\r
-\r
- def match_r(self, node):\r
- self.input.insert(0, node)\r
- children = 0\r
-\r
- for child in node:\r
- if children == 0:\r
- self.input.insert(0, '(')\r
- children = children + 1\r
- self.match_r(child)\r
-\r
- if children > 0:\r
- self.input.insert(0, ')')\r
-\r
- def match(self, ast=None):\r
- if ast is None:\r
- ast = self.ast\r
- self.input = []\r
-\r
- self.match_r(ast)\r
- self.parse(self.input)\r
-\r
- def resolve(self, list):\r
- #\r
- # Resolve ambiguity in favor of the longest RHS.\r
- #\r
- return list[-1]\r
-\r
-def _dump(tokens, sets, states):\r
- for i in range(len(sets)):\r
- print 'set', i\r
- for item in sets[i]:\r
- print '\t', item\r
- for (lhs, rhs), pos in states[item[0]].items:\r
- print '\t\t', lhs, '::=',\r
- print string.join(rhs[:pos]),\r
- print '.',\r
- print string.join(rhs[pos:])\r
- if i < len(tokens):\r
- print\r
- print 'token', str(tokens[i])\r
- print\r
projects / mirror_edk2.git / blobdiff