DC grammatik

Grammatik bygget på bestemte sætninger (abbr. DC grammatik , DCG ; fra engelsk.  Definite clause grammar ) er en måde at bygge grammatik på i logiske programmeringssprog, for eksempel Prolog . DC-grammatikken er normalt forbundet med Prolog, men andre sprog, såsom Mercury , kan også bruge DC-grammatikken. Udtrykket "visse sætninger" bruges i titlen, fordi denne grammatik er baseret på Horne -sætningen i førsteordens logik .

DCG-definitionen refererer til specifikke typer udtryk i Prolog og andre lignende sprog. Ikke alle måder at udtrykke en grammatik på ved hjælp af bestemte sætninger er dækket af DC-grammatikken. Alle funktioner og egenskaber i en DC-grammatik vil dog være nøjagtig de samme for enhver grammatik, der bruger bestemte sætninger på nøjagtig samme måde som Prolog.

For mere klart at forestille os, hvad DC-grammatikker er, kan vi lave følgende hypotetiske sammenligning: sættet af bestemte sætninger kan betragtes som et sæt af aksiomer, og korrektheden af ​​inputstrengen og eksistensen af ​​et parsetræ for det kan være betragtes som en sætning, hvis bevis er baseret på disse aksiomer [1] . Denne repræsentation har den fordel, at genkendelse og parsing af sprogudtryk bliver til bevis for udtryk, ligesom det gøres i logiske programmeringssprog.

Historie

DC-grammatikkens historie er tæt forbundet med Prologs historie, som igen blev skabt i Marseille (Frankrig) og Edinburgh (Skotland). Takket være Robert Kowalski , den første udvikler af Prolog-sproget, blev det første Prolog-system udviklet i 1972 af Alain Colmerauer og Philippe Roussel [2] . Det første program skrevet på sproget var et forsøg på at implementere et naturligt sprogbehandlingssystem. Også Fernando Pereira [F.Pereira] og David Warren [D.Warren] fra University of Edinburgh deltog i udviklingen af ​​Prolog.

Colmeroes tidligere arbejde var på et sprogbehandlingssystem kendt som Q-systemet, som blev brugt til at oversætte fra engelsk til fransk [3] . I 1978 skrev Colmeroe et papir om en måde at repræsentere grammatikker på kaldet metamorfosegrammatikker, som dannede grundlaget for den første version af Prolog, kaldet Marseilles Prolog. I denne artikel gav han en formel beskrivelse af metamorfe grammatikker og gav nogle eksempler, der demonstrerer deres anvendelse.

To andre Prolog-skabere, Fernando Pereira og David Warren, opfandt udtrykket "sætningsspecifik grammatik" og skabte DC-grammatikken, der bruges i Prolog den dag i dag. De satte pris på Kolmeroe og Kowalskis ideer og bemærkede, at DC-grammatikken er et specialtilfælde af Kolmerøs metamorfe grammatik. Denne idé blev introduceret i artiklen "Definite Clause Grammars for Language Analysis", som beskrev DC-grammatikken som "en formalisme ... hvor en grammatik er udtrykt ved sætninger af førsteordens prædikatlogik", som "tillader skabelsen af effektive programmer i Prolog-programmeringssproget" [4] .

Senere beskrev Pereira, Warren og andre Prolog-pionerer andre aspekter af DC-grammatikker. Pereira og Warren skrev papiret "Parsing as Deduction", der beskriver Earlys inferensbevisprocedure, der blev brugt til at analysere [5] . Pereira var også medforfatter til bogen Prolog and Natural Language Analysis med Stuart Scheiber, som var beregnet til at studere grundlaget for computerlingvistik ved hjælp af logisk programmering [6] .

Udvidelse

