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

Question

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

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

Answer 1

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

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

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

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

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

Answer 2

Вы можете попробовать использовать скомпилированную форму регулярного выражения и попытаться сопоставить некоторые метрики сложности кода с такими, как строки кода или цикломатическая сложность.Чтобы понять, что я имею в виду, посмотрите на следующий ответ 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)

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