SZ
Нет
Size: a a a
2021 November 19
SZ
cacactus !
SZ
Начало строки: 1
c : 1->2
a : 2->3
c : 3->4
a : ?? Из 4го состояния есть только переход по 't'
c : 1->2
a : 2->3
c : 3->4
a : ?? Из 4го состояния есть только переход по 't'
OP
Потому что ваня неправильно вбил данные
OP
Бектрекинга там не будет
OP
Лучший способ увидеть то что ты хочешь это написать
(ca)+cactus
тогда будет переход назад, но стейтов ты пройдешь максимум ровно столько сколько символов в строке. Почитай теорию конечных автоматов
(ca)+cactus
тогда будет переход назад, но стейтов ты пройдешь максимум ровно столько сколько символов в строке. Почитай теорию конечных автоматов
OP
Это детали, зависит от того как реализовать.
Есть множество алгоритмов, начиная от 256*2 байт на стейт и заканчивая mixed switch goto, который почти ничего не жрет по памяти
Есть множество алгоритмов, начиная от 256*2 байт на стейт и заканчивая mixed switch goto, который почти ничего не жрет по памяти
SZ
Я хочу увидеть, какому автомату соответствует эта регулярка https://t.me/modernperl/199658 и увидеть список стейтов, по которым он ходит при входной строке «cacactus» если утверждается, что он сматчит ее без бэктрекинга
OP
Щас не могу, компа нет под рукой
SZ
Mixed switch goto это че? Дафдевайс? Так он в общем случае жрет ровно столько, сколько я написал
OP
Бектрекинга в ДКА впринципе нет, если спецально не постараться
OP
Это switch case с предварительной проверкой диапазона и последующим goto на блок с новым стейтом. Специфика такова что почти на всех транзишенах он работает быстрее чем таблица, причем заметно, но не занимает памяти. Но подходит только для jit / compile
SZ
Ничего не понятно :) можешь перевести в термины gnu assembly (ну или сделать objdump -d если у тебя есть скомпиленный код)? Тогда станет гораздо яснее
OP
Открой в uri::router clib/src/panda/uri/router/RegexpParse.cc увидишь сгенеренный парсер для регэкспов по этому типу
OP
регэкспы выполняет он не этим кодом, это только парсер регэкспов шаг 1 перед составлением dfa
b
не матчит "cacatus", такого паттерна нет
SZ
@PerlBanjoBot echo cacactus |grep ctus && echo MATCH
P
Bareword "ctus" not allowed while "strict subs" in use at script.pl line 9.
Execution of script.pl aborted due to compilation errors.
https://PerlBanjo.com/41ca120eba
Execution of script.pl aborted due to compilation errors.
https://PerlBanjo.com/41ca120eba
SZ
Да, я уже открыл