class nltk.parse.ShiftReduceParser(grammar, trace=0)[source]

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.



__init__(grammar[, trace]) Create a new ShiftReduceParser, that uses grammar to parse texts.
parse_all(sent, *args, **kwargs)
parse_one(sent, *args, **kwargs)
rtype:Tree or None
parse_sents(sents, *args, **kwargs) Apply self.parse() to each element of sents.
trace([trace]) Set the level of tracing output that should be generated when parsing a text.