DC gramatika

Gramatika postavená na určitých větách (zkr. DC gramatika , DCG ; z angličtiny.  Definite clause Gramatika ) je způsob budování gramatiky v logických programovacích jazycích, například Prolog . DC gramatika je obvykle spojena s Prologem, ale jiné jazyky, jako je Mercury , mohou také používat DC gramatiku. Fráze „určité věty“ je použita v názvu, protože tato gramatika je založena na Horneově klauzuli v logice prvního řádu .

Definice DCG odkazuje na specifické typy výrazů v Prologu a dalších podobných jazycích. DC-gramatika nepokrývá všechny způsoby vyjádření gramatiky pomocí určitých vět. Všechny vlastnosti a vlastnosti DC gramatiky však budou naprosto stejné pro jakoukoli gramatiku, která používá určité věty přesně stejným způsobem jako Prolog.

Abychom si jasněji představili, co jsou DC-gramatiky, můžeme provést následující hypotetické srovnání: množinu určitých vět lze považovat za množinu axiomů a správnost vstupního řetězce a existence analyzovacího stromu pro něj může být považováno za teorém, jehož důkaz je založen na těchto axiomech [1] . Tato reprezentace má tu výhodu, že rozpoznávání a analyzování jazykových výrazů se mění na důkaz výrazů, stejně jako se to dělá v logických programovacích jazycích.

Historie

Historie DC gramatik úzce souvisí s historií Prologu, který zase vznikl v Marseille (Francie) a Edinburghu (Skotsko). Díky Robertu Kowalskimu , prvnímu vývojáři jazyka Prolog, byl první systém Prolog vyvinut v roce 1972 Alainem Colmerauerem a Philippem Rousselem [2] . První program napsaný v tomto jazyce byl pokusem implementovat systém zpracování přirozeného jazyka. Na vývoji Prologu se podíleli také Fernando Pereira [F.Pereira] a David Warren [D.Warren] z University of Edinburgh.

Colmeroeova předchozí práce se týkala systému zpracování jazyka známého jako Q-systém, který se používal k překladu z angličtiny do francouzštiny [3] . V roce 1978 Colmeroe napsal článek o způsobu reprezentace gramatik nazývaných metamorfózní gramatiky, který tvořil základ první verze Prologu nazvané Marseilles Prolog. V tomto článku poskytl formální popis metamorfních gramatik a poskytl několik příkladů demonstrujících jejich aplikaci.

Dva další tvůrci Prologu, Fernando Pereira a David Warren, vytvořili termín „gramatika specifická pro věty“ a vytvořili DC-gramatický zápis, který se v Prologu používá dodnes. Ocenili myšlenky Kolmeroea a Kowalského a všimli si, že DC gramatika je speciálním případem Kolmeroeových metamorfních gramatik. Tato myšlenka byla představena v článku „Definite Clause Grammars for Language Analysis“, který popisoval DC-gramatiku jako „formalismus... ve kterém je gramatika vyjádřena větami predikátové logiky prvního řádu“, který „umožňuje vytvoření efektivních programů v programovacím jazyce Prolog“ [4] .

Později Pereira, Warren a další průkopníci Prologu popsali další aspekty DC gramatik. Pereira a Warren napsali článek „Parsování jako dedukce“ popisující Earlyho inferenční důkazní postup používaný pro analýzu [5] . Pereira je také spoluautorem knihy Prolog and Natural Language Analysis se Stuartem Scheiberem, která byla určena ke studiu základů výpočetní lingvistiky pomocí logického programování [6] .

Rozšíření

Byla navržena vylepšení pro DC gramatiky popsané Pereirou a Warrenem. Například sám Pereira navrhoval extrapoziční gramatiky (extrapoziční gramatiky, XG) [7] . Tento formalismus byl nezbytný pro zjednodušení prezentace pozoruhodného gramatického jevu – extrapozice. Pereira napsal: "Rozdíl mezi pravidly XG a DC-gramatiky je v tom, že levá strana pravidla XG se může skládat z několika znaků." To usnadňuje vyjadřování kontextově citlivých gramatik. XG však lze přeměnit na DC gramatiku a DC gramatika v zásadě umí vše, co XG.

