- 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-грамматики описывает грамматику, которая порождает строки следующей формы , структурно представляя .[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. (1994). «Two ways of formalizing grammars». Linguistics and Philosophy 17 (3): 221–248.
- ↑ Kowalski, R. A.. «The early years of logic programming».
- ↑ Colmerauer, A. (1978). «Metamorphosis grammars». Natural Language Communication with Computers: 133–189.
- ↑ Pereira, F.; D. Warren (1980). «Definite clause grammars for language analysis».
- ↑ 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.
- ↑ Pereira F. C. N. Prolog and natural-language analysis. — Microtome Publishing.
- ↑ Pereira, F. (1981). «Extraposition grammars». Computational Linguistics 7 (4): 243–256.
- ↑ Shimazu, H.; Y. Takashima (1995). «Multimodal definite clause grammar». Systems and Computers in Japan 26 (3).
- ↑ Abramson, H. (1984). «Definite clause translation grammars».
- ↑ Sperberg-McQueen, C. M. A brief introduction to definite clause grammars and definite clause translation grammars. Архивировано из первоисточника 22 марта 2012. Проверено 21 апреля 2009.
- ↑ Fleck, Arthur Definite Clause Grammar Translation. Архивировано из первоисточника 22 марта 2012. Проверено 16 апреля 2009.
- ↑ Fisher, J. R. Prolog Tutorial -- 7.1. Архивировано из первоисточника 22 марта 2012. Проверено 16 апреля 2009.
- ↑ DCGs give us a Natural Notation for Features. Архивировано из первоисточника 22 марта 2012. Проверено 21 апреля 2009.
- ↑ Mercury Tutorial: DCG Notation. Архивировано из первоисточника 22 марта 2012. Проверено 21 апреля 2009.
Дополнительные источники
- Definite Clause Grammars (Amzi.com)
- NLP with Prolog
- Context-free grammars and DCGs
- Definite Clause Grammars: Not Just for Parsing Anymore
- Декларативное программирование. История.
- DCG (Definite Clause Grammars) — грамматики определяющих предложений
- [1] Ляхов А. В., Кучер В. А. Методы использования интуиционистского исчисления высказываний
Категория:- Формальные языки
Wikimedia Foundation. 2010.