Приветствую!

Не могу понять как реализовать lazy quantification (*?) в регулярке. Допустим мы строим сначала недетерминированный автомат и по нему строим детерминированный. Просто ручками я могу нарисовать автомат, но как его сгенерировать в программе?

интересно, ты хочешь написать рег.выр. или реализовать рег.выр .в ЯП? 



Это сообщение отредактировал(а) gcc - 3.4.2011, 17:11

Реализовать

Либо заменить ленивые операторы на обычные. Либо не строить детерминированный автомат.
Другого пути я не вижу.

То есть как?
Я видимо непонятно изъяснился. 
Обычное повторение жрет все пока может. Т.е. если мы имеем такое регулярное выражение: <.*>, то если запустить его на такой ввод: <aaa><bb>, то получим один токен вместо двух. Т.е. .*=aaa><bb
А вот если повторение ленивое (lazy quantification) <.*?>, то получим два правильных токена: <ааа> и <bb>, потому что ленивое повторение прекращается при первом возможном случае. 

Эти примеры просты. Но в общем случае может быть так: (regExp1)*?(regExp2)...

По регуляркам я строю недетерминированные автоматы, а по ним детерминированные. Если я могу от руки нарисовать автомат, то стало быть его можно сгенерировать. Но как?

Я пытался сделать что-то вроде такого: ((regExp1)*)||(^regExp2)
Здесь ^ - это отрицание регулярного выражения, т.е. все кроме того, что определяет регулярное выражение. || - означает оба автомата запускаются параллельно.
К сожалению такой метод не сработал. 

может быть найти библиотеки с рег. выр.?
...и посмотреть так как это сделано...
например, библиотека с perl рег. выр. есть в: php, javascript, Cpp (Boost), etc

вродебы это PCRE (Perl Compatible Regular Expressions) 

Это сообщение отредактировал(а) gcc - 5.4.2011, 17:11

Вроде нашел решение. Так что пока помечу тему решенной. 

На пальцах:
1) приводим регулярное выражение к виду regExp1|regExp2|...|regExpn, тут | означает или. То есть раскрываем все скобки.
2) для каждого ленивого повторения в regExpi:
    - вычисляем регулярное выражение от *? и до конца. Типа суффикс: suffixRegExpi
    - вычисляем рег. выр. которое лениво повторяется: repRegExpi
    - строим кросс-автомат для repRegExpi и suffixRegExpi, в котором состояния - это все возможные пары состяний обоих автоматов. от всех состояний, в которых присутствует конечное состояние автомата repRegExpi добавляем епсилон-переход в начало кросс автомата. Для всех состояний в которых присутствует конечное состояние автомата suffixRegExpi, добавляем епсилон-переход в конечное состояние кросс-автомата (сюда попадает и то состояние, которое состоит из двух конечных состояний обоих автоматов). Если достигнуто состояние-ловушка (trap-state), которое состоит из двух ловушек обоих автоматов - лексическая ошибка.

Вот так. Если кому надо, могу объяснить поподробнее. В инете ничего по теме не нашел, решение мое, посему может быть далеко не оптимальным. Может есть где зарытые собаки, так что надо будет подлатать.