Кстати, что за генератор, какие мотивы его реализации были?

У меня конструктор инкрементальных парсеров. Примерно как Tree-Sitter. Он получился значительно быстрее Tree-Sitter при инкрементальном разборе, и значительно быстрее Tree-Sitter при неинкрементальном разборе. Но он несколько медленнее, чем обычный не-инкрементальный парсер рекурсивного спуска. Я провёл множество улучшений и оптимизаций, и бенчмарков. И в целом выжал из системы довольно много. Так что она получилась не сильно медленнее, чем неинкрементальная. Но тем не менее она медленная(процентов на 40-50). Это проблема в частности потому, что я позиционирую свой фреймворк не только в качестве инструмента инкрементальной, но и в качестве инструмента для организации обычной неинкрементальной фронт-энд компиляции. Собственно бенчмарки на текущий момент показывают, что всё упирается в лексер. Вот поэтому и заморочился. Сейчас у меня лексер сделан довольно наивно. Он просто объединяет все регулярки в один гигантский автомат, минимизирует его, и затем делает кодогенерацию(без таблиц перехода, просто джампы в коде). И он делает это по нормализованным UTF-32 символам, что тоже скорее-всего не улучшает парсинг Ascii.

VVM}} Идея: идёте по файлу. VVM}} Все встреченные символы в таблицу. Нумеруем. VVM}} Перекодируем в эти номера. VVM}} В итоге с 21 бита получаем 6 / 7 / 11 битов ( скорее всего - 7) Так как насчёт идеи сперва вычислять набор используемых символов? Т.е. м.б. уже проверялась и не давала выигрыша в скорости? Какова статистика на тестовом корпусе ( он же есть?) исходных кодов на ЯП из поддерживаемого набора?

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

Да, медленнее. Не на порядок. Но процентов на 30-40.

Минусы этой идеи следующие. Во-первых, так не получится предварительно закодировать большие классы символов. Например, все алфавитные символы Unicode. Даже их некоторое подмножество будет довольно большим. По причинам, описанным здесь. Ну, теоретически можно, но компиляция лексера на типичной грамматике языка с разными кейвордами и unicode-идентификаторами займёт минуты (я это проверял). Во-вторых, декодирование utf-8 в utf-16 на каждый символ, это не бесплатные рантайм-издержки. Хотя может и не такие уж дорогие. В конце-концов декодирование будет происходить в рамках одного машинного слова.

Мне почему-то кажется, что в реальных исходных кодах будет: — Globish ( он же английский); — родная мова ( 1шт.) — греческий и прочие математические символы т.е. весь 2^21 мы не встретим никогда. Можно сделать штук 100 вариантов, зашить их, выбирать нужный в самом начале P.S. utf-16 — не ко мне... Я склоняюсь к "21-битному". Можно в 1 символ (?) в 24 битах, можно 3 с-ла в 64 битах

В реальных исходниках у вас может быть один-два комментария на родном языке, но если вы в принципе его поддерживаете, то лексер должен быть готов их встретить где угодно. А их полный алфавит довольно объёмный. Про 24-бита. Вы так формально сэкономите память, но вряд ли вы выиграете в производительности. По этому значению ведь как-то нужно будет перемещаться в таблице переходов(или в коде). Соответственно процессору всё равно придётся копировать это значение в своё машинное слово(32 или 64 бита).

Очередная идея: Считать символами всё кроме: — 0123456789 — точек, запятых, амперсандов т.е. ~!@#$%^&*()_+ — прочего, что имеет свою роль в грамматике контретного ЯП или набора ЯП Можно ещё таиладские цифры и наборы символов для математики, функциональных ЯП.

Ok Ж-) Согласен: идеи - материал для мозгового штурма

Очередная идея: Считать символами-буквами всё кроме: — 0123456789 — точек, запятых, амперсандов т.е. ~!@#$%^&*()_+ — прочего, что имеет свою роль в грамматике контретного ЯП или набора ЯП Можно ещё таиладские цифры и наборы символов для математики, функциональных ЯП.

Очередная идея: Считать символами-буквами всё кроме: — 0123456789 — точек, запятых, амперсандов, т.е. ~!@#$%^&*()_+ и тому подобного — прочего, что имеет свою роль в грамматике конкретного ЯП или набора ЯП Можно ещё таиландские цифры и наборы символов для математики, функциональных ЯП включить в соответствующие категории.

Not bad. We did that* (exclusion) in MPL grammar — and we have no problem with it. Letter ::= [^+0123456789!@.:;{}()«#x22#x23#x5B#x5D #x9#xA#xD-]

А Вы пробовали re2c посмотреть (содрать оттуда идеи), в таком случае?

I hope 😉. I going to try this "cm3" compiler of Modula-3 language. ( May it's happend not in near time.)

Это может и неплохая идея, кстати.

Попробуйте ( "на досуге") — м.б. будет выигрыш по скорости на "существующей аппаратуре"

Не пробовал, но сейчас посмотрю. Спасибо. Собственно, в документации написано: > It compiles regular expression specifications to deterministic finite automata and encodes them in the form of conditional jumps in the target language Это буквально то, что я сейчас и делаю. И мне казалось, что это плохая идея.

Адекватные benchmarks вообще трудно найти, насколько я помню. :( Ну вот что-то, например (см. и ссылки оттуда): https://github.com/Genivia/RE-flex/issues/86

Автор Re/Flex пишет: > I suspect that your transition function average asymptotic execution time is O(m) for m out-edges on average per DFA state, making your TDFA matching cost O(nm) on average instead of the linear time O(n). The m will quickly grow in TDFA and staDFA (perhaps even more) for practical regex patterns that are typically large. I already collected experimental stats some time ago to compare DFAs, which both grow larger when markers are used, depending on the pattern). The m originates from the conditional jump logic for direct-coded DFAs with if-then-else (rather than jump tables). That is why the (academic) community rejects the idea that direct-coded DFAs are (generally) faster than table-driven DFAs. Собственно, у меня те же соображения были. Тем не менее, re2c почему-то показал результаты лучше, чем re/flex.

Потому что это про сравнение submatch extraction (что к "обычным" случаям lexing совсем не относится), разве нет?

Я не очень понял, что там у них происходит, но я полагаю, что если мы говорим о сканнере, то сканнер может быть представлен, как один большой regex с кучей submatch.

Подождите. Обычный scanner — это DFA с кучей final states, и всё. Зачем там submatch?

Так re2c генерирует здоровенный switch, который потом компилятором оптимизируется до jump table

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

Уверен. Даже интерпретатор байткода со здоровенным switch так оптимизируется. Проверял сравнением генерируемого кода и бенчмарками для наивного switch и диспатча через gccшный computed goto

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

Кстати, а как у вас реализована инкрементальность?

Какой именно аспект?