# module pyparsing.py

#

# Copyright (c) 2003-2006  Paul T. McGuire

#

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

#

#from __future__ import generators

__doc__ = \

"""

pyparsing module - Classes and methods to define and execute parsing grammars

The pyparsing module is an alternative approach to creating and executing simple grammars, 

vs. the traditional lex/yacc approach, or the use of regular expressions.  With pyparsing, you

don't need to learn a new syntax for defining grammars or matching expressions - the parsing module 

provides a library of classes that you use to construct the grammar directly in Python.

Here is a program to parse "Hello, World!" (or any greeting of the form "<salutation>, <addressee>!")::

    from pyparsing import Word, alphas

    # define grammar of a greeting

    greet = Word( alphas ) + "," + Word( alphas ) + "!" 

    hello = "Hello, World!"

    print hello, "->", greet.parseString( hello )

The program outputs the following::

    Hello, World! -> ['Hello', ',', 'World', '!']

The Python representation of the grammar is quite readable, owing to the self-explanatory 

class names, and the use of '+', '|' and '^' operators.

The parsed results returned from parseString() can be accessed as a nested list, a dictionary, or an 

object with named attributes.

The pyparsing module handles some of the problems that are typically vexing when writing text parsers:

 - extra or missing whitespace (the above program will also handle "Hello,World!", "Hello  ,  World  !", etc.)

 - quoted strings

 - embedded comments

"""

__version__ = "1.4.5"

__versionTime__ = "16 December 2006 07:20"

__author__ = "Paul McGuire <ptmcg@users.sourceforge.net>"

import string

import copy,sys

import warnings

import re

import sre_constants

import xml.sax.saxutils

#~ sys.stderr.write( "testing pyparsing module, version %s, %s\n" % (__version__,__versionTime__ ) )

def _ustr(obj):

    """Drop-in replacement for str(obj) that tries to be Unicode friendly. It first tries

       str(obj). If that fails with a UnicodeEncodeError, then it tries unicode(obj). It

       then < returns the unicode object | encodes it with the default encoding | ... >.

    """

    try:

        # If this works, then _ustr(obj) has the same behaviour as str(obj), so

        # it won't break any existing code.

        return str(obj)

    except UnicodeEncodeError, e:

        # The Python docs (http://docs.python.org/ref/customization.html#l2h-182)

        # state that "The return value must be a string object". However, does a

        # unicode object (being a subclass of basestring) count as a "string

        # object"?

        # If so, then return a unicode object:

        return unicode(obj)

        # Else encode it... but how? There are many choices... :)

        # Replace unprintables with escape codes?

        #return unicode(obj).encode(sys.getdefaultencoding(), 'backslashreplace_errors')

        # Replace unprintables with question marks?

        #return unicode(obj).encode(sys.getdefaultencoding(), 'replace')

        # ...

def _str2dict(strg):

    return dict( [(c,0) for c in strg] )

    #~ return set( [c for c in strg] )

class _Constants(object):

    pass

alphas     = string.lowercase + string.uppercase

nums       = string.digits

hexnums    = nums + "ABCDEFabcdef"

alphanums  = alphas + nums    

class ParseBaseException(Exception):

    """base exception class for all parsing runtime exceptions"""

    __slots__ = ( "loc","msg","pstr","parserElement" )

    # Performance tuning: we construct a *lot* of these, so keep this

    # constructor as small and fast as possible        

    def __init__( self, pstr, loc, msg, elem=None ):

        self.loc = loc

        self.msg = msg

        self.pstr = pstr

        self.parserElement = elem

    def __getattr__( self, aname ):

        """supported attributes by name are:

            - lineno - returns the line number of the exception text

            - col - returns the column number of the exception text

            - line - returns the line containing the exception text

        """

        if( aname == "lineno" ):

            return lineno( self.loc, self.pstr )

        elif( aname in ("col", "column") ):

            return col( self.loc, self.pstr )

        elif( aname == "line" ):

            return line( self.loc, self.pstr )

        else:

            raise AttributeError, aname

    def __str__( self ):

        return "%s (at char %d), (line:%d, col:%d)" % ( self.msg, self.loc, self.lineno, self.column )

    def __repr__( self ):

        return _ustr(self)

    def markInputline( self, markerString = ">!<" ):

        """Extracts the exception line from the input string, and marks 

           the location of the exception with a special symbol.

        """

        line_str = self.line

        line_column = self.column - 1

        if markerString:

            line_str = "".join( [line_str[:line_column], markerString, line_str[line_column:]])

        return line_str.strip()

