class ShiftReduceParser(ParserI): (source)
Known subclasses: nltk.parse.shiftreduce.SteppingShiftReduceParser
Constructor: ShiftReduceParser(grammar, trace)
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 Also | |
| nltk.grammar |
| Method | __init__ |
Create a new ShiftReduceParser, that uses grammar to parse texts. |
| Method | grammar |
No summary |
| Method | parse |
When possible this list is sorted from most likely to least likely. |
| Method | trace |
Set the level of tracing output that should be generated when parsing a text. |
| Method | _check |
Check to make sure that all of the CFG productions are potentially useful. If any productions can never be used, then print a warning. |
| Method | _match |
No summary |
| Method | _reduce |
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... |
| Method | _shift |
Move a token from the beginning of remaining_text to the end of stack. |
| Method | _trace |
Print trace output displaying that production was used to reduce stack. |
| Method | _trace |
Print trace output displaying that a token has been shifted. |
| Method | _trace |
Print trace output displaying the given stack and text. |
| Instance Variable | _grammar |
Undocumented |
| Instance Variable | _trace |
Undocumented |
Inherited from ParserI:
| Method | parse |
No summary |
| Method | parse |
No summary |
| Method | parse |
Apply self.parse() to each element of sents. :rtype: iter(iter(Tree)) |
nltk.parse.shiftreduce.SteppingShiftReduceParserCreate a new ShiftReduceParser, 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. |
nltk.parse.api.ParserI.parsenltk.parse.shiftreduce.SteppingShiftReduceParserWhen possible this list is sorted from most likely to least likely.
| Parameters | |
| tokens | Undocumented |
| sent:list(str) | The sentence to be parsed |
| Returns | |
| iter(Tree) | An iterator that generates parse trees for the sentence. |
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 | Undocumented |
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 | Undocumented |
| Parameters | |
| rhs:list(terminal and Nonterminal) | The right hand side of a CFG production. |
| rightmost | The rightmost elements of the parser's stack. |
| Returns | |
| bool | 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. |
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(string and Tree) | A list of strings and Trees, encoding the structure of the text that has been parsed so far. |
| remaining | The portion of the text that is not yet covered by stack. |
| production | Undocumented |
| Returns | |
| Production or None | If a reduction is performed, then return the CFG production that the reduction is based on; otherwise, return false. |
Move a token from the beginning of remaining_text to the end of stack.
| Parameters | |
| stack:list(str and Tree) | A list of strings and Trees, encoding the structure of the text that has been parsed so far. |
| remaining | The portion of the text that is not yet covered by stack. |
| Returns | |
| None | Undocumented |