Bi-Directional Parsing for Natural Language Processing

Giorgio Satta, Dipartimento di Elettronica ed Informatica, University of Padua, Italy

October 24, 1995


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)