Gramatica DC

Gramatica construită pe anumite propoziții (abrev. DC grammar , DCG ; din engleză.  Definite clause grammar ) este o modalitate de a construi gramatica în limbaje de programare logică, de exemplu, Prolog . Gramatica DC este de obicei asociată cu Prolog, dar alte limbi, cum ar fi Mercury , pot folosi și gramatica DC. Expresia „anumite propoziții” este folosită în titlu deoarece această gramatică se bazează pe clauza Horne în logica de ordinul întâi .

Definiția DCG se referă la tipuri specifice de expresii din Prolog și alte limbi similare. Nu toate modurile de exprimare a unei gramatici folosind anumite propoziții sunt acoperite de gramatica DC. Cu toate acestea, toate caracteristicile și proprietățile unei gramatici DC vor fi exact aceleași pentru orice gramatică care utilizează anumite propoziții exact în același mod ca Prolog.

Pentru a ne imagina mai clar ce sunt gramaticile DC, putem face următoarea comparație ipotetică: setul de propoziții definite poate fi considerat ca un set de axiome, iar corectitudinea șirului de intrare și existența unui arbore de analiză pentru acesta poate fi considerată ca o teoremă, a cărei demonstrație se bazează pe aceste axiome [1] . Această reprezentare are avantajul că recunoașterea și analizarea expresiilor limbajului se transformă în dovada expresiilor, așa cum se face în limbajele de programare logică.

Istorie

Istoria gramaticilor DC este strâns legată de istoria lui Prolog, care la rândul său a fost creat în Marsilia (Franța) și Edinburgh (Scoția). Datorită lui Robert Kowalski , primul dezvoltator al limbajului Prolog, primul sistem Prolog a fost dezvoltat în 1972 de Alain Colmerauer și Philippe Roussel [2] . Primul program scris în limbaj a fost o încercare de a implementa un sistem de procesare a limbajului natural. De asemenea, Fernando Pereira [F.Pereira] și David Warren [D.Warren] de la Universitatea din Edinburgh au luat parte la dezvoltarea Prologului.

Lucrarea anterioară a lui Colmeroe a fost asupra unui sistem de procesare a limbii cunoscut sub numele de Q-system, care a fost folosit pentru a traduce din engleză în franceză [3] . În 1978, Colmeroe a scris o lucrare despre o modalitate de reprezentare a gramaticilor numită gramatica metamorfoză, care a stat la baza primei versiuni de Prolog, numită Marsilia Prolog. În acest articol, el a oferit o descriere formală a gramaticilor metamorfice și a oferit câteva exemple care demonstrează aplicarea lor.

Alți doi creatori ai Prologului, Fernando Pereira și David Warren, au inventat termenul „gramatică specifică propoziției” și au creat notația DC-gramatică care este folosită în Prolog până astăzi. Ei au apreciat ideile lui Kolmeroe și Kowalski și au observat că gramatica DC este un caz special al gramaticilor metamorfice ale lui Kolmeroe. Această idee a fost introdusă în articolul „Definite Clause Grammars for Language Analysis”, care descria DC-gramatica ca „un formalism... în care o gramatică este exprimată prin propoziții de logica predicatelor de ordinul întâi”, care „permite crearea de programe eficiente în limbajul de programare Prolog” [4] .

Mai târziu, Pereira, Warren și alți pionieri Prolog au descris alte aspecte ale gramaticilor DC. Pereira și Warren au scris lucrarea „Parsing as Deduction” care descrie procedura de demonstrare a inferenței lui Early utilizată pentru analiza [5] . Pereira a fost, de asemenea, coautor al cărții Prolog and Natural Language Analysis cu Stuart Scheiber, care a fost menită să studieze bazele lingvisticii computaționale folosind programarea logică [6] .

Extensie

Au fost propuse îmbunătățiri pentru gramaticile DC descrise de Pereira și Warren. De exemplu, Pereira însuși a propus gramatici extrapoziționale (gramatici de extrapoziție, XG) [7] . Acest formalism a fost necesar pentru a simplifica prezentarea unui fenomen gramatical remarcabil - extrapunerea. Pereira a scris: „Diferența dintre regulile XG și DC-gramatica este că partea stângă a regulii XG poate consta din mai multe caractere”. Acest lucru facilitează exprimarea gramaticilor sensibile la context. Cu toate acestea, XG poate fi transformat într-o gramatică DC, iar gramatica DC, în principiu, poate face tot ce poate face XG.

