Home | Trees | Indices | Help |
|
---|
|
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:
ChartParse
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.
SteppingChartParse
is a subclass of
ChartParse
that can be used to step through the parsing
process.
EarleyChartParse
is an implementation of the Earley
chart parsing algorithm. It makes a single left-to-right pass
through the chart, and applies one of three rules (predictor,
scanner, and completer) to each edge it encounters.
|
|||
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.
|
|
|||
|
|
|||
TD_STRATEGY = [CachedTopDownInitRule(), CachedTopDownExpandRul
|
|||
BU_STRATEGY = [BottomUpInitRule(), BottomUpPredictRule(), Sing
|
|
TD_STRATEGY
|
BU_STRATEGY
|
Home | Trees | Indices | Help |
|
---|
Generated by Epydoc 3.0beta1 on Wed May 16 22:47:19 2007 | http://epydoc.sourceforge.net |