JPSG Parser on Constraint Logic Programming

JPSG Parser on Constraint Logic Programming TUDA, Hirosi * Department of information science Faculty of science University of Tokyo 7-3-1 Hongo, Bunkyo-ku Tokyo, 113 Japan e-maih a30728%tansei.cc.u-tokyo.junet @relay.cs.net HASIDA, Kbiti Institute for New Generation Computer Technology (ICOT) 1-4-28 Mita, Minato-ku Tokyo, 108 Japan e-mail: hasida@icot.jp@relay.cs.net SIRAI, Hidetosi Tamagawa University 6-1-1 Tamagawa gakuen, Machida-shi Tokyo, 194 Japan e-mail: a88868%tansei.cc.u-tokyo.junet@relay.cs.net Abstract This paper presents a constraint logic programming language cu-Prolog and introduces a simple Japanese parser based on Japanese Phrase Structure Grammar (JPSG) as a suitable application of cu-Prolog. cu-Prolog adopts constraint unification instead of the normal Prolog unification. In cu-Prolog, con- straints in terms of user defined predicates can be directly added to the program clauses. Such a clause is called Constraint Added Horn Clause (CAHC}. Unlike conventional CLP systems, cu-Prolog deals with constraints about symbolic or combinatorial ob- jects. For natural language processing, such con- straints are more important than those on numeri- cal or boolean objects. In comparison with normal Prolog, cu-Prolog has more descriptive power, and is more declarative. It enables a natural implementa- tion of JPSG and other unification based grammar formalisms. *From this April, Fujitsu Corporation 1 Introduction Prolog is frequently used in implementing natural language parsers or generators based on unification based grammars. This is because Prolog is also based on unification, and therefore has a declarative feature. One important characteristic of unification based grammar is also a declarative grammar formal- ization [11]. However, Prolog does not have sufficient power of expressing constraints because it executes every parts of its programs as procedures and because every vari- able of Prolog can be instantiated with any objects. Hence, the constraints in unification based grammar are forced to be implemented not declaratively but procedurally. We developed a new constraint logic programming language cu-Prolog which is free from this defect of traditional Prolog [13]. In cu-Prolog, user defined constraints can be directly added to a program clause (constraint added Horn clause), and the constraint unification [12, 8] 1 is adopted instead of the nor- 1 In these earlier papers, "constraint unification" was called "conditioned unification." -95- mal unification. This paper discusses the outline of the cu-Prolog system, and presents a Japanese parser based on :IPSG (Japanese Phrase Structure Gram- mar) [7] as a suitable application of cu-Prolog. 2 Constraint Added Horn Clause (CAHC) Most of the constraint logic programming language systems (CAL [2], PrologIII [5], etc.) deal with con- straints about algebraic equations, i.e., constraints about numerical domains, such as that of real num- bers etc. However, in the problems arising in Artificial In- telligence, constraints on symbolic or combinatorial objects are far more important than those on nu- merical objects, cu-Prolog handles constraints de- scribed in terms of sequence of atomic formulas of Prolog. The program clauses of cu-Prolog are fol- lowing type, which we call Constraint Added Horn Clauses (CAHCs): 1. H :- Bt,B2,...,Bn;C1,C2,...,Cm. (H is called the head, B1, B2,... ,Bn is the body, C1, C2,..., Cm is the constraint. The body and the constraint …

Content truncated to 500 words