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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Грама́тика ви́значених ре́чень (англ. Definite Clause Grammar (DCG), рос. DC-грамматика) — це спосіб представлення граматики природних або формальних мов у логічних мовах програмування, таких як Пролог. Він тісно пов’язаний з концепцією атрибутних граматик (англ.) / афіксних граматик (англ.), з якої Пролог і було спочатку розроблено. Граматики визначених речень зазвичай асоціюються із Прологом, але їх також включають і схожі мови, такі як Mercury (англ.). Вони називаються граматиками визначених речень, оскільки представляють граматику множиною визначених речень (англ.) у логіці першого порядку.

Термін «граматики визначених речень» відноситься до певного типу виразу в Пролозі та інших подібних мовах; не всі способи вираження граматик з використанням визначених речень вважаються граматиками визначених речень. Тим не менш, всі можливості та властивості граматик визначених речень будуть однаковими для будь-якої граматики, що представлена визначеними реченнями, так само по суті, як і в Пролозі.

Визначені речення таких граматик можуть розглядатися як набір аксіом, де справедливість вхідної стрічки, а також факт того, що вона має певне дерево синтаксичного аналізу, можуть розглядатися як теореми, що випливають з цих аксіом.[1] Це має таку перевагу, що розпізнавання та аналіз виразів у мові перетворюється на доведення речень, таких як речення логічної мови програмування.

Зміст

Історія [ред.]

Історія граматик визначених речень тісно пов’язана з історією Прологу, а історія Прологу обертається навколо кількох дослідників у Марселі (Франція) та Единбурзі (Шотландія). Згідно Роберта Ковальського (англ.), початкового розробника Прологу, першу прологову систему було розроблено у 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]

Розширення [ред.]

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

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

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

Приклад [ред.]

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

речення --> група_іменника, група_присудка.
група_іменника --> означення, іменник.
група_присудка --> дієслово, група_іменника.
означення --> [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).

Списки відмінностей [ред.]

Аргументи кожного функтора, такі як (S1,S3) та (S1,S2), є списками відмінностей; списки відмінностей є способом представлення списку як різниці двох списків. Використовуючи запис Прологу для списків, список L можна представити парою ([L|X],X).

Списки відмінностей використовуються для представлення списків у граматиках визначених речень з міркувань ефективності. Ефективніше конкатенувати списки відмінностей, в умовах, в яких вони можуть застосовуватися, оскільки конкатенацією (S1,S2) та (S2,S3) є просто (S1,S3).[11]

Не-контекстно-вільні граматики [ред.]

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

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

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

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

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

Представлення словозмін [ред.]

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

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

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

Синтаксичний аналіз із граматиками визначених речень [ред.]

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

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

речення(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 у коді введення-виведення.[14] Вони також застосовуються і в інших подібних ситуаціях у Mercury.

Див. також [ред.]

Примітки [ред.]

  1. ↑ Johnson M. Two ways of formalizing grammars // Linguistics and Philosophy. — Т. 17. — (1994) (3) С. 221–240. DOI:10.1007/BF00985036.
  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.; 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.
  6. ↑ Pereira, F. C. N.; S. M. Shieber (2002). Prolog and natural-language analysis. Microtome Publishing. 
  7. ↑ Pereira F. Extraposition grammars // Computational Linguistics. — Т. 7. — (1981) (4) С. 243–256.
  8. ↑ Shimazu H., Y. Takashima Multimodal definite clause grammar // Systems and Computers in Japan. — Т. 26. — (1995) (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». Процитовано 2009-04-21. 
  11. ↑ Fleck, Arthur. «Definite Clause Grammar Translation». Процитовано 2009-04-16. 
  12. ↑ Fisher, J. R. «Prolog Tutorial -- 7.1». Процитовано 2012-09-24. 
  13. ↑ «DCGs give us a Natural Notation for Features». Процитовано 2009-04-21. 
  14. ↑ «Mercury Tutorial: DCG Notation». Процитовано 2009-04-21. 

Посилання [ред.]

Отримано з http://uk.wikipedia.org/w/index.php?title=Граматика_визначених_речень&oldid=12356257