Package nltk_lite :: Package parse :: Module chart
[hide private]
[frames] | no frames]

Module chart

source code

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:

Classes [hide private]
  EdgeI
A hypothesis about the structure of part of a sentence.
  TreeEdge
An edge that records the fact that a tree is (partially) consistent with the sentence.
  LeafEdge
An edge that records the fact that a leaf value is consistent with a word in the sentence.
  Chart
A blackboard for hypotheses about the syntactic constituents of a sentence.
  ChartRuleI
A rule that specifies what new edges are licensed by any given set of existing edges.
  AbstractChartRule
An abstract base class for chart rules.
  FundamentalRule
A rule that joins two adjacent edges to form a single combined edge.
  SingleEdgeFundamentalRule
A rule that joins a given edge with adjacent edges in the chart, to form combined edges.
  TopDownInitRule
A rule licensing edges corresponding to the grammar productions for the grammar's start symbol.
  TopDownExpandRule
A rule licensing edges corresponding to the grammar productions for the nonterminal following an incomplete edge's dot.
  TopDownMatchRule
A rule licensing an edge corresponding to a terminal following an incomplete edge's dot.
  CachedTopDownInitRule
A cached version of TopDownInitRule.
  CachedTopDownExpandRule
A cached version of TopDownExpandRule.
  BottomUpInitRule
A rule licensing any edges corresponding to terminals in the text.
  BottomUpPredictRule
A rule licensing any edge corresponding to a production whose right-hand side begins with a complete edge's left-hand side.
  CompleterRule
A rule that joins a given complete edge with adjacent incomplete edges in the chart, to form combined edges.
  ScannerRule
A rule licensing a leaf edge corresponding to a part-of-speech terminal following an incomplete edge's dot.
  PredictorRule
  EarleyChartParse
A chart parser implementing the Earley parsing algorithm:
  ChartParse
A generic chart parser.
  SteppingChartParse
A ChartParse that allows you to step through the parsing process, adding a single edge at a time.
Functions [hide private]
 
demo()
A demonstration of the chart parsers.
source code
Variables [hide private]
  TD_STRATEGY = [CachedTopDownInitRule(), CachedTopDownExpandRul...
  BU_STRATEGY = [BottomUpInitRule(), BottomUpPredictRule(), Sing...
Variables Details [hide private]

TD_STRATEGY

Value:
[CachedTopDownInitRule(), CachedTopDownExpandRule(), TopDownMatchRule(\
), SingleEdgeFundamentalRule()]

BU_STRATEGY

Value:
[BottomUpInitRule(), BottomUpPredictRule(), SingleEdgeFundamentalRule(\
)]