class ParseException(ParseBaseException):

    """exception thrown when parse expressions don't match class"""

    """supported attributes by name are:

        - lineno - returns the line number of the exception text

        - col - returns the column number of the exception text

        - line - returns the line containing the exception text

    """

    pass

class ParseFatalException(ParseBaseException):

    """user-throwable exception thrown when inconsistent parse content

       is found; stops all parsing immediately"""

    pass

class ReparseException(ParseBaseException):

    def __init_( self, newstring, restartLoc ):

        self.newParseText = newstring

        self.reparseLoc = restartLoc

class RecursiveGrammarException(Exception):

    """exception thrown by validate() if the grammar could be improperly recursive"""

    def __init__( self, parseElementList ):

        self.parseElementTrace = parseElementList

    def __str__( self ):

        return "RecursiveGrammarException: %s" % self.parseElementTrace

class ParseResults(object):

    """Structured parse results, to provide multiple means of access to the parsed data:

       - as a list (len(results))

       - by list index (results[0], results[1], etc.)

       - by attribute (results.<resultsName>)

       """

    __slots__ = ( "__toklist", "__tokdict", "__doinit", "__name", "__parent", "__accumNames" )

    def __new__(cls, toklist, name=None, asList=True, modal=True ):

        if isinstance(toklist, cls):

            return toklist

        retobj = object.__new__(cls)

        retobj.__doinit = True

        return retobj

    # Performance tuning: we construct a *lot* of these, so keep this

    # constructor as small and fast as possible

    def __init__( self, toklist, name=None, asList=True, modal=True ):

        if self.__doinit:

            self.__doinit = False

            self.__name = None

            self.__parent = None

            self.__accumNames = {}

            if isinstance(toklist, list):

                self.__toklist = toklist[:]

            else:

                self.__toklist = [toklist]

            self.__tokdict = dict()

        # this line is related to debugging the asXML bug

        #~ asList = False

        if name:

            if not modal:

                self.__accumNames[name] = 0

            if isinstance(name,int):

                name = _ustr(name) # will always return a str, but use _ustr for consistency

            self.__name = name

            if not toklist in (None,'',[]):

                if isinstance(toklist,basestring): 

                    toklist = [ toklist ]

                if asList:

                    if isinstance(toklist,ParseResults):

                        self[name] = (toklist.copy(),-1)

                    else:

                        self[name] = (ParseResults(toklist[0]),-1)

                    self[name].__name = name

                else:

                    try:

                        self[name] = toklist[0]

                    except (KeyError,TypeError):

                        self[name] = toklist

    def __getitem__( self, i ):

        if isinstance( i, (int,slice) ):

            return self.__toklist[i]

        else:

            if i not in self.__accumNames:

                return self.__tokdict[i][-1][0]

            else:

                return ParseResults([ v[0] for v in self.__tokdict[i] ])

    def __setitem__( self, k, v ):

        if isinstance(v,tuple):

            self.__tokdict[k] = self.__tokdict.get(k,list()) + [v]

            sub = v[0]

        elif isinstance(k,int):

            self.__toklist[k] = v

            sub = v

        else:

            self.__tokdict[k] = self.__tokdict.get(k,list()) + [(v,0)]

            sub = v

        if isinstance(sub,ParseResults):

            sub.__parent = self

    def __delitem__( self, i ):

        if isinstance(i,(int,slice)):

            del self.__toklist[i]

        else:

            del self._tokdict[i]

    def __contains__( self, k ):

        return self.__tokdict.has_key(k)

    def __len__( self ): return len( self.__toklist )

    def __nonzero__( self ): return len( self.__toklist ) > 0

    def __iter__( self ): return iter( self.__toklist )

    def keys( self ): 

        """Returns all named result keys."""

        return self.__tokdict.keys()

    def items( self ): 

        """Returns all named result keys and values as a list of tuples."""

        return [(k,self[k]) for k in self.__tokdict.keys()]

    def values( self ): 

        """Returns all named result values."""

        return [ v[-1][0] for v in self.__tokdict.values() ]

    def __getattr__( self, name ):

        if name not in self.__slots__:

            if self.__tokdict.has_key( name ):

                if name not in self.__accumNames:

                    return self.__tokdict[name][-1][0]

                else:

                    return ParseResults([ v[0] for v in self.__tokdict[name] ])

            else:

                return ""

        return None

    def __add__( self, other ):

        ret = self.copy()

        ret += other

        return ret

    def __iadd__( self, other ):

        if other.__tokdict:

            offset = len(self.__toklist)

            addoffset = ( lambda a: (a<0 and offset) or (a+offset) )

            otheritems = other.__tokdict.items()

            otherdictitems = [(k,(v[0],addoffset(v[1])) ) for (k,vlist) in otheritems for v in vlist]

            for k,v in otherdictitems:

                self[k] = v

                if isinstance(v[0],ParseResults):

                    v[0].__parent = self

        self.__toklist += other.__toklist

        self.__accumNames.update( other.__accumNames )

        del other

        return self

    def __repr__( self ):

        return "(%s, %s)" % ( repr( self.__toklist ), repr( self.__tokdict ) )

    def __str__( self ):

        out = "["

        sep = ""

        for i in self.__toklist:

            if isinstance(i, ParseResults):

                out += sep + _ustr(i)

            else:

                out += sep + repr(i)

            sep = ", "

        out += "]"

        return out

    def _asStringList( self, sep='' ):

        out = []

        for item in self.__toklist:

            if out and sep:

                out.append(sep)

            if isinstance( item, ParseResults ):

                out += item._asStringList()

            else:

                out.append( _ustr(item) )

        return out

    def asList( self ):

        """Returns the parse results as a nested list of matching tokens, all converted to strings."""

        out = []

        for res in self.__toklist:

            if isinstance(res,ParseResults):

                out.append( res.asList() )

            else:

                out.append( res )

        return out

    def asDict( self ):

        """Returns the named parse results as dictionary."""

        return dict( self.items() )

    def copy( self ):

        """Returns a new copy of a ParseResults object."""

        ret = ParseResults( self.__toklist )

        ret.__tokdict = self.__tokdict.copy()

        ret.__parent = self.__parent

        ret.__accumNames.update( self.__accumNames )

        ret.__name = self.__name

        return ret

    def asXML( self, doctag=None, namedItemsOnly=False, indent="", formatted=True ):

        """Returns the parse results as XML. Tags are created for tokens and lists that have defined results names."""

        nl = "\n"

        out = []

        namedItems = dict( [ (v[1],k) for (k,vlist) in self.__tokdict.items() for v in vlist ] )

        nextLevelIndent = indent + "  "

        # collapse out indents if formatting is not desired

        if not formatted:

            indent = ""

            nextLevelIndent = ""

            nl = ""

        selfTag = None

        if doctag is not None:

            selfTag = doctag

        else:

            if self.__name:

                selfTag = self.__name

        if not selfTag:

            if namedItemsOnly:

                return ""

            else:

                selfTag = "ITEM"

        out += [ nl, indent, "<", selfTag, ">" ]

        worklist = self.__toklist

        for i,res in enumerate(worklist):

            if isinstance(res,ParseResults):

                if i in namedItems:

                    out += [ res.asXML(namedItems[i], namedItemsOnly and doctag is None, nextLevelIndent,formatted)]

                else:

                    out += [ res.asXML(None, namedItemsOnly and doctag is None, nextLevelIndent,formatted)]

            else:

                # individual token, see if there is a name for it

                resTag = None

                if i in namedItems:

                    resTag = namedItems[i]

                if not resTag:

                    if namedItemsOnly:

                        continue

                    else:

                        resTag = "ITEM"

                xmlBodyText = xml.sax.saxutils.escape(_ustr(res))

                out += [ nl, nextLevelIndent, "<", resTag, ">", xmlBodyText, "</", resTag, ">" ]

        out += [ nl, indent, "</", selfTag, ">" ]

        return "".join(out)

    def __lookup(self,sub):

        for k,vlist in self.__tokdict.items():

            for v,loc in vlist:

                if sub is v:

                    return k

        return None

    def getName(self):

        """Returns the results name for this token expression."""

        if self.__name:

            return self.__name

        elif self.__parent:

            par = self.__parent

            if par:

                return par.__lookup(self)

            else:

                return None

        elif (len(self) == 1 and 

               len(self.__tokdict) == 1 and

               self.__tokdict.values()[0][0][1] in (0,-1)):

            return self.__tokdict.keys()[0]

        else:

            return None

    def dump(self,indent='',depth=0):

        """Diagnostic method for listing out the contents of a ParseResults.

           Accepts an optional indent argument so that this string can be embedded

           in a nested display of other data."""

        out = []

        out.append( indent+str(self.asList()) )

        keys = self.items()

        keys.sort()

        for k,v in keys:

            if out:

                out.append('\n')

            out.append( "%s%s- %s: " % (indent,('  '*depth), k) )

            if isinstance(v,ParseResults):

                if v.keys():

                    #~ out.append('\n')

                    out.append( v.dump(indent,depth+1) )

                    #~ out.append('\n')

                else:

                    out.append(str(v))

            else:

                out.append(str(v))

        #~ out.append('\n')

        return "".join(out)

    # add support for pickle protocol

    def __getstate__(self):

        return ( self.__toklist,

                 ( self.__tokdict.copy(),

                   self.__parent,

                   self.__accumNames,

                   self.__name ) )

    def __setstate__(self,state):

        self.__toklist = state[0]

        self.__tokdict, \

        self.__parent, \

        inAccumNames, \

        self.__name = state[1]

        self.__accumNames = {}

        self.__accumNames.update(inAccumNames)

