Граматика визначених тверджень

Історія граматик визначених тверджень тісно пов’язана з історією Прологу, а історія Прологу обертається навколо кількох дослідників у Марселі (Франція) та Единбурзі (Шотландія). Згідно з Робертом Ковальським, початковим розробником Прологу, першу прологову систему було розроблено у 1972 році Аланом Кольмерое та Філіпом Русселем.[2] Першою програмою, написаною цією мовою, була велика система обробки природної мови. До початкової розробки Прологу були також залучені Фернандо Перейра та Девід Воррен з Единбурзького університету.

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

Фернандо Перейра та Девід Воррен, двоє інших ранніх творців Прологу, створили термін «граматика визначених тверджень», і запис для них, що використовується в Пролозі й сьогодні. Вони віддали належне ідеї Кольмерое та Ковальського, і відзначили, що граматики визначених тверджень є окремим випадком метаморфозних граматик Кольмерое. Вони представили цю ідею у статті під назвою «Граматики визначених тверджень для мовного аналізу» (англ. «Definite Clause Grammars for Language Analysis»), де вони описали граматики визначених тверджень як «формалізм ... у якому граматики виражаються твердженнями логіки предикатів першого порядку», що «утворюють ефективні програми мови програмування Пролог».[4]

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

Простий приклад граматик визначених тверджень для ілюстрації того, чим вони є, і як вони виглядають.

речення --> група_іменника, група_присудка.
група_іменника --> означення, іменник.
група_присудка --> дієслово, група_іменника.
означення --> [the].
означення --> [a].
іменник --> [cat].
іменник --> [bat].
дієслово --> [eats].

Ця граматика створює такі речення, як "the cat eats the bat", "a bat eats the cat". Можна згенерувати всі коректні речення мови, що генеруються цією граматикою, ввівши в інтерпретаторі Прологу речення(X,[]). Аналогічно, можна перевірити, чи є якесь речення коректним у цій мові, ввівши щось на кшталт речення([the,bat,eats,the,bat],[]).

Запис граматик визначених тверджень є лише синтаксичним цукром для звичайних визначених тверджень Прологу. Наприклад, попередній приклад можна перекласти так:

речення(S1,S3) :- група_іменника(S1,S2), група_присудка(S2,S3).
група_іменника(S1,S3) :- означення(S1,S2), іменник(S2,S3).
група_присудка(S1,S3) :- дієслово(S1,S2), група_іменника(S2,S3).
означення([the|X], X).
означення([a|X], X).
іменник([cat|X], X).
іменник([bat|X], X).
дієслово([eats|X], X).

У чистій Пролог звичайні правила граматик визначених тверджень без додаткових аргументів на функторах, як у попередньому прикладі, можуть виражати лише контекстно-вільні граматики; у лівій частині продукції є лише один аргумент. Однак, контекстно-залежні граматики також можуть виражатися граматиками визначених тверджень шляхом надання додаткових аргументів, як у наступному прикладі:

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}.

Цей набір правил граматики визначених тверджень описує граматику, що генерує мову, що складається зі стрічок вигляду ${\displaystyle 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).

Цей набір правил граматики визначених тверджень описує граматику, що генерує мову, що складається зі стрічок вигляду ${\displaystyle a^{n}b^{n}c^{n}}$, представляючи ${\displaystyle n}$ структурно.^{[джерело?]}

Деякі лінгвістичні словозміни також можуть досить чітко представлятися граматиками визначених тверджень шляхом додавання додаткових аргументів до функторів.[9] Наприклад, розгляньмо наступний набір правил граматики визначених тверджень:

речення --> іменник(називний_відмінок), група_присудка.
група_присудка --> дієслово, іменник(знахідний_відмінок).
іменник(називний_відмінок) --> [кіт].
іменник(називний_відмінок) --> [кажан].
іменник(знахідний_відмінок) --> [кота].
іменник(знахідний_відмінок) --> [кажана].
дієслово --> [їсть].

Ця граматика дозволяє такі речення як «кіт їсть кажана» та «кіт їсть кота», але не «кажана їсть кіт» та «кота їсть кота».

Приклад дерева синтаксичного аналізу для цієї граматики.

Головним практичним застосуванням граматик визначених тверджень є синтаксичний аналіз виразів заданої граматики, тобто, побудова дерева синтаксичного розбору. Це може бути реалізовано за допомогою застосування «додаткових аргументів» у функторах граматики визначених тверджень, як у наступних правилах:

речення(s(NP,VP)) --> група_іменника(NP), група_присудка(VP).
група_іменника(np(D,N)) --> означення(D), іменник(N).
група_присудка(vp(V,NP)) --> дієслово(V), група_іменника(NP).
означення(d(the)) --> [the].
означення(d(a)) --> [a].
іменник(n(bat)) --> [bat].
іменник(n(cat)) --> [cat].
дієслово(v(eats)) --> [eats].

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

| ?- речення(Синтаксичне_дерево, [the,bat,eats,a,cat], []).
Синтаксичне_дерево = s(np(d(the),n(bat)),vp(v(eats),np(d(a),n(cat)))) ? ;

Граматики визначених тверджень можуть слугувати синтаксичним цукром для приховування деяких параметрів у коді і в інших застосуваннях, крім синтаксичного аналізу. В декларативно чистій мові програмування Mercury введення/виведення мусить представлятися парою аргументів io.state. Запис граматик визначених тверджень може застосовуватися для того, щоби робити використання введення/виведення зручнішим,[10] хоча зазвичай віддають перевагу записові зі змінними стану.^{[джерело?]} Запис граматик визначених тверджень застосовується в Mercury для синтаксичного аналізу та подібних речей так само, як і в Пролозі.

З тих пір, як Перейра та Воррен представили граматики визначених тверджень, було запропоновано декілька розширень. Сам Перейра запропонував розширення, назване екстрапозиційними граматиками (англ. extraposition grammars, XGs).[11] Цю формальну систему було представлено, зокрема, для спрощення вираження певних граматичних феноменів, таких як ліва екстрапозиція. Перейра писав, що «Різниця між правилами екстрапозиційних граматик та правилами граматик визначених тверджень тоді в тому, що ліва частина правила екстрапозиційної граматики може містити кілька символів.» Це спрощує вираження правил контекстно-залежних граматик.

Інше, новіше розширення, що зробили дослідники з корпорації NEC у 1995 році, було названо мультимодальними граматиками визначених тверджень (англ. Multi-Modal Definite Clause Grammars, MM-DCGs). Їхнє розширення призначалося для уможливлення розпізнавання та синтаксичного аналізу виразів, що містять не текстові частини, наприклад, зображення.[12]

У 1984 році було описано інше розширення, назване трансляційними граматиками визначених тверджень (англ. definite clause translation grammars, DCTGs).[13] Запис трансляційних граматик визначених тверджень дуже схожий на запис граматик визначених тверджень; основна відмінність полягає у використанні в правилах ::= замість -->. Його було розроблено для зручності маніпулювання граматичними атрибутами.[14] Перетворення трансляційних граматик визначених тверджень у звичайні твердження Прологу схоже на перетворення граматик визначених тверджень, але додається 3 аргументи замість 2.

• Обробка природної мови
• Граматика з фразовою структурою
• Ієрархія Чомскі
• Контекстно-вільна граматика

• Обробка природної мови за допомогою Прологу (англ.)
• Контекстно-вільні граматики та граматики визначених тверджень (англ.)
• Definite Clause Grammars for Language Analysis (англ.)