An efficient context-free backbone for natural language analyzers

Abstract

Parsing efficiency is crucial when building practical natural language systems. This paper introduces an efficient context-free parsing algorithm based on dynamic programming techniques, and focuses on its practical application to natural languages interfaces. Our analyzer takes a general class of context-free grammars as drivers, using the same user interface applied by the standard generators of parsers in UNIX, which facilitates its use in relation to another context-free analyzers. To assure computational efficiency, we consider the concept of non-deterministic push-down transducer as operational model simulating all possible computations at worst in cubic time and space complexity. So, the essential feature of our context-free parser is that we do not interpret the grammars, but we first compile them. In addition, we solve the problem of the optimal sharing of computations during the parse process introducing very simple techniques of dynamic programming. Another important question relies on the treatment of parse forest construction. In effect, the parse is represented by a sequence of rules to be used in a left-to-right reduction of the input sentence to the start symbol of the grammar, which allow us to gracefully solve the problem of the optimal sharing of the output syntactic structure. The new system has been baptized ICE, after Incremental Context-Free Environment. In an empirical comparison, ICE appears to be superior to the others context-free analyzers and comparable to the standard generators of deterministic parsers, when the input string is not ambiguous. Incremental facilities provided by ICE will not be commented in the present work. This aspect of the tool will be explained separately in a next paper because its complexity.