Der er blevet foreslået forbedringer for DC-grammatikkerne beskrevet af Pereira og Warren. For eksempel foreslog Pereira selv ekstrapositionelle grammatikker (ekstrapositionsgrammatikker, XG'er) [7] . Denne formalisme var nødvendig for at forenkle præsentationen af ​​et bemærkelsesværdigt grammatisk fænomen - ekstraposition. Pereira skrev: "Forskellen mellem reglerne for XG og DC-grammatik er, at venstre side af XG reglen kan bestå af flere tegn." Dette gør det lettere at udtrykke kontekstfølsomme grammatikker. XG kan dog omdannes til en DC grammatik, og DC grammatik kan i princippet alt hvad XG kan.

Meget senere, i 1995, udviklede forskere fra NEC Corporation en anden udvidelse kaldet Multi-Modal Definite Clause Grammars (MM-DCGs). Denne udvidelse var beregnet til at genkende og analysere udtryk, der ikke kun omfatter tekstdele, men også for eksempel billeder [8] .

I 1984 blev en anden udvidelse beskrevet kaldet oversættelses-DC-grammatikker (definite clause translation grammatics, DCTGs) [9] . DCTG-notationen ser næsten nøjagtigt ud som DC-grammatikken, bortset fra at notationen ::=i stedet for -->. Det blev opfundet for bekvemt at understøtte attributgrammatikker [10] . Oversættelsen af ​​DCTG til normale Prolog-sætninger er nøjagtig den samme som for DC-grammatikker, men tre argumenter tilføjes i stedet for to.

Eksempel

Et elementært eksempel på DC-grammatikker hjælper dig med at forstå, hvad sådanne grammatikker er i stand til, og hvad de er.

sætning --> navneord, verbum. navneord --> det, substantiv. udsagnsord --> udsagnsord, navneord. det --> [den]. det --> [a]. navneord --> [kat]. navneord --> [bat]. verbum --> [spiser].

Denne grammatik genererer applikationer som "katten spiser flagermusen", "en flagermus spiser katten". For at generere et korrekt sprogudtryk ved hjælp af denne grammatik skal du i Prolog-fortolkeren skrive: sentence(X,[]). Og for at teste, om en given sætning hører til et sprog, kan du skrive sentence([the,bat,eats,the,bat],[]).

Transformation til et sæt af bestemte sætninger

Notationen af ​​DC-grammatikker er syntaktisk sukker for det normale sæt af syntaktiske sætninger i Prolog. For eksempel kunne det foregående eksempel skrives som følger:

sætning(S1,S3) :- navneord(S1,S2), verbumsætning(S2,S3). navneord(S1,S3) :- det(S1,S2), navneord(S2,S3). verbum_frase(S1,S3) :- verbum(S1,S2), navneord(S2,S3). det([den|X],X). det([a|X],X). navneord([kat|X], X). navneord([bat|X], X). verbum([spiser|X], X).

Listeforskel

Argumenterne til hver funktion, for eksempel (S1,S3)og (S1,S2), er listeforskelle . En listeforskel er den måde en liste repræsenteres ved forskellen mellem to lister. Ved at bruge Prolog-notationen til en liste kan man skrive, at en liste Ler et par lister ([L|X],X).

Liste diff bruges til at repræsentere lister i DC grammatikker på grund af dens effektivitet. Det er mere praktisk at sammenkæde listeforskelle, hvor det er nødvendigt, fordi listesammenkædning (S1,S2)er (S2,S3)en liste (S1,S3). [elleve]

Kontekstfølsomme grammatikker

I Prolog undværer normale DC-regler ekstra argumenter i funktorer, som vist i det foregående eksempel. En sådan grammatik kan dog kun repræsentere kontekstfri grammatik, det vil sige med ét argument på venstre side. Kontekstfølsomme grammatikker kan dog også repræsenteres ved hjælp af en DC-grammatik ved at tilføje argumenter, som i følgende eksempel:

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

Dette sæt DC-grammatikregler beskriver en grammatik, der genererer strenge af formen , der repræsenterer . [12]

Præsentationsfunktioner

Også ved hjælp af DC-grammatikker kan forskellige sproglige træk ved sproget repræsenteres ganske kortfattet ved at tilføje yderligere argumenter til funktorer. [13] Overvej for eksempel følgende sæt DC-regler:

sætning --> pronomen(subjekt), verbumssætning. verb_frase --> verbum, pronomen(objekt). pronomen(emne) --> [han]. pronomen(subjekt) --> [hun]. pronomen(objekt) --> [ham]. pronomen(objekt) --> [hende]. verbum --> [synes godt om].

Denne grammatik genererer sætninger med formen "han kan lide hende" eller "han kan lide ham", men tillader ikke genereringen af ​​"hende kan lide han" eller "ham kan lide ham".

Parsing DC-grammatikker

Den vigtigste praktiske værdi ved at bruge DC-grammatikker er parsing af sætningerne i denne grammatik, det vil sige konstruktionen af ​​et parsetræ. Dette kan gøres ved at tilføje "ekstra argumenter" til funktionerne i DC-grammatikken, for eksempel, som det gøres i følgende eksempel:

sætning(s(NP,VP)) --> navneord(NP), verbumsætning(VP). substantiv_frase(np(D,N)) --> det(D), substantiv(N). verb_frase(vp(V,NP)) --> verbum(V), navneord(NP). det(d(den)) --> [den]. det(d(a)) --> [a]. substantiv(n(bat)) --> [flagermus]. navneord(n(kat)) --> [kat]. verb(v(spiser)) --> [spiser].

Nu, for enhver sætning, kan du få et parsetræ:

| ?- sætning(Parse_tree, [flagermusen,spiser,en,kat], []). Parse_tree = s(np(d(den),n(bat)),vp(v(spiser),np(d(a),n(kat))))? ;

Yderligere applikation

DC-grammatikker kan give yderligere syntaktisk sukker for at skjule parametre andre steder i koden, som ikke er relateret til applikationsparsing. For eksempel i programmeringssproget Mercury, som låner en del af Prologs syntaks, bruges DC-grammatikker til at skjule io__stateet argument i I/O-kode. [14] DC-grammatikker bruges også i andre situationer i Merkur.

Se også

Noter

  1. ↑ Johnson, M. To måder at formalisere grammatikker  //  Lingvistik og filosofi : journal. - 1994. - Bd. 17 , nr. 3 . - S. 221-248 .
  2. ↑ Kowalski, RA De tidlige år med logisk programmering  (neopr.) .
  3. ↑ Colmerauer, A. Metamorfosegrammatikker  (ubestemt)  // Naturlig sprogkommunikation med computere. - 1978. - S. 133-189 .
  4. ↑ Pereira, F.; D. Warren. Bestemte sætningsgrammatikker til  sproganalyse (neopr.) . - 1980.
  5. ↑ Pereira, FCN; D.H.D. Warren (1983). "Parsering som fradrag". Referat af 21. årsmøde om Foreningen for Datalingvistik . Association for Computational Linguistics Morristown, NJ, USA. pp. 137-144. Forældet parameter brugt |coauthors=( hjælp )
  6. ↑ Pereira, FCN; S.M. Shieber. Prolog og naturlig  sproganalyse (neopr.) . — Microtome Publishing, 2002.
  7. ↑ Pereira, F. Ekstrapositionsgrammatikker  (ubestemt)  // Computational Linguistics. - 1981. - V. 7 , nr. 4 . - S. 243-256 .
  8. ↑ Shimazu, H.; Y. Takashima. Multimodal bestemt klausul grammatik  (neopr.)  // Systemer og computere i Japan. - 1995. - T. 26 , nr. 3 .
  9. ↑ Abramson , H. Bestemte sætningsoversættelsesgrammatikker  . - 1984.
  10. ↑ Sperberg-McQueen, CM En kort introduktion til grammatikker for bestemte sætninger og definite sætningsoversættelsesgrammatikker . Hentet 21. april 2009. Arkiveret fra originalen 22. marts 2012.
  11. ↑ Fleck, Arthur Definite Clause Grammar Translation . Hentet 16. april 2009. Arkiveret fra originalen 22. marts 2012.
  12. ↑ Fisher, JR Prolog-vejledning -- 7.1 . Hentet 16. april 2009. Arkiveret fra originalen 22. marts 2012.
  13. ↑ DCG'er giver os en naturlig notation for funktioner . Hentet 21. april 2009. Arkiveret fra originalen 22. marts 2012.
  14. ↑ Mercury Tutorial: DCG-notation . Hentet 21. april 2009. Arkiveret fra originalen 22. marts 2012.

Yderligere kilder