Я правильно понимаю, что вы в качестве проверки имеете ввиду

выражения уровня ch >= '0' && ch <= '9' для чисел ? И спрашиваете как жить с кучей диапазонов в юникоде ? Если это так, т.е. если я правильно понял, то вы просто забываете, что можно взять таблицу(из битовых масок принадлежности к классам или побитово сжать, если хватает меньшего количества классов) для проверки или взять готовые реализации типа той которая емнип есть в исходниках iconv

Вот таблица как раз компактной не будет.

Вопрос в основном вокруг именно алфавитных символов. Конечно не только их, но конкретно алфавитных символов в юникоде очень много. Тысяч 15 наверное. Ну и получается нам нужна таблица на 15 тысяч символов, чтобы по ней проверять. Но у нас, очевидно, в процессе анализа могут возникать и иные классы.

Чуть около ляма символов - мегабайт для таблицы, но зато трудоёмкость теста O(1), если сжать до битов, то выйдет меньше

А как по вашему иначе ? К сожалению тут одно из двух - жирный switch который будет иметь огромную сложность при false, либо сделать, как и делают - взять огромный сишный исходник с массивом классовой принадлежности.

Таблица интервалов же.

Как здорово, что кеши современных CPU просто бесконечны (и в них это всё всегда влезет — это мегабайт на каждое состояние, не забывайте), правда? А, нет, подождите... ;)

Нет, вы недооцениваете проблему, мне кажется. Во-первых мегабайт скорее-всего в кеш не поместится. Значит процессор будет загружать кусочки таблицы на каждую проверку. Но это не самая критичная проблема. Представьте такую регулярку: abra|\w* Здесь мы имеем три класса символов: все unicode алфавитные символы, за исключением буквы a(мегабайт), ещё такая же, но за исключением b(ещё мегабайт), и ещё такая же за исключением r. Ну а о том, как долго такие автоматы будут строиться я вообще молчу. Потому что заранее сказать, какие классы символов нам нужно будет запечь мы не можем, нам нужно сперва помнимизировать автомат.

Вообще, если ты хочешь вкинуть кейворды, то не стоит их втыкать в автомат. Распознай идентификатор, и уже затем проверь кейворд он или нет.

я тут смотрел в автоген алекса для ответа на вопрос про лексеры и там нашёл две таблицы по 105 тысяч символов каждая

Ну весело у вас там в хаскеле.

в L3 первые 16 тыс символов залазят, частые сбросы 3-го кэш в таком случае маловероятны, т.к. сомнительно, чтобы у вас был микс из равномерно распределённых символов из всего юникода сразу

Ну, это будет ручная техника, как я понимаю. Кроме того, а почему вообще кейворды в автомат не втыкать? Мы экономим несколько не супер дешёвых проверок. В смысле, каждый кейворд проверять ведь то же не дёшево.

Ну, кеш может быть не так критичен будет.

Потому, что тогда автомат действительно может быть гигантским. По крайней мере если у тебя сотни кейвордов как в SQL.

Короче - хотите максимально шустро - используйте таблицы, хотите просто отмасштабировать упомянутую логику выше - делайте толстый switch/if(с доп оптимизацией по lru), хотите улучшить худшую оценку, ценой большей сложности чтения кода - используйте упомянутое @KvanTTT дерево отрезков. Вопрос только в том, что 1) юникод хотя и включает в себя 1 с небольшим ляма символов, но на практике вне ucs-2 - это символы уровня древних египетских иероглифов, смайликов и значков сект, они часто не имеют классовой принадлежности вне сверх узких приложений - регулярок к ним никто ПМСМ применять или не станет или им хватит статического false по факту непринадлежности к привычным классам.

> Короче - хотите максимально шустро - используйте таблицы А вот в benchmarks (современных написанных вручную lexers против FSM) нередко выходит, что наоборот. На современных CPU всё решать может тупо кеширование, т.е. общий размер кода + таблиц, понимаете? Кроме того, распределение длин токенов обычно совсем не равномерное, и когда, например, hand-crafted lexer ищет конец string literal с помощью strchr(), FSM этому трудно что-то противопоставить (у него существенно больший overhead per character/transition).

А почему prediction процессора будет лучше работать с кодом, нежели с таблицами перехода?

Хмм... разве я где-то писал про prediction?

Извините, это уже мои предположения конечно были. Просто вы написали про overhead per character. Я вот про этот момент хотел уточнить. А почему там оверхед?

Потому что конкретно в этой ситуации strchr() (компилируемый во что-то вроде rep scascb на x64, кажется) быстрее, чем, грубо говоря, скомпилированное state = fsm_table[state][сchar++];. Например, для flex я где-то (но не могу найти источник) видел такое: "For flex, the number of instructions for each input symbol is quite low: GCC generates 12 instructions for the DFA match loop."