An Extended Theory of Head-Driven Parsing

AN EXTENDED THEORY OF HEAD-DRIVEN PARSING Mark-Jan Nederhof * University of Nijmegen Department of Computer Science Toernooiveld, 6525 ED Nijmegen The Netherlands markj an¢cs, kun. nl Abstract We show that more head-driven parsing algorithms can he formulated than those occurring in the existing lit- erature. These algorithms are inspired by a family of left-to-right parsing algorithms from a recent publica- tion. We further introduce a more advanced notion of "head-driven parsing" which allows more detailed spec- ification of the processing order of non-head elements in the right-hand side. We develop a parsing algorithm for this strategy, based on LR parsing techniques. Introduction According to the head-driven paradigm, parsing of a formal language is started from the elements within the input string that are most contentful either from a syn- tactic or, more generally, from an information theoretic point of view. This results in the weakening of the left-to-right feature of most traditional parsing meth- ods. Following a pervasive trend in modern theories of Grammar (consider for instance [5, 3, 11]) the compu- tational linguistics community has paid large attention to the head-driven paradigm by investigating its appli- cations to context-free language parsing. Several methods have been proposed so far exploit- ing some nondeterministic head-driven strategy for context-free language parsing (see among others [6, 13, 2, 14]). All these proposals can be seen as general- izations to the head-driven case of parsing prescrip- tions originally conceived for the left-to-right case. The methods above suffer from deficiencies that are also no- ticeable in the left-to-right case. In fact, when more rules in the grammar share the same head element, or share some infix of their right-hand side including the head, the recognizer nondeterministically guesses a rule just after having seen the head. In this way analyses that could have been shared are duplicated in the pars- ing process. Interesting techniques have been proposed in the left- to-right deterministic parsing literature to overcome re- dundancy problems of the above kind, thus reducing *Supported by the Dutch Organisation for Scientific Re- search (NWO), under grant 00-62-518 Giorgio Satta Universith di Padova Dipartimento di Elettronica e Informatica via Gradenigo 6/A, 35131 Padova Italy satt a@dei, unipd, it the degree of nondeterminism of the resulting methods. These solutions range from predictive LR parsing to LR parsing [15, 1]. On the basis of work in [8] for nonde- terministic left-to-right parsing, we trace here a theory of head-driven parsing going from crude top-down and head-corner to more sophisticated solutions, in the at- tempt to successively make more deterministic the be- haviour of head-driven methods. Finally, we propose an original generalization of head- driven parsing, allowing a more detailed specification of the order in which elements of a right-hand side are to be processed. We study in detail a solution to such a head-driven strategy based on LR parsing. Other methods presented in this paper could be extended as well. Preliminaries The notation used in the sequel is for the most part standard and is summarised below. Let …

Content truncated to 500 words