DC-грамматика

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Грамматика, построенная на определённых предложениях (сокр. DC-грамматика, DCG; от англ. Definite clause grammar) — это способ построения грамматики в логических языках программирования, например, Пролог. DC-грамматика обычно ассоциируется с Прологом, но и другие языки, например, Mercury, также могут использовать DC-грамматику. Словосочетание «определенные предложения» используется в название потому, что эта грамматика основывается на дизъюнкте Хорна в логике первого порядка.

Определение DCG ссылается на специфичные типы выражений в Пролог и других подобных ему языках. Не все способы выражения грамматики, использующие определённые предложения, рассматриваются с помощью DC-грамматики. Однако, все возможности и свойства DC-грамматики будут точно такими же для любой грамматики, которая использует определённые предложения точно так же, как и Пролог.

Чтобы яснее представить себе, что же такое DC-грамматики, можно провести следующее гипотетическое сопоставление: множество определённых предложений можно рассмотреть как множество аксиом, а корректность входной строки и существование для неё дерева разбора — как теорему, доказательство которой строится на этих аксиомах [1]. Такое представление имеет преимущество, так как распознавание и разбор выражений языка превращается в доказательство выражений, точно так же как это делается в логических языках программирования.

История[править | править вики-текст]

История DC-грамматик тесно связана с историей Пролога, которая в свою очередь создавалась в Марселе (Франция) и Эдинбурге (Шотландия). Благодаря Роберту Ковальски, первому разработчику языка Пролог, первая Пролог система была разработана в 1972 году Алэном Колмероэ и Филлипом Роусселом[2]. Первая программа, написанная на языке, была попыткой реализации системы обработки естественного языка. Также в разработке Пролога принимали участие Фернандо Переиро и Девид Уоррен из университета Эдинбурга.

Предыдущая работа Колмероэ была посвящена системе обработки языка, известной под названием Q-система, которая использовалась для перевода с английского на французский [3]. В 1978 Колмероэ написал статью о способе представления грамматик, которые назывались метаморфозными грамматики (metamorphosis grammars) и которые лежали в основе первой версии Пролога, называемого марсельским Прологом. В этой статье он дал формальное описание метаморфозным грамматикам и привел некоторые примеры, демонстрирующие их применение.

Два других создателя Пролога, Фернандо Перейра и Давид Уоррен, придумали термин грамматика с определёнными предложениями и создали ту нотацию DC-грамматик, которая используется в Прологе по сей день. Они оценили идеи Колмероэ и Ковальски и заметили, что DC-грамматика — это частный случай метаморфозных грамматик Колмероэ. Эта идея была представлена в статье «Definite Clause Grammars for Language Analysis» (DC-грамматики для языкового анализа), в которой описывалась DC-грамматика, как «формализм … в котором грамматика выражается предложениями предикатной логики первого порядка», что «позволяет создавать эффективные программы на языке программирования Пролог»[4].

Позже Перейра, Уоррен и другие пионеры Пролога описали другие аспекты DC-грамматик. Перейра и Уоррен написали статью «Parsing as Deduction» (Разбор с помощью логического вывода), описывающую процедуру доказательства логического вывода Эрли, использующаяся для разбора[5]. Также Перейра в соавторстве со Стюартом Шейбером написал книгу «Prolog and Natural Language Analysis» (Пролог и анализ естественных языков), которая была предназначена для изучения основ вычислительной лингвистики с использованием логического программирования[6].

Расширение[править | править вики-текст]

Для DC-грамматик, описанных Перейрой и Уорреном, были предложены улучшения. Например, сам Перейра предложил экстрапозиционные грамматики (extraposition grammars, XGs)[7]. Этот формализм был необходим для того, чтобы упростить представление примечательного грамматического феномена — экстрапозиции. Перейра писал : «Различие между правилами XG и DC-грамматики заключается в том, что левая часть XG правила может состоять из нескольких символов.» Это делает её проще для выражения контекстно-зависимых грамматик. Однако, XG может быть трансформирована в DC-грамматику, а DC-грамматика, в принципе, может все, что умеет XG.

