Optimistic Backtracking - A Backtracking Overlay for Deterministic Incremental Parsing

Gisle Ytrestøl
Department of Informatics / University of Oslo


Abstract

This paper describes a backtracking strategy for an incremental deterministic transition-based parser for HPSG. The method could theoretically be implemented on any other transition-based parser with some adjustments. In this paper, the algorithm is evaluated on CuteForce, an efficient deterministic shift-reduce HPSG parser. The backtracking strategy may serve to improve existing parsers, or to assess if a deterministic parser would benefit from backtracking as a strategy to improve parsing.




Full paper: http://www.aclweb.org/anthology/P/P11/P11-1095.pdf