DC nyelvtan

Bizonyos mondatokra épülő nyelvtan (rövidítve DC grammar , DCG ; angolból.  Határozott záradék grammatika ) a nyelvtan felépítésének módja a logikai programozási nyelvekben, például a Prologban . A DC nyelvtant általában a Prologhoz társítják, de más nyelvek, például a Mercury is használhatják a DC nyelvtant. A címben a „bizonyos mondatok” kifejezés szerepel, mivel ez a nyelvtan az elsőrendű logikában a Horne - záradékon alapul .

A DCG definíció a Prolog és más hasonló nyelvek meghatározott típusú kifejezéseire vonatkozik. A DC-nyelvtan nem fedi le a nyelvtan bizonyos mondatokkal történő kifejezésének minden módját. Azonban a DC nyelvtan minden jellemzője és tulajdonsága pontosan ugyanaz lesz minden olyan nyelvtan esetében, amely bizonyos mondatokat pontosan ugyanúgy használ, mint a Prolog.

A DC-grammatika pontosabb elképzeléséhez a következő hipotetikus összehasonlítást tehetjük: a határozott mondatok halmaza axiómák halmazának tekinthető, és a bemeneti karakterlánc helyessége és a hozzá tartozó elemzőfa létezése. tételnek tekintjük, melynek bizonyítása ezeken az axiómákon alapul [1] . Ennek az ábrázolásnak megvan az az előnye, hogy a nyelvi kifejezések felismerése és elemzése kifejezések igazolásává válik, akárcsak a logikai programozási nyelvekben.

Történelem

A DC nyelvtanok története szorosan kapcsolódik a Prolog történetéhez, amely viszont Marseille-ben (Franciaország) és Edinburgh-ban (Skócia) jött létre. Robert Kowalskinak , a Prolog nyelv első fejlesztőjének köszönhetően az első Prolog rendszert 1972-ben Alain Colmerauer és Philippe Roussel [ 2] fejlesztette ki . A nyelven írt első program egy természetes nyelvi feldolgozó rendszer megvalósítására tett kísérletet. Továbbá Fernando Pereira [F.Pereira] és David Warren [D.Warren] az Edinburghi Egyetemről részt vett a Prolog fejlesztésében.

Colmeroe korábbi munkája a Q-rendszer néven ismert nyelvfeldolgozó rendszerről szólt, amelyet angolról franciára fordítottak [3] . 1978-ban Colmeroe írt egy tanulmányt a nyelvtanok metamorfózis grammatikáknak nevezett ábrázolásáról, amely a Prolog első változatának, a Marseilles Prolognak az alapját képezte. Ebben a cikkben formális leírást adott a metamorf nyelvtanokról, és néhány példát mutatott be azok alkalmazására.

A Prolog másik két alkotója, Fernando Pereira és David Warren megalkotta a "mondatspecifikus nyelvtan" kifejezést, és létrehozta a DC-grammatikai jelölést, amelyet a Prolog a mai napig használ. Nagyra értékelték Kolmeroe és Kowalski ötleteit, és észrevették, hogy a DC nyelvtan a Kolmeroe metamorf nyelvtanainak speciális esete. Ezt az ötletet a „Határozott záradéknyelvtanok nyelvelemzéshez” című cikk vezette be, amely a DC-gramtant „formalizmusként írta le, amelyben a nyelvtant elsőrendű predikátumlogika mondatai fejezik ki”, amely „lehetővé teszi a létrehozást hatékony programok a Prolog programozási nyelven" [4] .

Később Pereira, Warren és más Prolog úttörők leírták a DC nyelvtan egyéb vonatkozásait is. Pereira és Warren megírta a "Parsing as Deduction" című tanulmányt, amelyben leírja az elemzéshez használt Early-féle következtetés-bizonyítási eljárást [5] . Pereira Stuart Scheiberrel közösen írta a Prolog and Natural Language Analysis című könyvet is, amely a számítógépes nyelvészet alapjait hivatott tanulmányozni logikai programozás segítségével [6] .

Kiterjesztés

Javításokat javasoltak a Pereira és Warren által leírt DC nyelvtanokhoz. Például Pereira maga javasolta az extrapozíciós nyelvtanokat (extraposition grammars, XGs) [7] . Erre a formalizmusra azért volt szükség, hogy leegyszerűsítsék egy figyelemreméltó nyelvtani jelenség - az extrapozíció - bemutatását. Pereira ezt írta: "Az XG és a DC-grammatika szabályai között az a különbség, hogy az XG szabály bal oldala több karakterből állhat." Ez megkönnyíti a környezetérzékeny nyelvtanok kifejezését. Az XG azonban átalakítható DC nyelvtanná, és a DC nyelvtan elvileg mindent meg tud csinálni, amit az XG.

