Deductive Parsing With Multiple Levels of Representation.

DEDUCTIVE PARSING WITH MULTIPLE LEVELS OF REPRESENTATION.* Mark Johnson, Brain and Cognitive Sciences, M.I.T. ABSTRACT This paper discusses a sequence of deductive parsers, called PAD1 - PAD5, that utilize an axiomatization of the principles and parameters of GB theory, including a restricted transformational component (Move-a). PAD2 uses an inference control strategy based on the "freeze" predicate of Prolog-II, while PAD3 - 5 utilize the Unfold-Fold transformation to transform the original axiomatization into a form that functions as a recursive descent Prolog parser for the fragment. INTRODUCTION This paper reports on several deductive parsers for a fragment of Chomsky's Government and Binding theory (Chomsky 1981, 1986; Van Riemsdijk and Williams 1984). These parsers were constructed to illustrate the 'Parsing as Deduction' approach, which views a parser as a specialized theorem-prover which uses knowledge of a language (i.e. its grammar) as a set of axioms from which information about the utterances of that language (e.g. their structural descriptions) can be deduced. This approach directly inspired by the seminal paper by Pereira and Warren (1983). Johnson (1988a) motivates the Parsing as Deduction approach in more detail than is possible here, and Johnson (1988b) extends the techniques presented in this paper to deal with a more complex fragment. Steven Abney, Bob Berwick, Nelson Correa, Tim Hickey, Elizabeth Highleyman, Ewan Klein, Peter Ludlow, Martin Kay, Fernando Pereira and Whitman Richards all made helpful suggestions regarding this work, although all responsibility for errors remains my own. The research reported here was supported by a grant by the Systems Development Foundation to the Center for the Study of Language and Information at Stanford University and a Postdoctoral Fellowship awarded by the Fairchild Foundation through the Brain and Cognitive Sciences Department at MIT. In this paper I describe a sequence of model deductive parsers, called PAD1 - PAD5, for a fragment of GB theory. These parsers are not designed for practical application, but simply to show that GB deductive parsers can actually be built. These parsers take PF representations as their input and produce LF representations as their output. They differ from most extant GB parsers in that they make explicit use of the four levels of representation that GB attributes to an utterance - namely D-structure, S- structure, PF and LF - and the transformational relationship that holds between them. A "grammar" for these parsers consists entirely of a set of parameter values that parameterize the principles of GB theory - thus the parsers described here can be regarded as "principle- based' (Berwick 1987) - and the parsers' top- level internal structure transparently reflects (some of) the principles of that theory; X" and @ theory apply at D-structure, Case theory applies at S-structure, Move-or is stated as a relation between D- and S-structure, and LF- movement relates S-structure and LF. In particular, the constraints on S-structures that result from the interaction of Move-c~ with principles constraining D-structure (i.e. X' and @ theories) are used constructively throughout the parsingprocess. The PAD parsers are designed to directly mirror the …

Content truncated to 500 words