Parsing as Deduction

PARSING AS DEDUCTION l Fernando C. N. Pereira David H. D. Warren Artificial Intelligence Center SRI International 333 Ravenswood Ave., Menlo Park CA 04025 Abstract By exploring the relationship between parsing and deduction, a new and more general view of chart parsing is obtained, which encompasses parsing for grammar formalisms based on unification, and is the basis of the Earley Deduction proof procedure for definite clauses. The efficiency of this approach for an interesting class of grammars is discussed. 1. Introduction The aim of this paper is to explore the relationship between parsing and deduction. The basic notion, which goes back to Kowaiski (Kowalski, 1980} and Colmerauer {Colmeraucr, 1978), h'zs seen a very efficient, if limited, realization in tile use of the logic programming language Prolog for parsing {Colmerauer, 1978; Pereira and Warren, 1980). The connection between parsing and deduction was developed further in the design of the Eariey Deduction proof procedure (Warren, 1975), which will also be discussed at length here. Investigation of the connection between parsing and deduction yields several important benefits: • A theoretically clean mechanism to connect parsing with the inference needed for semantic interpretation. llandling of gaps and unbounded dependencies "on the fly" without adding special mechanisms to the parser. :\ reinterprecation and generalization of chart parsing that abstracts from unessential data- structure details. * Techniques that are applicable to parsing in related formalisms not directly based on logic. IThis work wa~ partially supported by the Defense Advanced Research Projects Agency under Contract N00039-80-C-0575 with the Naval Electronic Systems Command. The views and conclusions contained in this article are those of the authors and should not be interpreted as representative of the official policies, either expressed or imp{led, of the Defense Advanced Research Projects Agency or the United Slates Government. • Elucidation of parsing complexity issues for related formalisms, in particular lexieal-functional grammar (LFG). Our study of these topics is still far from complete; therefore, besides offering some initial results, we shall discuss various outstanding questions. The connection between parsing and deduction is based on the axiomatization of context-free grammars in definite clauses, a particularly simple subset of first- order logic (Kowalski, 1080; van Emden and Kowalski, 1976). This axiomatization allows us to identify context- free parsing algorithms with proof procedures for a restricted class of definite clauses, those derived from context-free rules. This identification can then be generalized to inc{ude larger classes of definite clauses to which the same algorithms can be applied, with simple modifications. Those larger classes of definite clauses can be seen as grammar formalisms in which the atomic grammar symbols of context-free grammars have been replaced by complex symbols that are matched by unification (Robinson, 1965; Colmerauer, 1978; Pereir3 and Warren, 1980}. The simplest of these formalisms is definite-clause grammars (DCG) (Pereira and Warren, 1980). There is a close relationship between DCGs ~nd other ~,rammar formalisms based on unification, such as Unification Grammar {UG) (Kay, 1070), LFG, PATR-2 {Shieber. 1083) and the more recent versions of GPSG (Gazdar and Pullum, …

Content truncated to 500 words