Fixed / overloading when enabling true division.
[tx] / parser.py
1 # -*- coding:utf-8 -*-
2
3 # Generic parser
4 # Copyright (C) 2005  Frédéric Jolliton <frederic@jolliton.com>
5
6 # This program is free software; you can redistribute it and/or modify
7 # it under the terms of the GNU General Public License as published by
8 # the Free Software Foundation; either version 2 of the License, or
9 # (at your option) any later version.
10
11 # This program is distributed in the hope that it will be useful,
12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 # GNU General Public License for more details.
15
16 # You should have received a copy of the GNU General Public License
17 # along with this program; if not, write to the Free Software
18 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19
20 __all__ = [
21         #
22         # Exceptions
23         #
24         'Reject' , 'NoMatch' , 'AmbiguousMatch' ,
25         #
26         # State
27         #
28         'ParserState' ,
29         #
30         # Primitives
31         #
32         'Regex' , 'Either' , 'Sequence' , 'Multi' , 'Wrapper' ,
33         #
34         # Complex
35         #
36         'Integer' , # *DEPRECATED*
37         'Space' ,   # *DEPRECATED*
38         'Literal' ,
39         'Empty' ,'ZeroOrMore' , 'OneOrMore' , 'Optional' ,
40         'List'
41 ]
42
43 #
44 # Syntax inspired from pyparsing (http://pyparsing.sourceforge.net/)
45 # by Paul McGuire
46 #
47
48 import sys
49
50 _debug = False
51
52 import re
53
54 from error import Error
55 from misc import identity, constantly
56
57 def flattenSequence( sequence ) :
58
59         '''Flatten sequence 'sequence' as a list.'''
60
61         result = []
62         if isinstance( sequence , basestring ) :
63                 result = [ sequence ]
64         else :
65                 try :
66                         for item in sequence :
67                                 result += flattenSequence( item )
68                 except TypeError :
69                         result = [ sequence ]
70         return result
71
72 def _preprocess( expr ) :
73
74         '''Process subexpression. Currently used to automatically
75         treat string as Literal.'''
76
77         if expr is None :
78                 pass
79         elif isinstance( expr , basestring ) :
80                 expr = Literal( expr )
81         return expr
82
83 class Reject( Error ) : pass
84
85 class NoMatch( Error ) :
86
87         '''Exception raised when no matches can be found.'''
88
89         def __init__( self , state ) :
90
91                 self.state = state
92
93         def __repr__( self ) :
94
95                 return '<NoMatch at %d>' % ( self.state.pos + 1 )
96
97         def __str__( self ) :
98
99                 return 'Error at position %d' % ( self.state.pos + 1 )
100
101 class AmbiguousMatch( Error ) :
102
103         '''Exception raised when several matches are found.'''
104
105         def __init__( self , count ) :
106
107                 self.count = count
108
109         def __repr__( self ) :
110
111                 return '<AmbiguousMatch>' % ( self.count , )
112
113         def __str__( self ) :
114
115                 return 'Ambiguous match (%d results)' % ( self.count , )
116
117 class ParserState( object ) :
118
119         '''State of the parser (the text itself, and the current position.)'''
120
121         def __init__( self , data , pos = 0 ) :
122
123                 self.data = data
124                 self.pos = pos
125
126         def _advance( self , count ) :
127
128                 self.pos += count
129
130         def clone( self , offset = 0 ) :
131
132                 newInstance = self.__new__( self.__class__ )
133                 newInstance.restore( self , offset )
134                 return newInstance
135
136         def restore( self , other , offset = 0 ) :
137
138                 self.data = other.data
139                 self.pos = other.pos + offset
140                 return self
141
142         def __repr__( self ) :
143
144                 return '<ParserState %d bytes in buffer, position at %d>' \
145                         % ( len( self.data ) , self.pos )
146
147 #############################################################################
148 #
149 # Primitive
150 #
151 #############################################################################
152
153 # 5 primitives: Regex, Either, Sequence, Multi, Wrapper
154
155 class Base( object ) :
156
157         def __init__( self ) :
158
159                 self.__callEnter = []
160                 self.__callLeave = []
161                 self.__ignore = False
162
163         def parse( self , s , start = 0 ) :
164
165                 state = ParserState( s , start )
166                 results = self._parse( state )
167                 assert results , 'expected some results'
168
169                 match = None
170                 count = 0
171                 for result in results :
172                         e = result[ 0 ]
173                         if result[ 1 ].pos == len( s ) :
174                                 if match is None :
175                                         count += 1
176                                         match = e
177                                 elif match == e :
178                                         pass # Same result
179                                 else :
180                                         count += 1
181                 if count > 1 :
182                         raise AmbiguousMatch( count )
183                 if match is None :
184                         raise NoMatch( min( map( lambda r : r[ 1 ].pos , results ) ) )
185                 return match
186
187         def __add__( self , other ) :
188
189                 return Sequence( self , other )
190
191         def __or__( self , other ) :
192
193                 return Either( self , other )
194
195         def __debug( self , data , markers ) :
196
197                 if _debug :
198                         if isinstance( self , Wrapper ) and not self.__name :
199                                 pass
200                         else :
201                                 n = len( markers ) - 1
202                                 if n is not None :
203                                         prefix = '#%d' % n
204                                 else :
205                                         prefix = '##'
206                                 s = self.asString( 3 )
207                                 print prefix , '%d: %s' % ( markers[ 0 ] , s )
208                                 print prefix , data
209                                 blankLine = ' ' * ( max( markers ) + 1 )
210                                 base = blankLine
211                                 lines = []
212                                 for i , m in enumerate( markers ) :
213                                         base = base[ : m ] + '^' + base[ m + 1 : ]
214                                         if i == 0 :
215                                                 mm = '@'
216                                         elif 1 <= i <= 9 :
217                                                 mm = chr( ord( '1' ) + i - 1 )
218                                         elif 10 <= i <= 35 :
219                                                 mm = chr( ord( 'A' ) + i - 10 )
220                                         else :
221                                                 mm = '#'
222                                         for j , line in enumerate( lines ) :
223                                                 if line[ m ] == ' ' :
224                                                         lines[ j ] = line[ : m ] + mm + line[ m + 1 : ]
225                                                         break
226                                         else :
227                                                 line = blankLine[ : m ] + mm + blankLine[ m + 1 : ]
228                                                 lines.append( line )
229                                 lines.insert( 0 , base )
230                                 for line in lines :
231                                         print prefix , line
232                                 print
233
234         def _parse( self , state ) :
235
236                 for fun in self.__callEnter :
237                         fun()
238                 results = self._process( state )
239                 if not isinstance( results , list ) :
240                         results = [ results ]
241                 self.__debug( state.data , [ state.pos ] + [ s[ 1 ].pos for s in results ] )
242                 newResults = []
243                 for value , state in results :
244                         discard = False
245                         if True :
246                                 for i , fun in enumerate( self.__callLeave ) :
247                                         try :
248                                                 v = fun( value )
249                                         except Reject :
250                                                 discard = True
251                                                 break
252                                         else :
253                                                 if v is not None :
254                                                         value = v
255                         else :
256                                 value = ( self.__name or '#%X' % id( self ) , value )
257                         if not discard :
258                                 newResults.append( ( value , state ) )
259                 return newResults
260
261         def name( self , newName ) :
262
263                 self.__name = newName
264                 return self
265
266         def enter( self , fun ) :
267
268                 self.__callEnter.insert( 0 , fun )
269                 return self
270
271         def call( self , fun ) :
272
273                 self.__callLeave.append( fun )
274                 return self
275
276         def ignore( self ) :
277
278                 self.__ignore = True
279                 return self
280
281         def ignorable( self ) :
282
283                 return self.__ignore
284
285         def asString( self , level = 1 , refs = None ) :
286
287                 # 'refs' is used to prevent recursion
288                 if refs is None :
289                         refs = {}
290                 x = id( self )
291                 if x in refs :
292                         s = '##'
293                 else :
294                         refs[ x ] = True
295                         if level <= 0 :
296                                 s = '...'
297                         else :
298                                 s = self._str( level - 1 , refs )
299                 return s
300
301         def __str__( self ) :
302
303                 return self.asString()
304
305         def _str( self , level , refs ) :
306
307                 raise NotImplementedError
308
309         def _getName( self ) :
310
311                 result = ''
312                 if self.__name :
313                         result = ':[%s]' % self.__name
314                 return result
315
316 class Regex( Base ) :
317
318         def __init__( self , data , flags = 0 ) :
319
320                 Base.__init__( self )
321                 self.__data = data
322                 self.regexp = re.compile( data , flags )
323
324         def _process( self , state ) :
325
326                 r = self.regexp.match( state.data , state.pos )
327                 if r is None :
328                         raise NoMatch( state )
329                 if r.groups() :
330                         s = r.group( 1 )
331                 else :
332                         s = r.group( 0 )
333                 result = s , state.clone( r.end( 0 ) - state.pos )
334                 return result
335
336         def _str( self , level , refs ) :
337
338                 return '<Regex%s %r>' % ( self._getName() , self.__data )
339
340 class Either( Base ) :
341
342         def __init__( self , *exprs ) :
343
344                 Base.__init__( self )
345                 self.__exprs = map( _preprocess , flattenSequence( exprs ) )
346
347         def _getExprs( self ) :
348
349                 return self.__exprs
350
351         def _process( self , state ) :
352
353                 branches = []
354                 for expr in self.__exprs :
355                         try :
356                                 branches += expr._parse( state )
357                         except NoMatch :
358                                 pass
359                 if not branches :
360                         raise NoMatch( state )
361                 return branches
362
363         def _str( self , level , refs ) :
364
365                 return '<EitherFork%s %s>' \
366                         % ( self._getName() , ', '.join( [ expr.asString( level , refs ) for expr in self.__exprs ] ) )
367
368 class Sequence( Base ) :
369
370         def __init__( self , *exprs ) :
371
372                 Base.__init__( self )
373                 self.__exprs = map( _preprocess , flattenSequence( exprs ) )
374
375         def _getExprs( self ) : return self.__exprs
376
377         def _process( self , state ) :
378
379                 branches = [ ( [] , state ) ]
380                 for expr in self.__exprs :
381                         newBranches = []
382                         for value , state in branches :
383                                 try :
384                                         for newValue , newState in expr._parse( state ) :
385                                                 if expr.ignorable() :
386                                                         branch = value , newState
387                                                 else :
388                                                         branch = value + [ newValue ] , newState
389                                                 newBranches.append( branch )
390                                 except NoMatch :
391                                         pass
392                         branches = newBranches
393                         if not branches :
394                                 raise NoMatch( state )
395                 return branches
396
397         def _str( self , level , refs ) :
398
399                 return '<Sequence%s %s>' \
400                         % ( self._getName() , ', '.join( [ expr.asString( level , refs ) for expr in self.__exprs ] ) )
401
402 class Multi( Base ) :
403
404         def __init__( self , min , max , expr ) :
405
406                 Base.__init__( self )
407                 self.__min = min
408                 self.__max = max
409                 self.__expr = _preprocess( expr )
410
411         def _process( self , state ) :
412
413                 branches = [ ( [] , state ) ]
414                 expr = self.__expr
415                 for i in range( self.__min ) :
416                         newBranches = []
417                         for value , state in branches :
418                                 try :
419                                         for newValue , newState in expr._parse( state ) :
420                                                 newBranches.append( ( value + [ newValue ] , newState ) )
421                                 except NoMatch :
422                                         pass
423                         branches = newBranches
424                         if not branches :
425                                 raise NoMatch( state )
426                 i = self.__min
427                 finalBranches = []
428                 while self.__max is None or i < self.__max :
429                         i += 1
430                         newBranches = []
431                         for value , state in branches :
432                                 try :
433                                         for newValue , newState in expr._parse( state ) :
434                                                 newBranches.append( ( value + [ newValue ] , newState ) )
435                                 except NoMatch :
436                                         pass
437                                 finalBranches.append( ( value , state ) )
438                         branches = newBranches
439                         if not branches :
440                                 break
441                 finalBranches += branches
442                 return finalBranches
443
444         def _str( self , level , refs ) :
445
446                 return '<Multi%s %s {%s,%s}>' \
447                         % ( self._getName() , self.__expr.asString( level , refs ) , self.__min , self.__max or '' )
448
449 class Wrapper( Base ) :
450
451         def __init__( self , expr = None ) :
452
453                 Base.__init__( self )
454                 self.__expr = _preprocess( expr )
455
456         def _process( self , branches ) :
457
458                 assert self.__expr is not None , 'Wrapper should be set with an expression'
459                 return self.__expr._parse( branches )
460
461         def set( self , expr ) :
462
463                 assert self.__expr is None , 'Wrapper already contains an expression'
464                 self.__expr = _preprocess( expr )
465                 return self
466
467         __lshift__ = set
468
469         def _str( self , level , refs ) :
470
471                 if self._getName() :
472                         return '<Wrapper%s %s>' \
473                                 % ( self._getName() , self.__expr.asString( level , refs ) )
474                 else :
475                         return self.__expr.asString( level + 1 , refs )
476
477 #--[ Misc ]------------------------------------------------------------------
478
479 def Integer() :
480
481         return Regex( r'\d+' )
482
483 def Space() :
484
485         return Regex( r'\s+' )
486
487 def Literal( s ) :
488
489         return Regex( re.escape( s ) )
490
491 def Empty() :
492
493         return Literal( '' )
494
495 def ZeroOrMore( expr ) :
496
497         return Multi( 0 , None , expr )
498
499 def OneOrMore( expr ) :
500
501         return Multi( 1 , None , expr )
502
503 def Optional( expr ) :
504
505         return Multi( 0 , 1 , expr )
506
507 def List( expr1 , expr2 ) :
508
509         def normalize( e ) :
510                 return [ e[ 0 ] ] + sum( e[ 1 ] , [] )
511
512         return Wrapper( Sequence( expr1 , ZeroOrMore( Sequence( expr2 , expr1 ) ) ).call( normalize ) )
513
514 # Local Variables:
515 # tab-width: 4
516 # python-indent: 4
517 # End: