| рикурсияэтасложна |
[Jan. 18th, 2022|02:03 am] |
день с лихуем искал дурацкий баг в компиляторе регэкспов. оказалось — забыл один рекурсивный вызов.
в общем, спасибо Драконьей Книге (в очередной раз): прямой компилятор регэкспов в DFA работает. правда, такая компиляция ужасно неэффективна, тормозная, требует кучу памяти и налагает ограничение на длину регэкспов — но в нашем случае это неважно, оно делается один раз на старте.
точнее, почти неважно: длина регэкспов роялит, поскольку кейвордов может быть очень много, а размер рабочих структур данных линейно зависит от количества листочков в AST регэкспа. грубо говоря, каждая буква — это листок. в каждой внутренней ноде надо иметь место для хранения двух множеств такого размера, в каждой листовой — трёх. и ещё 256 таких же множеств — рабочая область. в общем, много.
есть мнение, что можно не строить одну огромную регулярку на все возможные кейворды, а компилировать каждый кейворд в отдельный DFA, и потом эти DFA тупо смержить. я нутром чую, что это совсем несложно, но доказать пока не могу. буду думать дальше.
ещё одна проблема в том, что DFA — распознаватель, а нам нужен классификатор (чтобы отличать кейворд от числа, например). но в принципе, это решается заменой флага «accept state» в DFA-ноде на «accept id». то есть, не просто отмечать ноду как возможное завершение матчера, а записывать в ней, какой именно матчер там кончился. это дополнительно даёт возможность детектить ошибки в наборе для хайлайта: если нам надо отметить DFA-ноду как «принимающую», а она уже отмечена, и с другим id — у нас есть конфликт распознавания: две регулярки могут отматчиться в одно и то же. удобный побочный эффект.
нет, проблем для вещей типа `for` и `foreach` это не создаст, потому что в процессе сканирования текста мы запоминаем последнюю увиденую «принимающую» ноду (её id, точнее), но распознавание не останавливаем, пока не зайдём в тупик. то есть, распознавалка «жадная». да, из-за этого придётся иногда делать откат назад и дополнительные проверки. в принципе, можно чуть усложнить алгоритм, указав, какие id обязаны заканчиватся на границе слов текста, и ввинтить прочие оптимизации — но это уже мелкие технические детали.
в общем, надо сделать код, который мержит два DFA — и машинка для подсветки синтаксиса готова. прогрев у неё долгий, зато потом она очень-очень быстрая, и не требует для матчинга дополнительной памяти (то бишь, не зависит от количества и вида регулярок в автомате).
в общем-то, всем этим можно было не заморачиваться, конечно, а сделать и применить универсальный движок регэкспов по томпсону на NFA, он бы не особо и тормозил. но это неизящно: раз уж я всё равно делаю велосипеды, то пусть некоторые велосипеды будут красивей общепринятых. |
|
|