Abstract
While natural language is usually analyzed from left to right, bi-directional parsing is very attractive for both theoretical and practical reasons. In fact bi-directional parsing can exploit head information as early as possible, thus reducing local ambiguities in the input sentence, and prove useful in cases of ill-formed or “noisy” input, again reducing the amount of nondeterminism that needs to be simulated by a deterministic algorithm.Pursuing the approach based on grammar covers, first proposed in (Leermakers, 1989), I will develop a uniform framework that offers a systematization of bi-directional parsing and facilitates the design and the analysis of new parsing algorithms for these strategies, when dealing with phrase rewriting systems based on a context-free backbone. Some algorithms for head-driven and island-driven parsing will be presented. In the head-driven algorithms, the syntactic analysis of a constituent is always triggered by some fixed element within it, chosen on the basis of its information content. In the island-driven algorithms, syntactic analysis starts from any dynamically chosen positions within the input sentence, combining bottom-up and top-down processing without redundancy.(Joint work with Mark-Jan Nederhof and Oliviero Stock)