nltk.parse.pchart module

Classes and interfaces for associating probabilities with tree structures that represent the internal organization of a text. The probabilistic parser module defines BottomUpProbabilisticChartParser.

BottomUpProbabilisticChartParser is an abstract class that implements a bottom-up chart parser for PCFG grammars. It maintains a queue of edges, and adds them to the chart one at a time. The ordering of this queue is based on the probabilities associated with the edges, allowing the parser to expand more likely edges before less likely ones. Each subclass implements a different queue ordering, producing different search strategies. Currently the following subclasses are defined:

• InsideChartParser searches edges in decreasing order of their trees’ inside probabilities.

• RandomChartParser searches edges in random order.

• LongestChartParser searches edges in decreasing order of their location’s length.

The BottomUpProbabilisticChartParser constructor has an optional argument beam_size. If non-zero, this controls the size of the beam (aka the edge queue). This option is most useful with InsideChartParser.

class nltk.parse.pchart.BottomUpProbabilisticChartParser

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)

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()

Returns

The grammar used by this parser.

parse(tokens)

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)

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

trace(trace=2)

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

class nltk.parse.pchart.InsideChartParser

Bases: BottomUpProbabilisticChartParser

A bottom-up parser for PCFG grammars that tries edges in descending order of the inside probabilities of their trees. The “inside probability” of a tree is simply the probability of the entire tree, ignoring its context. In particular, the inside probability of a tree generated by production p with children c[1], c[2], …, c[n] is P(p)P(c[1])P(c[2])…P(c[n]); and the inside probability of a token is 1 if it is present in the text, and 0 if it is absent.

This sorting order results in a type of lowest-cost-first search strategy.

sort_queue(queue, chart)

Sort the given queue of edges, in descending order of the inside probabilities of the edges’ trees.

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

class nltk.parse.pchart.LongestChartParser

Bases: BottomUpProbabilisticChartParser

A bottom-up parser for PCFG grammars that tries longer edges before shorter ones. This sorting order results in a type of best-first search strategy.

sort_queue(queue, chart)

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

class nltk.parse.pchart.ProbabilisticBottomUpInitRule

Bases: AbstractChartRule

NUM_EDGES = 0

apply(chart, grammar)

Return a generator that will add edges licensed by this rule and the given edges to the chart, one at a time. Each time the generator is resumed, it will either add a new edge and yield that edge; or return.

Parameters

edges (list(EdgeI)) – A set of existing edges. The number of edges that should be passed to apply() is specified by the NUM_EDGES class variable.

Return type

iter(EdgeI)

class nltk.parse.pchart.ProbabilisticBottomUpPredictRule

Bases: AbstractChartRule

NUM_EDGES = 1

apply(chart, grammar, edge)

Return a generator that will add edges licensed by this rule and the given edges to the chart, one at a time. Each time the generator is resumed, it will either add a new edge and yield that edge; or return.

Parameters

edges (list(EdgeI)) – A set of existing edges. The number of edges that should be passed to apply() is specified by the NUM_EDGES class variable.

Return type

iter(EdgeI)

class nltk.parse.pchart.ProbabilisticFundamentalRule

Bases: AbstractChartRule

NUM_EDGES = 2

apply(chart, grammar, left_edge, right_edge)

Return a generator that will add edges licensed by this rule and the given edges to the chart, one at a time. Each time the generator is resumed, it will either add a new edge and yield that edge; or return.

Parameters

edges (list(EdgeI)) – A set of existing edges. The number of edges that should be passed to apply() is specified by the NUM_EDGES class variable.

Return type

iter(EdgeI)

class nltk.parse.pchart.ProbabilisticLeafEdge

Bases: LeafEdge

prob()

class nltk.parse.pchart.ProbabilisticTreeEdge

Bases: TreeEdge

__init__(prob, *args, **kwargs)

Construct a new TreeEdge.

Parameters

• span (tuple(int, int)) – A tuple (s, e), where tokens[s:e] is the portion of the sentence that is consistent with the new edge’s structure.

• lhs (Nonterminal) – The new edge’s left-hand side, specifying the hypothesized tree’s node value.

• rhs (list(Nonterminal and str)) – The new edge’s right-hand side, specifying the hypothesized tree’s children.

• dot (int) – The position of the new edge’s dot. This position specifies what prefix of the production’s right hand side is consistent with the text. In particular, if sentence is the list of tokens in the sentence, then okens[span[0]:span[1]] can be spanned by the children specified by rhs[:dot].

static from_production(production, index, p)

Return a new TreeEdge formed from the given production. The new edge’s left-hand side and right-hand side will be taken from production; its span will be (index,index); and its dot position will be 0.

Return type

TreeEdge

prob()

class nltk.parse.pchart.RandomChartParser

Bases: BottomUpProbabilisticChartParser

A bottom-up parser for PCFG grammars that tries edges in random order. This sorting order results in a random search strategy.

sort_queue(queue, chart)

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

class nltk.parse.pchart.SingleEdgeProbabilisticFundamentalRule

Bases: AbstractChartRule

NUM_EDGES = 1

apply(chart, grammar, edge1)

Return a generator that will add edges licensed by this rule and the given edges to the chart, one at a time. Each time the generator is resumed, it will either add a new edge and yield that edge; or return.

Parameters

edges (list(EdgeI)) – A set of existing edges. The number of edges that should be passed to apply() is specified by the NUM_EDGES class variable.

Return type

iter(EdgeI)

class nltk.parse.pchart.UnsortedChartParser

Bases: BottomUpProbabilisticChartParser

A bottom-up parser for PCFG grammars that tries edges in whatever order.

sort_queue(queue, chart)

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

nltk.parse.pchart.demo(choice=None, draw_parses=None, print_parses=None)

A demonstration of the probabilistic parsers. The user is prompted to select which demo to run, and how many parses should be found; and then each parser is run on the same demo, and a summary of the results are displayed.