BiDirectional Context-Free Grammar Parsing for Natural Language Processing

While natural language is usually analyzed from left to right, bidirectional parsing is very attractive for both theoretical and practical reasons. In this paper, we describe a formal framework for bidirectional tabular parsing of general context-free languages, and some applications to natural language processing are studied. The framework is general and permits a comparison between known approaches and the algorithms outlined here. A detailed analysis of the redundancy problem is given and a technique for improving the performance of bidirectional tabular parsers, whilst maintaining the flexibility of bidirectional strategies, is described. An algorithm for head-driven parsing and a general algorithm for island-driven parsing are studied. The former allows analyses 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 positions within the input sentence, combining bottom-up and top-down processing without redundancy.