def col (loc,strg):

    """Returns current column within a string, counting newlines as line separators.

   The first column is number 1.

   """

    return (loc<len(strg) and strg[loc] == '\n') and 1 or loc - strg.rfind("\n", 0, loc)

def lineno(loc,strg):

    """Returns current line number within a string, counting newlines as line separators.

   The first line is number 1.

   """

    return strg.count("\n",0,loc) + 1

def line( loc, strg ):

    """Returns the line of text containing loc within a string, counting newlines as line separators.

       """

    lastCR = strg.rfind("\n", 0, loc)

    nextCR = strg.find("\n", loc)

    if nextCR > 0:

        return strg[lastCR+1:nextCR]

    else:

        return strg[lastCR+1:]

def _defaultStartDebugAction( instring, loc, expr ):

    print "Match",expr,"at loc",loc,"(%d,%d)" % ( lineno(loc,instring), col(loc,instring) )

def _defaultSuccessDebugAction( instring, startloc, endloc, expr, toks ):

    print "Matched",expr,"->",toks.asList()

def _defaultExceptionDebugAction( instring, loc, expr, exc ):

    print "Exception raised:", exc

def nullDebugAction(*args):

    """'Do-nothing' debug action, to suppress debugging output during parsing."""

    pass

class ParserElement(object):

    """Abstract base level parser element class."""

    DEFAULT_WHITE_CHARS = " \n\t\r"

    def setDefaultWhitespaceChars( chars ):

        """Overrides the default whitespace chars

        """

        ParserElement.DEFAULT_WHITE_CHARS = chars

    setDefaultWhitespaceChars = staticmethod(setDefaultWhitespaceChars)

    def __init__( self, savelist=False ):

        self.parseAction = list()

        self.failAction = None

        #~ self.name = "<unknown>"  # don't define self.name, let subclasses try/except upcall

        self.strRepr = None

        self.resultsName = None

        self.saveAsList = savelist

        self.skipWhitespace = True

        self.whiteChars = ParserElement.DEFAULT_WHITE_CHARS

        self.copyDefaultWhiteChars = True

        self.mayReturnEmpty = False

        self.keepTabs = False

        self.ignoreExprs = list()