Mult mai târziu, în 1995, cercetătorii de la NEC Corporation au dezvoltat o altă extensie numită Multi-Modal Definite Clause Grammars (MM-DCGs). Această extensie a fost menită să recunoască și să analizeze expresii care includ nu numai părți de text, ci și, de exemplu, imagini [8] .

În 1984, a fost descrisă o altă extensie numită gramatica DC de traducere (gramatica de traducere cu clauze definite, DCTGs) [9] . Notația DCTG arată aproape exact ca notația gramaticală DC, cu excepția faptului că notația ::=în loc de -->. A fost inventat pentru a sprijini convenabil gramaticile atributelor [10] . Traducerea DCTG în propoziții normale Prolog este exact aceeași ca și pentru gramatici DC, dar trei argumente sunt adăugate în loc de două.

Exemplu

Un exemplu elementar de gramatică DC vă va ajuta să înțelegeți de ce sunt capabile astfel de gramatici și ce sunt.

propoziție --> frază_substantiv, expresie_verbală. frază_substantiv --> det, substantiv. expresie_verbală --> verb, expresie_substantiv. det --> [the]. det --> [a]. substantiv --> [pisica]. substantiv --> [liliac]. verb --> [manca].

Această gramatică generează aplicații precum „pisica mănâncă liliacul”, „un liliac mănâncă pisica”. Pentru a genera o expresie corectă a limbajului folosind această gramatică, în interpretul Prolog, trebuie să tastați: sentence(X,[]). Și pentru a testa dacă o anumită propoziție aparține unei limbi, puteți tasta sentence([the,bat,eats,the,bat],[]).

Transformarea într-un set de propoziții determinate

Notarea gramaticilor DC este zahăr sintactic pentru setul normal de propoziții sintactice din Prolog. De exemplu, exemplul anterior ar putea fi scris după cum urmează:

propoziție(S1,S3) :- expresie_substantiv(S1,S2), expresie_verbal(S2,S3). frază_substantiv(S1,S3) :- det(S1,S2), substantiv(S2,S3). expresie_verbal(S1,S3) :- verb(S1,S2), expresie_substantiv(S2,S3). det([the|X],X). det([a|X],X). substantiv([pisica|X], X). substantiv ([bat|X], X). verb([manca|X], X).

Listă diferența

Argumentele fiecărui functor, de exemplu, (S1,S3)și (S1,S2), sunt diferențe de listă . O diferență de listă este modul în care o listă este reprezentată prin diferența a două liste. Folosind notația Prolog pentru o listă, se poate scrie că o listă Leste o pereche de liste ([L|X],X).

List diff este folosit pentru a reprezenta liste în gramaticile DC datorită eficienței sale. Este mai convenabil să concatenați diferențele de listă acolo unde este necesar, deoarece concatenarea listelor (S1,S2)este (S2,S3)o listă (S1,S3). [unsprezece]

Gramatici sensibile la context

În Prolog, regulile DC normale nu au argumente suplimentare în functori, așa cum s-a demonstrat în exemplul anterior. Cu toate acestea, o astfel de gramatică poate reprezenta doar gramatici fără context, adică cu un argument în partea stângă. Cu toate acestea, gramaticile sensibile la context pot fi reprezentate și folosind o gramatică DC prin adăugarea de argumente, ca în exemplul următor:

s --> simboluri(Sem,a), simboluri(Sem,b), simboluri(Sem,c). simboluri(sfârșit,_) --> []. simboluri(s(Sem),S) --> [S], simboluri(Sem,S).

Acest set de reguli de gramatică DC descrie o gramatică care generează șiruri de forma , reprezentând . [12]

Caracteristici de prezentare

De asemenea, cu ajutorul gramaticilor DC, diferitele trăsături lingvistice ale limbii pot fi reprezentate destul de succint prin adăugarea de argumente suplimentare la functori. [13] De exemplu, luați în considerare următorul set de reguli DC:

propoziție --> pronume (subiect), frază_verbală. expresie_verbală --> verb, pronume (obiect). pronume(subiect) --> [el]. pronume(subiect) --> [ea]. pronume(obiect) --> [el]. pronume(obiect) --> [ea]. verb --> [place].

