Package nltk_lite :: Package parse :: Module sr :: Class ShiftReduce
[hide private]
[frames] | no frames]

Class ShiftReduce

source code

object --+        
         |        
    ParseI --+    
             |    
 AbstractParse --+
                 |
                ShiftReduce
Known Subclasses:
SteppingShiftReduce

A simple bottom-up CFG parser that uses two operations, "shift" and "reduce", to find a single parse for a text.

ShiftReduce maintains a stack, which records the structure of a portion of the text. This stack is a list of Strings and Trees that collectively cover a portion of the text. For example, while parsing the sentence "the dog saw the man" with a typical grammar, ShiftReduce will produce the following stack, which covers "the dog saw":

  [(NP: (Det: 'the') (N: 'dog')), (V: 'saw')]

ShiftReduce attempts to extend the stack to cover the entire text, and to combine the stack elements into a single tree, producing a complete parse for the sentence.

Initially, the stack is empty. It is extended to cover the text, from left to right, by repeatedly applying two operations:

Often, more than one operation can be performed on a given stack. In this case, ShiftReduce uses the following heuristics to decide which operation to perform:

Note that these heuristics are not guaranteed to choose an operation that leads to a parse of the text. Also, if multiple parses exists, ShiftReduce will return at most one of them.


See Also: nltk.cfg

Instance Methods [hide private]
 
__init__(self, grammar, trace=0)
Create a new ShiftReduce, that uses grammar to parse texts.
source code
Tree
get_parse(self, tokens)
Returns: A parse tree that represents the structure of the sentence.
source code
None
_shift(self, stack, remaining_text)
Move a token from the beginning of remaining_text to the end of stack.
source code
boolean
_match_rhs(self, rhs, rightmost_stack)
Returns: true if the right hand side of a CFG production matches the rightmost elements of the stack.
source code
Production or None
_reduce(self, stack, remaining_text, production=None)
Find a CFG production whose right hand side matches the rightmost stack elements; and combine those stack elements into a single Tree, with the node specified by the production's left-hand side.
source code
None
trace(self, trace=2)
Set the level of tracing output that should be generated when parsing a text.
source code
None
_trace_stack(self, stack, remaining_text, marker=' ')
Print trace output displaying the given stack and text.
source code
None
_trace_shift(self, stack, remaining_text)
Print trace output displaying that a token has been shifted.
source code
None
_trace_reduce(self, stack, production, remaining_text)
Print trace output displaying that production was used to reduce stack.
source code
None
_check_grammar(self)
Check to make sure that all of the CFG productions are potentially useful.
source code

Inherited from AbstractParse: get_parse_list, grammar, parse

Inherited from ParseI: get_parse_dict, get_parse_probs

Inherited from object: __delattr__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __str__

Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, grammar, trace=0)
(Constructor)

source code 

Create a new ShiftReduce, that uses grammar to parse texts.

Parameters:
  • grammar (Grammar) - The grammar used to parse texts.
  • trace (int) - The level of tracing that should be used when parsing a text. 0 will generate no tracing output; and higher numbers will produce more verbose tracing output.
Overrides: AbstractParse.__init__

get_parse(self, tokens)

source code 
Returns: Tree
A parse tree that represents the structure of the sentence. If no parse is found, then return None.
Overrides: AbstractParse.get_parse

_shift(self, stack, remaining_text)

source code 

Move a token from the beginning of remaining_text to the end of stack.

Parameters:
  • stack (list of String and Tree) - A list of Strings and Trees, encoding the structure of the text that has been parsed so far.
  • remaining_text (list of String) - The portion of the text that is not yet covered by stack.
Returns: None

_match_rhs(self, rhs, rightmost_stack)

source code 
Parameters:
  • rhs (list of (terminal and Nonterminal)) - The right hand side of a CFG production.
  • rightmost_stack (list of (String and Tree)) - The rightmost elements of the parser's stack.
Returns: boolean
true if the right hand side of a CFG production matches the rightmost elements of the stack. rhs matches rightmost_stack if they are the same length, and each element of rhs matches the corresponding element of rightmost_stack. A nonterminal element of rhs matches any Tree whose node value is equal to the nonterminal's symbol. A terminal element of rhs matches any String whose type is equal to the terminal.

_reduce(self, stack, remaining_text, production=None)

source code 

Find a CFG production whose right hand side matches the rightmost stack elements; and combine those stack elements into a single Tree, with the node specified by the production's left-hand side. If more than one CFG production matches the stack, then use the production that is listed earliest in the grammar. The new Tree replaces the elements in the stack.

Parameters:
  • stack (list of String and Tree) - A list of Strings and Trees, encoding the structure of the text that has been parsed so far.
  • remaining_text (list of String) - The portion of the text that is not yet covered by stack.
Returns: Production or None
If a reduction is performed, then return the CFG production that the reduction is based on; otherwise, return false.

trace(self, trace=2)

source code 

Set the level of tracing output that should be generated when parsing a text.

Parameters:
  • trace (int) - The trace level. A trace level of 0 will generate no tracing output; and higher trace levels will produce more verbose tracing output.
Returns: None

_trace_stack(self, stack, remaining_text, marker=' ')

source code 

Print trace output displaying the given stack and text.

Parameters:
  • marker - A character that is printed to the left of the stack. This is used with trace level 2 to print 'S' before shifted stacks and 'R' before reduced stacks.
Returns: None

_check_grammar(self)

source code 

Check to make sure that all of the CFG productions are potentially useful. If any productions can never be used, then print a warning.

Returns: None