проФорт

Язык регулярных выражений позволяет конструировать минипрограммы которые отвечают на один вопрос - совпадает ли данный произвольный текст с конкретным образцом. Краткое описание языка: строка текста и регексп просматриваются слева направо и последовательно сопоставляются. Каждый символ регекспа (кроме специальных) сопоставляется только с самим собой. Специальные символы это -- круглые скобки () которые группируют подрегексп в один элемент, a* сопоставляется с последовательностью из нуля или более элементов a (вместо одного символа может быть произвольный регексп заключённый в скобки),a|b совпадёт либо с a либо с b. Например (0|1)(0|1)* сопоставится с записью любого числа в двоичной системе. Для удобства использования добавлены также дополнительные конструкции (спец символы) которые выражаются через вышеописанные. Это a+ == aa* -- один или более, [xyz] == (x|y|z) (где x y z это одиночные символы) -- множество, [123a-e] == [123abcde] -- интервал, [^ab] -- любой символ кроме a и b, \d == [0-9] -- цифра, \s -- пробельный символ, a{n,m} -- сопоставится с последовательностью повторения a длины от n до m, . -- (точка) любой символ, итд. Для того чтобы вставить в образец спецсимвол который бы обозначал себя, а не спецконструкцию - его надо заэкранировать - символом \.

Программная реализация библиотеки регекспов подразумевает написание функции которая принимает строку и образец и возвращает логическое значение. На практике обычно этого недостаточно и хочется уметь выбирать из сопоставившейся строки подстроку совпавшую с данным подрегекспом. Границы этих подрегекспов, которые "ловят" строку определяются круглыми скобками и идентифицируются по номеру открывающей скобки если считать слева направо. Т.е.

(\d{1,3})\.\d{1,3}\.(\d{1,3}\.\d{1,3})

сопоставится с традиционной записью IP адреса при этом подрегексп (или карман) номер один будет соответствовать первому байту адреса, а второй -- последним двум с точкой между ними. За нулевой карман принимается вся совпавшая строка.

Для того чтобы запись регекспов не различалась между разными реализациями -- был разработан стандарт POSIX-регекспов. Другой обширный класс регекспов был сформирован де-факто по реализации регекспов в языке Perl. Эти два вида совпадают в базовых понятиях, но отличаются во многих подробностях. Впрочем во многих реализации есть свои дополнительные "фишки".

Изначально регексп задаётся программистом в виде строки в тексте программы. В языках (читай -- реализациях), где регекспы не являются базовой сущностью (например C/C++, Java, O'Caml, и т.д.), эта строка во время исполнения программы парсится, формируется автомат для разбора или сразу запускается алгоритм сопоставления. В форте же, благодаря наличию first-class компиляции (спасибо true-grue за термин), можно этап парсинга и построения автомата перенести на этап компиляции (так же делается в языках, где регекспы реализованы в ядре языка -- Perl, Ruby (?)). И во время компиляции можно провести редукцию автомата и другие возможные оптимизации, проверить синтаксис регекспа на правильность, и т.п. Это очень важное преимущество. Стоит также отметить что compile-time разбор RE можно реализовать на обычных языках если отказаться от классического представления регекспа в виде строки, а формировать его из меньших составных частей представленных "родными" элементами языка -- это то что называется parser generators (e.g. micmatch (O'Caml), boost::xpressive (C++), Gray (Forth), и т.д.)

В репозитории spf есть несколько обёрток к внешним dll-библиотекам PCRE и BREGEXP. Либа ~ygrek/lib/re реализует базовый функционал регекспов на чистом форте. Регекспы задаются в виде строки как

RE" (hi|hello)\sworld"

При этом во время компиляции проиходит разбор строки, проверка синтаксиса, преобразование в NFA (non-deterministic finite automata) и сохранение структуры автомата в кодофайл. Можно также создавать регекспы во время исполнения с помощью BUILD-REGEX ( a u -- re ) (такие динамические регекспы после использования надо удалять с помощью FREE-REGEX ( re -- )). Реализация стремится соответствовать стандарту POSIX (довольно утомительное чтиво ), но пока не полностью. Полученный re можно использовать для сопоставления со строкой словом re_match? ( a u re -- ?), информацию о подсовпадениях-карманах можно извлечь словом get-group ( n -- a u ). Пример -- "калькулятор"

REQUIRE re_match? ~ygrek/lib/re/re.f

: NUM ( a u -- n ) 0 0 2SWAP >NUMBER NIP ABORT" not a number" D>S ;

: calc
  RE" \s*(\d+)\s*([+*/-])\s*(\d+)\s*" re_match? NOT ABORT" oops"
  \1 NUM \3 NUM \2 EVALUATE ;

: readline ( n -- a u ) PAD SWAP ACCEPT PAD SWAP ; 

: run BEGIN 20 readline ['] calc CATCH IF 2DROP ." Nope" ELSE ." Result : " . THEN CR AGAIN ;

run

\2 это более короткая запись для 2 get-group. Обратите внимание что в перечислении знаков операторов '-' оставлен последним, этого требует POSIX, чтобы знак минус не был воспринят как указатель диапазона.
Т.к. RE" это слово форта которое само выбирает строку из входного потока, то оно понимает квотирование кавычки обратным слешем. В ext.f определены некоторые дополнительные стандартные операции с регекспами :

• re_split ( a u re -- list ) разбить строку по регекспу в список
  
• re_search_all ( a u re -- list ) найти все подстроки совпавшие с re и вернуть их список
  
• re_search ( a u re -- a1 u1 ) находит первое подстроку совпадающую с re
  
• re_divide-> ( a u re --> a2 u2 a1 u1 \ <-- ) бакфорт итератор возвращающий совпавшие и несовпавшие подстроки
  

Либа покрыта юнит-тестами в количестве 140 штук и надёжно работает. Все экспортируемые слова подробно описаны в начале файла re.f.
В качестве бонуса -- визуализация внутренней структуры автомата. Слово dotto: ( a u "filename" -- ? (из dot.f) сохранит dot диаграмму регекспа a u в файл filename.

S" ~ygrek/lib/re/dot.f" INCLUDED
S" AB+(CD)+|12?3" dotto: regexp.dot . BYE

результат :


Либа реализует NFA-алгоритм. Благодаря этому для неё не существует "патологических" регекспов - т.е. время сопоставления зависит только от длины регекспа и строки. Пример приводящий к экспоненциальному росту времени работы рекурсивных "сопоставителей" см. в конце файла re.f. С другой стороны это значит что на "простых" регекспах рекурсивная реализация в большинстве случаев будет быстрее. Возможное решение проблемы -- переход от NFA к DFA. Вдобавок в этой конкретной реализации не очень эффективно реализовано сохранение подвыражений что прилично сказывается на скорости выполнения (можно и нужно переписать). Ещё один существенный недостаток этой реализации -- отсутствие поддержки юникода, впрочем UTF-8 можно кое-как обрабатывать (по-байтово). Также в планах -- реализовать рекурсивный алгоритм сопоставления. Также для более полного соответствия POSIX надо правильно вычислять границы подвыражений (leftmost longest) и пройти все тесты AT&T.