Определенная грамматика предложения

Грамматика с определенным предложением ( DCG ) — это способ выражения грамматики, как для естественных , так и для формальных языков, на языке логического программирования, таком как Пролог . Оно тесно связано с концепцией атрибутивных грамматик / аффиксных грамматик . DCG обычно ассоциируются с Прологом, но подобные языки, такие как Mercury, также включают DCG. Они называются грамматиками определенных предложений, потому что представляют грамматику как набор определенных предложений в логике первого порядка .

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

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

История

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

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

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

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

Пример

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

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

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

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

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

 sentence(A,Z) :- noun_phrase(A,B), verb_phrase(B,Z).
 noun_phrase(A,Z) :- det(A,B), noun(B,Z).
 verb_phrase(A,Z) :- verb(A,B), noun_phrase(B,Z).
 det([the|X], X).
 det([a|X], X).
 noun([cat|X], X).
 noun([bat|X], X).
 verb([eats|X], X).

Списки различий

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

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

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

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

A = P + B = P + (Q + Z) = (P + Q) + Z = S + Z = A

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

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

 s --> a(N), b(N), c(N).
 a(0) --> [].
 a(M) --> [a], a(N), {M is N + 1}.
 b(0) --> [].
 b(M) --> [b], b(N), {M is N + 1}.
 c(0) --> [].
 c(M) --> [c], c(N), {M is N + 1}.

Этот набор правил DCG описывает грамматику, которая генерирует язык, состоящий из строк вида $a^{n}b^{n}c^{n}$ . ^[8]

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

Этот набор правил DCG описывает грамматику, которая генерирует язык, состоящий из строк вида $a^{n}b^{n}c^{n}$ , структурно представляя $n$ ^{[ нужна ссылка ]}

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

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

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

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

Разбор с помощью DCG

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

 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)))) ? ;

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

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

Расширения

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

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

Еще одно, более свежее, расширение было сделано исследователями из корпорации NEC в 1995 году под названием «Мультимодальные грамматики с определенными предложениями» (MM-DCG). Их расширения были предназначены для того, чтобы позволить распознавать и анализировать выражения, которые включают нетекстовые части, такие как изображения. ^[15]

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

См. также

Примечания

^ Джонсон, М. (1994). «Два способа формализации грамматик». Языкознание и философия . 17 (3): 221–240. дои : 10.1007/BF00985036 . S2CID 62165766 .
^ Ковальски, Роберт А. (январь 1988 г.). «Ранние годы логического программирования» (PDF) . Коммуникации АКМ . 31 (1): 38–43. дои : 10.1145/35043.35046 . S2CID 12259230 .
^ Кольмерауэр, А. (1978). «Метаморфозы грамматики». Общение на естественном языке с компьютерами . Конспекты лекций по информатике. Том. 63. стр. 133–189. дои : 10.1007/BFb0031371 . ISBN 3-540-08911-Х .
^ Перейра, Фернандо CN; Уоррен, Дэвид HD (1980). «Грамматики определенных предложений для языкового анализа — обзор формализма и сравнение с расширенными сетями переходов» (PDF) . Искусственный интеллект . 13 (3): 231–278. дои : 10.1016/0004-3702(80)90003-X .
^ Перейра, ФКН; ДХД Уоррен (1983). «Разбор как дедукция» (PDF) . Материалы 21-го ежегодного собрания Ассоциации компьютерной лингвистики . Ассоциация компьютерной лингвистики Морристаун, Нью-Джерси, США. стр. 137–144.
^ Перейра, ФКН; С.М. Шибер (2002). Пролог и анализ естественного языка . Издательство Микротом. ISBN 9780971977709 .
^ Флек, Артур. «Перевод грамматики определенного предложения» . Проверено 16 апреля 2009 г.
^ Фишер, Дж.Р. «Учебное пособие по Прологу — 7.1» . Проверено 17 мая 2016 г.
^ «DCG дают нам естественное обозначение функций» . Проверено 21 апреля 2009 г.
^ «Руководство по переходу от Prolog к Mercury: ввод/вывод» . Проверено 26 марта 2015 г.
^ «Справочное руководство Mercury Language: правила DCG» . www.mercurylang.org . Проверено 7 апреля 2023 г.
^ Перейра, Ф. (1981). «Экстрапозиционные грамматики» (PDF) . Компьютерная лингвистика . 7 (4): 243–256.
^ Ван Рой, Питер (1990). «Расширенная нотация DCG: инструмент для аппликативного программирования на Прологе» . Технический отчет UCB . 90 (583).
^ Исходный код доступен по адресу [1] .
^ Симадзу, Х.; Ю. Такашима (1995). «Мультимодальная грамматика определенного предложения» (PDF) . Системы и компьютеры в Японии . 26 (3): 93–102. дои : 10.1002/scj.4690260309 . S2CID 8199913 .
^ Абрамсон, Х. (апрель 1984 г.). Грамматики перевода определенных предложений (PDF) (Технический отчет). 84-3.
^ Сперберг-МакКуин, CM «Краткое введение в грамматики определенного предложения и грамматики перевода определенного предложения» . Проверено 21 апреля 2009 г.

