Package nltk :: Package parse :: Module pchart :: Class BottomUpChartParser

Class BottomUpChartParser

 object --+    
          |    
api.ParserI --+
              |
             BottomUpChartParser

Known Subclasses:

An abstract bottom-up parser for PCFGs that uses a Chart to record partial results. BottomUpChartParser 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. BottomUpChartParser 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 BottomUpChartParser. 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.

Instance Methods

[hide private]

__init__(self, grammar, beam_size=0, trace=0)
Create a new BottomUpChartParser, that uses grammar to parse texts. source code

grammar(self)
Returns: The grammar used by this parser.

source code

None

trace(self, trace=2)
Set the level of tracing output that should be generated when parsing a text.

source code

list of Tree

nbest_parse(self, tokens, n=None)
Returns: A list of parse trees that represent possible structures for the given sentence.

source code

_setprob(self, tree, prod_probs)

source code

None

sort_queue(self, queue, chart)
Sort the given queue of Edges, placing the edge that should be tried first at the beginning of the queue. source code

_prune(self, queue, chart)
Discard items in the queue if the queue is longer than the beam.

source code

Inherited from api.ParserI: batch_iter_parse, batch_nbest_parse, batch_parse, batch_prob_parse, iter_parse, parse, prob_parse

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

Deprecated

Inherited from api.ParserI: batch_test, get_parse, get_parse_dict, get_parse_list, get_parse_prob

Instance Variables

[hide private]

PCFG _grammar
The grammar used to parse sentences.

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

Properties

[hide private]

Inherited from object: __class__

Method Details

[hide private]

init(self, grammar, beam_size=0, trace=0)
(Constructor)

source code

Create a new BottomUpChartParser, 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.

Overrides: object.__init__

grammar(self)

source code

Returns:: The grammar used by this parser.
Overrides: api.ParserI.grammar: (inherited documentation)

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

nbest_parse(self, tokens, n=None)

source code

Parameters:

sent - The sentence to be parsed
n - The maximum number of trees to return.

Returns: list of Tree

A list of parse trees that represent possible structures for the given sentence. When possible, this list is sorted from most likely to least likely. If n is specified, then the returned list will contain at most n parse trees.

Overrides: api.ParserI.nbest_parse

(inherited documentation)

sort_queue(self, queue, chart)

source code

Sort the given queue of Edges, 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 of Edge) - The queue of Edges 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.

Returns: None

Class BottomUpChartParser

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

grammar(self)

trace(self, trace=2)

nbest_parse(self, tokens, n=None)

sort_queue(self, queue, chart)

init(self, grammar, beam_size=0, trace=0)
(Constructor)