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

Длина этого регулярного выражения 28 символов

ну если что максимальная длина этого выражения 10

Что в твоем понятии длина выражения? Явно не длина строки, я так понимаю?

на входе функции регулярное выражение, на выходе его максимальная длина, например
(?<Month>\d{1,2})/(?<Day>\d{1,2})/(?<Year>(?:\d{4}|\d{2})) -> 10
\w+ -> неопределённо
(?<Zip>\d{5})-(?<Sub>\d{4}) -> 10

построй конечный автомат, обходи его в ширину, считай максимальный путь. если нашёл цикл, значит бесконечный путь есть.

Банальная рекурсия

Подниматься вверх по дереву. Запоминать пусто множество или нет, а также максимальную длину подвыражений (целое не отрицательное число или бесконечность).

Ну и естественно это работает только для не расширенных регулярных выражения (== не содержащих пересечений и дополнений). Если расширенные - то действительно надо строить конечный автомат. Потом пройтись по нему поиском в глубину из начальной вершины. Если встретится серая вершина - то есть цикл, и, если из этого цикла достижимо какое-нибудь конечное состояние, то выражение бесконечно. Завершая посещение вершины нужно поставить на ней метку, равную 0 если из вершины все ребра видут к ней же, и <максимум по всем вершинам, в которые из данной выходят ребра> + 1 для всех остальных). После этого в начальной вершине будет ответ.

А что будет начальной вершиной? К примеру для этого выражения (?<Month>\d{1,2})/(?<Day>\d{1,2})/(?<Year>(?:\d{4}|\d{2}))

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

>К примеру для этого выражения (?<Month>\d{1,2})/(?<Day>\d{1,2})/(?<Year>(?:\d{4}|\d{2}))

Ну это вообщето не расширенное. Можно просто считать рекурсией. Пусть F - искомая функция.

F(\d) = 1

для F(R{1,2}) - это 2 * F(R) при R=\d это 2

F(/) = 1;

А от конкатенации - это сумма по подвыражениям. Ответ 8 :)

Как преобразовывать регулярное выражение в автомат - надо курить теориюю. Объяснить на форуме в принципе можно, но почти бесполезно, - лучше по книжке (копать в "Детерминированный конечный автомат")

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

Большое спасибо!

P.S. Вообще то длина будет 10, в выражении же ещё есть два слэша ))

кстати нашел неплохую статью по теме http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspx