nltk.parse.BottomUpProbabilisticChartParser

class nltk.parse.BottomUpProbabilisticChartParser[source]

Bases: ParserI

An abstract bottom-up parser for PCFG grammars that uses a Chart to record partial results. BottomUpProbabilisticChartParser maintains a queue of edges that can be added to the chart. This queue is initialized with edges for each token in the text that is being parsed. BottomUpProbabilisticChartParser inserts these edges into the chart one at a time, starting with the most likely edges, and proceeding to less likely edges. For each edge that is added to the chart, it may become possible to insert additional edges into the chart; these are added to the queue. This process continues until enough complete parses have been generated, or until the queue is empty.

The sorting order for the queue is not specified by BottomUpProbabilisticChartParser. Different sorting orders will result in different search strategies. The sorting order for the queue is defined by the method sort_queue; subclasses are required to provide a definition for this method.

Variables

  • _grammar – The grammar used to parse sentences.

  • _trace – The level of tracing output that should be generated when parsing a text.

__init__(grammar, beam_size=0, trace=0)[source]

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

Parameters

  • grammar (PCFG) – The grammar used to parse texts.

  • beam_size (int) – The maximum length for the parser’s edge queue.

  • 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.

grammar()[source]
Returns

The grammar used by this parser.

trace(trace=2)[source]

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.

Return type

None

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)

sort_queue(queue, chart)[source]

Sort the given queue of Edge objects, placing the edge that should be tried first at the beginning of the queue. This method will be called after each Edge is added to the queue.

Parameters

  • queue (list(Edge)) – The queue of Edge objects to sort. Each edge in this queue is an edge that could be added to the chart by the fundamental rule; but that has not yet been added.

  • chart (Chart) – The chart being used to parse the text. This chart can be used to provide extra information for sorting the queue.

Return type

None

parse_all(sent, *args, **kwargs)[source]
Return type

list(Tree)

parse_one(sent, *args, **kwargs)[source]
Return type

Tree or None

parse_sents(sents, *args, **kwargs)[source]

Apply self.parse() to each element of sents. :rtype: iter(iter(Tree))