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

Question

Регулярные выражения быстро становятся слишком сложными (для меня), чтобы понять. Даже что-то так просто, как [ab][cd], имеет несколько логических ветвей. Моя цель - повысить удобство сопровождения нашей кодовой базы, чтобы ответы на эти вопросы могли помочь нам обнаружить и исправить сложный код:

1. Существуют ли метрики вычислительной сложности (аналогичные цикломатической сложности), которые включают сложность, присущую регулярным выражениям?
2. Существуют ли инструменты, которые производят число сложности для регулярных выражений?
3. Существуют ли инструменты, которые могут предложить упрощения регулярных выражений?

Answer 1

Вы можете попробовать использовать скомпилированную форму регулярного выражения и попытаться сопоставить некоторые метрики сложности кода с такими, как строки кода или цикломатическая сложность. Чтобы понять, что я имею в виду, посмотрите на следующий ответ stackru: /questions/17532934/kak-vyi-otlazhivaete-regulyarnoe-vyirazhenie/17532938#17532938, который показывает, как с помощью perl вы можете получить доступ к скомпилированной форме регулярного выражения. Другой пример показан здесь: http://perldoc.perl.org/perldebguts.html со ссылкой на вывод инструмента с этой страницы:

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)

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

Answer 2

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

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

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

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

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