Как создать движок RegEx на Python

Часть 1: Грамматика. Создание движка регулярных выражений со всеми основными функциями.

В этой серии статей мы рассмотрим шаги по созданию RegEx Engine на Python. Я выбрал Python из множества альтернатив по нескольким причинам:

Хорошо интегрирован с командной строкой Linux.
Потому что да.

В каком-то смысле я считаю Python «менее подробной версией Java» и «менее запутанной версией JavaScript», которые были двумя другими альтернативами, которые я рассматривал.

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

А когда я не знаю, как что-то делать, я нахожу JS слишком запутанным, это просто ощущение, а не универсальная правда, и я считаю, что с Java я могу лучше организовать свои идеи.

Но поскольку мне не нравится, насколько многословна и ограничивает Java, но мне нужны классы, и я люблю иметь функции как первоклассный гражданин, Python казался мне идеальным сочетанием.

В любом случае, пора приступить к самому проекту.

То, что нам нужно

Чтобы сопоставить строку с регулярным выражением нашей воли, нам нужно выполнить несколько шагов:

понять регулярное выражение
создать его внутреннее представление (чтобы мы могли видеть, совпадает ли с ним переданная строка)
сопоставьте строку с регулярным выражением, используя построенное нами внутреннее представление.

Для выполнения первых двух шагов нам понадобятся два компонента:

Lexer (или сканер) для синтаксического анализа регулярного выражения в токенах («словах», общих «частях информации»). Например, в предложении «Я красивый, очень красивый» каждое слово («я», «я»,…) представляет собой лексему типа «слово», а запятая - лексема типа «пунктуация».
синтаксический анализатор, который последовательно считывает все токены и «понимает» их, создавая при этом внутреннее представление регулярного выражения (которое будет деревом, называемым абстрактным синтаксическим деревом, AST для друзей).

Для выполнения третьего шага нам нужно создать компонент, способный принимать в качестве входных данных AST, созданный анализатором, и строку, и посещать дерево, чтобы сопоставить каждый лист дерева с некоторой частью строки. (и еще кое-что, мы обсудим позже).
Этот компонент называется:

Двигатель.

Дорожная карта

Итак, теперь, когда мы знаем, какие модули нам придется кодировать, давайте составим план:

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

Грамматика

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

Я предполагаю, что вы знаете, что такое формальная грамматика, и понимаете нотацию EBNF, если нет, НЕ ПАНИКА, погуглите.

Грамматика регулярных выражений, которую мы узнаем, будет следующей:

Производство верхнего уровня RE :: = RE_SEQ действительно бесполезно, но оно есть, потому что я использовал его в одной из ранних версий проекта и мне было лень удалить его позже. В любом случае, я обещаю, это совершенно безвредно, и это будет стоить вам всего пары строк кода и всего лишь одного вызова в стеке во время выполнения.