Această gramatică generează propoziții de forma „îi place de ea” sau „îi place de el”, dar nu permite generarea „ei îi place el” sau „îi place el”.

Analizarea gramaticilor DC

Principala valoare practică a utilizării gramaticilor DC este analizarea propozițiilor acestei gramatici, adică construcția unui arbore de analiză. Acest lucru se poate face prin adăugarea de „argumente suplimentare” la functorii gramaticii DC, de exemplu, așa cum se face în exemplul următor:

propoziție(s(NP,VP)) --> propoziție_substantiv(NP), frază_verb(VP). frază_substantiv(np(D,N)) --> det(D), substantiv(N). expresie_verbal(vp(V,NP)) --> verb(V), expresie_substantiv(NP). det(d(the)) --> [the]. det(d(a)) --> [a]. substantiv(n(liliac)) --> [liliac]. substantiv(n(pisică)) --> [pisică]. verb(v(manca)) --> [manca].

Acum, pentru orice propoziție, puteți obține un arbore de analiză:

| ?- propoziție (parse_tree, [liliac, mănâncă, o, pisică], []). Arbore_parse = s(np(d(the),n(liliac)),vp(v(mâncă),np(d(a),n(pisică))))? ;

Aplicație suplimentară

Gramaticile DC pot oferi zahăr sintactic suplimentar pentru a ascunde parametrii în alte locuri din cod care nu au legătură cu analiza aplicației. De exemplu, în limbajul de programare Mercury, care împrumută o parte din sintaxa lui Prolog, gramaticile DC sunt folosite pentru a ascunde io__stateun argument în codul I/O. [14] Gramaticile DC sunt folosite și în alte situații în Mercur.

Vezi și

Note

  1. ↑ Johnson, M. Two ways of formalizing grammatics  //  Linguistics and Philosophy : jurnal. - 1994. - Vol. 17 , nr. 3 . - P. 221-248 .
  2. ↑ Kowalski, RA Primii ani ai programării logice  (neopr.) .
  3. ↑ Colmerauer, A. Gramaticile metamorfozei  (nedefinite)  // Comunicarea limbajului natural cu computerele. - 1978. - S. 133-189 .
  4. ↑ Pereira, F.; D. Warren. Gramatici cu clauze definite pentru analiza limbajului  (neopr.) . — 1980.
  5. ↑ Pereira, FCN; D.H.D. Warren (1983). „Analizarea ca deducere”. Lucrările celei de-a 21-a reuniuni anuale privind Asociația pentru Lingvistică Computațională . Asociația pentru Lingvistică Computațională Morristown, NJ, SUA. pp. 137-144. Parametrul depreciat folosit |coauthors=( ajutor )
  6. ↑ Pereira, FCN; S.M. Shieber. Prolog și analiză în limbaj natural  (neopr.) . — Editura Microtome, 2002.
  7. ↑ Pereira, F. Gramatici de extrapunere  (nedefinite)  // Lingvistică computațională. - 1981. - V. 7 , nr 4 . - S. 243-256 .
  8. ↑ Shimazu, H.; Y. Takashima. Gramatică cu clauză definită multimodală  (neopr.)  // Sisteme și calculatoare în Japonia. - 1995. - T. 26 , nr. 3 .
  9. ↑ Abramson , H. Definite clause translation grammatics  . — 1984.
  10. ↑ Sperberg-McQueen, CM O scurtă introducere în gramaticile cu clauze definite și gramaticile pentru traducerea clauzelor definite . Consultat la 21 aprilie 2009. Arhivat din original pe 22 martie 2012.
  11. ↑ Fleck, Arthur Definite Clause Grammar Translation . Consultat la 16 aprilie 2009. Arhivat din original pe 22 martie 2012.
  12. ↑ Fisher, JR Prolog Tutorial -- 7.1 . Consultat la 16 aprilie 2009. Arhivat din original pe 22 martie 2012.
  13. ↑ DCG-urile ne oferă o notație naturală pentru caracteristici . Consultat la 21 aprilie 2009. Arhivat din original pe 22 martie 2012.
  14. ↑ Mercury Tutorial: DCG Notation . Consultat la 21 aprilie 2009. Arhivat din original pe 22 martie 2012.

Surse suplimentare