Значительно позднее в 1995 году исследователями из NEC корпорации было разработано другое расширение, называемое — многомодальной DC-грамматикой (Multi-Modal Definite Clause Grammars, MM-DCGs). Их расширение предназначалось для того, чтобы распознавать и разбирать выражения, которые включают в себя не только текстовые части, но и, например, картинки[8].

В 1984 году было описано другое расширение, называемое DC-грамматиками трансляции (definite clause translation grammars, DCTGs)[9]. DCTG нотация выглядит практически точно также, как и нотация DC-грамматики, за исключением того, что в правилах использовалась запись ::= вместо -->. Она была придумана для удобной поддержки атрибутных грамматик[10]. Перевод DCTG в нормальные предложения Пролога точно такое же, как и при DC-грамматиках, но добавляется три аргумента вместо двух.

Пример[править | править вики-текст]

Элементарный пример DC-грамматик поможет понять на что способны такие грамматики и что они из себя представляют.

sentence --> noun_phrase, verb_phrase. 
noun_phrase --> det, noun. 
verb_phrase --> verb, noun_phrase. 
det --> [the]. 
det --> [a]. 
noun --> [cat]. 
noun --> [bat]. 
verb --> [eats]. 

Эта грамматика порождает приложения вида «the cat eats the bat», «a bat eats the cat». Для того чтобы породить корректное выражение языка при помощи этой грамматики в интерпретаторе Пролога необходимо набрать: sentence(X,[]). А для того, чтобы протестировать, принадлежит ли данное предложение языку, можно набрать sentence([the,bat,eats,the,bat],[]).

Трансформация в множество определённых предложений[править | править вики-текст]

Нотация DC-грамматик представляет собой синтаксический сахар для нормального множества синтаксических предложений в Прологе. Например, предыдущий пример может быть записан следующим образом:

sentence(S1,S3) :- noun_phrase(S1,S2), verb_phrase(S2,S3). 
noun_phrase(S1,S3) :- det(S1,S2), noun(S2,S3). 
verb_phrase(S1,S3) :- verb(S1,S2), noun_phrase(S2,S3). 
det([the|X], X). 
det([a|X], X). 
noun([cat|X], X). 
noun([bat|X], X). 
verb([eats|X], X). 

Разница списков[править | править вики-текст]

Аргументы для каждого функтора, например, (S1,S3) и (S1,S2), представляют собой разницу списков. Разницей списков является способ представления списка с помощью разницы двух списков. Используя нотацию Пролога для списка, можно записать, что список L является парой списков ([L|X],X).

Разница списков используется для представления списков в DC-грамматиках по причине своей эффективности. Более удобно производить конкатенацию разницы списков там, где это необходимо, потому что конкатенацией списков (S1,S2) и (S2,S3) является списком (S1,S3).[11]

Контекстно-зависимые грамматики[править | править вики-текст]

В Прологе нормальные DC правила обходятся без дополнительных аргументов в функторах, как это было продемонстрировано в предыдущем примере. Однако, такая грамматика может представлять только контекстно-свободные грамматики, то есть с одним аргументом в левой части. Однако контекстно-зависимые грамматики также могут быть представлены с помощью DC-грамматики при помощи добавления аргументов так, как это сделано в следующем примере:

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

Это множество правил DC-грамматики описывает грамматику, которая порождает строки следующей формы a^{n}b^{n}c^{n}, структурно представляя n.[12]

Особенности представления[править | править вики-текст]

Также с помощью DC-грамматик могут быть довольно лаконично представлены различные лингвистические особенности языка путем добавления дополнительных аргументов функторам.[13] Для примера рассмотрим следующее множество DC правил:

