<s> """<STR_LIT>""" <EOL> __author__ = "<STR_LIT>" <EOL> import sys <EOL> from StringIO import StringIO <EOL> HUGE = <NUM_LIT> <EOL> _type_reprs = { } <EOL> def type_repr ( type_num ) : <EOL> global _type_reprs <EOL> if not _type_reprs : <EOL> from pygram import python_symbols <EOL> for name , val in python_symbols . __dict__ . items ( ) : <EOL> if type ( val ) == int : _type_reprs [ val ] = name <EOL> return _type_reprs . setdefault ( type_num , type_num ) <EOL> class Base ( object ) : <EOL> """<STR_LIT>""" <EOL> type = None <EOL> parent = None <EOL> children = ( ) <EOL> was_changed = False <EOL> def __new__ ( cls , * args , ** kwds ) : <EOL> """<STR_LIT>""" <EOL> assert cls is not Base , "<STR_LIT>" <EOL> return object . __new__ ( cls ) <EOL> def __eq__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if self . __class__ is not other . __class__ : <EOL> return NotImplemented <EOL> return self . _eq ( other ) <EOL> def __ne__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if self . __class__ is not other . __class__ : <EOL> return NotImplemented <EOL> return not self . _eq ( other ) <EOL> def _eq ( self , other ) : <EOL> """<STR_LIT>""" <EOL> raise NotImplementedError <EOL> def clone ( self ) : <EOL> """<STR_LIT>""" <EOL> raise NotImplementedError <EOL> def post_order ( self ) : <EOL> """<STR_LIT>""" <EOL> raise NotImplementedError <EOL> def pre_order ( self ) : <EOL> """<STR_LIT>""" <EOL> raise NotImplementedError <EOL> def set_prefix ( self , prefix ) : <EOL> """<STR_LIT>""" <EOL> raise NotImplementedError <EOL> def get_prefix ( self ) : <EOL> """<STR_LIT>""" <EOL> raise NotImplementedError <EOL> def replace ( self , new ) : <EOL> """<STR_LIT>""" <EOL> assert self . parent is not None , str ( self ) <EOL> assert new is not None <EOL> if not isinstance ( new , list ) : <EOL> new = [ new ] <EOL> l_children = [ ] <EOL> found = False <EOL> for ch in self . parent . children : <EOL> if ch is self : <EOL> assert not found , ( self . parent . children , self , new ) <EOL> if new is not None : <EOL> l_children . extend ( new ) <EOL> found = True <EOL> else : <EOL> l_children . append ( ch ) <EOL> assert found , ( self . children , self , new ) <EOL> self . parent . changed ( ) <EOL> self . parent . children = l_children <EOL> for x in new : <EOL> x . parent = self . parent <EOL> self . parent = None <EOL> def get_lineno ( self ) : <EOL> """<STR_LIT>""" <EOL> node = self <EOL> while not isinstance ( node , Leaf ) : <EOL> if not node . children : <EOL> return <EOL> node = node . children [ <NUM_LIT:0> ] <EOL> return node . lineno <EOL> def changed ( self ) : <EOL> if self . parent : <EOL> self . parent . changed ( ) <EOL> self . was_changed = True <EOL> def remove ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . parent : <EOL> for i , node in enumerate ( self . parent . children ) : <EOL> if node is self : <EOL> self . parent . changed ( ) <EOL> del self . parent . children [ i ] <EOL> self . parent = None <EOL> return i <EOL> def get_next_sibling ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . parent is None : <EOL> return None <EOL> for i , child in enumerate ( self . parent . children ) : <EOL> if child is self : <EOL> try : <EOL> return self . parent . children [ i + <NUM_LIT:1> ] <EOL> except IndexError : <EOL> return None <EOL> def get_prev_sibling ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . parent is None : <EOL> return None <EOL> for i , child in enumerate ( self . parent . children ) : <EOL> if child is self : <EOL> if i == <NUM_LIT:0> : <EOL> return None <EOL> return self . parent . children [ i - <NUM_LIT:1> ] <EOL> def get_suffix ( self ) : <EOL> """<STR_LIT>""" <EOL> next_sib = self . get_next_sibling ( ) <EOL> if next_sib is None : <EOL> return "<STR_LIT>" <EOL> return next_sib . get_prefix ( ) <EOL> class Node ( Base ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , type , children , context = None , prefix = None ) : <EOL> """<STR_LIT>""" <EOL> assert type >= <NUM_LIT> , type <EOL> self . type = type <EOL> self . children = list ( children ) <EOL> for ch in self . children : <EOL> assert ch . parent is None , repr ( ch ) <EOL> ch . parent = self <EOL> if prefix is not None : <EOL> self . set_prefix ( prefix ) <EOL> def __repr__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return "<STR_LIT>" % ( self . __class__ . __name__ , <EOL> type_repr ( self . type ) , <EOL> self . children ) <EOL> def __str__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return "<STR_LIT>" . join ( map ( str , self . children ) ) <EOL> def _eq ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return ( self . type , self . children ) == ( other . type , other . children ) <EOL> def clone ( self ) : <EOL> """<STR_LIT>""" <EOL> return Node ( self . type , [ ch . clone ( ) for ch in self . children ] ) <EOL> def post_order ( self ) : <EOL> """<STR_LIT>""" <EOL> for child in self . children : <EOL> for node in child . post_order ( ) : <EOL> yield node <EOL> yield self <EOL> def pre_order ( self ) : <EOL> """<STR_LIT>""" <EOL> yield self <EOL> for child in self . children : <EOL> for node in child . post_order ( ) : <EOL> yield node <EOL> def set_prefix ( self , prefix ) : <EOL> """<STR_LIT>""" <EOL> if self . children : <EOL> self . children [ <NUM_LIT:0> ] . set_prefix ( prefix ) <EOL> def get_prefix ( self ) : <EOL> """<STR_LIT>""" <EOL> if not self . children : <EOL> return "<STR_LIT>" <EOL> return self . children [ <NUM_LIT:0> ] . get_prefix ( ) <EOL> def set_child ( self , i , child ) : <EOL> """<STR_LIT>""" <EOL> child . parent = self <EOL> self . children [ i ] . parent = None <EOL> self . children [ i ] = child <EOL> self . changed ( ) <EOL> def insert_child ( self , i , child ) : <EOL> """<STR_LIT>""" <EOL> child . parent = self <EOL> self . children . insert ( i , child ) <EOL> self . changed ( ) <EOL> def append_child ( self , child ) : <EOL> """<STR_LIT>""" <EOL> child . parent = self <EOL> self . children . append ( child ) <EOL> self . changed ( ) <EOL> class Leaf ( Base ) : <EOL> """<STR_LIT>""" <EOL> prefix = "<STR_LIT>" <EOL> lineno = <NUM_LIT:0> <EOL> column = <NUM_LIT:0> <EOL> def __init__ ( self , type , value , context = None , prefix = None ) : <EOL> """<STR_LIT>""" <EOL> assert <NUM_LIT:0> <= type < <NUM_LIT> , type <EOL> if context is not None : <EOL> self . prefix , ( self . lineno , self . column ) = context <EOL> self . type = type <EOL> self . value = value <EOL> if prefix is not None : <EOL> self . prefix = prefix <EOL> def __repr__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return "<STR_LIT>" % ( self . __class__ . __name__ , <EOL> self . type , <EOL> self . value ) <EOL> def __str__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . prefix + str ( self . value ) <EOL> def _eq ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return ( self . type , self . value ) == ( other . type , other . value ) <EOL> def clone ( self ) : <EOL> """<STR_LIT>""" <EOL> return Leaf ( self . type , self . value , <EOL> ( self . prefix , ( self . lineno , self . column ) ) ) <EOL> def post_order ( self ) : <EOL> """<STR_LIT>""" <EOL> yield self <EOL> def pre_order ( self ) : <EOL> """<STR_LIT>""" <EOL> yield self <EOL> def set_prefix ( self , prefix ) : <EOL> """<STR_LIT>""" <EOL> self . changed ( ) <EOL> self . prefix = prefix <EOL> def get_prefix ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . prefix <EOL> def convert ( gr , raw_node ) : <EOL> """<STR_LIT>""" <EOL> type , value , context , children = raw_node <EOL> if children or type in gr . number2symbol : <EOL> if len ( children ) == <NUM_LIT:1> : <EOL> return children [ <NUM_LIT:0> ] <EOL> return Node ( type , children , context = context ) <EOL> else : <EOL> return Leaf ( type , value , context = context ) <EOL> class BasePattern ( object ) : <EOL> """<STR_LIT>""" <EOL> type = None <EOL> content = None <EOL> name = None <EOL> def __new__ ( cls , * args , ** kwds ) : <EOL> """<STR_LIT>""" <EOL> assert cls is not BasePattern , "<STR_LIT>" <EOL> return object . __new__ ( cls ) <EOL> def __repr__ ( self ) : <EOL> args = [ type_repr ( self . type ) , self . content , self . name ] <EOL> while args and args [ - <NUM_LIT:1> ] is None : <EOL> del args [ - <NUM_LIT:1> ] <EOL> return "<STR_LIT>" % ( self . __class__ . __name__ , "<STR_LIT:U+002CU+0020>" . join ( map ( repr , args ) ) ) <EOL> def optimize ( self ) : <EOL> """<STR_LIT>""" <EOL> return self <EOL> def match ( self , node , results = None ) : <EOL> """<STR_LIT>""" <EOL> if self . type is not None and node . type != self . type : <EOL> return False <EOL> if self . content is not None : <EOL> r = None <EOL> if results is not None : <EOL> r = { } <EOL> if not self . _submatch ( node , r ) : <EOL> return False <EOL> if r : <EOL> results . update ( r ) <EOL> if results is not None and self . name : <EOL> results [ self . name ] = node <EOL> return True <EOL> def match_seq ( self , nodes , results = None ) : <EOL> """<STR_LIT>""" <EOL> if len ( nodes ) != <NUM_LIT:1> : <EOL> return False <EOL> return self . match ( nodes [ <NUM_LIT:0> ] , results ) <EOL> def generate_matches ( self , nodes ) : <EOL> """<STR_LIT>""" <EOL> r = { } <EOL> if nodes and self . match ( nodes [ <NUM_LIT:0> ] , r ) : <EOL> yield <NUM_LIT:1> , r <EOL> class LeafPattern ( BasePattern ) : <EOL> def __init__ ( self , type = None , content = None , name = None ) : <EOL> """<STR_LIT>""" <EOL> if type is not None : <EOL> assert <NUM_LIT:0> <= type < <NUM_LIT> , type <EOL> if content is not None : <EOL> assert isinstance ( content , basestring ) , repr ( content ) <EOL> self . type = type <EOL> self . content = content <EOL> self . name = name <EOL> def match ( self , node , results = None ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( node , Leaf ) : <EOL> return False <EOL> return BasePattern . match ( self , node , results ) <EOL> def _submatch ( self , node , results = None ) : <EOL> """<STR_LIT>""" <EOL> return self . content == node . value <EOL> class NodePattern ( BasePattern ) : <EOL> wildcards = False <EOL> def __init__ ( self , type = None , content = None , name = None ) : <EOL> """<STR_LIT>""" <EOL> if type is not None : <EOL> assert type >= <NUM_LIT> , type <EOL> if content is not None : <EOL> assert not isinstance ( content , basestring ) , repr ( content ) <EOL> content = list ( content ) <EOL> for i , item in enumerate ( content ) : <EOL> assert isinstance ( item , BasePattern ) , ( i , item ) <EOL> if isinstance ( item , WildcardPattern ) : <EOL> self . wildcards = True <EOL> self . type = type <EOL> self . content = content <EOL> self . name = name <EOL> def _submatch ( self , node , results = None ) : <EOL> """<STR_LIT>""" <EOL> if self . wildcards : <EOL> for c , r in generate_matches ( self . content , node . children ) : <EOL> if c == len ( node . children ) : <EOL> if results is not None : <EOL> results . update ( r ) <EOL> return True <EOL> return False <EOL> if len ( self . content ) != len ( node . children ) : <EOL> return False <EOL> for subpattern , child in zip ( self . content , node . children ) : <EOL> if not subpattern . match ( child , results ) : <EOL> return False <EOL> return True <EOL> class WildcardPattern ( BasePattern ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , content = None , min = <NUM_LIT:0> , max = HUGE , name = None ) : <EOL> """<STR_LIT>""" <EOL> assert <NUM_LIT:0> <= min <= max <= HUGE , ( min , max ) <EOL> if content is not None : <EOL> content = tuple ( map ( tuple , content ) ) <EOL> assert len ( content ) , repr ( content ) <EOL> for alt in content : <EOL> assert len ( alt ) , repr ( alt ) <EOL> self . content = content <EOL> self . min = min <EOL> self . max = max <EOL> self . name = name <EOL> def optimize ( self ) : <EOL> """<STR_LIT>""" <EOL> subpattern = None <EOL> if ( self . content is not None and <EOL> len ( self . content ) == <NUM_LIT:1> and len ( self . content [ <NUM_LIT:0> ] ) == <NUM_LIT:1> ) : <EOL> subpattern = self . content [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] <EOL> if self . min == <NUM_LIT:1> and self . max == <NUM_LIT:1> : <EOL> if self . content is None : <EOL> return NodePattern ( name = self . name ) <EOL> if subpattern is not None and self . name == subpattern . name : <EOL> return subpattern . optimize ( ) <EOL> if ( self . min <= <NUM_LIT:1> and isinstance ( subpattern , WildcardPattern ) and <EOL> subpattern . min <= <NUM_LIT:1> and self . name == subpattern . name ) : <EOL> return WildcardPattern ( subpattern . content , <EOL> self . min * subpattern . min , <EOL> self . max * subpattern . max , <EOL> subpattern . name ) <EOL> return self <EOL> def match ( self , node , results = None ) : <EOL> """<STR_LIT>""" <EOL> return self . match_seq ( [ node ] , results ) <EOL> def match_seq ( self , nodes , results = None ) : <EOL> """<STR_LIT>""" <EOL> for c , r in self . generate_matches ( nodes ) : <EOL> if c == len ( nodes ) : <EOL> if results is not None : <EOL> results . update ( r ) <EOL> if self . name : <EOL> results [ self . name ] = list ( nodes ) <EOL> return True <EOL> return False <EOL> def generate_matches ( self , nodes ) : <EOL> """<STR_LIT>""" <EOL> if self . content is None : <EOL> for count in xrange ( self . min , <NUM_LIT:1> + min ( len ( nodes ) , self . max ) ) : <EOL> r = { } <EOL> if self . name : <EOL> r [ self . name ] = nodes [ : count ] <EOL> yield count , r <EOL> elif self . name == "<STR_LIT>" : <EOL> yield self . _bare_name_matches ( nodes ) <EOL> else : <EOL> save_stderr = sys . stderr <EOL> sys . stderr = StringIO ( ) <EOL> try : <EOL> for count , r in self . _recursive_matches ( nodes , <NUM_LIT:0> ) : <EOL> if self . name : <EOL> r [ self . name ] = nodes [ : count ] <EOL> yield count , r <EOL> except RuntimeError : <EOL> for count , r in self . _iterative_matches ( nodes ) : <EOL> if self . name : <EOL> r [ self . name ] = nodes [ : count ] <EOL> yield count , r <EOL> finally : <EOL> sys . stderr = save_stderr <EOL> def _iterative_matches ( self , nodes ) : <EOL> """<STR_LIT>""" <EOL> nodelen = len ( nodes ) <EOL> if <NUM_LIT:0> >= self . min : <EOL> yield <NUM_LIT:0> , { } <EOL> results = [ ] <EOL> for alt in self . content : <EOL> for c , r in generate_matches ( alt , nodes ) : <EOL> yield c , r <EOL> results . append ( ( c , r ) ) <EOL> while results : <EOL> new_results = [ ] <EOL> for c0 , r0 in results : <EOL> if c0 < nodelen and c0 <= self . max : <EOL> for alt in self . content : <EOL> for c1 , r1 in generate_matches ( alt , nodes [ c0 : ] ) : <EOL> if c1 > <NUM_LIT:0> : <EOL> r = { } <EOL> r . update ( r0 ) <EOL> r . update ( r1 ) <EOL> yield c0 + c1 , r <EOL> new_results . append ( ( c0 + c1 , r ) ) <EOL> results = new_results <EOL> def _bare_name_matches ( self , nodes ) : <EOL> """<STR_LIT>""" <EOL> count = <NUM_LIT:0> <EOL> r = { } <EOL> done = False <EOL> max = len ( nodes ) <EOL> while not done and count < max : <EOL> done = True <EOL> for leaf in self . content : <EOL> if leaf [ <NUM_LIT:0> ] . match ( nodes [ count ] , r ) : <EOL> count += <NUM_LIT:1> <EOL> done = False <EOL> break <EOL> r [ self . name ] = nodes [ : count ] <EOL> return count , r <EOL> def _recursive_matches ( self , nodes , count ) : <EOL> """<STR_LIT>""" <EOL> assert self . content is not None <EOL> if count >= self . min : <EOL> yield <NUM_LIT:0> , { } <EOL> if count < self . max : <EOL> for alt in self . content : <EOL> for c0 , r0 in generate_matches ( alt , nodes ) : <EOL> for c1 , r1 in self . _recursive_matches ( nodes [ c0 : ] , count + <NUM_LIT:1> ) : <EOL> r = { } <EOL> r . update ( r0 ) <EOL> r . update ( r1 ) <EOL> yield c0 + c1 , r <EOL> class NegatedPattern ( BasePattern ) : <EOL> def __init__ ( self , content = None ) : <EOL> """<STR_LIT>""" <EOL> if content is not None : <EOL> assert isinstance ( content , BasePattern ) , repr ( content ) <EOL> self . content = content <EOL> def match ( self , node ) : <EOL> return False <EOL> def match_seq ( self , nodes ) : <EOL> return len ( nodes ) == <NUM_LIT:0> <EOL> def generate_matches ( self , nodes ) : <EOL> if self . content is None : <EOL> if len ( nodes ) == <NUM_LIT:0> : <EOL> yield <NUM_LIT:0> , { } <EOL> else : <EOL> for c , r in self . content . generate_matches ( nodes ) : <EOL> return <EOL> yield <NUM_LIT:0> , { } <EOL> def generate_matches ( patterns , nodes ) : <EOL> """<STR_LIT>""" <EOL> if not patterns : <EOL> yield <NUM_LIT:0> , { } <EOL> else : <EOL> p , rest = patterns [ <NUM_LIT:0> ] , patterns [ <NUM_LIT:1> : ] <EOL> for c0 , r0 in p . generate_matches ( nodes ) : <EOL> if not rest : <EOL> yield c0 , r0 <EOL> else : <EOL> for c1 , r1 in generate_matches ( rest , nodes [ c0 : ] ) : <EOL> r = { } <EOL> r . update ( r0 ) <EOL> r . update ( r1 ) <EOL> yield c0 + c1 , r </s>
