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