Efficient Probabilistic Top-Down and Left-Corner Parsing

This paper examines efficient predictive broad-coverage parsing without dynamic programming. In contrast to bottom-up methods, top-down parsing produces partial parses that are fully connected trees spanning the entire left context, from which any kind of non-local dependency or partial semantic interpretation can in principle be read. We contrast top-down and left-corner parsing, and find both to be viable approaches. In addition, we find that enhancement with non-local information not only improves parser accuracy, but also substantially improves the search efficiency. 1 Introduction Strong empirical evidence has been presented over the past 15 years indicating that the human sentence processing mechanism makes on line use of contextual information in the preceding discourse (Crain and Steedman, 1985; Altmann and Steedman, 1988; Britt, 1994) and in the visual environment (Tanenhaus et al., 1995). These results lend support to Mark Steedman's (1989) "intuition" that sentence interpr..