Компиляторы, интерпретаторы… Сколько им посвещено книг и проектов! Баста, надоело!
А вот сунешся в область анализа естественных языков, и никакой информации! А все что есть как-то очень сложно, непонятно и не универсально.
Была у меня идея создать средневековую лингвистическую новеллу. Чтобы можно было разговаривать с персонажами на каком нибудь древнем естественном или вымышленном языке. На Латыни например? И на Квенья. И чтобы они понимали. А почему бы и нет?
Для этого всего то нужно:
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 (как по слову получить его характеристики)
Следовательно наш анализатор будет оперировать этими абстракциями.
Спецификация языка «Ололо».
В репозитории имеются сводки для языков Quenya (хорошо проработанная) и для Lingua Latina (самая малость). Но мы будем писать сводку для простого вымышленного инопланетного языка «Ололо». Найти можно там же. Открываем спецификацию etc/al/tpl:
0) Алфавит.
0.1) Глассные (a, o, u).
0.2) Согласные (l).
etc/al/tpl/verb.tpl.txt /* * It's time to introduce your experimental 'lol' language. * The 'lol' language has only two verb: 'ololoo' and 'olalaa'. * The infinitive coinsides to vocabular stem. * Present time of the verb forms by shorthening of the last vowel. * Past time forms by replacing of the first vowel 'o' to any other vowel. */
1) У нас есть два глагола (ololoo, olalaa).
1.1) Настоящее время образуется сокращением последней гласной (ololo, olala).
1.2) Прошедшее время образуется заменой начальной глассной на любую другую (ulolloo, alallaa).
etc/al/tpl/noun.tpl.txt /* * It's time to introduce your experimental 'lol' language. * The 'lol' language has only one noun: 'll'. * But there are small assumption: between two consonants can be places * arbitrary count of arbitrary vowels. */
2) У нас одно существительное (ll, lol, lool, luol, ...) без склонений.
etc/al/tpl/prep.tpl.txt /* * It's time to introduce your experimental 'lol' language. * The 'lol' language has only two preposition: 'ao' and 'oa'. * But there are small assumption: adjacent prepositions can be concatenated. */
3) У нас два предлога (ao, oa).
3.1) Смежные предлоги в тексте склеиваются (ao oa -> aooa).
etc/al/tpl/adj.tpl.txt /* * It's time to introduce your experimental 'lol' language. * The 'lol' language has only two adjective: 'lo' and 'ol'. * If adjective ends with consonant - it is consonant declension AD.C (ol). * If adjective ends with vowel - it is vowel declension AD.V (lo). * If adjective has not additional endings - it has singular number. * Plural number forms like this: * For AD.C by adding vowel 'a' * For AD.V by adding suffix 'la' * Superlative A.sup. and comparative A.cmp. are formed like this: * A.sup. by prefix 'al' * A.cmp. exists only for adjective starts with consonant and * forms by appending any short vowel (wildcard @ from 'etc.tpl.txt') * at the beggining of the word. * Superlative and comparative forms plural number on it's own manner. * Only adjectives ends with vowel can form plural A.sup. or A.cmp. by * appending the 'lolo' suffix to the end of the word. */
4) У нас два прилагательных (lo, ol) разных склонений.
4.1) Множественное число (lo -> lola, ol -> ola) соответственно.
4.2) Суперлатив (lo -> allo, ol -> alol).
4.3) Компаратив только для одного склонения (lo -> alo, ulo, olo).
4.4) Множественное число только для одного склонения (lo -> lololo).
Конкурс. Учимся поэзии инопланетян.
ll ololo — Простое предложение (1 грамматическая основа).
lol ulalaa oa lul olala allololo — Сложное предложение (2 грамматических основ).
Конкурс: придумайте начальный перевод приведенным словарным формам и напишите самое красивое и звучное восьмеростишье на языке «Ололо» (соблюдая все правила описанной выше грамматики). Предложение действует в течение 2х недель с момента публикации статьи.
Ответы пишите в комментариях и обязательно дублируйте на адрес apborezkiy@gmail.com, указывая тему «ACC #1».
Победитель будет объявлен в последующих статьях и получит бесплатную Skype консультацию на любую из тем в которых я могу быть чем-то полезен.
Разработка через тестирование.
Используя принцип TDD сначала подготовим тестовый материал для нашего анализатора.
var/test.tpl/test.in oa /* preposition */ aooaaooa /* concatenated preposition */ loool /* noun */ ll /* noun */ ololoo /* verb infinitive */ olalaa /* verb infinitive */ ulalaa /* verb past time */ uloloo /* verb past time */ ololo /* verb present time */ olala /* verb present time */ lo /* singular adjective vowel declension */ ol /* singular adjective consonant declension */ lola /* plural adjective vowel declension */ ola /* plural adjective consonant declension */ allo /* singular superlative adjective vowel declension */ alol /* singular superlative adjective consonant declension */ ulo /* singular comparative adjective vowel declension */ allololo /* plural superlative adjective vowel declension */ ulololo /* plural comparative adjective vowel declension */
Забегая вперед, скажу, что мы научим наш анализатор на выходе выдавать вот такой вот подробный анализ:
var/test.tpl/test.out
oa {
preposition { /* 1.4.1.1.1.1.1.100. */
pars_orationis = p. /* preposition */
{
mp_prep = oa /* voc_prepositions */
}
}
}
aooaaooa {
preposition { /* 1.4.1.1.1.2.1.2.1.1.2.1.2.1.1.2.1.2.1.1.1.1.100.100.100.100. */
pars_orationis = p. /* preposition */
{
mp_prep = oa /* voc_prepositions */
mp_prep = ao /* voc_prepositions */
mp_prep = oa /* voc_prepositions */
mp_prep = ao /* voc_prepositions */
}
}
}
loool {
noun { /* 1.2.1.1.1.2.1.2.2.1.2.1.1.3.1.1.2.100. */
pars_orationis = n. /* noun */
{
mn_stem = ll /* voc_nouns */
/* mn_vowel_left = ooo */
/* mn_vowel_left = o */
/* mn_vowel_left */
/* mn_vowel_right */
}
}
}
ll {
noun { /* 1.2.1.1.1.1.1.3.1.1.2.100. */
pars_orationis = n. /* noun */
{
mn_stem = ll /* voc_nouns */
/* mn_vowel_left */
/* mn_vowel_right */
}
}
}
ololoo {
verb { /* 1.3.1.1.1.1.1.2.100. */
pars_orationis = vb. /* verb */
mvb_time = V.inf. /* infinitive */
{
mvb_stem = ololoo /* voc_verbs */
/* mvb_time_past */
}
}
}
olalaa {
verb { /* 1.3.1.2.2.1.1.1.100. */
pars_orationis = vb. /* verb */
mvb_time = V.inf. /* infinitive */
{
mvb_stem = olalaa /* voc_verbs */
/* mvb_time_present */
}
}
}
ulalaa {
verb { /* 1.3.1.1.1.2.1.2.100. */
mvb_time = V.p. /* past time */
pars_orationis = vb. /* verb */
{
mvb_stem = olalaa /* voc_verbs */
/* mvb_time_past = o */
}
}
}
uloloo {
verb { /* 1.3.1.1.1.2.1.2.100. */
mvb_time = V.p. /* past time */
pars_orationis = vb. /* verb */
{
mvb_stem = ololoo /* voc_verbs */
/* mvb_time_past = o */
}
}
}
ololo {
verb { /* 1.3.1.2.2.2.1.1.100. */
mvb_time = V.pr. /* present time */
pars_orationis = vb. /* verb */
{
mvb_stem = ololoo /* voc_verbs */
/* mvb_time_present = oo */
}
}
}
olala {
verb { /* 1.3.1.2.2.2.1.1.100. */
mvb_time = V.pr. /* present time */
pars_orationis = vb. /* verb */
{
mvb_stem = olalaa /* voc_verbs */
/* mvb_time_present = aa */
}
}
}
lo {
adjective { /* 1.1.1.1.1.3.1.3.2.1.2.100. */
aa_number = A.sg. /* singular number */
pars_orationis = adj. /* adjective */
{
ma_stem = lo /* voc_adjectives */
/* ma_degree */
/* ma_number */
}
}
}
ol {
adjective { /* 1.1.1.1.1.3.1.3.1.1.2.100. */
aa_number = A.sg. /* singular number */
pars_orationis = adj. /* adjective */
{
ma_stem = ol /* voc_adjectives */
/* ma_degree */
/* ma_number */
}
}
}
lola {
adjective { /* 1.1.1.1.1.3.1.3.4.1.2.100. */
aa_degree = A.no. /* no special degree */
aa_number = A.pl. /* plural number */
pars_orationis = adj. /* adjective */
{
ma_stem = lo /* voc_adjectives */
/* ma_degree */
/* ma_number = la */
}
}
}
ola {
adjective { /* 1.1.1.1.1.3.1.3.3.1.2.100. */
aa_number = A.pl. /* plural number */
aa_degree = A.no. /* no special degree */
pars_orationis = adj. /* adjective */
{
ma_stem = ol /* voc_adjectives */
/* ma_degree */
/* ma_number = a */
}
}
}
allo {
adjective { /* 1.1.1.1.1.1.1.3.2.1.2.100. */
aa_number = A.sg. /* singular number */
pars_orationis = adj. /* adjective */
aa_degree = A.sup. /* superlative */
{
ma_stem = lo /* voc_adjectives */
/* ma_degree = al */
/* ma_number */
}
}
}
alol {
adjective { /* 1.1.1.1.1.1.1.3.1.1.2.100. */
aa_number = A.sg. /* singular number */
pars_orationis = adj. /* adjective */
aa_degree = A.sup. /* superlative */
{
ma_stem = ol /* voc_adjectives */
/* ma_degree = al */
/* ma_number */
}
}
}
ulo {
adjective { /* 1.1.1.1.1.2.1.3.2.1.2.100. */
aa_number = A.sg. /* singular number */
aa_degree = A.cmp. /* comparative */
pars_orationis = adj. /* adjective */
{
ma_stem = lo /* voc_adjectives */
/* ma_degree = ul */
/* ma_number */
}
}
}
allololo {
adjective { /* 1.1.1.1.1.1.1.3.5.1.2.100. */
aa_number = A.pl. /* plural number */
pars_orationis = adj. /* adjective */
aa_degree = A.sup. /* superlative */
{
ma_stem = lo /* voc_adjectives */
/* ma_degree = al */
/* ma_number = lolo */
}
}
}
ulololo {
adjective { /* 1.1.1.1.1.2.1.3.5.1.2.100. */
aa_degree = A.cmp. /* comparative */
aa_number = A.pl. /* plural number */
pars_orationis = adj. /* adjective */
{
ma_stem = lo /* voc_adjectives */
/* ma_degree = ul */
/* ma_number = lolo */
}
}
}
Числа означают цепочку правил (горизонтальных и вертикальных). По ней очень удобно отследить последовательность анализа.
Пишем нашу первую сводку.
Алфавит
Так что будет содержать язык описания сводок? Во-первых, алфавит в стиле ООП.
Зарезервированными лексемами являются:
1) .alphabet — Указывает на начало описания алфавита
2) .base — Указывает на родительский алфавит
3) = "" {}
etc/al/tpl/etc.tpl.txt
.alphabet short_vowel {
a = "vowel (a)"
o = "vowel (o)"
u = "vowel (u)"
}
.alphabet long_vowel {
aa = "long vowel (a)"
oo = "long vowel (o)"
}
.alphabet vowel .base short_vowel long_vowel { }
.alphabet consonant {
l = "consonant l"
}
.alphabet phoneme .base vowel consonant { }
Иерархия лингвистических сущностей
Во-вторых, описание сущностей (частей речи) и их аттрибутов.
Зарезервированными лексемами являются:
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
В следующем выпуске мы перейдем непосредственно к проектированию и кодированию нашего анализатора.
Автор: apborezkiy
