<s> """<STR_LIT>""" <EOL> from collections import defaultdict <EOL> from pprint import pprint <EOL> try : <EOL> from nltk import Tree <EOL> def nltk_tree ( t ) : <EOL> return Tree ( t [ <NUM_LIT:0> ] , [ c if isinstance ( c , basestring ) else nltk_tree ( c ) for c in t [ <NUM_LIT:1> : ] ] ) <EOL> nltk_is_available = True <EOL> except ImportError : <EOL> nltk_is_available = False <EOL> from stat_parser . learn import build_model <EOL> from stat_parser . tokenizer import PennTreebankTokenizer <EOL> from stat_parser . treebanks . normalize import un_chomsky_normal_form <EOL> from stat_parser . word_classes import is_cap_word <EOL> def argmax ( lst ) : <EOL> return max ( lst ) if lst else ( <NUM_LIT:0.0> , None ) <EOL> def backtrace ( back , bp ) : <EOL> if not back : return None <EOL> if len ( back ) == <NUM_LIT:6> : <EOL> ( X , Y , Z , i , s , j ) = back <EOL> return [ X , backtrace ( bp [ i , s , Y ] , bp ) , <EOL> backtrace ( bp [ s + <NUM_LIT:1> , j , Z ] , bp ) ] <EOL> else : <EOL> ( X , Y , i , i ) = back <EOL> return [ X , Y ] <EOL> def CKY ( pcfg , norm_words ) : <EOL> x , n = [ ( "<STR_LIT>" , "<STR_LIT>" ) ] + norm_words , len ( norm_words ) <EOL> pi = defaultdict ( float ) <EOL> bp = defaultdict ( tuple ) <EOL> for i in range ( <NUM_LIT:1> , n + <NUM_LIT:1> ) : <EOL> for X in pcfg . N : <EOL> norm , word = x [ i ] <EOL> if ( X , norm ) in pcfg . q1 : <EOL> pi [ i , i , X ] = pcfg . q1 [ X , norm ] <EOL> bp [ i , i , X ] = ( X , word , i , i ) <EOL> for l in range ( <NUM_LIT:1> , n ) : <EOL> for i in range ( <NUM_LIT:1> , n - l + <NUM_LIT:1> ) : <EOL> j = i + l <EOL> for X in pcfg . N : <EOL> score , back = argmax ( [ ( <EOL> pcfg . q2 [ X , Y , Z ] * pi [ i , s , Y ] * pi [ s + <NUM_LIT:1> , j , Z ] , <EOL> ( X , Y , Z , i , s , j ) <EOL> ) for s in range ( i , j ) <EOL> for Y , Z in pcfg . binary_rules [ X ] <EOL> if pi [ i , s , Y ] > <NUM_LIT:0.0> <EOL> if pi [ s + <NUM_LIT:1> , j , Z ] > <NUM_LIT:0.0> <EOL> ] ) <EOL> if score > <NUM_LIT:0.0> : <EOL> bp [ i , j , X ] , pi [ i , j , X ] = back , score <EOL> _ , top = max ( [ ( pi [ <NUM_LIT:1> , n , X ] , bp [ <NUM_LIT:1> , n , X ] ) for X in pcfg . N ] ) <EOL> return backtrace ( top , bp ) <EOL> class Parser : <EOL> def __init__ ( self , pcfg = None ) : <EOL> if pcfg is None : <EOL> pcfg = build_model ( ) <EOL> self . pcfg = pcfg <EOL> self . tokenizer = PennTreebankTokenizer ( ) <EOL> if nltk_is_available : <EOL> self . parse = self . nltk_parse <EOL> else : <EOL> self . parse = self . raw_parse <EOL> def norm_parse ( self , sentence ) : <EOL> words = self . tokenizer . tokenize ( sentence ) <EOL> if is_cap_word ( words [ <NUM_LIT:0> ] ) : <EOL> words [ <NUM_LIT:0> ] = words [ <NUM_LIT:0> ] . lower ( ) <EOL> norm_words = [ ] <EOL> for word in words : <EOL> if isinstance ( word , tuple ) : <EOL> norm_words . append ( word ) <EOL> else : <EOL> norm_words . append ( ( self . pcfg . norm_word ( word ) , word ) ) <EOL> return CKY ( self . pcfg , norm_words ) <EOL> def raw_parse ( self , sentence ) : <EOL> tree = self . norm_parse ( sentence ) <EOL> un_chomsky_normal_form ( tree ) <EOL> return tree <EOL> def nltk_parse ( self , sentence ) : <EOL> return nltk_tree ( self . raw_parse ( sentence ) ) <EOL> def display_tree ( tree ) : <EOL> if nltk_is_available : <EOL> tree . draw ( ) <EOL> else : <EOL> pprint ( tree ) </s>
