nltk.parse.featurechart module

Extension of chart parsing implementation to handle grammars with feature structures as nodes.

class nltk.parse.featurechart.FeatureBottomUpChartParser

Bases: FeatureChartParser

__init__(grammar, **parser_args)

Create a new chart parser, that uses grammar to parse texts.

Parameters

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

• strategy (list(ChartRuleI)) – A list of rules that should be used to decide what edges to add to the chart (top-down strategy by default).

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

• trace_chart_width (int) – The default total width reserved for the chart in trace output. The remainder of each line will be used to display edges.

• use_agenda (bool) – Use an optimized agenda-based algorithm, if possible.

• chart_class – The class that should be used to create the parse charts.

class nltk.parse.featurechart.FeatureBottomUpLeftCornerChartParser

Bases: FeatureChartParser

__init__(grammar, **parser_args)

Create a new chart parser, that uses grammar to parse texts.

Parameters

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

• strategy (list(ChartRuleI)) – A list of rules that should be used to decide what edges to add to the chart (top-down strategy by default).

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

• trace_chart_width (int) – The default total width reserved for the chart in trace output. The remainder of each line will be used to display edges.

• use_agenda (bool) – Use an optimized agenda-based algorithm, if possible.

• chart_class – The class that should be used to create the parse charts.

class nltk.parse.featurechart.FeatureBottomUpPredictCombineRule

Bases: BottomUpPredictCombineRule

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.featurechart.FeatureBottomUpPredictRule

Bases: BottomUpPredictRule

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.featurechart.FeatureChart

Bases: Chart

A Chart for feature grammars. :see: Chart for more information.

parses(start, tree_class=<class 'nltk.tree.tree.Tree'>)

Return an iterator of the complete tree structures that span the entire chart, and whose root node is root.

select(**restrictions)

Returns an iterator over the edges in this chart. See Chart.select for more information about the restrictions on the edges.

class nltk.parse.featurechart.FeatureChartParser

Bases: ChartParser

__init__(grammar, strategy=[<nltk.parse.chart.LeafInitRule object>, <nltk.parse.featurechart.FeatureEmptyPredictRule object>, <nltk.parse.featurechart.FeatureBottomUpPredictCombineRule object>, <nltk.parse.featurechart.FeatureSingleEdgeFundamentalRule object>], trace_chart_width=20, chart_class=<class 'nltk.parse.featurechart.FeatureChart'>, **parser_args)

Create a new chart parser, that uses grammar to parse texts.

Parameters

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

• strategy (list(ChartRuleI)) – A list of rules that should be used to decide what edges to add to the chart (top-down strategy by default).

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

• trace_chart_width (int) – The default total width reserved for the chart in trace output. The remainder of each line will be used to display edges.

• use_agenda (bool) – Use an optimized agenda-based algorithm, if possible.

• chart_class – The class that should be used to create the parse charts.

class nltk.parse.featurechart.FeatureEmptyPredictRule

Bases: EmptyPredictRule

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.featurechart.FeatureFundamentalRule

Bases: FundamentalRule

A specialized version of the fundamental rule that operates on nonterminals whose symbols are FeatStructNonterminal``s.  Rather than simply comparing the nonterminals for equality, they are unified.  Variable bindings from these unifications are collected and stored in the chart using a ``FeatureTreeEdge. When a complete edge is generated, these bindings are applied to all nonterminals in the edge.

The fundamental rule states that:

• [A -> alpha \* B1 beta][i:j]

• [B2 -> gamma \*][j:k]

licenses the edge:

• [A -> alpha B3 \* beta][i:j]

assuming that B1 and B2 can be unified to generate B3.

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.featurechart.FeatureSingleEdgeFundamentalRule

Bases: SingleEdgeFundamentalRule

A specialized version of the completer / single edge fundamental rule that operates on nonterminals whose symbols are FeatStructNonterminal. Rather than simply comparing the nonterminals for equality, they are unified.

class nltk.parse.featurechart.FeatureTopDownChartParser

Bases: FeatureChartParser

