nltk.parse.chart

module documentation

(source)

Data classes and parser implementations for "chart parsers", which use dynamic programming to efficiently parse a text. A chart parser derives parse trees for a text by iteratively adding "edges" to a "chart." Each edge represents a hypothesis about the tree structure for a subsequence of the text. The chart is a "blackboard" for composing and combining these hypotheses.

When a chart parser begins parsing a text, it creates a new (empty) chart, spanning the text. It then incrementally adds new edges to the chart. A set of "chart rules" specifies the conditions under which new edges should be added to the chart. Once the chart reaches a stage where none of the chart rules adds any new edges, parsing is complete.

Charts are encoded with the Chart class, and edges are encoded with the TreeEdge and LeafEdge classes. The chart parser module defines three chart parsers:

ChartParser is a simple and flexible chart parser. Given a set of chart rules, it will apply those rules to the chart until no more edges are added.

SteppingChartParser is a subclass of ChartParser that can be used to step through the parsing process.

Class	`AbstractChartRule`	An abstract base class for chart rules. `AbstractChartRule` provides:
Class	`BottomUpChartParser`	A `ChartParser` using a bottom-up parsing strategy. See `ChartParser` for more information.
Class	`BottomUpLeftCornerChartParser`	A `ChartParser` using a bottom-up left-corner parsing strategy. This strategy is often more efficient than standard bottom-up. See `ChartParser` for more information.
Class	`BottomUpPredictCombineRule`	A rule licensing any edge corresponding to a production whose right-hand side begins with a complete edge's left-hand side. In particular, this rule specifies that `[A -> alpha \]` licenses the edge `[B -> A \ beta]`...
Class	`BottomUpPredictRule`	A rule licensing any edge corresponding to a production whose right-hand side begins with a complete edge's left-hand side. In particular, this rule specifies that `[A -> alpha \]` licenses the edge `[B -> \ A beta]`...
Class	`CachedTopDownPredictRule`	A cached version of `TopDownPredictRule`. After the first time this rule is applied to an edge with a given `end` and `next`, it will not generate any more edges for edges with that `end` and `next`.
Class	`Chart`	A blackboard for hypotheses about the syntactic constituents of a sentence. A chart contains a set of edges, and each edge encodes a single hypothesis about the structure of some portion of the sentence.
Class	`ChartParser`	A generic chart parser. A "strategy", or list of `ChartRuleI` instances, is used to decide what edges to add to the chart. In particular, `ChartParser` uses the following algorithm to parse texts:
Class	`ChartRuleI`	A rule that specifies what new edges are licensed by any given set of existing edges. Each chart rule expects a fixed number of edges, as indicated by the class variable `NUM_EDGES`. In particular:
Class	`EdgeI`	A hypothesis about the structure of part of a sentence. Each edge records the fact that a structure is (partially) consistent with the sentence. An edge contains:
Class	`EmptyPredictRule`	A rule that inserts all empty productions as passive edges, in every position in the chart.
Class	`FilteredBottomUpPredictCombineRule`	Undocumented
Class	`FilteredSingleEdgeFundamentalRule`	Undocumented
Class	`FundamentalRule`	A rule that joins two adjacent edges to form a single combined edge. In particular, this rule specifies that any pair of edges
Class	`LeafEdge`	An edge that records the fact that a leaf value is consistent with a word in the sentence. A leaf edge consists of:
Class	`LeafInitRule`	Undocumented
Class	`LeftCornerChartParser`	Undocumented
Class	`SingleEdgeFundamentalRule`	A rule that joins a given edge with adjacent edges in the chart, to form combined edges. In particular, this rule specifies that either of the edges:
Class	`SteppingChartParser`	A `ChartParser` that allows you to step through the parsing process, adding a single edge at a time. It also allows you to change the parser's strategy or grammar midway through parsing a text.
Class	`TopDownChartParser`	A `ChartParser` using a top-down parsing strategy. See `ChartParser` for more information.
Class	`TopDownInitRule`	A rule licensing edges corresponding to the grammar productions for the grammar's start symbol. In particular, this rule specifies that `[S -> \* alpha][0:i]` is licensed for each grammar production `S -> alpha`...
Class	`TopDownPredictRule`	A rule licensing edges corresponding to the grammar productions for the nonterminal following an incomplete edge's dot. In particular, this rule specifies that `[A -> alpha \* B beta][i:j]` licenses the edge ...
Class	`TreeEdge`	An edge that records the fact that a tree is (partially) consistent with the sentence. A tree edge consists of:
Function	`demo`	A demonstration of the chart parsers.
Function	`demo_grammar`	Undocumented
Constant	`BU_LC_STRATEGY`	Undocumented
Constant	`BU_STRATEGY`	Undocumented
Constant	`LC_STRATEGY`	Undocumented
Constant	`TD_STRATEGY`	Undocumented
Function	`_bottomup_filter`	Undocumented

def demo(choice=None, print_times=True, print_grammar=False, print_trees=True, trace=2, sent='I saw John with a dog with my cookie', numparses=5): (source) ¶

A demonstration of the chart parsers.

def demo_grammar(): (source) ¶

Undocumented

BU_LC_STRATEGY = (source) ¶

Undocumented

Value

[LeafInitRule(),
 EmptyPredictRule(),
 BottomUpPredictCombineRule(),
 SingleEdgeFundamentalRule()]

BU_STRATEGY = (source) ¶

Undocumented

Value

[LeafInitRule(),
 EmptyPredictRule(),
 BottomUpPredictRule(),
 SingleEdgeFundamentalRule()]

LC_STRATEGY = (source) ¶

Undocumented

Value

[LeafInitRule(),
 FilteredBottomUpPredictCombineRule(),
 FilteredSingleEdgeFundamentalRule()]

TD_STRATEGY = (source) ¶

Undocumented

Value

[LeafInitRule(),
 TopDownInitRule(),
 CachedTopDownPredictRule(),
 SingleEdgeFundamentalRule()]

def _bottomup_filter(grammar, nexttoken, rhs, dot=0): (source) ¶

Undocumented