Mnohem později, v roce 1995, výzkumníci z NEC Corporation vyvinuli další rozšíření nazvané Multi-Modal Definite Clause Grammars (MM-DCG). Toto rozšíření mělo za úkol rozpoznávat a analyzovat výrazy, které zahrnují nejen textové části, ale také například obrázky [8] .

V roce 1984 bylo popsáno další rozšíření nazvané překladové DC gramatiky (definite clause translation Gramatiky, DCTG) [9] . Zápis DCTG vypadá téměř přesně jako zápis gramatiky DC, až na to, že zápis ::=místo -->. Byl vynalezen, aby pohodlně podporoval atributové gramatiky [10] . Překlad DCTG do normálních vět Prologu je úplně stejný jako u DC-gramatiky, ale místo dvou jsou přidány tři argumenty.

Příklad

Elementární příklad DC gramatik vám pomůže pochopit, čeho jsou takové gramatiky schopny a čím jsou.

věta --> podstatná_fráze, slovesná_fráze. noun_phrase --> det, podstatné jméno. slovesná_fráze --> sloveso, podstatné_jméno. det --> [the]. det --> [a]. podstatné jméno --> [kočka]. podstatné jméno --> [netopýr]. sloveso --> [jíst].

Tato gramatika generuje aplikace jako „kočka žere netopýra“, „netopýr žere kočku“. Chcete-li pomocí této gramatiky vygenerovat správný jazykový výraz, musíte v interpretu Prolog zadat: sentence(X,[]). A abyste otestovali, zda daná věta patří do jazyka, můžete zadat sentence([the,bat,eats,the,bat],[]).

Transformace do množiny určitých vět

Zápis DC gramatik je syntaktický cukr pro normální sadu syntaktických vět v Prologu. Například předchozí příklad by mohl být zapsán takto:

věta(S1,S3) :- podstatné_slovo(S1,S2), sloveso(S2,S3). noun_phrase(S1,S3) :- det(S1,S2), noun(S2,S3). sloveso_fráze(S1,S3) :- sloveso(S1,S2), podstatné_jmeno(S2,S3). det([the|X],X). det([a|X],X). podstatné jméno([cat|X], X). podstatné jméno([bat|X], X). sloveso([jíst|X], X).

Rozdíl v seznamu

Aktanty pro každý funktor, například (S1,S3)a (S1,S2), jsou seznamové rozdíly . Rozdíl v seznamu je způsob, jakým je seznam reprezentován rozdílem dvou seznamů. Pomocí zápisu Prolog pro seznam lze napsat, že seznam Lje dvojice seznamů ([L|X],X).

List diff se používá k reprezentaci seznamů v DC gramatikách kvůli své účinnosti. V případě potřeby je pohodlnější zřetězit rozdíly v seznamech, protože zřetězení seznamů (S1,S2)je (S2,S3)seznam (S1,S3). [jedenáct]

Kontextově citlivé gramatiky

V Prologu se normální DC pravidla obejdou bez dalších argumentů ve funktorech, jak bylo ukázáno v předchozím příkladu. Taková gramatika však může reprezentovat pouze bezkontextové gramatiky, tedy s jedním argumentem na levé straně. Kontextově citlivé gramatiky však lze také reprezentovat pomocí DC gramatiky přidáním argumentů, jako v následujícím příkladu:

s --> symboly (Sem,a), symboly (Sem,b), symboly (Sem,c). symbols(end,_) --> []. symboly(s(Sem),S) --> [S], symboly(Sem,S).

Tato sada pravidel DC-grammar popisuje gramatiku, která generuje řetězce formuláře , představující . [12]

Funkce prezentace

Pomocí DC-gramatiky lze také poměrně stručně znázornit různé lingvistické rysy jazyka přidáním dalších aktantů k funktorům. [13] Zvažte například následující sadu pravidel DC:

věta --> zájmeno(předmět), sloveso_fráze. sloveso_fráze --> sloveso, zájmeno (předmět). zájmeno (předmět) --> [on]. zájmeno (předmět) --> [ona]. zájmeno (předmět) --> [on]. zájmeno (předmět) --> [jí]. sloveso --> [líbí se mi].