Jóval később, 1995-ben a NEC Corporation kutatói kifejlesztettek egy másik kiterjesztést, a Multi-Modal Definite Clause Grammars (MM-DCG) nevet. Ez a kiterjesztés olyan kifejezések felismerésére és elemzésére szolgált, amelyek nem csak szövegrészeket, hanem például képeket is tartalmaznak [8] .

1984-ben egy másik kiterjesztést írtak le, az úgynevezett fordítási DC nyelvtanokat (definite clauses translation grammars, DCTGs) [9] . A DCTG jelölés szinte pontosan úgy néz ki, mint a DC nyelvtani jelölés, kivéve, hogy a jelölés ::=helyett -->. Az attribútumnyelvtanok kényelmes támogatására találták ki [10] . A DCTG normál Prolog mondatokká való fordítása pontosan ugyanaz, mint a DC-nyelvtanoknál, de kettő helyett három argumentumot adunk hozzá.

Példa

A DC nyelvtanok egy elemi példája segít megérteni, mire képesek az ilyen nyelvtanok és mik azok.

mondat --> főnév_kifejezés, ige_kifejezés. főnév_kifejezés --> det, főnév. ige_kifejezés --> ige, főnév_kifejezés. det --> [a]. det --> [a]. főnév --> [macska]. főnév --> [denevér]. ige --> [eszik].

Ez a nyelvtan olyan alkalmazásokat generál, mint "a macska megeszi a denevért", "a denevér megeszi a macskát". A helyes nyelvi kifejezés létrehozásához ezzel a nyelvtannal a Prolog értelmezőben be kell írnia: sentence(X,[]). És annak teszteléséhez, hogy egy adott mondat egy nyelvhez tartozik-e, begépelheti a következőt sentence([the,bat,eats,the,bat],[]).

Átalakítás határozott mondatok halmazává

A DC nyelvtanok jelölése szintaktikai cukor a Prolog normál szintaktikai mondatkészletéhez. Például az előző példa a következőképpen írható:

mondat(S1,S3) :- főnév_kifejezés(S1,S2), ige_kifejezés(S2,S3). főnév_kifejezés(S1,S3) :- det(S1,S2), főnév(S2,S3). ige_kifejezés(S1,S3) :- ige(S1,S2), főnév_kifejezés(S2,S3). det([az|X],X). det([a|X],X). főnév ([macska|X], X). főnév([bat|X], X). ige([eat|X], X).

Lista különbség

Az egyes függvények argumentumai, például (S1,S3)és (S1,S2), listás különbségek . A listakülönbség az, ahogyan egy listát két lista különbsége ábrázol. A Prolog jelöléssel egy listára írhatjuk, hogy a lista Legy listapár ([L|X],X).

A List diff hatékonysága miatt a listák ábrázolására szolgál a DC nyelvtanokban. Kényelmesebb összefűzni a listák különbségeit, ahol szükséges, mivel a listaösszefűzés (S1,S2)egy (S2,S3)lista (S1,S3). [tizenegy]

Környezetérzékeny nyelvtanok

A Prologban a normál DC-szabályok mellőzik a funktorokban lévő extra argumentumokat, amint azt az előző példában bemutattuk. Egy ilyen nyelvtan azonban csak kontextusmentes nyelvtanokat tud reprezentálni, vagyis egy argumentummal a bal oldalon. A kontextusérzékeny nyelvtanok azonban DC nyelvtan segítségével is megjeleníthetők argumentumok hozzáadásával, mint a következő példában:

s --> szimbólumok(Sem,a), szimbólumok(Sem,b), szimbólumok(Sem,c). szimbólumok(vége,_) --> []. szimbólumok(s(Sem),S) --> [S], szimbólumok(Sem,S).

Ez a DC-nyelvtani szabálykészlet olyan nyelvtant ír le, amely formátumú karakterláncokat generál , amely a . [12]

Prezentációs funkciók

Ezenkívül a DC-grammatika segítségével a nyelv különféle nyelvi jellemzői meglehetősen tömören ábrázolhatók, ha további argumentumokat adunk a funktorokhoz. [13] Vegyük például a következő DC-szabályokat:

mondat --> névmás(tárgy), ige_kifejezés. ige_kifejezés --> ige, névmás(tárgy). névmás(alany) --> [ő]. névmás(alany) --> [ő]. névmás(tárgy) --> [ő]. névmás(tárgy) --> [ő]. ige --> [tetszik].

