Вычислительная сложность регулярных выражений

Вы можете попробовать использовать скомпилированную форму регулярного выражения и попытаться сопоставить с ней некоторые показатели сложности кода, например строки кода или цикломатическую сложность. Чтобы понять, что я имею в виду, посмотрите на следующий ответ stackoverflow: https://stackoverflow.com/a/2348725/5747415 , который показывает, как с помощью perl вы можете получить доступ к скомпилированной форме регулярного выражения. Другой пример показан здесь: http://perldoc.perl.org/perldebguts.html#Debugging-Regular-Expressions, цитируя вывод инструмента с этой страницы:

Compiling REx '[bc]d(ef*g)+h[ij]k$'
1: ANYOF[bc](12)
12: EXACT <d>(14)
14: CURLYX[0] {1,32767}(28)
16:   OPEN1(18)
18:     EXACT <e>(20)
20:     STAR(23)
21:       EXACT <f>(0)
23:     EXACT <g>(25)
25:   CLOSE1(27)
27:   WHILEM[1/1](0)
28: NOTHING(29)
29: EXACT <h>(31)
31: ANYOF[ij](42)
42: EXACT <k>(44)
44: EOL(45)
45: END(0)

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

Если вы имеете дело с системой регулярных выражений, эквивалентной формальным регулярным выражениям (которые описывают регулярные языки; без подсчета, без ретроспективного просмотра, без сопоставления пар скобок и т. д.), ИЛИ если вы будете иметь дело только с регулярными выражениями, которые используют эти функции (несмотря на то, что ваша система регулярных выражений способна описывать нерегулярные языки), тогда существует точное понятие сложности (или, по крайней мере, вы можете его вывести), и есть определенный смысл, в котором регулярные выражения могут быть «минимизированы».

По теореме Майхилла-Нероде все регулярные языки имеют конечное число классов эквивалентности при отношении неразличимости строк. Эти классы эквивалентности непосредственно соответствуют состояниям в минимальном детерминированном конечном автомате для регулярного языка. Вы можете принять количество состояний минимального детерминированного конечного автомата для языка как «фундаментальную» сложность самого языка.

Существуют алгоритмы, которые могут привести вас от (формального) регулярного выражения к минимальному детерминированному конечному автомату, а затем обратно к регулярному выражению. Это должно дать вам каноническое регулярное выражение для каждого регулярного языка. Я предполагаю - но не разработал доказательство - что процесс создания регулярного выражения из минимального детерминированного конечного автомата может быть изменен так, чтобы он производил возможное сокращенное (с точки зрения количества операций) регулярное выражение.

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

Если вам действительно нужны нестандартные функции регулярного выражения, то вам не повезло; в языковых классах более высокого порядка нет понятия вычислимой минимизации. Вы можете целыми днями изобретать метрики сложности, но вы никогда не получите общего алгоритмического ответа на вопрос «насколько это неэффективно по сравнению с базовым планом?» Другой способ выразить то, что я имею в виду, таков: сделать торт может быть сложнее, чем сделать попкорн, но если вам нужен торт, вы должны приложить дополнительные усилия, чтобы получить то, что вам нужно.