Можно написать регулярное выражение, которое в некоторых случаях требует экспоненциального времени выполнения. Такой пример(aa|aa)*, Если есть ввод нечетного числаas это требует экспоненциального времени работы.

Это легко проверить. Если вход содержит толькоas и имеет длину 51, Regex требуется несколько секунд для вычисления (на моей машине). Вместо этого, если длина ввода равна 52, его вычислительное время не является ледяным (я проверил это с помощью встроенного Regex-парсера JavaRE).

Я написал Regex-парсер, чтобы найти причину такого поведения, но я не нашел его. Мой парсер может построитьАСТ илиNFA основанный на регулярном выражении. После этого он может перевести NFA вDFA, Для этого он используеталгоритм построения powerset.

Когда я анализирую Rgex, упомянутый выше, парсер создает NFA с 7 состояниями - после преобразования в DFA остается только 3 состояния. DFA представляет более разумный Regex(aa)*, который может быть проанализирован очень быстро.

Таким образом, я не понимаю, почему существуют парсеры, которые могут быть такими медленными. Что является причиной этого? Разве они не переводят NFA в DFA? Если да, то почему нет? И каковы технические причины, почему они вычисляют так медленно?