Реализация простого механизма регулярных выражений в 70 строк кода

[Andrey_Solomatin]

В функции match_from_pos(ition) находится основной механизм регулярных выражений основанный на применении рекурсии.

Всегда считал, что для этого используются конечные автоматы.
Код с конечными автоматами получается хорошо структуированным и легко читается.

[QtRoS]

Это так и есть. Тут уже зависит от работодателя - примет ли он решение на самодельном велосипеде или таки откажет из-за того, что не использован годами проверенный инструмент (НКА).

[nick1612]

Да, конечные автоматы это первый и один из стандартных механизмов реализации регулярных выражений. Первый подобный алгоритм был написам Кеном Томпсоном и строил конечный автомат, а после чего на лету компилировал его напрямую в машинные коды. Есть еще варианты со стековой виртуальной машиной, но они все достоточно громоздкие для этой задачи. На хабре кстати есть перевод хорошей статьи по этому поводу https://habr.com/ru/company/mailru/blog/270507/

[poletos]

В конкретно упомянутой постановке задача допускает гораздо более простое решение. Единственный элемент, который действительно сопоставляется - это точка "." (в настоящих регулярных выражениях есть еще "один из символов" "[a-z]" и "один символ кроме перечисленых" "[^a-z]" например. Поэтому регулярное выражение из символов "^$.*?+" это указание, сколько точек нужено найти, возможно с привязкой к началу/концу строки.
Конкретнее, регулярное выражение это строка следующего вида:

1. "^" - начало строки, либо есть, либо нет. Пока пропускаем.

2. Последовательность из ".", ".*", ".?", ".+". В этой последовательности каждая часть - это просто указание, от скольки до скольки произвольных символов может подойти. Точнее:

   • "." - минимум 1 символ, максимум 1 символ, далее - (1, 1);

   • ".*" - (0, ∞);

   • ".?" - (0, 1);

   • ".+" - (1, ∞);

3. "$" - конец строки, либо есть либо нет. Пока пропускаем.

Для пар (минимум, максимум) в регулярном выражении считаем сумму всех пар (допускаем, что ∞ + x = ∞ для любого x). Получаем (min, max).
В итоге регулярное выражение - это указание, что в строке от min до max символов в строке, возможно с привязкой к началу/концу. Дальше можно разобрать случаи с началом/концом:

• Есть и "^", и "$". Тогда считаем количество символов в строке, если min <= len <= max, то вся строка и подходит, иначе совпадения нет;

• Есть только "^". Тогда возвращаем min первых символов, если столько есть, иначе совпадения нет.

• Есть только "$". Тогда возвращаем min последних символов, если столько есть, иначе совпадения нет.

• Нет ни "^", ни "$". Возвращаем min любых символов (например первых) если есть, иначе совпадения нет.

P.S. Заметил, что не используется max, его можно использовать, чтобы прикрутить при желании нахождение всех совпадений.

[amishaa]

Ещё сопоставляются все буквы. Например, регулярке a* строка aaa удовлетворяет, а строка bbb (той же длинны) - нет.

[nick1612]

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

[poletos]

С обычными символами не будет работать, это я упустил.

[a-tk]

А как группы символов и выбор вариантов вида (?:abc|abf|$) ?

[nick1612]

А разве в статье написано про их реализацию? Мог бы быть заголовок "Пишем полный аналог PCRE в 70 строк кода" :)

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

[nick1612]

<?php
if (match_metachar($re_tokens, $re_pos + 1, "|"))
		return match_from_pos($re_tokens, $re_pos + 2, $str, $str_pos) || (!is_end($str, $str_pos) &&
			match_char($re_tokens[$re_pos], $str[$str_pos]) && 
			match_from_pos($re_tokens, $re_pos + 3, $str, $str_pos + 1));

ну и добавть "|" в массив META_CHARS

[a-tk]

Тогда можно было бы свести задачу к wildcard-символам типа * и _ в именах файлов или % с _ в SQL. Задача та же, но более применима в реальной жизни, чем некоторое ограниченное подмножество регулярок, из которого отрезано всё полезное.

[nick1612]

Не совсем понял, в чем заключается ваше решение, можете привести пример (желательно с примером кода)? Если есть более простое решение, буду рад узнать.

[insecto]

О боже, я в красках представил себе производительность.

[nick1612]

По моему я нигде не говорил, что это какое-то производительное production решение, но мне так же не понятно с чего вы взяли, что его производительность настолько ужасна? Для тестовой утилиты командной строки оно работает вполне нормально.