Да, кстати, а какого размера грамматика, и как быстро генерится

лексер?

В моем случае в тестовой грамматике было порядка 20-30 ключевых слов, и несколько generic правил. В том числе правило для идентификатора заданное как повторение всех известных символов этой грамматики кроме заданного набора. Это некорректное определение идентификатора, просто для тестирования такое выбрано. Каждое регулярное выражение по правилам Томпсона трансформируется в NFA. Затем каждый NFA трансформируется в минимизированный DFA алгоритмом Бжозовского. (эта операция выполняется быстро). Затем полученные автоматы объединяются в один единый NFA взятием объединения по эпсилон-переходу. Полученный автомат трансормируется в минимизированный DFA тоже алгоритмом Бжозовского. Последняя трансофрмация выполняется очень долго(порядка минуты). Её получается немного оптимизировать бинарной попарной union-редукцией автоматов, но принципиально это на производительности не отражается.

Минуты на генерацию это очень много. Даже тупая генерация с помощью производных от регулярок столько времени не занимает.

Ну, взятие производных наверное не такой тупой метод. Вообще, я думал на него перейти. А что есть лучше взятия производных?

Не знаю. Я реализовывал в стиле ехал Box через Box, но с более эффективным представлением дерева он наверное даже может достаточно быстро работать.

Ну, каждая регулярка по отдельности у меня быстро трансформируется в минимальны DFA. Весь процесс меньше секунды занимает. Проблема возникает при их объединении в один единый.

Так там автомат для лексера целиком генерится.

Подвох алгоритма Бржозовского в том, что DFA для перевёрнутого языка может оказаться экспоненциально больше DFA исходного

То есть лучше на Хопкрофта перейти?

Даже на питоне генерация производными столько не занимает. У меня лексер для си меньше секунды генерился. Это с поддержкой ютф-8 в комментах и строках

Можно начать с производных. Они за один проход дают хорошее приближение к минимальному автомату. Если этого покажется недостаточно, можно Хопкрофтом доминимизировать

Вообще, к слову, я с этим игрался. В смысле, я отказывался от минимизации, и просто детерминировал конечный автомат обычным взятием суперсета. Без минимизации. И скорость не сильно возросла в сравнении с Бжозовским. Не на порядок. Ну может раза в два быстрее выходило. Поэтому я бы предположил, что сам по себе алгоритм Бжозовского не настолько медленнее условного Хопкрофта. В общем, видимо все упирается в неэффективное кодирование. И надо либо деривативы брать, либо думать, как кодировать на коленке более аккуратно.

Звучит как-то совсем печально. Может дело в том, как строится NFA? Если это делать неаккуратно, можно получить кучу лишних переходов и состояний. Если нет, значит где-то в детерминизации что-то очень сильно тормозит

Ну смотрите. Я NFA строю правилами Томпсона. И там конечно вставляются эпсилон-переходы на каждый чих. Тем не менее каждый по отдельности regex не очень большой, и детерминизация с ним справляется быстро. Ну то есть я сначала детерминирую каждый полученный автомат по отдельности, и это в целом происходит быстро, в течение сотен миллисекунд на все regex-ы(меньше секунды всего). После этого я из полученного набора автоматов конструирую один единый union просто добавляя новое входное состояние, и соединяя его эпсилон-переходом в каждый вход каждого автомата. Не более того. И уже детерминизация этого автомата растёт, скажем так, экспоненциально. Поэтому можно было бы предположить, что детерминизация узкое место. И наверное так и есть, но я не представляю, как его ускорить. Сам по себе алгоритм не может быть быстрым по определению. Я разумеется делаю некоторые разумные оптимизации. Я не строю единый кросс-продукт сразу, я строю кросс-продукты по мере необходимости. Вычилслил очередное замыкание по символу алфавита, положил его в очередь на обработку(если в очереди его ещё нет). Очередь у меня имеет хеш-таблицу, поэтому просмотр наличия замыкания в очереди относительно оптимизировано.

А какого размера автоматы получаются на выходе?

Я сейчас не у компа, ну на вскидку сотни состояний после всех оптимизаций.

Совсем странно, у меня автоматы на десятки тысяч состояний производными прожёвывались за секунды. На питоне

А насколько у вас регэксы увеличивают ветвистость единого автомата?

Я для отдельных регекспов автоматы и не строю, сразу единый получаю, как в https://www.ccs.neu.edu/home/turon/re-deriv.pdf

Ну да, я читал. Думаю так же попробовать.