Tato gramatika generuje věty ve tvaru „má ji rád“ nebo „má ho rád“, ale neumožňuje generování „jí má rád on“ nebo „on ho má rád“.

Analýza DC gramatiky

Hlavní praktickou hodnotou použití DC-gramatiky je parsování vět této gramatiky, to znamená konstrukce stromu analýzy. To lze provést přidáním „extraargumentů“ k funktorům DC gramatiky, například, jak je to provedeno v následujícím příkladu:

věta(s(NP,VP)) --> noun_phrase(NP), sloveso_phrase(VP). noun_phrase(np(D,N)) --> det(D), noun(N). sloveso_fráze(vp(V,NP)) --> sloveso(V), podstatné jméno(NP). det(d(the)) --> [the]. det(d(a)) --> [a]. podstatné jméno(n(netopýr)) --> [netopýr]. podstatné jméno(n(kočka)) --> [kočka]. sloveso(v(jíst)) --> [jíst].

Nyní pro jakoukoli větu můžete získat strom analýzy:

| ?- věta(Parse_tree, [the,bat,eats,a,cat], []). Parse_tree = s(np(d(the),n(bat)),vp(v(jí),np(d(a),n(kočka)))) ? ;

Další aplikace

DC gramatiky mohou poskytnout další syntaktický cukr pro skrytí parametrů na jiných místech v kódu, která nesouvisejí s analýzou aplikace. Například v programovacím jazyce Mercury, který si vypůjčuje část syntaxe Prologu, se DC gramatiky používají ke skrytí io__stateargumentu v I/O kódu. [14] DC-gramatiky se v Merkuru používají i v jiných situacích.

Viz také

Poznámky

  1. ↑ Johnson, M. Dva způsoby formalizace gramatik  //  Lingvistika a filozofie : deník. - 1994. - Sv. 17 , č. 3 . - str. 221-248 .
  2. ↑ Kowalski, RA Raná léta logického programování  (neopr.) .
  3. ↑ Colmerauer, A. Metamorphosis Gramatiky  (neurčité)  // Komunikace přirozeného jazyka s počítači. - 1978. - S. 133-189 .
  4. ↑ Pereira, F.; D. Warren. Určité větné gramatiky pro jazykovou analýzu  (neopr.) . — 1980.
  5. ↑ Pereira, FCN; D. H. D. Warren (1983). „Parsování jako dedukce“. Sborník příspěvků z 21. výroční schůze Asociace pro počítačovou lingvistiku . Association for Computational Linguistics Morristown, NJ, USA. str. 137-144. Použitý zastaralý parametr |coauthors=( nápověda )
  6. ↑ Pereira, FCN; S.M. Shieber. Prolog a analýza přirozeného jazyka  (neopr.) . — Microtome Publishing, 2002.
  7. ↑ Pereira, F. Extrapoziční gramatiky  (neurčité)  // Computational Linguistics. - 1981. - V. 7 , č. 4 . - S. 243-256 .
  8. ↑ Shimazu, H.; Y. Takashima. Multimodální gramatika s určitou klauzulí  (neopr.)  // Systémy a počítače v Japonsku. - 1995. - T. 26 , č. 3 .
  9. ↑ Abramson , H. Překladové gramatiky určitých vět  . — 1984.
  10. ↑ Sperberg-McQueen, CM Stručný úvod do gramatik s určitými větami a překladových gramatik s určitými větami . Získáno 21. dubna 2009. Archivováno z originálu 22. března 2012.
  11. ↑ Fleck, Arthur Překlad určité klauzule gramatiky . Získáno 16. dubna 2009. Archivováno z originálu 22. března 2012.
  12. ↑ Fisher, JR Výukový program Prolog -- 7.1 . Získáno 16. dubna 2009. Archivováno z originálu 22. března 2012.
  13. ↑ DCG nám poskytují přirozený zápis funkcí . Získáno 21. dubna 2009. Archivováno z originálu 22. března 2012.
  14. ↑ Mercury Tutorial: DCG notace . Získáno 21. dubna 2009. Archivováno z originálu 22. března 2012.

Další zdroje