Алгоритмы / [Из песочницы] Как я создавал синтаксический анализатор

в 18:57, , рубрики: алгоритм, грамматика, синтаксический анализ, метки: , ,

Однажды, сидя на кухне со своим ноутбуком, я думал: что бы такое написать. В голову ничего не шло, и я вспомнил свою поделку — синонимайзер. Он был всем хорош — использовал морфологию, умел склонять и спрягать, работал с n-граммами. Но не было в нем одной интересной фичи — перефразирования текста, позволяющего, к примеру, фразу “корова паслась на лугу” переделать в “пятнистая буренка жевала сочную траву на зеленом лугу”. Конечно же, подобного рода преобразования требуют очень большую базу связей между словами и выражениями, отсутствие которой и свело на нет всю работу. Но это уже другая история. Сейчас же я расскажу о том, как решал вопрос синтаксического анализа предложений, которые затем должны были преобразоваться во что-то новое, но такое же человекочитаемое.
Википедия определяет синтаксический анализ следующим образом: “синтакси́ческий ана́лиз (па́рсинг) — это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом. Синтаксический анализатор (парсер) — это программа или часть программы, выполняющая синтаксический анализ.”
Для успешного преобразования текста необходимо разбить его на абзацы, а те, в свою очередь, на строки. Это делалось внутренними средствами морфологического движка Solarix, купленного мной для синонимайзера еще в 2008 году. На выходе разделителя получался массив абзацев, каждый из которых содержал массив строк.
На всякий случай хочу отметить: в этой статье я намеренно не указываю язык программирования, так как, во-первых, хочу избежать холивара на тему ЯП, и, во-вторых, здесь будет идти речь о методе разбора строки, а не о конкретном способе реализации этого разбора. Кроме того, по некоторым причинам я не мог использовать встроенный в Solarix синтаксический анализатор, из-за чего и пришлось городить собственный огород.
Программа-обработчик представляет собой многопроходный анализатор, который может обрабатывать не только отдельные слова, но и целые предложения, используя контекст предложений и абзацев, и используя его при возникновении трудностей с омонимией или в случае неполных или непонятных предложений.
Разбиение на абзацы позволяет выделить основную мысль данного абзаца (если она, конечно, есть), создавая тем самым контекст. Формально контекстом параграфа можно считать все пары подлежащих и сказуемых, встречающихся во всех предложениях данного абзаца. В случае односоставных предложений используется только один состав предложения. Если его, конечно же, удается найти.
Вся основная работа производится на уровне предложений. Алгоритм анализа предложения достаточно прост и может быть описан в виде состояний конечного автомата. К сожалению, даже несмотря на наличие знаний по созданию конечных автоматов, опыта создания таких автоматов у меня нет. Поэтому было решено сделать все старым дедовским способом, используя процедурный подход. Тем более, что руки чесались очень сильно и я уже даже примерно знал, что и как буду делать. Теперь я знаю, что это было неправильно, так как уже спустя несколько часов я увяз в дебрях грамматики русского языка и потратил на ее изучение достаточно много времени. Хотя не факт, что потратив еще неделю на создание конечного автомата, я достиг бы лучшего результата.
Итак, я изучал грамматику русского языка, параллельно строя свой анализатор. В основе анализатора лежало несколько аксиом, основанных на базовых принципах построения фраз в русском языке:
— в предложении может быть ноль или более подлежащих;
— несколько подлежащих, идущих подряд и стоящих в одном и том же падеже образуют составное подлежащее;
— простое подлежащее связано со сказуемым в единственном числе, а составное подлежащее — со сказуемым, имеющим множественное число;
— сказуемое может быть как простым, так и сложным;
— сложное сказуемое состоит из двух и более сказуемых, имеющих одно и то же число и время;
— второстепенные члены предложения (обстоятельства, определения, дополнения и приложения) определяются на основании их расположения относительно главных членов предложения, а также соответствующих им морфологических признаков, таких как род, число и время.
Вначале обрабатывались самые простые предложения: “мама мыла раму”, “кот и собака сидят на полу”, “кошка пила молоко”. Эти предложения не представляют никакой сложности, так как содержат достаточно мало комбинаций морфологических признаков. К примеру, “мама мыла раму” разбирается очень легко: в данном случае подлежащим может быть только имя существительное в именительном падеже (мама). Сказуемым является глагол “мыла”, связанное с подлежащим по роду и числу. Третье слово — дополнение, так как оно отвечает на вопрос косвенного падежа (что?).
Внимательный читатель может спросить: а как же насчет третьего предложения о пьющей молоко кошке, в котором есть два существительных, стоящих в именительном падеже, и одно из которых может быть глаголом? В данном случае мы имеем дело с омонимией, и решается она достаточно просто: для слова, имеющего признаки и существительного, и глагола мы должны найти существительное, связанное с глаголом по роду и числу, или только по числу в случае составного подлежащего или простого подлежащего во множественном числе. Кроме того, в случае наличия уточнения, выраженного косвенным или вопросительным местоимением (который?, что?), омонимия снимается еще проще — такие слова-омонимы автоматически считаются подлежащими подчиненного предложения: “кошка, которая пила молоко, хотела спать” => “кошка ( хотела ( спать ), пила ( которая ) молоко ) ”. Таким образом мы получаем два набора “подлежащее-сказуемое”: “кошка пила” и “кошка хотела”, а само предложение считается сложным.
Дальнейшая доработка анализатора не представляет особой сложности: мы ищем все второстепенные члены предложения, основываясь на их положении и связи морфологических признаков относительно уже найденных членов предложения.
Кстати, для облегчения разбора предложения перед самим разбором нужно производить упрощение предложений, привязывая наречия (хорошо, быстро, легко) к глаголам, деепричастиям или прилагательным, рядом с которыми они стоят, при необходимости связывая эти наречия в цепочки в случае, когда они связаны запятыми или союзами (и, или, но не).
В случае, если анализ конкретного предложения вызывает затруднение, оно помечается, как проблемное, и его анализ откладывается на второй проход анализатора, когда контекст параграфа уже более-менее определен. При этом, используя этот контекст, можно с достаточно большой долей уверенности определить проблемные части речи в проблемном предложении и добавить его контекст в контекст параграфа.
К сожалению, синтаксический анализатор завершен не был, хоть я и смог реализовать разбор достаточно экзотических предложений, как простых, так и сложных. Также я не стал создавать базу связей слов и словосочетаний. Это произошло как из-за потери интереса к проекту (надеюсь, я его однажды возобновлю), так и из-за недостатка времени, связанного с параллельной работой в нескольких коммерческих проектах, из-за чего свободного времени, которое я мог бы потратить на хобби, практически не осталось.


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js