Discard duplicate matches. (Also "tabified" source.)
authorFrederic Jolliton <frederic@jolliton.com>
Mon, 12 Sep 2005 09:09:23 +0000 (09:09 +0000)
committerFrederic Jolliton <frederic@jolliton.com>
Mon, 12 Sep 2005 09:09:23 +0000 (09:09 +0000)
 * Updated Base.parse to discard duplicate matches.
git-archimport-id: frederic@jolliton.com--2005-main/tx--main--0.1--patch-33

parser.py

index 83f5ac5..d57df61 100644 (file)
--- a/parser.py
+++ b/parser.py
@@ -46,6 +46,7 @@ __all__ = [
 #
 
 import sys
+import operator as op
 
 _debug = False
 
@@ -56,93 +57,93 @@ from misc import identity, constantly
 
 def flattenSequence( sequence ) :
 
-    '''Flatten sequence 'sequence' as a list.'''
+       '''Flatten sequence 'sequence' as a list.'''
 
-    result = []
-    if isinstance( sequence , basestring ) :
-        result = [ sequence ]
-    else :
-        try :
-            for item in sequence :
-                result += flattenSequence( item )
-        except TypeError :
-            result = [ sequence ]
-    return result
+       result = []
+       if isinstance( sequence , basestring ) :
+               result = [ sequence ]
+       else :
+               try :
+                       for item in sequence :
+                               result += flattenSequence( item )
+               except TypeError :
+                       result = [ sequence ]
+       return result
 
 def _preprocess( expr ) :
 
-    '''Process subexpression. Currently used to automatically
-    treat string as Literal.'''
+       '''Process subexpression. Currently used to automatically
+       treat string as Literal.'''
 
-    if expr is None :
-        pass
-    elif isinstance( expr , basestring ) :
-        expr = Literal( expr )
-    return expr
+       if expr is None :
+               pass
+       elif isinstance( expr , basestring ) :
+               expr = Literal( expr )
+       return expr
 
 class Reject( Error ) : pass
 
 class NoMatch( Error ) :
 
-    '''Exception raised when no matches can be found.'''
+       '''Exception raised when no matches can be found.'''
 
-    def __init__( self , state ) :
+       def __init__( self , state ) :
 
-        self.state = state
+               self.state = state
 
-    def __repr__( self ) :
+       def __repr__( self ) :
 
-        return '<NoMatch at %d>' % ( self.state.pos + 1 )
+               return '<NoMatch at %d>' % ( self.state.pos + 1 )
 
-    def __str__( self ) :
+       def __str__( self ) :
 
-        return 'Error at position %d' % ( self.state.pos + 1 )
+               return 'Error at position %d' % ( self.state.pos + 1 )
 
 class AmbiguousMatch( Error ) :
 
-    '''Exception raised when several matches are found.'''
+       '''Exception raised when several matches are found.'''
 
-    def __init__( self , count ) :
+       def __init__( self , count ) :
 
-        self.count = count
+               self.count = count
 
-    def __repr__( self ) :
+       def __repr__( self ) :
 
-        return '<AmbiguousMatch>' % ( self.count , )
+               return '<AmbiguousMatch>' % ( self.count , )
 
-    def __str__( self ) :
+       def __str__( self ) :
 
-        return 'Ambiguous match (%d results)' % ( self.count , )
+               return 'Ambiguous match (%d results)' % ( self.count , )
 
 class ParserState( object ) :
 
-    '''State of the parser (the text itself, and the current position.)'''
+       '''State of the parser (the text itself, and the current position.)'''
 
-    def __init__( self , data , pos = 0 ) :
+       def __init__( self , data , pos = 0 ) :
 
-        self.data = data
-        self.pos = pos
+               self.data = data
+               self.pos = pos
 
-    def _advance( self , count ) :
+       def _advance( self , count ) :
 
-        self.pos += count
+               self.pos += count
 
-    def clone( self , offset = 0 ) :
+       def clone( self , offset = 0 ) :
 
-        newInstance = self.__new__( self.__class__ )
-        newInstance.restore( self , offset )
-        return newInstance
+               newInstance = self.__new__( self.__class__ )
+               newInstance.restore( self , offset )
+               return newInstance
 
-    def restore( self , other , offset = 0 ) :
+       def restore( self , other , offset = 0 ) :
 
-        self.data = other.data
-        self.pos = other.pos + offset
-        return self
+               self.data = other.data
+               self.pos = other.pos + offset
+               return self
 
-    def __repr__( self ) :
+       def __repr__( self ) :
 
-        return '<ParserState %d bytes in buffer, position at %d>' \
-            % ( len( self.data ) , self.pos )
+               return '<ParserState %d bytes in buffer, position at %d>' \
+                       % ( len( self.data ) , self.pos )
 
 #############################################################################
 #
@@ -154,354 +155,362 @@ class ParserState( object ) :
 
 class Base( object ) :
 
-    def __init__( self ) :
-
-        self.__callEnter = []
-        self.__callLeave = []
-        self.__ignore = False
-
-    def parse( self , s , start = 0 ) :
-
-        state = ParserState( s , start )
-        results = self._parse( state )
-        assert results , 'expected some results'
-        #
-        # Keep longest result
-        #
-        matches = [ result for result in results if result[ 1 ].pos == len( s ) ]
-        if not matches :
-            raise NoMatch( result[ 0 ].state )
-        elif len( matches ) > 1 :
-            raise AmbiguousMatch( len( matches ) )
-        else :
-            return matches[ 0 ][ 0 ]
-
-    def __add__( self , other ) :
-
-        return Sequence( self , other )
-
-    def __or__( self , other ) :
-
-        return Either( self , other )
-
-    def __debug( self , data , markers ) :
-
-        if _debug :
-            if isinstance( self , Wrapper ) and not self.__name :
-                pass
-            else :
-                n = len( markers ) - 1
-                if n is not None :
-                    prefix = '#%d' % n
-                else :
-                    prefix = '##'
-                s = self.asString( 3 )
-                print prefix , '%d: %s' % ( markers[ 0 ] , s )
-                print prefix , data
-                blankLine = ' ' * ( max( markers ) + 1 )
-                base = blankLine
-                lines = []
-                for i , m in enumerate( markers ) :
-                    base = base[ : m ] + '^' + base[ m + 1 : ]
-                    if i == 0 :
-                        mm = '@'
-                    elif 1 <= i <= 9 :
-                        mm = chr( ord( '1' ) + i - 1 )
-                    elif 10 <= i <= 35 :
-                        mm = chr( ord( 'A' ) + i - 10 )
-                    else :
-                        mm = '#'
-                    for j , line in enumerate( lines ) :
-                        if line[ m ] == ' ' :
-                            lines[ j ] = line[ : m ] + mm + line[ m + 1 : ]
-                            break
-                    else :
-                        line = blankLine[ : m ] + mm + blankLine[ m + 1 : ]
-                        lines.append( line )
-                lines.insert( 0 , base )
-                for line in lines :
-                    print prefix , line
-                print
-
-    def _parse( self , state ) :
-
-        for fun in self.__callEnter :
-            fun()
-        results = self._process( state )
-        if not isinstance( results , list ) :
-            results = [ results ]
-        self.__debug( state.data , [ state.pos ] + [ s[ 1 ].pos for s in results ] )
-        newResults = []
-        for value , state in results :
-            discard = False
-            if True :
-                for i , fun in enumerate( self.__callLeave ) :
-                    try :
-                        v = fun( value )
-                    except Reject :
-                        discard = True
-                        break
-                    else :
-                        if v is not None :
-                            value = v
-            else :
-                value = ( self.__name or '#%X' % id( self ) , value )
-            if not discard :
-                newResults.append( ( value , state ) )
-        return newResults
-
-    def name( self , newName ) :
-
-        self.__name = newName
-        return self
-
-    def enter( self , fun ) :
-
-        self.__callEnter.insert( 0 , fun )
-        return self
-
-    def call( self , fun ) :
-
-        self.__callLeave.append( fun )
-        return self
-
-    def ignore( self ) :
-
-        self.__ignore = True
-        return self
-
-    def ignorable( self ) :
-
-        return self.__ignore
-
-    def asString( self , level = 1 , refs = None ) :
-
-        # 'refs' is used to prevent recursion
-        if refs is None :
-            refs = {}
-        x = id( self )
-        if x in refs :
-            s = '##'
-        else :
-            refs[ x ] = True
-            if level <= 0 :
-                s = '...'
-            else :
-                s = self._str( level - 1 , refs )
-        return s
-
-    def __str__( self ) :
-
-        return self.asString()
-
-    def _str( self , level , refs ) :
-
-        raise NotImplementedError
-
-    def _getName( self ) :
-
-        result = ''
-        if self.__name :
-            result = ':[%s]' % self.__name
-        return result
+       def __init__( self ) :
+
+               self.__callEnter = []
+               self.__callLeave = []
+               self.__ignore = False
+
+       def parse( self , s , start = 0 ) :
+
+               state = ParserState( s , start )
+               results = self._parse( state )
+               assert results , 'expected some results'
+
+               match = None
+               count = 0
+               for result in results :
+                       e = result[ 0 ]
+                       if result[ 1 ].pos == len( s ) :
+                               if match is None :
+                                       count += 1
+                                       match = e
+                               elif match == e :
+                                       pass # Same result
+                               else :
+                                       count += 1
+               if count > 1 :
+                       raise AmbiguousMatch( count )
+               if match is None :
+                       raise NoMatch( min( map( op.attrgetter( 'state' ) , results ) ) )
+               return match
+
+       def __add__( self , other ) :
+
+               return Sequence( self , other )
+
+       def __or__( self , other ) :
+
+               return Either( self , other )
+
+       def __debug( self , data , markers ) :
+
+               if _debug :
+                       if isinstance( self , Wrapper ) and not self.__name :
+                               pass
+                       else :
+                               n = len( markers ) - 1
+                               if n is not None :
+                                       prefix = '#%d' % n
+                               else :
+                                       prefix = '##'
+                               s = self.asString( 3 )
+                               print prefix , '%d: %s' % ( markers[ 0 ] , s )
+                               print prefix , data
+                               blankLine = ' ' * ( max( markers ) + 1 )
+                               base = blankLine
+                               lines = []
+                               for i , m in enumerate( markers ) :
+                                       base = base[ : m ] + '^' + base[ m + 1 : ]
+                                       if i == 0 :
+                                               mm = '@'
+                                       elif 1 <= i <= 9 :
+                                               mm = chr( ord( '1' ) + i - 1 )
+                                       elif 10 <= i <= 35 :
+                                               mm = chr( ord( 'A' ) + i - 10 )
+                                       else :
+                                               mm = '#'
+                                       for j , line in enumerate( lines ) :
+                                               if line[ m ] == ' ' :
+                                                       lines[ j ] = line[ : m ] + mm + line[ m + 1 : ]
+                                                       break
+                                       else :
+                                               line = blankLine[ : m ] + mm + blankLine[ m + 1 : ]
+                                               lines.append( line )
+                               lines.insert( 0 , base )
+                               for line in lines :
+                                       print prefix , line
+                               print
+
+       def _parse( self , state ) :
+
+               for fun in self.__callEnter :
+                       fun()
+               results = self._process( state )
+               if not isinstance( results , list ) :
+                       results = [ results ]
+               self.__debug( state.data , [ state.pos ] + [ s[ 1 ].pos for s in results ] )
+               newResults = []
+               for value , state in results :
+                       discard = False
+                       if True :
+                               for i , fun in enumerate( self.__callLeave ) :
+                                       try :
+                                               v = fun( value )
+                                       except Reject :
+                                               discard = True
+                                               break
+                                       else :
+                                               if v is not None :
+                                                       value = v
+                       else :
+                               value = ( self.__name or '#%X' % id( self ) , value )
+                       if not discard :
+                               newResults.append( ( value , state ) )
+               return newResults
+
+       def name( self , newName ) :
+
+               self.__name = newName
+               return self
+
+       def enter( self , fun ) :
+
+               self.__callEnter.insert( 0 , fun )
+               return self
+
+       def call( self , fun ) :
+
+               self.__callLeave.append( fun )
+               return self
+
+       def ignore( self ) :
+
+               self.__ignore = True
+               return self
+
+       def ignorable( self ) :
+
+               return self.__ignore
+
+       def asString( self , level = 1 , refs = None ) :
+
+               # 'refs' is used to prevent recursion
+               if refs is None :
+                       refs = {}
+               x = id( self )
+               if x in refs :
+                       s = '##'
+               else :
+                       refs[ x ] = True
+                       if level <= 0 :
+                               s = '...'
+                       else :
+                               s = self._str( level - 1 , refs )
+               return s
+
+       def __str__( self ) :
+
+               return self.asString()
+
+       def _str( self , level , refs ) :
+
+               raise NotImplementedError
+
+       def _getName( self ) :
+
+               result = ''
+               if self.__name :
+                       result = ':[%s]' % self.__name
+               return result
 
 class Regex( Base ) :
 
-    def __init__( self , data , flags = 0 ) :
+       def __init__( self , data , flags = 0 ) :
 
-        Base.__init__( self )
-        self.__data = data
-        self.regexp = re.compile( data , flags )
+               Base.__init__( self )
+               self.__data = data
+               self.regexp = re.compile( data , flags )
 
-    def _process( self , state ) :
+       def _process( self , state ) :
 
-        r = self.regexp.match( state.data , state.pos )
-        if r is None :
-            raise NoMatch( state )
-        if r.groups() :
-            s = r.group( 1 )
-        else :
-            s = r.group( 0 )
-        result = s , state.clone( r.end( 0 ) - state.pos )
-        return result
+               r = self.regexp.match( state.data , state.pos )
+               if r is None :
+                       raise NoMatch( state )
+               if r.groups() :
+                       s = r.group( 1 )
+               else :
+                       s = r.group( 0 )
+               result = s , state.clone( r.end( 0 ) - state.pos )
+               return result
 
-    def _str( self , level , refs ) :
+       def _str( self , level , refs ) :
 
-        return '<Regex%s %r>' % ( self._getName() , self.__data )
+               return '<Regex%s %r>' % ( self._getName() , self.__data )
 
 class Either( Base ) :
 
-    def __init__( self , *exprs ) :
+       def __init__( self , *exprs ) :
 
-        Base.__init__( self )
-        self.__exprs = map( _preprocess , flattenSequence( exprs ) )
+               Base.__init__( self )
+               self.__exprs = map( _preprocess , flattenSequence( exprs ) )
 
-    def _getExprs( self ) :
+       def _getExprs( self ) :
 
-        return self.__exprs
+               return self.__exprs
 
-    def _process( self , state ) :
+       def _process( self , state ) :
 
-        branches = []
-        for expr in self.__exprs :
-            try :
-                branches += expr._parse( state )
-            except NoMatch :
-                pass
-        if not branches :
-            raise NoMatch( state )
-        return branches
+               branches = []
+               for expr in self.__exprs :
+                       try :
+                               branches += expr._parse( state )
+                       except NoMatch :
+                               pass
+               if not branches :
+                       raise NoMatch( state )
+               return branches
 
-    def _str( self , level , refs ) :
+       def _str( self , level , refs ) :
 
-        return '<EitherFork%s %s>' \
-            % ( self._getName() , ', '.join( [ expr.asString( level , refs ) for expr in self.__exprs ] ) )
+               return '<EitherFork%s %s>' \
+                       % ( self._getName() , ', '.join( [ expr.asString( level , refs ) for expr in self.__exprs ] ) )
 
 class Sequence( Base ) :
 
-    def __init__( self , *exprs ) :
+       def __init__( self , *exprs ) :
 
-        Base.__init__( self )
-        self.__exprs = map( _preprocess , flattenSequence( exprs ) )
+               Base.__init__( self )
+               self.__exprs = map( _preprocess , flattenSequence( exprs ) )
 
-    def _getExprs( self ) : return self.__exprs
+       def _getExprs( self ) : return self.__exprs
 
-    def _process( self , state ) :
+       def _process( self , state ) :
 
-        branches = [ ( [] , state ) ]
-        for expr in self.__exprs :
-            newBranches = []
-            for value , state in branches :
-                try :
-                    for newValue , newState in expr._parse( state ) :
-                        if expr.ignorable() :
-                            branch = value , newState
-                        else :
-                            branch = value + [ newValue ] , newState
-                        newBranches.append( branch )
-                except NoMatch :
-                    pass
-            branches = newBranches
-            if not branches :
-                raise NoMatch( state )
-        return branches
+               branches = [ ( [] , state ) ]
+               for expr in self.__exprs :
+                       newBranches = []
+                       for value , state in branches :
+                               try :
+                                       for newValue , newState in expr._parse( state ) :
+                                               if expr.ignorable() :
+                                                       branch = value , newState
+                                               else :
+                                                       branch = value + [ newValue ] , newState
+                                               newBranches.append( branch )
+                               except NoMatch :
+                                       pass
+                       branches = newBranches
+                       if not branches :
+                               raise NoMatch( state )
+               return branches
 
-    def _str( self , level , refs ) :
+       def _str( self , level , refs ) :
 
-        return '<Sequence%s %s>' \
-            % ( self._getName() , ', '.join( [ expr.asString( level , refs ) for expr in self.__exprs ] ) )
+               return '<Sequence%s %s>' \
+                       % ( self._getName() , ', '.join( [ expr.asString( level , refs ) for expr in self.__exprs ] ) )
 
 class Multi( Base ) :
 
-    def __init__( self , min , max , expr ) :
-
-        Base.__init__( self )
-        self.__min = min
-        self.__max = max
-        self.__expr = _preprocess( expr )
-
-    def _process( self , state ) :
-
-        branches = [ ( [] , state ) ]
-        expr = self.__expr
-        for i in range( self.__min ) :
-            newBranches = []
-            for value , state in branches :
-                try :
-                    for newValue , newState in expr._parse( state ) :
-                        newBranches.append( ( value + [ newValue ] , newState ) )
-                except NoMatch :
-                    pass
-            branches = newBranches
-            if not branches :
-                raise NoMatch( state )
-        i = self.__min
-        finalBranches = []
-        while self.__max is None or i < self.__max :
-            i += 1
-            newBranches = []
-            for value , state in branches :
-                try :
-                    for newValue , newState in expr._parse( state ) :
-                        newBranches.append( ( value + [ newValue ] , newState ) )
-                except NoMatch :
-                    pass
-                finalBranches.append( ( value , state ) )
-            branches = newBranches
-            if not branches :
-                break
-        finalBranches += branches
-        return finalBranches
-
-    def _str( self , level , refs ) :
-
-        return '<Multi%s %s {%s,%s}>' \
-            % ( self._getName() , self.__expr.asString( level , refs ) , self.__min , self.__max or '' )
+       def __init__( self , min , max , expr ) :
+
+               Base.__init__( self )
+               self.__min = min
+               self.__max = max
+               self.__expr = _preprocess( expr )
+
+       def _process( self , state ) :
+
+               branches = [ ( [] , state ) ]
+               expr = self.__expr
+               for i in range( self.__min ) :
+                       newBranches = []
+                       for value , state in branches :
+                               try :
+                                       for newValue , newState in expr._parse( state ) :
+                                               newBranches.append( ( value + [ newValue ] , newState ) )
+                               except NoMatch :
+                                       pass
+                       branches = newBranches
+                       if not branches :
+                               raise NoMatch( state )
+               i = self.__min
+               finalBranches = []
+               while self.__max is None or i < self.__max :
+                       i += 1
+                       newBranches = []
+                       for value , state in branches :
+                               try :
+                                       for newValue , newState in expr._parse( state ) :
+                                               newBranches.append( ( value + [ newValue ] , newState ) )
+                               except NoMatch :
+                                       pass
+                               finalBranches.append( ( value , state ) )
+                       branches = newBranches
+                       if not branches :
+                               break
+               finalBranches += branches
+               return finalBranches
+
+       def _str( self , level , refs ) :
+
+               return '<Multi%s %s {%s,%s}>' \
+                       % ( self._getName() , self.__expr.asString( level , refs ) , self.__min , self.__max or '' )
 
 class Wrapper( Base ) :
 
-    def __init__( self , expr = None ) :
+       def __init__( self , expr = None ) :
 
-        Base.__init__( self )
-        self.__expr = _preprocess( expr )
+               Base.__init__( self )
+               self.__expr = _preprocess( expr )
 
-    def _process( self , branches ) :
+       def _process( self , branches ) :
 
-        assert self.__expr is not None , 'Wrapper should be set with an expression'
-        return self.__expr._parse( branches )
+               assert self.__expr is not None , 'Wrapper should be set with an expression'
+               return self.__expr._parse( branches )
 
-    def set( self , expr ) :
+       def set( self , expr ) :
 
-        assert self.__expr is None , 'Wrapper already contains an expression'
-        self.__expr = _preprocess( expr )
-        return self
+               assert self.__expr is None , 'Wrapper already contains an expression'
+               self.__expr = _preprocess( expr )
+               return self
 
-    __lshift__ = set
+       __lshift__ = set
 
-    def _str( self , level , refs ) :
+       def _str( self , level , refs ) :
 
-        if self._getName() :
-            return '<Wrapper%s %s>' \
-                % ( self._getName() , self.__expr.asString( level , refs ) )
-        else :
-            return self.__expr.asString( level + 1 , refs )
+               if self._getName() :
+                       return '<Wrapper%s %s>' \
+                               % ( self._getName() , self.__expr.asString( level , refs ) )
+               else :
+                       return self.__expr.asString( level + 1 , refs )
 
 #--[ Misc ]------------------------------------------------------------------
 
 def Integer() :
 
-    return Regex( r'\d+' )
+       return Regex( r'\d+' )
 
 def Space() :
 
-    return Regex( r'\s+' )
+       return Regex( r'\s+' )
 
 def Literal( s ) :
 
-    return Regex( re.escape( s ) )
+       return Regex( re.escape( s ) )
 
 def Empty() :
 
-    return Literal( '' )
+       return Literal( '' )
 
 def ZeroOrMore( expr ) :
 
-    return Multi( 0 , None , expr )
+       return Multi( 0 , None , expr )
 
 def OneOrMore( expr ) :
 
-    return Multi( 1 , None , expr )
+       return Multi( 1 , None , expr )
 
 def Optional( expr ) :
 
-    return Multi( 0 , 1 , expr )
+       return Multi( 0 , 1 , expr )
 
 def List( expr1 , expr2 ) :
 
-    def normalize( e ) :
-        return [ e[ 0 ] ] + sum( e[ 1 ] , [] )
+       def normalize( e ) :
+               return [ e[ 0 ] ] + sum( e[ 1 ] , [] )
 
-    return Wrapper( Sequence( expr1 , ZeroOrMore( Sequence( expr2 , expr1 ) ) ).call( normalize ) )
+       return Wrapper( Sequence( expr1 , ZeroOrMore( Sequence( expr2 , expr1 ) ) ).call( normalize ) )
 
 # Local Variables:
 # tab-width: 4