Ez a nyelvtan a „tetszik neki” vagy „tetszik neki” formájú mondatokat generál, de nem teszi lehetővé a „tetszik neki” vagy „tetszik neki” kifejezések generálását.

DC nyelvtanok elemzése

A DC-nyelvtanok használatának fő gyakorlati értéke a nyelvtan mondatainak elemzése, vagyis egy elemzőfa felépítése. Ezt megteheti például "extra argumentumok" hozzáadásával a DC nyelvtan függvényeihez, amint az a következő példában történik:

mondat(ok(NP,VP)) --> főnévi_kifejezés(NP), igei_kifejezés(VP). főnév_kifejezés(np(D,N)) --> det(D), főnév(N). ige_kifejezés(vp(V,NP)) --> ige(V), főnév_kifejezés(NP). det(d(a)) --> [a]. det(d(a)) --> [a]. főnév(n(bat)) --> [denevér]. főnév(n(macska)) --> [macska]. ige(v(eszik)) --> [eszik].

Most bármelyik mondathoz kaphat egy elemzőfát:

| ?- mondat(Parse_tree, [a,denevér,eszik,macska], []). Elemző_fa = s(np(d(a),n(bat)),vp(v(eats),np(d(a),n(macska)))) ? ;

További alkalmazás

A DC nyelvtanok további szintaktikai cukrot biztosíthatnak a kód más helyein lévő paraméterek elrejtéséhez, amelyek nem kapcsolódnak az alkalmazás elemzéséhez. Például a Mercury programozási nyelvben, amely a Prolog szintaxisának egy részét kölcsönzi, a DC nyelvtanokat arra használják, hogy elrejtsenek io__stateegy argumentumot az I/O kódban. [14] A DC-nyelvtanokat más helyzetekben is használják a Merkúrban.

Lásd még

Jegyzetek

  1. ↑ Johnson, M. A nyelvtan formalizálásának két módja  //  Nyelvészet és filozófia : folyóirat. - 1994. - 1. évf. 17 , sz. 3 . - P. 221-248 .
  2. ↑ Kowalski, RA A logikai programozás korai évei  (neopr.) .
  3. ↑ Colmerauer, A. Metamorphosis  grammars (határozatlan)  // Természetes nyelvi kommunikáció számítógépekkel. - 1978. - S. 133-189 .
  4. ↑ Pereira, F.; D. Warren. Határozott tagmondat-nyelvtan  nyelvelemzéshez (neopr.) . – 1980.
  5. ↑ Pereira, FCN; D.H.D. Warren (1983). "Elemzés levonásként". A Számítógépes Nyelvészeti Egyesület 21. éves ülésének anyaga . Számítógépes Nyelvészeti Egyesület Morristown, NJ, USA. pp. 137-144. Elavult használt paraméter |coauthors=( súgó )
  6. ↑ Pereira, FCN; S. M. Shieber. Prolog és természetes nyelvű elemzés  (neopr.) . — Microtome Publishing, 2002.
  7. ↑ Pereira, F. Kifejezési nyelvtanok  (határozatlan)  // Számítógépes nyelvészet. - 1981. - V. 7 , 4. sz . - S. 243-256 .
  8. ↑ Shimazu, H.; Y. Takashima. Multimodális határozott záradék nyelvtan  (neopr.)  // Rendszerek és számítógépek Japánban. - 1995. - T. 26 , 3. sz .
  9. ↑ Abramson , H. Határozott mondatfordítási nyelvtanok  . – 1984.
  10. ↑ Sperberg-McQueen, CM Rövid bevezetés a határozott tagmondat-nyelvtanokhoz és a határozott mondatfordítási nyelvtanokhoz . Letöltve: 2009. április 21. Az eredetiből archiválva : 2012. március 22..
  11. ↑ Fleck, Arthur Határozott záradék nyelvtani fordítása . Letöltve: 2009. április 16. Az eredetiből archiválva : 2012. március 22..
  12. ↑ Fisher, JR Prolog oktatóanyag -- 7.1 . Letöltve: 2009. április 16. Az eredetiből archiválva : 2012. március 22..
  13. ↑ A DCG-k természetes jelölést adnak a funkciókhoz . Letöltve: 2009. április 21. Az eredetiből archiválva : 2012. március 22..
  14. ↑ Mercury oktatóanyag: DCG jelölés . Letöltve: 2009. április 21. Az eredetiből archiválva : 2012. március 22..

További források