1. A best-first probabilistic shift-reduce parser
- Author
-
Alon Lavie and Kenji Sagae
- Subjects
Parsing ,Computer science ,LR parser ,business.industry ,Shift-reduce parser ,Treebank ,Parsing expression grammar ,Top-down parsing ,computer.software_genre ,Canonical LR parser ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Parser combinator ,Top-down parsing language ,Artificial intelligence ,Deterministic parsing ,business ,computer ,Natural language processing ,Generative grammar - Abstract
Recently proposed deterministic classifier-based parsers (Nivre and Scholz, 2004; Sagae and Lavie, 2005; Yamada and Mat-sumoto, 2003) offer attractive alternatives to generative statistical parsers. Deterministic parsers are fast, efficient, and simple to implement, but generally less accurate than optimal (or nearly optimal) statistical parsers. We present a statistical shift-reduce parser that bridges the gap between deterministic and probabilistic parsers. The parsing model is essentially the same as one previously used for deterministic parsing, but the parser performs a best-first search instead of a greedy search. Using the standard sections of the WSJ corpus of the Penn Treebank for training and testing, our parser has 88.1% precision and 87.8% recall (using automatically assigned part-of-speech tags). Perhaps more interestingly, the parsing model is significantly different from the generative models used by other well-known accurate parsers, allowing for a simple combination that produces precision and recall of 90.9% and 90.7%, respectively.
- Published
- 2006