nltk.parse.shiftreduce module¶
- class nltk.parse.shiftreduce.ShiftReduceParser[source]¶
Bases:
ParserI
A simple bottom-up CFG parser that uses two operations, “shift” and “reduce”, to find a single parse for a text.
ShiftReduceParser
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,ShiftReduceParser
will produce the following stack, which covers “the dog saw”:[(NP: (Det: 'the') (N: 'dog')), (V: 'saw')]
ShiftReduceParser
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:
“shift” moves a token from the beginning of the text to the end of the stack.
“reduce” uses a CFG production to combine the rightmost stack elements into a single Tree.
Often, more than one operation can be performed on a given stack. In this case,
ShiftReduceParser
uses the following heuristics to decide which operation to perform:Only shift if no reductions are available.
If multiple reductions are available, then apply the reduction whose CFG production is listed earliest in the grammar.
Note that these heuristics are not guaranteed to choose an operation that leads to a parse of the text. Also, if multiple parses exists,
ShiftReduceParser
will return at most one of them.- See:
nltk.grammar
- __init__(grammar, trace=0)[source]¶
Create a new
ShiftReduceParser
, that usesgrammar
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.
- class nltk.parse.shiftreduce.SteppingShiftReduceParser[source]¶
Bases:
ShiftReduceParser
A
ShiftReduceParser
that allows you to setp through the parsing process, performing a single operation at a time. It also allows you to change the parser’s grammar midway through parsing a text.The
initialize
method is used to start parsing a text.shift
performs a single shift operation, andreduce
performs a single reduce operation.step
will perform a single reduce operation if possible; otherwise, it will perform a single shift operation.parses
returns the set of parses that have been found by the parser.- Variables:
_history – A list of
(stack, remaining_text)
pairs, containing all of the previous states of the parser. This history is used to implement theundo
operation.- See:
nltk.grammar
- __init__(grammar, trace=0)[source]¶
Create a new
ShiftReduceParser
, that usesgrammar
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.
- initialize(tokens)[source]¶
Start parsing a given text. This sets the parser’s stack to
[]
and sets its remaining text totokens
.
- parse(tokens)[source]¶
- Returns:
An iterator that generates parse trees for the sentence. When possible this list is sorted from most likely to least likely.
- Parameters:
sent (list(str)) – The sentence to be parsed
- Return type:
iter(Tree)
- parses()[source]¶
- Returns:
An iterator of the parses that have been found by this parser so far.
- Return type:
iter(Tree)
- reduce(production=None)[source]¶
Use
production
to combine the rightmost stack elements into a single Tree. Ifproduction
does not match the rightmost stack elements, then do nothing.- Returns:
The production used to reduce the stack, if a reduction was performed. If no reduction was performed, return None.
- Return type:
Production or None
- reducible_productions()[source]¶
- Returns:
A list of the productions for which reductions are available for the current parser state.
- Return type:
list(Production)
- remaining_text()[source]¶
- Returns:
The portion of the text that is not yet covered by the stack.
- Return type:
list(str)
- set_grammar(grammar)[source]¶
Change the grammar used to parse texts.
- Parameters:
grammar (CFG) – The new grammar.
- shift()[source]¶
Move a token from the beginning of the remaining text to the end of the stack. If there are no more tokens in the remaining text, then do nothing.
- Returns:
True if the shift operation was successful.
- Return type:
bool
- step()[source]¶
Perform a single parsing operation. If a reduction is possible, then perform that reduction, and return the production that it is based on. Otherwise, if a shift is possible, then perform it, and return True. Otherwise, return False.
- Returns:
False if no operation was performed; True if a shift was performed; and the CFG production used to reduce if a reduction was performed.
- Return type:
Production or bool
- undo()[source]¶
Return the parser to its state before the most recent shift or reduce operation. Calling
undo
repeatedly return the parser to successively earlier states. If no shift or reduce operations have been performed,undo
will make no changes.- Returns:
true if an operation was successfully undone.
- Return type:
bool