Here's a bottom-up chart parsing algorithm which is about 2 times faster than the standard one (tested on the ATIS grammar). It makes a Combine directly after prediction (sometimes called Kilbury prediction).
Put the following in e.g., parse/chart.py:
BUC_STRATEGY = [BottomUpInitRule(), BottomUpCombinePredictRule(), SingleEdgeFundamentalRule()]
class BottomUpCombinePredictRule(AbstractChartRule):
"""
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:
- [AS{->}S{alpha}*]
licenses the edge:
- [BS{->}A*S{beta}]
for each grammar production C{BS{->}AS{beta}}
"""
NUM_EDGES = 1
def apply_iter(self, chart, grammar, edge):
if edge.is_incomplete(): return
for prod in grammar.productions(rhs=edge.lhs()):
new_edge = TreeEdge((edge.start(),edge.end()), prod.lhs(), prod.rhs(), 1)
if chart.insert(new_edge, ()):
yield new_edge
peter ljunglöf
2008-06-23
Logged In: YES
user_id=1932543
Originator: YES
Tree building afterwards doesn't work. The rule should add some backpointers, but I don't know how they work, so I can't figure out what is needed. So, the parsing works, but the extracted trees are not correct.
Perhaps it's best to skip this patch.
Steven Bird
2008-12-09