tailieunhanh - Báo cáo khoa học: "PARSING AS DEDUCTION"

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. I n t r o d u c t i o n 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. | PARSING AS DEDUCTION1 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 Kowalski Kowalski 1980 and Colmerauer Colmerauer 1978 has seen a very efficient if limited realization in the 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 Earley 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. Handling of gaps and unbounded dependencies on the fly without adding special mechanisms to the parser. A reinterpretation 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. This work was 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 OĨ the official policies either expressed or implied of the Defense Advanced Research Projects Agency or the L nited States Government. Elucidation of parsing complexity .