__init__(grammar, **parser_args)

Create a new chart parser, that uses grammar to parse texts.

Parameters

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

• strategy (list(ChartRuleI)) – A list of rules that should be used to decide what edges to add to the chart (top-down strategy by default).

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

• trace_chart_width (int) – The default total width reserved for the chart in trace output. The remainder of each line will be used to display edges.

• use_agenda (bool) – Use an optimized agenda-based algorithm, if possible.

• chart_class – The class that should be used to create the parse charts.

class nltk.parse.featurechart.FeatureTopDownInitRule

Bases: TopDownInitRule

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.featurechart.FeatureTopDownPredictRule

Bases: CachedTopDownPredictRule

A specialized version of the (cached) top down predict rule that operates on nonterminals whose symbols are FeatStructNonterminal. Rather than simply comparing the nonterminals for equality, they are unified.

The top down expand rule states that:

• [A -> alpha \* B1 beta][i:j]

licenses the edge:

• [B2 -> \* gamma][j:j]

for each grammar production B2 -> gamma, assuming that B1 and B2 can be unified.

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.featurechart.FeatureTreeEdge

Bases: TreeEdge

A specialized tree edge that allows shared variable bindings between nonterminals on the left-hand side and right-hand side.

Each FeatureTreeEdge contains a set of bindings, i.e., a dictionary mapping from variables to values. If the edge is not complete, then these bindings are simply stored. However, if the edge is complete, then the constructor applies these bindings to every nonterminal in the edge whose symbol implements the interface SubstituteBindingsI.

__init__(span, lhs, rhs, dot=0, bindings=None)

Construct a new edge. If the edge is incomplete (i.e., if dot<len(rhs)), then store the bindings as-is. If the edge is complete (i.e., if dot==len(rhs)), then apply the bindings to all nonterminals in lhs and rhs, and then clear the bindings. See TreeEdge for a description of the other arguments.

bindings()

Return a copy of this edge’s bindings dictionary.

static from_production(production, index)

Returns

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

move_dot_forward(new_end, bindings=None)

Returns

A new FeatureTreeEdge formed from this edge. The new edge’s dot position is increased by 1, and its end index will be replaced by new_end.

Return type

FeatureTreeEdge

Parameters

• new_end (int) – The new end index.

• bindings (dict) – Bindings for the new edge.

next_with_bindings()

variables()

Returns

The set of variables used by this edge.

Return type

set(Variable)

class nltk.parse.featurechart.InstantiateVarsChart

Bases: FeatureChart

A specialized chart that ‘instantiates’ variables whose names start with ‘@’, by replacing them with unique new variables. In particular, whenever a complete edge is added to the chart, any variables in the edge’s lhs whose names start with ‘@’ will be replaced by unique new Variable.

__init__(tokens)

Construct a new chart. The chart is initialized with the leaf edges corresponding to the terminal leaves.

Parameters

tokens (list) – The sentence that this chart will be used to parse.

initialize()

Clear the chart.

insert(edge, child_pointer_list)

Add a new edge to the chart, and return True if this operation modified the chart. In particular, return true iff the chart did not already contain edge, or if it did not already associate child_pointer_lists with edge.

Parameters

• edge (EdgeI) – The new edge

• child_pointer_lists (sequence of tuple(EdgeI)) – A sequence of lists of the edges that were used to form this edge. This list is used to reconstruct the trees (or partial trees) that are associated with edge.

Return type

bool

inst_vars(edge)

instantiate_edge(edge)

If the edge is a FeatureTreeEdge, and it is complete, then instantiate all variables whose names start with ‘@’, by replacing them with unique new variables.

Note that instantiation is done in-place, since the parsing algorithms might already hold a reference to the edge for future use.

nltk.parse.featurechart.demo(print_times=True, print_grammar=True, print_trees=True, print_sentence=True, trace=1, parser=<class 'nltk.parse.featurechart.FeatureChartParser'>, sent='I saw John with a dog with my cookie')

nltk.parse.featurechart.demo_grammar()

nltk.parse.featurechart.run_profile()