Klein, Dan and Manning, Christopher D. (2001) An O(n^3) Agenda-Based Chart Parser for Arbitrary Probabilistic Context-Free Grammars. Technical Report. Stanford.
![[img]](/style/images/fileicons/application_pdf.png)  Preview |
| PDF
132Kb |
Abstract
While $O(n^3)$ methods for parsing probabilistic context-free grammars (PCFGs) are well known, a tabular parsing framework for arbitrary PCFGs which naturally allows top-down, bottom-up, and other strategies, corresponding to active chart parsing for CFGs, has not yet been provided. This paper presents such an algorithm, and shows its correctness and advantages over prior work. The paper finishes by bringing out the connections between the algorithm and work on hypergraphs, which permits us to extend the presented Viterbi (best parse) algorithm to an inside (total probability) algorithm.
| Item Type: | Techreport (Technical Report) |
|---|
| Uncontrolled Keywords: | nlp, parsing, probabilistic parsing, chart parsing, hypergraphs |
|---|
| Subjects: | Computer Science |
|---|
| Projects: | Miscellaneous |
|---|
| Related URLs: | Project Homepage | http://www-nlp.stanford.edu/ |
|---|
| ID Code: | 491 |
|---|
| Deposited By: | Import Account |
|---|
| Deposited On: | 26 Apr 2001 17:00 |
|---|
| Last Modified: | 27 Dec 2008 10:10 |
|---|
Available Versions of this Item
- An O(n^3) Agenda-Based Chart Parser for Arbitrary Probabilistic Context-Free Grammars. (deposited 26 Apr 2001 17:00) [Currently Displayed]
Download statistics
Repository Staff Only: item control page
