Регулярные выражения + логическое программирование. Что в результате?

    Здравствуйте, уважаемые читатели.

    Регулярные выражения — хорошо известная вещь, которая используется в разнообразных проектах, чаще всего, для не очень сложных случаев разбора структурированных текстов. Занимаясь, на первый взгляд, такой несколько иной задачей, как обратный синтез моделей программ (когда есть код программы, порожденный автоматически некоторой системой по некоторой блочной модели решаемой задачи, и необходимо по этому коду воссоздать исходную модель), а также синтезом моделей программ по текстовому описанию задачи, я столкнулся с проблемой анализа текстов, а точнее — идентификации фрагментов текста некоторым настраиваемым шаблонам. Хотелось получить достаточно простое и гибкое (настраиваемое) решение. Регулярные выражения, с ходу, такими не казались, поскольку даже в такой простой задаче, как проверка слова по словарю, требовала, к сожалению, тщательного перечисления всех вариантов в этом выражении. Да и дерево синтаксического разбора они не строили. Однако, их явно можно было улучшить. Об этом и пойдет речь.

    Итак, были поставлены следующие задачи:

    1. Регулярное выражение должно иметь возможность выдавать дерево синтаксического разбора. Необходимо реализовать стандартные средства доступа к этому дереву.
    2. Регулярное выражение должно иметь возможность включения проверок найденных фрагментов по словарю (точное или нестрогое соответствие по Левенштейну), а также более сложных проверок по нескольким таблицам одновременно.
    3. Хотелось бы иметь помимо простых проверок (перечисленных выше) еще и более нечеткие проверки, например, сочетаемости слов и выражений, нейронной сетью

    Дерево разбора.


    В регулярных выражениях разобранные фрагменты идентифицируются по номерам скобок. Это, мягко говоря, неудобно, поэтому было принято решение о возможности именования скобок. Кстати, именно эти имена должны фигурировать в дереве синтаксического разбора. Синтаксис был выбран простой:

    (фрагмент_выражения)->{имя_скобок}

    Если после круглых скобок в исходном выражении стоял какой-либо оператор (*,+ и т.п.), то он «преезжал» за правую фигурную скобку. Например:

    (\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.

    Надеюсь, что эти идеи окажутся кому-либо полезны.

    Сейчас с применением таких регулярно-логических выражений + программирования на чистом Прологе, удалось, во-первых, написать дополнение к системе порождения программ, которое восстанавливает исходную модель программы по ранее сгенерированному ей коду, во-вторых, сделать для этой системы элементы естественно-языкового интерфейса (принимается постановка задачи на весьма упрощенном русском языке и формулируется по ней модель задачи, по которой уже порождается программа).
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 3

      +1
      Синтаксис именования скобок давно установлен де факто стандартом: Раз, два, три. Вы могли бы выбрать вариант Perl или Python уже по вкусу, но остаться в рамках совместимости с PCRE и многими другими движками. Сейчас у вас синтаксис получился с заметным потенциальным (а то и реальным) конфликтом с другим механизмом, который используется в таких выражениях — {} как установкой квантификаторов (например: \d{1,3}), и требуется сложный разбор вперёд, чтобы убедиться, что ->{что-то} это именно ваша конструкция, по содержанию этого «что-то», а не дефис, после которого квантификаторы для правой угловой скобки.

      Идея с предикатами неплоха, но 1) давно есть в некоторых движках, как в том же perlre, 2) есть альтернативное движение, которое в столь сложных случаях вместо языка регулярных выражений подключает PEG-движки. Многим они значительно удобнее — например, см. эту дискуссию.
      Ещё непонятно, как именно вы собрались подключать сложные внешние предикаты в движок — встроенные средства для этого, насколько я знаю, недостаточны.

      В общем же статья воспринимается примерно как «зверски круто, но чем они там таким занимаются, что это всё требуется, но они порождают кучу велосипедов для языка, популярность которого близка к нулю?» (ничего личного, но факт)
        0
        Сейчас у вас синтаксис получился с заметным потенциальным (а то и реальным) конфликтом с другим механизмом, который используется в таких выражениях — {} как установкой квантификаторов (например: \d{1,3}), и требуется сложный разбор вперёд, чтобы убедиться, что ->{что-то} это именно ваша конструкция

        Нет, разбор не такой уж и сложный. По крайней мере отличить предикаты в фигурных скобках от цифр не так сложно.
        Идея с предикатами неплоха, но 1) давно есть в некоторых движках, как в том же perlre

        Не нашел такого в pelre. Если Вы имеете в виду конструкции (??{}) и (?{}), то это не предикаты, а алгоритмический perl-код (или, возможно, код на ином языке). Здесь же предлагается языко-независимое логическое решение. Думаю, оно несколько компактнее и проще, чем (??{}) и (?{}). Если я ошибаюсь, поправьте меня.
        2) есть альтернативное движение, которое в столь сложных случаях вместо языка регулярных выражений подключает PEG-движки.

        Насколько я почитал, PEG все-равно не решает даже проблему перечисления альтернатив (они все равно присутствуют в грамматике, а хотелось бы подкачивать их из таблицы). Не видел я там и нестрогого сравнения с образцом.
        Ещё непонятно, как именно вы собрались подключать сложные внешние предикаты в движок — встроенные средства для этого, насколько я знаю, недостаточны.

        Теоретически, можно написать произвольное количество предикатов, включить их в динамически подгружаемый модуль и придумать regex-директиву для подключения модуля.
          0
          > Нет, разбор не такой уж и сложный. По крайней мере отличить предикаты в фигурных скобках от цифр не так сложно.

          Я не о принципиальной возможности разбора (на сейчас), а о создании потенциального конфликта. Это путь, который прошли многие языки, а больше всего известно в C++: на данном этапе конфликта нет, а чуть позже уже не поймёшь, ">>" это сдвиг или закрытие двух шаблонов; most vexing parse, и тому подобное. Кто наступил на эти грабли — старается их не создавать даже в отдалённой перспективе. Ибо чем и как вы захотите через год расширить этот язык — никому пока не известно…

          > Не нашел такого в pelre. Если Вы имеете в виду конструкции (??{}) и (?{}),

          Да. Что с ними громоздко — факт, и тут независимый язык… в перле, который интерпретатор, разницы особой нет, в компилируемом — да, приходится вставлять свой движок интерпретатора.

          > Насколько я почитал, PEG все-равно не решает даже проблему перечисления альтернатив

          Сам по себе — да. Я вообще не об этом говорю, а о том, что начиная с некоторого уровня сложности грамматики разбираемого — регулярные выражения становятся настолько громоздкими, что хочется переписать их в явную грамматику.

          > Теоретически, можно написать произвольное количество предикатов, включить их в динамически подгружаемый модуль и придумать regex-директиву для подключения модуля.

          Ну, у вас даже на этом этапе свой язык завёлся с какими-то стандартными функциями… значит, часть такого уже сделана.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое