La lecture en ligne est gratuite
Télécharger
Actes JFPC 2010
1
Une
mode´lisationenCSPdes proprie´t´es
grammaires
de
Denys Duchier, Thi-Bich-Hanh Dao, Yannick Parmentier, Willy Lesaint LaboratoiredInformatiqueFondamentaledOrle´ansUniversit´edOrl´eans Baˆtiment3IA,RueL´eonarddeVinci45067Orle´ansCedex2 prenom.nom@univ-orleans.fr
Re´sume´ LesGrammairesdePropri´et´es(GP)constituentun formalisme`abasedecontraintescapableded´ecrire`a lafoisdes´enonce´sbien-form´esetdes´enonce´sagram-maticaux,cequienfaitunformalismeparticulie`rement int´eressantpourtraiterdelagradiencedegrammatica-lit´e,commelade´montre´Prost[12].Duchieret al[7] ontde´niunes´emantiquedesgrammairesdepropri´et´es enth´eoriedesmode`les.Cetarticlepoursuitcetravailen montrantcomment,a`partirdecettese´mantique,d´enir lanalysesyntaxiqueenGPsouslaformedunProbl`eme de Satisfaction de Contraintes (CSP), traitable au moyen de la programmation par contraintes. Abstract Property grammars offer a constraint-based forma-lism capable of handling both well-formed and deviant utterances. It is thus well-suited for addressing issues of gradience of grammaticality, as demonstrated by Prost [12]. Duchieret al[7] contributed precise model-theoretic semantics for property grammars. The present article follows up on that work and explains how to turn such a formalization into a concrete constraint satisfac-tion problem (CSP), solvable using constraint program-ming.
Introduction
Danscetravail,nousnousint´eressons`aunetˆache spe´ciquedudomaineduTraitementAutomatiquedes Langues,`asavoirlanalysesyntaxique.Cettetaˆche apourbutdeconstruire,`apartirdunedescription formelle de la syntaxe de la langue naturelle (i.e., une grammaire), une structure exprimant les relations entrelesdiversconstituantsdune´nonc´e.Cettestruc-tureprendge´n´eralementuneformearborescente,on parle alors d’arbre syntaxique.
Denombreuxformalismesgrammaticauxont´et´e propos´espourd´ecrirelasyntaxedelalanguenaturelle, g´en´eralementensebasantsurunsyste`medere´e´cri-ture (e.g.ˆanıedhcuterceirr´e´serrasgaimmpoesleur hors-contexte[4],ouencorer´ee´crituredarbrespour lesgrammairesdarbresadjoints[10]).Unproble`me majeur de ces formalismes, dans un contexte de Trai-tement Automatique de la Langue, est leur manque de robustesse. En effet, ils ne permettent pas d’analyser dese´nonc´esquisontmal-forme´s,mˆemelorsquilsagit d’erreurs mineures. Commelontde´montre´PullumetScholz[13],les grammaires formelles de typesve-aritnee´ex´gnyat e´num´erativentrentceonecssleelu`oerusemalsnad, surlag´en´erationdemode`lesbienform´es,sontintrin-s`equementinadapte´esautraitementd´enonce´sagram-maticaux. Par contre, des grammaires formelles de typexetandfoynshte´roeie´seruallesdesmod`e, qui se concentrentsurunevalidationdemod`elesentermes decontraintessatisfaites,sontnaturellementadapt´ees au traitement dequasi-expressions. Blache[2,3]apropos´eleformalismedesGram-mairesdePropri´ete´s(GP),commeunformalismea` basedecontraintes,permettantdanalysera`lafoisdes e´nonce´sgrammaticauxetagrammaticaux.Prost[12] ad´evelopp´eunetechniquedanalysesyntaxiqueutili-sant GP, et permettant de produire une structure syn-taxiquepourtouttyped´enonc´e,toutenyassociant unjugementpre´cissurlagrammaticalite´del´enonc´e en question. Duchieret alno]7uoft[anem-iurns´ne tiqueenthe´oriedesmod`elespourGP,ainsiquune d´enitionlogiqueformelledestravauxdanalysesyn-taxiquemene´sparProst.Danscetarticle,nousmon-tronscommentunetelleformalisationdelase´man-tiquedeGP,peuteˆtreconvertieenunCSP,ouvrant lavoiea`limplantationdunanalyseursyntaxiquea`
base de contraintes, qui calcule des arbres syntaxiques optimaux(entermesdegrammaticalit´ed´enonc´e),au moyen d’une recherche de typebranch-and-bound. Larticleeststructure´commesuit.Ensection2, nous introduisons le formalisme des grammaires de proprie´t´es.Ensection3,nousde´nissonsunese´man-tiquedesgrammairesdeproprie´t´esbas´eesurlath´eorie desmod`eles.Cettes´emantiquevaservirdecadre`ala d´enitiondelatˆachedanalysesyntaxiqueentermes deproble`medesatisfactiondecontraintes.Cetted´e-nition va reposer sur deux types de contraintes permet-tantdeconstruirelarbresyntaxiquedun´enonc´e.Le premier type de contraintes, les contraintes de struc-turedarbre,serapre´sente´ensection4,lesecondtype decontraintes,lescontraintesdepropri´et´es,ensec-tion5.Cetted´enitiona`basedecontraintesdelana-lysesyntaxiquepourlesgrammairesdepropri´ete´sm`e-neranaturellementa`uneimplantationenprogram-mation par contraintes, qui sera introduite en sec-tion 6. Enfin, en section 7, nous comparons notre tra-vail avec les approches existantes, et en section 8, nous concluonsenpre´sentantlestravauxfuturs.
2
Grammairesdeproprie´te´s
Lesgrammairesdepropri´ete´s[2,3]constituentun formalismepermettantded´ecrirelalanguenaturelle entermesdecontrainteslocales,appel´eese´s´iteprrop. Cespropri´et´espeuventˆetreviol´eesinde´pendemment les unes des autres, ce qui rend possible la description de´nonce´sagrammaticaux(i.e.ptsaianeirev´eruine,q lensembledesproprie´te´sdelalangue),et´egalement dede´nirunenotiondegrammaticalite´(ratioentre proprie´te´sviol´eesetproprie´t´esv´erie´es). Lespropri´et´esutilis´eespourde´crirelalanguese basent sur des observations linguistiques : ordre (par-tiel) entre les mots, exclusion mutuelle entre certains motsdansuncontexteproche,cooccurrencesyste´ma-tique de certains mots dans un contexte proche, non-r´ep´etitiondecertainsmotsdansuncontexteproche, pre´sencefacultativedecertainsmots,etc. Chaqueproprie´t´ealaformeA:ψ,o`uAneetrepr´es lacat´egorie(i.e.renarbnnud)etusnadduœl,etquti´e syntaxique, etψla contrainte qui s’applique sur les nœudslsdecelui-ci.Lensembledesproprie´t´esaux-quellesnousnousint´eressonsestlesuivant: obligationA:4Buddutnœquet´etietpo,tourA, pre´sencedaumoinsunnœudls´etiquet´eB, unicit´eA:B!,pourtoutœndude´ituqteetApr,-´e sencedauplusunnœudlse´tiquete´B, line´arit´eA:BCtourpo,teuqtee´itdudtuœnA, encasdepr´esencedenœudslse´tiquet´esBetC, Bp´rcee`edC,
1 exigenceA:BCe´ddœutnttueiqet,pourtou A´rpal,decnese´teudlunnœiques´etBimplique lapr´esencedunnœudlse´tiquete´C, exclusionA:B6⇔Cruottuœndude´ituqteet,poA, desnœudslsd´etiquettesBetCsont mutuelle-ment exclusifs, constituenceA:Soutnourt´etœuddetteuqip,A, lese´tiquettesdesnœudslsappartiennenta`len-sembleS. Apartirdecetensembledeproprie´te´s,ilestpos-sibled´enonceruncertainnombredere`glesgramma-ticalesde´crivantlasyntaxedelalanguenaturelle. Parexemple,uner`eglegrammaticalestipulantquun groupe nominal contient exactement un nom et que ce nompeutˆetrepre´ce´d´edunde´terminant,pourraitˆetre repre´sent´eeparlensembledeproprie´te´sci-dessous: SN:{D,N},SN:4N,SN:N!,SN:D!, (1) (2) (3) (4) SN:DN,D:{},N:{} (5) (6) (7) o`uSN´ale`erttueiqete`fe´rSyntagme Nominal(groupe nominal),Da`Dete´nimrtna, etN`aNomap.Lprro´ei´et (1) (SN:{D,N}) indique que, dans un arbre syntaxique, lesnœudslsdunœudrepr´esentantlegroupenomi-naldoiventeˆtre´etiquete´sDouN. (2) (SN:4N) in-dique qu’un nœudSNdomine directement au moins un nœudN. (3) (SN:N!) indique qu’un nœudSNdo-mine directement au plus un nœudN. (4) (SN:D!) indique qu’un nœudSNdomine directement au plus un nœudD. (5) (SN:DN) indique que, pour tout nœudde´tiquetteSN, si ce nœud comporte deux nœuds lsd´etiquettesrespectivesDetN,alorte´-inelsdduœ quetteD`eecceder´ptteqieu´teuldiN. Enfin, (6) et (7) permettentdesassurerquelesnœudsd´etiquettesD etNsont des nœuds feuilles (seuls les mots du lexique peuventˆetresitu´esendessousdecesnœuds).Len-sembledecespropri´ete´saexactementdeuxmod`eles d’arbre syntaxique ayant la racineSN: SN SN
D
N
N
Les´etiquettesintroduitesdanscetexemplesontap-pel´eesiqaxsuesyntries´egocatet renseignent sur le type d’un constituant de la phrase. Une grammaire de pro-pri´et´esde´nitdoncdescontraintessurlesrelations entrelesdi´erentstypesdeconstituantsapparaissant dans une phrase. Pour faire le lien avec le lexique, on d´enituneassociationentremotsetcat´egoriessyn-taxiques.Parexemple,onpeutspe´cierquelemot pommee(monnutscat´egorieN) via :
cat(pomme) =N ´ 1.Egalementappele´ecooccurrence.erutare´ttislnaald