Грамматика с определенным предложением - Definite clause grammar

А грамматика определенных предложений (DCG) является способом выражения грамматики, либо для естественный или формальный языков, на языке логического программирования, например Пролог. Это тесно связано с концепцией грамматики атрибутов / аффиксные грамматики из которого изначально был разработан Prolog. DCG обычно связаны с Prolog, но подобные языки, такие как Меркурий также включают DCG. Их называют грамматиками с определенными предложениями, потому что они представляют грамматику как набор определенные статьи в логика первого порядка.

Термин DCG относится к определенному типу выражения в Прологе и других подобных языках; не все способы выражения грамматики с использованием определенных предложений считаются DCG. Однако все возможности или свойства DCG будут одинаковыми для любой грамматики, которая представлена ​​определенными предложениями, по сути, так же, как в Прологе.

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

История

История DCG тесно связана с историей Пролога, а история Пролога вращается вокруг нескольких исследователей как из Марселя, Франция, так и Эдинбурга, Шотландия. Согласно с Роберт Ковальски, один из первых разработчиков Prolog, первая система Prolog была разработана в 1972 г. Ален Колмерауэр и Филипп Руссель.[2] Первая программа, написанная на этом языке, была большой системой обработки естественного языка. Фернандо Перейра и Дэвид Уоррен в Эдинбургском университете также участвовали в ранней разработке Prolog.

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

Фернандо Перейра и Дэвид Уоррен, два других ранних архитектора Пролога, придумали термин «грамматика с определенными предложениями» и создали нотацию для DCG, которая используется в Прологе сегодня. Они признали идею Колмерауэра и Ковальски и отмечают, что DCG являются частным случаем метаморфозных грамматик Колмерауэра. Они представили эту идею в статье под названием «Грамматики с определенными предложениями для анализа языка», где они описывают DCG как «формализм ... в котором грамматики выражаются предложениями логики предикатов первого порядка», которые «составляют эффективные программы языка программирования. Пролог ».[4]

Перейра, Уоррен и другие пионеры Пролога позже писали о некоторых других аспектах DCG. Перейра и Уоррен написали статью под названием «Разбор как дедукция», описывая такие вещи, как использование процедуры доказательства дедукции Эрли для синтаксического анализа.[5] Перейра также сотрудничал с Стюарт М. Шибер о книге "Пролог и анализ естественного языка", которая была задумана как общее введение в компьютерная лингвистика с использованием логического программирования.[6]

пример

Базовый пример DCG помогает проиллюстрировать, что они из себя представляют и как выглядят.

 приговор --> словосочетание, фразовый глагол. словосочетание --> Det, имя существительное. фразовый глагол --> глагол, словосочетание. Det --> [то]. Det --> [а]. имя существительное --> [Кот]. имя существительное --> [летучая мышь]. глагол --> [ест].

Это порождает такие предложения, как «кошка ест летучую мышь», «летучая мышь ест кошку». Можно сгенерировать все допустимые выражения на языке, сгенерированные этой грамматикой, в интерпретаторе Пролога, набрав предложение (X, []). Точно так же можно проверить, действительно ли предложение на языке, набрав что-то вроде предложение ([the, bat, ест, the, bat], []).

Перевод на определенные предложения

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

 приговор(А,Z) :- словосочетание(А,B), фразовый глагол(B,Z). словосочетание(А,Z) :- Det(А,B), имя существительное(B,Z). фразовый глагол(А,Z) :- глагол(А,B), словосочетание(B,Z). Det([то|Икс], Икс). Det([а|Икс], Икс). имя существительное([Кот|Икс], Икс). имя существительное([летучая мышь|Икс], Икс). глагол([ест|Икс], Икс).

Списки отличий

Аргументы каждого функтора, например (А, Б) и (B, Z) находятся списки различий; Списки различий - это способ представления префикса списка как разницы между двумя его суффиксами (больший, включая меньший). Используя нотацию Пролога для списков, префикс одноэлементного списка P = [H] можно рассматривать как разницу между [H | X] и Икс, и, таким образом, представлена ​​парой ([H | X], X), например.

Говоря это п разница между А и B это то же самое, что сказать, что добавить (P, B, A) держит. Или в случае предыдущего примера добавить ([H], X, [H | X]).

Списки различий используются для представления списков с DCG по соображениям эффективности. Гораздо эффективнее объединять различия списков (префиксы) в тех случаях, когда их можно использовать, потому что объединение (А, Б) и (B, Z) просто (А, Я).[7]

Действительно, добавить (P, B, A), добавить (Q, Z, B) влечет за собой добавить (P, Q, S), добавить (S, Z, A). Это то же самое, что сказать, что объединение списков ассоциативный:

А = П + В = П + (Q + Z) = (P + Q) + Z = S + Z = A

Неконтекстно-свободные грамматики

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

 s --> а(N), б(N), c(N). а(0) --> []. а(M) --> [а], а(N), {M является N + 1}. б(0) --> []. б(M) --> [б], б(N), {M является N + 1}. c(0) --> []. c(M) --> [c], c(N), {M является N + 1}.

Этот набор правил DCG описывает грамматику, которая генерирует язык, состоящий из строк в форме .[8]

 s --> символы(Сем,а), символы(Сем,б), символы(Сем,c). символы(конец,_) --> []. символы(s(Сем),S) --> [S], символы(Сем,S).

