Logo Search packages:      
Sourcecode: eclipse-pydev version File versions  Download package

spark.py

#  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 sys
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

Generated by  Doxygen 1.6.0   Back to index