Using Active Constraints to Parse GPSGs

Using Active Constraints to I)arse "")~'(' ',.:, [ ,~ k,,<; Philipl)e I/la(:he lnstitut d'hffor,natiqu(~ Universit6 de NeuchateI (Suisse) e-mail: Blach e((~i,ffo, unine,ch Abstract 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. Keywords : constraints, syntax, ID/I,P formalism, bottom-up filtering, Prolog IlI 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 lat- ter with the systematic use of well-formalized lin- guistic 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 computa- tional 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 re- duces 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 con- straints. 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 pre- cisely, 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 : NX ~ ('~,...,C,, can be interpreted as the fl~llowmg implication : (,'1 A ... A (.',, D ,S'X the clausal form of which is : ~Ci V , . • V ~(5',, V ,b'X 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 a set. of PS rule, corre- sponds to a set of clauses. To verify the grammat- icality of a sentence is tluls …

Content truncated to 500 words