<s> from __future__ import print_function , unicode_literals <EOL> from nltk . grammar import Nonterminal <EOL> from nltk . tree import Tree <EOL> from nltk . compat import unicode_repr <EOL> from nltk . parse . api import ParserI <EOL> class ShiftReduceParser ( ParserI ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , grammar , trace = <NUM_LIT:0> ) : <EOL> """<STR_LIT>""" <EOL> self . _grammar = grammar <EOL> self . _trace = trace <EOL> self . _check_grammar ( ) <EOL> def grammar ( self ) : <EOL> return self . _grammar <EOL> def parse ( self , tokens ) : <EOL> tokens = list ( tokens ) <EOL> self . _grammar . check_coverage ( tokens ) <EOL> stack = [ ] <EOL> remaining_text = tokens <EOL> if self . _trace : <EOL> print ( '<STR_LIT>' % "<STR_LIT:U+0020>" . join ( tokens ) ) <EOL> self . _trace_stack ( stack , remaining_text ) <EOL> while len ( remaining_text ) > <NUM_LIT:0> : <EOL> self . _shift ( stack , remaining_text ) <EOL> while self . _reduce ( stack , remaining_text ) : pass <EOL> if len ( stack ) == <NUM_LIT:1> : <EOL> if stack [ <NUM_LIT:0> ] . label ( ) == self . _grammar . start ( ) . symbol ( ) : <EOL> yield stack [ <NUM_LIT:0> ] <EOL> def _shift ( self , stack , remaining_text ) : <EOL> """<STR_LIT>""" <EOL> stack . append ( remaining_text [ <NUM_LIT:0> ] ) <EOL> remaining_text . remove ( remaining_text [ <NUM_LIT:0> ] ) <EOL> if self . _trace : self . _trace_shift ( stack , remaining_text ) <EOL> def _match_rhs ( self , rhs , rightmost_stack ) : <EOL> """<STR_LIT>""" <EOL> if len ( rightmost_stack ) != len ( rhs ) : return False <EOL> for i in range ( len ( rightmost_stack ) ) : <EOL> if isinstance ( rightmost_stack [ i ] , Tree ) : <EOL> if not isinstance ( rhs [ i ] , Nonterminal ) : return False <EOL> if rightmost_stack [ i ] . label ( ) != rhs [ i ] . symbol ( ) : return False <EOL> else : <EOL> if isinstance ( rhs [ i ] , Nonterminal ) : return False <EOL> if rightmost_stack [ i ] != rhs [ i ] : return False <EOL> return True <EOL> def _reduce ( self , stack , remaining_text , production = None ) : <EOL> """<STR_LIT>""" <EOL> if production is None : <EOL> productions = self . _grammar . productions ( ) <EOL> else : <EOL> productions = [ production ] <EOL> for production in productions : <EOL> rhslen = len ( production . rhs ( ) ) <EOL> if self . _match_rhs ( production . rhs ( ) , stack [ - rhslen : ] ) : <EOL> tree = Tree ( production . lhs ( ) . symbol ( ) , stack [ - rhslen : ] ) <EOL> stack [ - rhslen : ] = [ tree ] <EOL> if self . _trace : <EOL> self . _trace_reduce ( stack , production , remaining_text ) <EOL> return production <EOL> return None <EOL> def trace ( self , trace = <NUM_LIT:2> ) : <EOL> """<STR_LIT>""" <EOL> self . _trace = trace <EOL> def _trace_stack ( self , stack , remaining_text , marker = '<STR_LIT:U+0020>' ) : <EOL> """<STR_LIT>""" <EOL> s = '<STR_LIT:U+0020>' + marker + '<STR_LIT>' <EOL> for elt in stack : <EOL> if isinstance ( elt , Tree ) : <EOL> s += unicode_repr ( Nonterminal ( elt . label ( ) ) ) + '<STR_LIT:U+0020>' <EOL> else : <EOL> s += unicode_repr ( elt ) + '<STR_LIT:U+0020>' <EOL> s += '<STR_LIT>' + '<STR_LIT:U+0020>' . join ( remaining_text ) + '<STR_LIT:]>' <EOL> print ( s ) <EOL> def _trace_shift ( self , stack , remaining_text ) : <EOL> """<STR_LIT>""" <EOL> if self . _trace > <NUM_LIT:2> : print ( '<STR_LIT>' % stack [ - <NUM_LIT:1> ] ) <EOL> if self . _trace == <NUM_LIT:2> : self . _trace_stack ( stack , remaining_text , '<STR_LIT:S>' ) <EOL> elif self . _trace > <NUM_LIT:0> : self . _trace_stack ( stack , remaining_text ) <EOL> def _trace_reduce ( self , stack , production , remaining_text ) : <EOL> """<STR_LIT>""" <EOL> if self . _trace > <NUM_LIT:2> : <EOL> rhs = "<STR_LIT:U+0020>" . join ( production . rhs ( ) ) <EOL> print ( '<STR_LIT>' % ( production . lhs ( ) , rhs ) ) <EOL> if self . _trace == <NUM_LIT:2> : self . _trace_stack ( stack , remaining_text , '<STR_LIT:R>' ) <EOL> elif self . _trace > <NUM_LIT:1> : self . _trace_stack ( stack , remaining_text ) <EOL> def _check_grammar ( self ) : <EOL> """<STR_LIT>""" <EOL> productions = self . _grammar . productions ( ) <EOL> for i in range ( len ( productions ) ) : <EOL> for j in range ( i + <NUM_LIT:1> , len ( productions ) ) : <EOL> rhs1 = productions [ i ] . rhs ( ) <EOL> rhs2 = productions [ j ] . rhs ( ) <EOL> if rhs1 [ : len ( rhs2 ) ] == rhs2 : <EOL> print ( '<STR_LIT>' % productions [ i ] ) <EOL> class SteppingShiftReduceParser ( ShiftReduceParser ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , grammar , trace = <NUM_LIT:0> ) : <EOL> self . _grammar = grammar <EOL> self . _trace = trace <EOL> self . _stack = None <EOL> self . _remaining_text = None <EOL> self . _history = [ ] <EOL> def parse ( self , tokens ) : <EOL> tokens = list ( tokens ) <EOL> self . initialize ( tokens ) <EOL> while self . step ( ) : <EOL> pass <EOL> return self . parses ( ) <EOL> def stack ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _stack <EOL> def remaining_text ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _remaining_text <EOL> def initialize ( self , tokens ) : <EOL> """<STR_LIT>""" <EOL> self . _stack = [ ] <EOL> self . _remaining_text = tokens <EOL> self . _history = [ ] <EOL> def step ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . reduce ( ) or self . shift ( ) <EOL> def shift ( self ) : <EOL> """<STR_LIT>""" <EOL> if len ( self . _remaining_text ) == <NUM_LIT:0> : return False <EOL> self . _history . append ( ( self . _stack [ : ] , self . _remaining_text [ : ] ) ) <EOL> self . _shift ( self . _stack , self . _remaining_text ) <EOL> return True <EOL> def reduce ( self , production = None ) : <EOL> """<STR_LIT>""" <EOL> self . _history . append ( ( self . _stack [ : ] , self . _remaining_text [ : ] ) ) <EOL> return_val = self . _reduce ( self . _stack , self . _remaining_text , <EOL> production ) <EOL> if not return_val : self . _history . pop ( ) <EOL> return return_val <EOL> def undo ( self ) : <EOL> """<STR_LIT>""" <EOL> if len ( self . _history ) == <NUM_LIT:0> : return False <EOL> ( self . _stack , self . _remaining_text ) = self . _history . pop ( ) <EOL> return True <EOL> def reducible_productions ( self ) : <EOL> """<STR_LIT>""" <EOL> productions = [ ] <EOL> for production in self . _grammar . productions ( ) : <EOL> rhslen = len ( production . rhs ( ) ) <EOL> if self . _match_rhs ( production . rhs ( ) , self . _stack [ - rhslen : ] ) : <EOL> productions . append ( production ) <EOL> return productions <EOL> def parses ( self ) : <EOL> """<STR_LIT>""" <EOL> if ( len ( self . _remaining_text ) == <NUM_LIT:0> and <EOL> len ( self . _stack ) == <NUM_LIT:1> and <EOL> self . _stack [ <NUM_LIT:0> ] . label ( ) == self . _grammar . start ( ) . symbol ( ) <EOL> ) : <EOL> yield self . _stack [ <NUM_LIT:0> ] <EOL> def set_grammar ( self , grammar ) : <EOL> """<STR_LIT>""" <EOL> self . _grammar = grammar <EOL> def demo ( ) : <EOL> """<STR_LIT>""" <EOL> from nltk import parse , CFG <EOL> grammar = CFG . fromstring ( """<STR_LIT>""" ) <EOL> sent = '<STR_LIT>' . split ( ) <EOL> parser = parse . ShiftReduceParser ( grammar , trace = <NUM_LIT:2> ) <EOL> for p in parser . parse ( sent ) : <EOL> print ( p ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> demo ( ) </s>
