A New Design of Prolog-Based Bottom-Up Parsing System With Government-Binding Theory

A NEW DESIGN OF PROLOG-BASED BOTTOM-UP PARSING SYSTEM WITH GOVERNMENT.BINDING THEORY Hsin-Hsi Chen*,**, I-Peng Lin* and Chien-Ping Wu** * Department of Computer Science and Information Engineering National Taiwan University, Taipei, Taiwan, R.O.C. ** Graduate Institute of Electrical Engineering National Taiwan University, Taipei, Taiwan, R.O.C. abstract This paper addresses the problems of movement transformation in Prolog-based bottom-up parsing system. Three principles of Government-Binding theory are employed to deal with these problems. They are Empty Category Principle, C-command Principle, and Subjacency Principle. A formalism based upon them is proposed. Translation algorithms are given to add these linguistic principles to the general grammar rules, the leftward movement grammar rules, and the rightward movement grammar rules respectively. This approach has the following specific features: the uniform treatments of leftward and rightward movements, the arbitrary number of movement non-terminals in the rule body, and automatic detection of grammar errors before parsirlg. An example in Chinese demonstrates all the concepts. 1. Introduction The movement transformation is one of the major problems encountered in natural language processing. It has relation to the empty constituents (traces) that exist at various levels of representation in natural language statements. Consider the following example in Chinese: ~][~, ~ ~ N T o (That book, I read.) The word "N" (read) is a transitive verb, which should take a direct object. However, the object "JJl~" (that book) is topicalized to the first position of the sentence. For the treatment of this phenomenon, we cannot just write down the rules: sentence --> noun-phrase,verb-phrase. verb-phrase --> transitive-verb,noun-phrase. verb-phrase --> transitive-verb. verb-phrase --> intransitive-verb. This is because many ungrammatical sentences will be accepted. Thus, we must provide some mechanisms in the grammars in order to capture them. It is still a hard work to do. Several difficulties are listed as follows: (1) The determination of movement is difficult. That is, an element may be in a topicalization position, but it is not moved from some other place in the sentence. For example, (Fruit, I like.) zk~, ~ ~gt ~o (As for fruit, I like banana.) the first can be considered to be a movement phenomenon, but the second cannot. (2) The empty constituent may exist at many possible positiofis. For example, given an n-word sentence such as Cl Wl e2 w2 e 3 ... e(n_l) W(n-1) e(n) W(n) e(n+l) where w i is the i-th word and e i is an empty constituent, there am (n+l) possible positions from which the moved constituent may originate. That is, for a moved constituent (if there is any), there are so many possible empty constituents to co-index. (3) Since the gap in between the moved constituent and its corresponding trace is arbitrary, it is implausible to list all the possible movements exhaustively, and specify each movement constraint explicitly in the grammars. 112 The Government-Binding (GB) theory [1] provides universal principles to explain the movements. Some of them are shown as follows: (1) Empty Category Principle [7] - A trace must be properly governed. (2) C-command Principle [7]- a …

Content truncated to 500 words