BIDIRECTIONAL CONTEXT-FREE GRAMMAR PARSING NATURAL-LANGUAGE PROCESSING

While natural language is usually analyzed from left to right, bidirec tional parsing is very attractive for both theoretical and practical r easons. In this paper, we describe a formal framework for bidirectiona l tabular parsing of general context-free languages, and some applicat ions to natural language processing are studied. The framework is gene ral and permits a comparison between known approaches and the algorith ms outlined here. A detailed analysis of the redundancy problem is giv en and a technique for improving the performance of bidirectional tabu lar parsers, whilst maintaining the flexibility of bidirectional strat egies, is described. An algorithm for head-driven parsing and a genera l algorithm for island-driven parsing are studied. The former allows a nalyses of each constituent to be triggered by some fixed immediately dominated element, chosen on the basis of its information content. The latter permits analyses to start from any dynamically chosen position s within the input sentence, combining bottom-up and top-down processi ng without redundancy.