FCL/sf/adapt/qemu: comparison symbian-qemu-0.9.1-12/python-2.6.1/Parser/spark.py

equal deleted inserted replaced

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