Using Active Constraints to Parse GPSGs
Active constraints of tile CO,lslratnl higic program-in,rig paradigm allow (l) the reduction of the search space of progr~tms and (2) a very concise representation of the problcnls. These two l)rop erties are particuhtrly interesting for I)arsing prob-[elns : they can hel I) us to reduce non-determinisln and to use large coverage gramlnars. In this paper, we describe how to use Slleh constraints tot parsing ID/LP grammars and propose an inlplenlelmtl, iou in Prolog Ill. 1 Introduction Logic programming is one of the nlost useful tools in computational linguistics. These two domains are progressing very rapidly. The former with the emergence of the constraint paradignl and the latter with the systematic use of well-formalized linguistic theories. In the l~st few years, natural lal> guage processing (hereafter NLP) and more pre cisely syntax have created tools allowing expression of general knowledge. Constraints simplify parsing problems to a con siderable extent, both in a formal and computational way. From a formal point of view, we will see that they allow a very good adequacy between linguistic aim computational theories. We know that this prol)erty is essential to solve generality, reusability and coverage prolflems. On the otimr hal,d, from a computatiolml point of view, con straints set up a control of the I)rocesses which reduces non-determmisnl m parsing. The question is to know whether it, is possible to illlph!tlleIlt a I)arsiag Illethod I)ased oil actllal eoil-straints. The answer depends on the choice of the grmmnatical formalism. We think thai the II)/LP formalism used lit (IPS(-I theory can bring a sohl tion to this I)roblem. In this paper, we will describe a parsing method based on [D/LP formalism using boolean constraints. We will show that this nlethod agrees with th(goals of generality and corm'el. 2 Parsing and deduction IIoth for historical itllll [orlilal reasolls, parsing turn ck)se relalions with logic The birth of Prolog, for example, w~s conditioimd by Ihat aud NLP was one of the early applications of this language. One of the re~molls, a.s shown in [PereiraS,g], is tiiat we ('.all compare |)arsdlg and dednet, ion, More precisely , it phrase-structure rule (hereafter PS-rule) can be interpreted its a Rmnula (an ilnplication), like a classical inDrenee rule. '['hus, a PS-rule of the form : Because of the ui,iquei~ess of the positive literal, we can interpret a PS-.rule as a Ilorn clause, with a direct translation into I'rolog. Thus, a context-free gr~unlnar, represenled by …