Этот набор правил DCG описывает грамматику, которая генерирует язык, состоящий из строк в форме , структурно представляя п[нужна цитата ]

Представление функций

Различные лингвистические Особенности также можно довольно кратко представить с помощью DCG путем предоставления дополнительных аргументов функторам.[9] Например, рассмотрим следующий набор правил DCG:

 приговор --> местоимение(предмет), фразовый глагол. фразовый глагол --> глагол, местоимение(объект). местоимение(предмет) --> [он]. местоимение(предмет) --> [она]. местоимение(объект) --> [ему]. местоимение(объект) --> [ее]. глагол --> [нравится].

Эта грамматика допускает такие предложения, как "он любит ее" и "он любит его", но нет «она любит он» и «он любит его».

Разбор с DCG

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

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

 приговор(s(НП,Вице-президент)) --> словосочетание(НП), фразовый глагол(Вице-президент). словосочетание(нп(D,N)) --> Det(D), имя существительное(N). фразовый глагол(вице-президент(V,НП)) --> глагол(V), словосочетание(НП). Det(d(то)) --> [то]. Det(d(а)) --> [а]. имя существительное(п(летучая мышь)) --> [летучая мышь]. имя существительное(п(Кот)) --> [Кот]. глагол(v(ест)) --> [ест].

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

 | ?- приговор(Parse_tree, [то,летучая мышь,ест,а,Кот], []). Parse_tree = s(нп(d(то),п(летучая мышь)),вице-президент(v(ест),нп(d(а),п(Кот)))) ? ;

Другое использование

DCG могут служить удобным синтаксическим сахаром для сокрытия определенных параметров в коде в других местах, помимо приложений для синтаксического анализа. В декларативно чистом языке программирования. Меркурий Ввод / вывод должен быть представлен парой io.state Аргументы. Обозначение.DCG может использоваться для более удобного использования ввода-вывода,[10] хотя обычно предпочтительнее обозначение переменных состояния.[нужна цитата ]Нотация DCG также используется для синтаксического анализа и подобных вещей в Mercury, как и в Prolog.

Расширения

С тех пор, как DCG были введены Перейрой и Уорреном, было предложено несколько расширений. Сам Перейра предложил расширение, называемое грамматиками экстрапозиций (XG).[11] Этот формализм был отчасти предназначен для облегчения выражения определенных грамматических явлений, таких как левое экстрапозиционирование. Перейра утверждает: «Разница между правилами XG и правилами DCG состоит в том, что левая часть правила XG может содержать несколько символов». Это упрощает формулирование правил для контекстно-зависимых грамматик.

Питер Ван Рой расширил DCG, допустив несколько аккумуляторов.[12][13]

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

Другое расширение, называемое грамматиками перевода определенных предложений (DCTG), было описано в 1984 году.[15] Нотация DCTG очень похожа на нотацию DCG; основное отличие в том, что используется ::= вместо того --> в правилах. Он был разработан для удобной обработки грамматических атрибутов.[16] Преобразование DCTG в обычные предложения Prolog аналогично преобразованию DCG, но добавляются 3 аргумента вместо 2.

Смотрите также

Примечания

  1. ^ Джонсон, М. (1994). «Два способа формализации грамматики». Лингвистика и философия. 17 (3): 221–240. Дои:10.1007 / BF00985036.
  2. ^ Ковальский, Р.А. «Первые годы логического программирования» (PDF). Цитировать журнал требует | журнал = (Помогите)
  3. ^ Колмерауэр, А. (1978). «Метаморфозы грамматики». Общение на естественном языке с компьютером: 133–189.
  4. ^ Pereira, F .; Д. Уоррен (1980). «Грамматики с определенными предложениями для анализа языка» (PDF). Цитировать журнал требует | журнал = (Помогите)
  5. ^ Pereira, F.C.N .; Д. Х. Д. Уоррен (1983). "Разбор как вычет" (PDF). Труды 21-го ежегодного собрания Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики Морристаун, Нью-Джерси, США. С. 137–144.
  6. ^ Pereira, F.C.N .; С. М. Шибер (2002). Пролог и анализ естественного языка. Издательство "Микротом".
  7. ^ Флек, Артур. "Грамматический перевод с определенным предложением". Получено 2009-04-16.
  8. ^ Фишер, Дж. Р. "Учебное пособие по Prolog - 7.1". Получено 2016-05-17.
  9. ^ «DCG дают нам естественную нотацию для функций». Получено 2009-04-21.
  10. ^ «Пролог к ​​Руководству по переходу на Меркурий: ввод / вывод». Получено 2015-03-26.
  11. ^ Перейра, Ф. (1981). «Экстрапозиционные грамматики» (PDF). Компьютерная лингвистика. 7 (4): 243–256.
  12. ^ Ван Рой, Питер (1990). «Расширенная нотация DCG: инструмент для прикладного программирования на прологе». Технический отчет UCB. 90 (583).
  13. ^ Исходный код доступен по адресу [1].
  14. ^ Shimazu, H .; Ю. Такашима (1995). «Мультимодальная грамматика с определенными предложениями» (PDF). Системы и компьютеры в Японии. 26 (3).
  15. ^ Абрамсон, Х. (1984). "Грамматики перевода определенных предложений". Цитировать журнал требует | журнал = (Помогите)
  16. ^ Сперберг-Маккуин, К. "Краткое введение в грамматики определенных предложений и грамматики перевода определенных предложений". Получено 2009-04-21.

внешняя ссылка