Универсальный грамматический анализатор естественных языков с нуля. Выпуск 1
А вот сунешся в область анализа естественных языков, и никакой информации! А все что есть как-то очень сложно, непонятно и не универсально.
Была у меня идея создать средневековую лингвистическую новеллу. Чтобы можно было разговаривать с персонажами на каком нибудь древнем естественном или вымышленном языке. На Латыни например? И на Квенья. И чтобы они понимали. А почему бы и нет?
Для этого всего то нужно:
1) Разработать формат описания грамматики произволького языка.
2) Написать грамматики для Квенья и Латыни.
3) Разработать универсальный грамматический анализатор и синтаксический анализатор.
4) Сделать связь между поведением персонажений и синтаксическим анализатором.
Например, фраза «Леголас, подойди к дереву» интерпретировалась бы так:
Запускается скрипт глагола «идти», в качестве субьекта действия передается «Леголас» (поиском по тегу находим игровой объект),
указывается время (императив), что без дополнительных условий ожидания заставляет субьекта действия идти в позицию объекта действия.
В этом цикле статей мы займемся разработкой грамматического анализатора с нуля до полностью стабильной версии, уже находящейся на гитхабе (ссылка в конце статьи):
1) Спроектируем архитектуру анализатора
2) Разработаем язык описания сводкок грамматик (чтобы на нем могли писать обычные лингвисты)
3) Научим наш анализатор читать сводки
4) Научим анализатор на основе сводки грамматики анализировать текст
Код анализатора будет:
1) Качественный
2) Расширяемый
3) Легко поддерживаемый
4) Приятный для чтения
Анализатором можно будет пользоваться:
1) Из командной строки
2) Удаленно или локально, через RPC
Думаете будет нереально много кода?
Если бы мы писали это на С++ мы бы действительно мало что успели, но в следующем выпуске, по секрету, я расскажу вам об очень приятном, кратком и лаконичном языке, на котором написать такой проект можно за 2 месяца (по вечерам).
Итак, начнем!
Для начала подумаем, как вообще должен выглядеть язык описания сводок грамматик?
Следуя замечательным принципам SOLID мы полностью перейдем на абстракции.
Какие абстракции можно выделить в лингвистике? Я выделил целый 'лист':
L) Алфавит L (множество символов)
E) Сущность E (глагол, существительное и т.д.)
A) Атрибуты A (время, наклонение и т.д.)
F) Правило сопоставления F (как по слову получить его характеристики)
Иерархия лингвистических сущностей
Во-вторых, описание сущностей (частей речи) и их аттрибутов.
Зарезервированными лексемами являются:
1) .attribute — Указывает на начало описания атрибута.
2) .class — Указывает на начало описание сущности.
3) = » {}
etc/al/tpl/lang.tpl.txt
.attribute pars_orationis 0 {
n. = "noun"
adj. = "adjective"
vb. = "verb"
p. = "preposition"
}
etc/al/tpl/verb.tpl.txt
.attribute mvb_time 1 {
V.inf. = "infinitive"
V.pr. = "present time"
V.p. = "past time"
}
.class verb {
pars_orationis
mvb_time
}
etc/al/tpl/noun.tpl.txt
.class noun {
pars_orationis
}
etc/al/tpl/prep.tpl.txt
.class preposition {
pars_orationis
}
etc/al/tpl/adj.tpl.txt
.attribute aa_declension 1 .verbose {
AD.C = "consonant declension"
AD.V = "vovel declension"
}
.attribute aa_number 2 {
A.sg. = "singular number"
A.pl. = "plural number"
}
.attribute aa_degree 3 {
A.no. = "no special degree"
A.sup. = "superlative"
A.cmp. = "comparative"
}
.class adjective {
pars_orationis
aa_declension
aa_number
aa_degree
}
Цифра после имени атрибута будет обозначать порядок вывода атрибута в выходном файле (для наглядности).
Словарь
Пора ввести словарик:
etc/al/tpl/voc.tpl.txt
.vocabulary voc_adjectives {
lo adj. AD.V
ol adj. AD.C
}
.vocabulary voc_nouns {
ll n.
}
.vocabulary voc_prepositions {
ao p.
oa p.
}
.vocabulary voc_verbs {
ololoo vb.
olalaa vb.
}
Зарезервированными лексемами являются:
1) .vocabulary — Указывает на начало описания словаря.
2) {}
Здесь каждой словарной записи сопоставляется сущность и набор атрибутов. Помните нашу волшебную формулу?
Подстановочные знаки
Еще нужно ввести подстановочные символы (алиасы), которые будут использоваться в мутациях и правилах сопоставления.
etc/al/tpl/etc.tpl.txt
.wildcard . phoneme
.wildcard * vowel
.wildcard # consonant
.wildcard @ short_vowel
Здесь мы задаем подстановочные знаки для наших алфавитов, которые мы описали выше.
Теперь нам нужно описать преобразования (мутации), возникающие в словах.
etc/al/tpl/etc.tpl.txt
.mutation longify_vowel {
a = aa
o = oo
}
.mutation change_vowel_to_o {
* = o
}
Зарезервированными лексемами являются:
1) .mutation — Указывает на начало описания преобразования.
2) {}
3) =
Слева в мутациях можно записывать как символы алфавита, так и подстановочные знаки.
Ну, а теперь сами подстановочные знаки для наших мутаций:
etc/al/tpl/etc.tpl.txt
.wildcard (a>aa,o>oo) longify_vowel
.wildcard (*>o) change_vowel_to_o
Правила сопоставления
Осталось самое сложное. Правила сопоставления. Идея похожая на словарь, но вместо словарных форм используется маска с подстановочными символами и символами алфавита.
Правила сопоставления существительных.
etc/al/tpl/voc.tpl.txt
.vocabular .inward mn_stem voc_nouns
.match .forward mn_vowel_left {
=##
=#+* mn_vowel_left
}
.match .backward mn_vowel_right {
=##
mn_vowel_right +*=#
}
.match .inward-void m_noun {
mn_vowel_left mn_stem mn_vowel_right | n. noun
}
Зарезервированными лексемами являются:
1) .match — Указывает на начало описания правила сопоставления.
2) .backward — Маска начинает сопоставляться с конца слова (удобно для суффиксов и окончаний).
2) .forward — Маска начинает сопоставляться с начала слова (удобно для префиксов).
3) .inward-void — Сначала с конца, потом сначала, и так до словарной основы.
4) | — После вертикальной черты начинаются соответствующие характеристики слова, подходящего под маску.
5) {}
6) + — =
Слева указывается маска слова, справа — аттрибуты или сущность, которой соответствует данная маска. Маска состоит из последовательности правил, которые могут быть либо самостоятельным правилом, либо комбинацией подстановочных символов с символами алфавита и со специальными знаками »+»,»-»,»=».
Напишем спецификацию правил сопоставления:
etc/al/tpl/adj.tpl.txt
/*
* Match specification is the powerful easy mechanism for words recognision.
* Each regular match expression has 3 mode:
*
* '=' match mode:
* only comparation.
* '+' rift mode:
* comparation and rifting from subword copy,
* appending detached part to rule 'value' field that could be
* found in the output generated files.
* '-' hold mode (comparation and holding)
* comparation and holding (not detaching),
* appending holded part to rule 'value' field that could be
* found in the output generated files.
*
* Also regular expressions supports negotiation of the single next character
* or wildcard (wildcard can has arbitrary name length) through the preceding
* reserved symbol '~'.
*
* Examples: /* meaning */
* =~a /* not 'a' */
* =~ab /* not 'a' followed by 'b' */
* =~a~b /* not 'a' followed by not 'b' */
* =~# /* not any phoneme from wildcard '#' consistent alphabet tree */
*/
Разбираем правила сопоставления существительных
Теперь как это все работает. На примере существительных.
.match .inward-void m_noun {
mn_vowel_left mn_stem mn_vowel_right | n. noun
}
Сначала c конца рассматривается правило «m_noun», которое сразу переходит в рассмотрение правила сопоставления «с конца» — «mn_vowel_right», которое выглядит так:
.match .backward mn_vowel_right {
=##
mn_vowel_right +*=#
}
Проверяется первая маска »=##». Вначале стоит указатель на банальный режим посимвольного сравнения »=». За ней два наших вышеописанных подстановочных символа »#», означающих две согласных. Значит, в конце слова должно быть два согласных, на этом правило заканчивается.
Рассмотрим альтернативный вариант развития событий «mn_vowel_right +*=#». Это правило рекурсивное. Оно означает что в конце стоит согласная. После этого перед этой согласной мы должны отщепить одну гласную и записать ее как результат этого правила. И делать так до тех пор пока не наткнемся на единственно возможный вариант »=##». Т.е. все глассные которые мы удалим будут результатом «mn_vowel_right», что мы должны увидеть в результатах анализа.
Поэтапно правило «mn_vowel_right». Возьмем к примеру слово «loolool».
Остаток слова | Шаблон сопоставления | Результат |
loolool | # в режиме сравнения | |
loolol | * в режиме отщепления | o |
loolol | # в режиме сравнения | o |
looll | * в режиме отщепления | oo |
looll | ## в режиме сравнения | oo |
К концу мы получили «looll». Оно и пойдет дальше в «mn_vowel_left». Аналогично к концу мы получим «lll». Оно и пойдет дальше в «mn_stem» и будет искаться в словаре.
Поскольку в словаре такого слова нет, эта цепочка правил сочтется неподходящей. А вот если бы мы взяли «looool», мы бы получили нашу словарную форму существительного «ll».
C существительным разобрались. Фууух. Вы еще не устали? Чуток отдохнем и пора браться за глагол.
Разбираем правила сопоставления глагола
etc/al/tpl/verb.tpl.txt
.vocabulary voc_verbs ; /* preemptive declaration, see 'voc.tpl.txt' */
.vocabular .inward mvb_stem voc_verbs
.match .backward mvb_time_present { /* e.g. */
=. | V.inf. /* '.' is any phoneme ('etc.tpl.txt') */ /* 1 */
-(a>aa,o>oo) | V.pr. /* ololo -> ololoo, olala -> olalaa */ /* 2 */
}
.match .forward mvb_time_past { /* e.g. */
=. | V.inf. /* '.' is any phoneme ('etc.tpl.txt') */ /* 1 */
=~o-(*>o) | V.p. /* eloloo -> ololoo, ulalaa -> olalaa */ /* 2 */
}
.match .inward-void m_verb {
mvb_time_past mvb_stem | vb. verb /* 1 */
mvb_stem mvb_time_present | vb. verb /* 2 */
}
Здесь намного интереснее, мы используем вышеописанные мутации для восстановления последствий фузий. Впервые используется режим удержания »-», который вместо отщепления »+» сохраняет символ на месте как »=», но записывает его в результат правила как »+».
Поехали с начала. Возьмем слово «ulolloo». Проанализируем на правила прошедшего и настоящего времен.
Правило «mvb_time_past».
Остаток слова | Шаблон сопоставления | Результат |
ulolloo | ||
ololloo | (*>o) в режиме удержания | u |
ololloo | не «o» в режиме сравнения | u |
Анализатором рассматриваются всевозможные цепочки событий, но если встречаются противоречивые характеристики, например V.inf. и V.p. то подобный вариант развития событий прекращается как невозможный.
Правило «mvb_time_present». Возьмем слово «olollo».
Остаток слова | Шаблон сопоставления | Результат |
olollo | ||
ololloo | (a>aa, o>oo) в режиме удержания | o |
Разбираем правила сопоставления прилагательных
Тильда перед характеристикой отрицает ее.»~ A.no.» значит в будущем допускается либо A.sup., либо A.cmp., либо ничего.
.match .backward ma_number { /* e.g. */
=# | A.sg. AD.C /* al -> al */
=* | A.sg. AD.V /* lo -> lo */
=#+a | A.pl. AD.C A.no. /* ola -> ol */
=*+la | A.pl. AD.V A.no. /* lola -> lo */
=*+lolo | A.pl. AD.V ~ A.no. /* allololo -> allo */
}
.match .forward ma_degree { /* e.g. */
+al | A.sup. /* allo -> lo, alol -> ol */
+@-# | A.cmp. /* ulo -> lo */
=. | ~ A.sup. ~ A.cmp. /* '.' is any phoneme wildcard ('etc.tpl.txt') */
}
.match .inward-void m_adjective {
ma_degree ma_stem ma_number | adj. adjective
}
Возьмем слово allololo. Рассмотрим более крупными шагами.
Исходное слово | Правило | Подходящий шаблон сопоставления | Результат | Остаток слова |
allololo | ma_number | »=*» либо »=*+lolo» | нет либо «lolo» | allololo либо allo |
allololo, allo | ma_degree | »+al» либо »+@-#» либо »=.» | «al» либо «al» либо нет | lololo, lo либо llololo, llo либо allololo, allo |
lololo, lo либо llololo, llo либо allololo, allo | ma_stem | словарь | нет | нет |
Подходит только lo. Таким образом, мы получили единственно подходящую цепочку сопоставлений характеристик: «A.pl. AD.V ~ A.no. A.sup. adj. adjective». Следовательно, слово allololo однозначно представляет собой «plural superlative adjective vowel declension».
Если будет интересно, для языка описания грамматик мы посветим отдельный цикл статей. А пока, пока!
Универсальный грамматический анализатор доступен по адресу:
github.com/ArseniyBorezkiy/arda_compiler_collection
В следующем выпуске мы перейдем непосредственно к проектированию и кодированию нашего анализатора.
Комментарии (2)
11 марта 2017 в 20:39
0↑
↓
Мега круто, а яндексовский tomita parser это не то же самое?
11 марта 2017 в 20:39
0↑
↓
tech.yandex.ru/tomita