sentence --> pronoun(subject), verb_phrase. 
verb_phrase --> verb, pronoun(object). 
pronoun(subject) --> [he]. 
pronoun(subject) --> [she]. 
pronoun(object) --> [him]. 
pronoun(object) --> [her]. 
verb --> [likes]. 

Такая грамматика порождает предложения вида «he likes her» или «he likes him», но не позволяет порождать «her likes he» или «him likes him».

Разбор DC-грамматик[править | править вики-текст]

Пример дерева разбора для этой грамматики.

Главная практическая ценность использования DC-грамматик — это разбор предложений данной грамматики, то есть построение дерева разбора. Это может быть сделано при помощи добавления «дополнительных аргументов» в функторы DC-грамматики, например, так, как это сделано в следующем примере:

sentence(s(NP,VP)) --> noun_phrase(NP), verb_phrase(VP). 
noun_phrase(np(D,N)) --> det(D), noun(N). 
verb_phrase(vp(V,NP)) --> verb(V), noun_phrase(NP). 
det(d(the)) --> [the]. 
det(d(a)) --> [a]. 
noun(n(bat)) --> [bat]. 
noun(n(cat)) --> [cat]. 
verb(v(eats)) --> [eats]. 

Теперь для любого предложения можно получить дерево разбора:

| ?- sentence(Parse_tree, [the,bat,eats,a,cat], []). 
Parse_tree = s(np(d(the),n(bat)),vp(v(eats),np(d(a),n(cat)))) ? ; 

Дополнительное применение[править | править вики-текст]

DC-грамматики могут предоставлять дополнительный синтаксический сахар для сокрытия параметров в других местах кода, которые не связаны с разбором приложений. Например, в языке программирования Mercury, который частично заимствует синтаксис Пролога, DC-грамматики используются для того, чтобы скрыть io__state аргумент в коде ввода-вывода.[14] Также DC-грамматики используются и в других ситуациях в Mercury.

См. также[править | править вики-текст]

Замечания[править | править вики-текст]

  1. Johnson, M. (1994). «Two ways of formalizing grammars». Linguistics and Philosophy 17 (3): 221–248.
  2. Kowalski, R. A.. «The early years of logic programming».
  3. Colmerauer, A. (1978). «Metamorphosis grammars». Natural Language Communication with Computers: 133–189.
  4. Pereira, F.; D. Warren (1980). «Definite clause grammars for language analysis».
  5. Pereira, F. C. N.; D. H. D. Warren (1983). "Parsing as deduction". Proceedings of the 21st annual meeting on Association for Computational Linguistics: 137–144, Association for Computational Linguistics Morristown, NJ, USA. 
  6. Pereira F. C. N. Prolog and natural-language analysis. — Microtome Publishing.
  7. Pereira, F. (1981). «Extraposition grammars». Computational Linguistics 7 (4): 243–256.
  8. Shimazu, H.; Y. Takashima (1995). «Multimodal definite clause grammar». Systems and Computers in Japan 26 (3).
  9. Abramson, H. (1984). «Definite clause translation grammars».
  10. Sperberg-McQueen, C. M. A brief introduction to definite clause grammars and definite clause translation grammars. Проверено 21 апреля 2009. Архивировано из первоисточника 22 марта 2012.
  11. Fleck, Arthur Definite Clause Grammar Translation. Проверено 16 апреля 2009. Архивировано из первоисточника 22 марта 2012.
  12. Fisher, J. R. Prolog Tutorial -- 7.1. Проверено 16 апреля 2009. Архивировано из первоисточника 22 марта 2012.
  13. DCGs give us a Natural Notation for Features. Проверено 21 апреля 2009. Архивировано из первоисточника 22 марта 2012.
  14. Mercury Tutorial: DCG Notation. Проверено 21 апреля 2009. Архивировано из первоисточника 22 марта 2012.

Дополнительные источники[править | править вики-текст]