Регулярные выражения + логическое программирование. Что в результате?
Здравствуйте, уважаемые читатели.
Регулярные выражения — хорошо известная вещь, которая используется в разнообразных проектах, чаще всего, для не очень сложных случаев разбора структурированных текстов. Занимаясь, на первый взгляд, такой несколько иной задачей, как обратный синтез моделей программ (когда есть код программы, порожденный автоматически некоторой системой по некоторой блочной модели решаемой задачи, и необходимо по этому коду воссоздать исходную модель), а также синтезом моделей программ по текстовому описанию задачи, я столкнулся с проблемой анализа текстов, а точнее — идентификации фрагментов текста некоторым настраиваемым шаблонам. Хотелось получить достаточно простое и гибкое (настраиваемое) решение. Регулярные выражения, с ходу, такими не казались, поскольку даже в такой простой задаче, как проверка слова по словарю, требовала, к сожалению, тщательного перечисления всех вариантов в этом выражении. Да и дерево синтаксического разбора они не строили. Однако, их явно можно было улучшить. Об этом и пойдет речь.
Итак, были поставлены следующие задачи:
- Регулярное выражение должно иметь возможность выдавать дерево синтаксического разбора. Необходимо реализовать стандартные средства доступа к этому дереву.
- Регулярное выражение должно иметь возможность включения проверок найденных фрагментов по словарю (точное или нестрогое соответствие по Левенштейну), а также более сложных проверок по нескольким таблицам одновременно.
- Хотелось бы иметь помимо простых проверок (перечисленных выше) еще и более нечеткие проверки, например, сочетаемости слов и выражений, нейронной сетью
Дерево разбора.
В регулярных выражениях разобранные фрагменты идентифицируются по номерам скобок. Это, мягко говоря, неудобно, поэтому было принято решение о возможности именования скобок. Кстати, именно эти имена должны фигурировать в дереве синтаксического разбора. Синтаксис был выбран простой:
(фрагмент_выражения)->{имя_скобок}
Если после круглых скобок в исходном выражении стоял какой-либо оператор (*,+ и т.п.), то он «преезжал» за правую фигурную скобку. Например:
(\w+\s)->{A}+
Ничто не мешает давать имена и вложенным скобкам, например:
((\w+)->{ID}\s)->{A}+
В последнем примере модифицированное регулярное выражение породит дерево разбора с некоторым условным корнем, на следующем уровне идут экземпляры A (их может быть более одного), на следующем уровне идут значения ID. К такому дереву удобно обращаться с помощью XPath, что и было мною реализовано, например, возможен такой запрос:
//A[2]/ID[text()!=""]/text()
Проверки слов по словарям, таблицам и простой нейронной сетью
Разбор регулярного выражения очень напоминает разбор простого логического выражения, например, в языке Пролог. Это приводит к идее, что в такие выражения органично впишутся Пролог-подобные фрагменты, которые и будут представлять собой:
а) цепочки различных проверок. Это несложно, тем более, что переменные уже появились (в виде именованных скобок);
б) или пополнения таблиц/словарей обнаруженными фрагментами;
в) или исключения из таблиц/словарей обнаруженных фрагментов;
г) или команду создания/обучения нейронной сети.
Общий синтаксис здесь будет таким:
(фрагмент_выражения)символ_операций=>{предикат1,предикат2,...}
символ_операций зависит от операции: проверки (?), пополнения (+), исключения (-), создания/обучения (*). Что же касается предикатов, то указывается имя предиката (стандартного или своего) и список его параметров в круглых скобках. Параметры могут быть константами, входными переменными, выходными переменными (префиксуются знаком »$»), знаком произвольного значения »_», ссылкой на текущее значение фрагмента_выражения (одиночный символ »$»). Разбор такого выражения считается успешным, если будут успешны все предикаты в цепочке.
Например, такое выражение:
([А-Яа-я]+)->{V1}\s+([А-Яа-я]+)->{V2}()?=>{check(V1},check(V2),correlate(V1,V2)}
выделяет два идущих подряд слова на русском языке и помещает их в переменные V1 и V2, а затем проверяет эти слова предикатом check (это может простая проверка по таблице) и, в заключение, предикатом correlate (тоже может быть проверка по таблице). Вид проверки (строгая или нестрогая) определяется спецификацией предиката.
Если таблица correlate будет содержать не сами слова, а некоторые коды слов и характеристику их сочетаемости, то может быть и такое выражение:
()->{C1}()->{C2}([А-Яа-я]+)->{check($,$C1}\s+([А-Яа-я]+)->{V2}()?=>{check(V2,$C2),correlate(C1,C2,1)}
Здесь сначала введены две переменные, C1 и C2. Предикат correlate может быть и нейронной сетью с двумя входами (коды слов) и одним выходом (сочетаемость), которая обучена по некоторому заранее заданному или динамически собранному (при работе регулярного выражения) набору.
Осталось добавить, что в качестве предикатов могут также указываться специальные директивы parallel и sequential, которые, соответственно, включают и вычисляют параллелизм исполнений в цепочке предикатов (которая при этом преобразуется в дерево зависимостей предикатов, в соответствии с которым и распараллеливается). Кроме того, можно включить специальный режим, при котором делается попытка динамически предсказать время выполнения отдельных предикатов и решить, будет ли параллелизм эффективен, или наоборот, внесет только дополнительные издержки.
Заключение
Все описанные модификации регулярных выражений реализованы в прототипе (модификация стандартного regexpr.pas) на Free Pascal.
Надеюсь, что эти идеи окажутся кому-либо полезны.
Сейчас с применением таких регулярно-логических выражений + программирования на чистом Прологе, удалось, во-первых, написать дополнение к системе порождения программ, которое восстанавливает исходную модель программы по ранее сгенерированному ей коду, во-вторых, сделать для этой системы элементы естественно-языкового интерфейса (принимается постановка задачи на весьма упрощенном русском языке и формулируется по ней модель задачи, по которой уже порождается программа).
