Direct parsing of ID/LP grammars

Abstract

The Immediate Dominance/Linear Precedence (ID/LP) formalism is a recent extension of Generalized Phrase Structure Grammar (GPSG) designed to perform some of the tasks previously assigned to metarules--for example, modeling the word-order characteristics of so-called free-word-order languages. It allows a simple specification of classes of rules that differ only in constituent order. ID/LP grammars (as well as metarule grammars) have been proposed for use in parsing by expanding them into equivalent context-free grammars. We develop a parsing algorithm, based on the algorithm of Earley, for parsing ID/LP grammars directly, circumventing the initial expansion phase. A proof of correctness is supplied. We also discuss some aspects of the time complexity of the algorithm and some formal properties associated with ID/LP grammars and their relationship to context-free grammars.