Внешние ссылки

[1] Джонсон, М. (1994). «Два способа формализации грамматик». Языкознание и философия . 17 (3): 221–240. дои : 10.1007/BF00985036 . S2CID 62165766 .

[2] Ковальски, Роберт А. (январь 1988 г.). «Ранние годы логического программирования» (PDF) . Коммуникации АКМ . 31 (1): 38–43. дои : 10.1145/35043.35046 . S2CID 12259230 .

[3] Кольмерауэр, А. (1978). «Метаморфозы грамматики». Общение на естественном языке с компьютерами . Конспекты лекций по информатике. Том. 63. стр. 133–189. дои : 10.1007/BFb0031371 . ISBN 3-540-08911-Х .

[4] Перейра, Фернандо CN; Уоррен, Дэвид HD (1980). «Грамматики определенных предложений для языкового анализа — обзор формализма и сравнение с расширенными сетями переходов» (PDF) . Искусственный интеллект . 13 (3): 231–278. дои : 10.1016/0004-3702(80)90003-X .

[5] Перейра, ФКН; ДХД Уоррен (1983). «Разбор как дедукция» (PDF) . Материалы 21-го ежегодного собрания Ассоциации компьютерной лингвистики . Ассоциация компьютерной лингвистики Морристаун, Нью-Джерси, США. стр. 137–144.

[6] Перейра, ФКН; С.М. Шибер (2002). Пролог и анализ естественного языка . Издательство Микротом. ISBN 9780971977709 .

[7] Флек, Артур. «Перевод грамматики определенного предложения» . Проверено 16 апреля 2009 г.

[8] Фишер, Дж.Р. «Учебное пособие по Прологу — 7.1» . Проверено 17 мая 2016 г.

[9] «DCG дают нам естественное обозначение функций» . Проверено 21 апреля 2009 г.

[10] «Руководство по переходу от Prolog к Mercury: ввод/вывод» . Проверено 26 марта 2015 г.

[11] «Справочное руководство Mercury Language: правила DCG» . www.mercurylang.org . Проверено 7 апреля 2023 г.

[12] Перейра, Ф. (1981). «Экстрапозиционные грамматики» (PDF) . Компьютерная лингвистика . 7 (4): 243–256.

[13] Ван Рой, Питер (1990). «Расширенная нотация DCG: инструмент для аппликативного программирования на Прологе» . Технический отчет UCB . 90 (583).

[14] Исходный код доступен по адресу [1] .

[15] Симадзу, Х.; Ю. Такашима (1995). «Мультимодальная грамматика определенного предложения» (PDF) . Системы и компьютеры в Японии . 26 (3): 93–102. дои : 10.1002/scj.4690260309 . S2CID 8199913 .

[16] Абрамсон, Х. (апрель 1984 г.). Грамматики перевода определенных предложений (PDF) (Технический отчет). 84-3.

[17] Сперберг-МакКуин, CM «Краткое введение в грамматики определенного предложения и грамматики перевода определенного предложения» . Проверено 21 апреля 2009 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

v т и Алгоритмы разбора
Сверху вниз	Эрли LL Рекурсивный спуск Хвостовая рекурсия
Вверх дном	Приоритет Простой Оператор Маневровый двор ЛР Простой смотреть вперед Канонический Обобщенный ГАЛОЧКА Рекурсивное восхождение Shift-уменьшить
Смешанное, другое	Комбинатор Диаграмма Левый угол Статистический
Связанные темы	ПЭГ Определенная грамматика предложения Детерминированный анализ Динамическое программирование Мемоизация Генератор парсера ЛАЛР Дерево разбора АСТ Бессканерный парсинг История создания компилятора Сравнение генераторов парсеров Грамматика приоритета операторов