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

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

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

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

История править

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

Предыдущая работа Колмероэ была посвящена системе обработки языка, известной под названием 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.

См. также править

Замечания править

↑ Johnson, M. Two ways of formalizing grammars (англ.) // Linguistics and Philosophy (англ.) (рус. : journal. — 1994. — Vol. 17, no. 3. — P. 221—248.
↑ Kowalski, R. A. The early years of logic programming (неопр.).
↑ Colmerauer, A. Metamorphosis grammars (неопр.) // Natural Language Communication with Computers. — 1978. — С. 133—189.
↑ Pereira, F.; D. Warren. Definite clause grammars for language analysis (неопр.). — 1980.
↑ Pereira, F. C. N. (1983). "Parsing as deduction". Proceedings of the 21st annual meeting on Association for Computational Linguistics. Association for Computational Linguistics Morristown, NJ, USA. pp. 137—144. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка)
↑ Pereira, F. C. N.; S. M. Shieber. Prolog and natural-language analysis (неопр.). — Microtome Publishing, 2002.
↑ Pereira, F. Extraposition grammars (неопр.) // Computational Linguistics. — 1981. — Т. 7, № 4. — С. 243—256.
↑ Shimazu, H.; Y. Takashima. Multimodal definite clause grammar (неопр.) // Systems and Computers in Japan. — 1995. — Т. 26, № 3.
↑ Abramson, H. Definite clause translation grammars (неопр.). — 1984.
↑ Sperberg-McQueen, C. M. A brief introduction to definite clause grammars and definite clause translation grammars (неопр.). Дата обращения: 21 апреля 2009. Архивировано 22 марта 2012 года.
↑ Fleck, Arthur Definite Clause Grammar Translation (неопр.). Дата обращения: 16 апреля 2009. Архивировано 22 марта 2012 года.
↑ Fisher, J. R. Prolog Tutorial -- 7.1 (неопр.). Дата обращения: 16 апреля 2009. Архивировано 22 марта 2012 года.
↑ DCGs give us a Natural Notation for Features (неопр.). Дата обращения: 21 апреля 2009. Архивировано 22 марта 2012 года.
↑ Mercury Tutorial: DCG Notation (неопр.). Дата обращения: 21 апреля 2009. Архивировано 22 марта 2012 года.

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

Definite Clause Grammars (Amzi.com) (недоступная ссылка с 13-05-2013 [3987 дней] — история)
NLP with Prolog
Context-free grammars and DCGs
Definite Clause Grammars: Not Just for Parsing Anymore
Декларативное программирование. История.
DCG (Definite Clause Grammars) — грамматики определяющих предложений
[1] Ляхов А. В., Кучер В. А. Методы использования интуиционистского исчисления высказываний

[1] Johnson, M. Two ways of formalizing grammars (англ.) // Linguistics and Philosophy (англ.) (рус. : journal. — 1994. — Vol. 17, no. 3. — P. 221—248.

[2] Kowalski, R. A. The early years of logic programming (неопр.).

[3] Colmerauer, A. Metamorphosis grammars (неопр.) // Natural Language Communication with Computers. — 1978. — С. 133—189.

[4] Pereira, F.; D. Warren. Definite clause grammars for language analysis (неопр.). — 1980.

[5] Pereira, F. C. N. (1983). "Parsing as deduction". Proceedings of the 21st annual meeting on Association for Computational Linguistics. Association for Computational Linguistics Morristown, NJ, USA. pp. 137—144. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка)

[6] Pereira, F. C. N.; S. M. Shieber. Prolog and natural-language analysis (неопр.). — Microtome Publishing, 2002.

[7] Pereira, F. Extraposition grammars (неопр.) // Computational Linguistics. — 1981. — Т. 7, № 4. — С. 243—256.

[8] Shimazu, H.; Y. Takashima. Multimodal definite clause grammar (неопр.) // Systems and Computers in Japan. — 1995. — Т. 26, № 3.

[9] Abramson, H. Definite clause translation grammars (неопр.). — 1984.

[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 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]