Badoo corporate blog
Programming
C++
Compilers
C
Comments 25
+1
Если ничего не напутал — вместо
#undef PEEK_ARG

должно быть
#undef NEXT_ARG

для удаления объявленного ранее макроса.
0
И Си заменить на Си++ :-)

Раз уж на то пошло, тогда уж разумней сделать парочку static inline функций, лямбы тут совершенно ни к чему.
+1
Я подумал, что уместо, т.к. обычно программистам на С++ такие вещи бывают интересны и понятны.

Там зачем там лямбды? :-)
0
— видимость лямбды ограничена функцией `matcher_accept`
— в коде не хватает проверок на `#ifdef NEXT_OP ...`

Не, я не спорю, макросы иногда очень выручают, но данный код был бы гораздо лучше без них. Тем более отказавшись от них, код, как мне кажется, стал бы чуть более безопасным и выразительным.
0
Ну, сложно сказать. Привычку для таких операций я приобрел, читая код популярных интепретаторов вроде Питона :-) Вот ifdef-ы я точно бы не стал здесь вносить, их совсем тяжело бывает читать.

Наверное, в плюсах я бы подумал над лямбда-функциями, но… Просто маленькие функции, которые легко заинлайнятся, тут сработали бы даже лучше.
0
Ничем :-)

Это сериализованный в байт-код недетерменированный конечный автомат. «Недетерминированность» здесь означает именно тот факт, что автомат может одновременно несколькими путям, эм, идти.
+1
Чисто теоретически, можно подобрать такое регулярное выражение, и такой вход, что каждый поток будет форкаться на каждом шаге, т.е. кол-во потоков будет удваиваться. Тогда программа либо упадёт из-за исчерпания лимита потоков, либо будет сильно тормозить, если лимит потоков довольно большой, а входная строка специально удерживает кол-во работающих потоков почти на пределе.
0
Вопрос хороший, да. :-)

В практической реализации при добавлении потоков инструкцией SPLIT или любым другим способом мы будем проверять, нет ли уже потока с данной инструкцией. Добавлять новый не имеет смысла — у него то же самое состояние (единственный указатель на текущую инструкцию).

То есть при длине сессии N и длине байт-кода M мы будем иметь максимум M потоков. Для целой сессии мы максимум O(N*M) раз побеспокоим наши потоки.
0
Интересное решение. К сожалению, оно не работает, если в регулярном выражении есть группы и после окончания сопоставления нужно будет также вернуть позицию каждой группы в строке.
0
в моей задаче был нужен сам факт достижения определенной точки регулярного выражения плюс, возможно, счетчик числа достижений, поиск групп там был скорее теоретической возможностью.

Однако, если, допустим, добавить инструкции SAVE, сохраняющие массив, почему вдруг мы не можем извлечь подгруппы..?
0
Потому что сейчас у каждого потока в контексте есть только текущий Instruction Pointer, а если делать с группами, то форк, который делает поток на уже существующий Instruction Pointer, должен иметь свои данные, и сжать два потока в один будет нельзя.
0

Вы не против, если я подумаю вслух?


У потока, строго говоря, три значения в контексте: instruction pointer, текущее событие, массив подгрупп. На каждом шаге обработки потоков текущее событие будет одинаково. Различаются IP и массивы подгрупп.


Пускай у нас регулярное выражение вида "(a*)b", которое соответствует байт-коду


SAVE 1
splitlabel:
SPLIT label1 label2
label1:
NEXT
EVENT a
JUMP splitlabel
label2:
SAVE 2
NEXT
EVENT b
MATCH

Предположим, мы матчим строку aab. На втором шаге у нас будет два потока, один из которых уже сматчил первое событие a. Надо добавить второй поток, у котрого тот же IP и будет то же текущее событие. Разница в том, что первый поток уже сохранил историю в виде SAVE 1. Дальше они будут работать одинаково.


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


Я согласен с вами в том смысле, что тут масса тонкостей, но по крайней мере часть из вопросов решить можно.

0
Тут есть над чем подумать. Я полагал, что недетерминированные автоматы всегда будут иметь экспоненциальные затраты памяти, но оказывается, что не всегда. Вопрос только, это частный случай или любой автомат можно так оптимизировать.
0
Я вот честно скажу, что тут надо смотреть детали, и этот прототип скорее сделан для проверки идеи.

В простом случае, который я с самого начала указал (нет подгрупп, просто не больше одного потока на каждый конкретный IP), такой недетерминированный автомат соответствует конечному, и это легко показать: пускай каждое состояние недетерминированного автомата в виде распределения потоков по разным IP соответствует одному состоянию конечного автомата. Обозначим его числом 1.Каждое следующее событие будет как-то менять распределение событий, и будет это делать предсказуемым способом. То есть мы можем и это новое состояние тоже поставить в соответствие одному распределению потоков, и обозначить числом. И т.д.

Словом, это один из стандартных методов построения DFA из NFA.

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

А вы интересуетесь темой?
0
Я интересуюсь алгоритмами поиска (автоматы, суффиксные деревья).

Стандартный способ построения DFA из NFA — это каждому множеству состояний NFA сопоставить одно состояние нового DFA. В общем случае, если у NFA n состояний, то у DFA их будет 2^n (кол-во подмножеств множества 1..n) и потребление памяти на хранение номера состояния будет расти экспоненциально.

Если в лоб сконвертировать NFA, получится DFA с большим кол-вом состояний и переходов, которые в явном виде хранить будет тяжко. А тут выходит какая-то хитрость, что состояние DFA не является классическим числом, а размазано по нескольким переменным (списку потоков), и это позволяет уменьшить накладные расходы. Этот подход интересно изучить подробнее, всегда ли можно его применять.
+1
Стандартных способов несколько.

В данном случае, опять же если не обсуждать вопрос групп и других вещей, которые очень легко делать именно на NFA, то это называется «создание DFA на лету». Т.е. мы в каком-то смысле можем закешировать те состояния, при не обязательно сразу строить весь автомат.

Если кеш — пара ключ-значение, то ключом будет пара из состояния списка потоков и входного события, а значением — следующее состояние списка потоков. Если пронумеровать состояния списка потока, и построить эти состояния для всех корректных входных событий, то получим DFA в кеше.

Профит — не обязательно строить полный DFA, можно просто частично его генерировать по мере необходимости.

Но лично меня интересует не DFA, а возможность слегка облегчить страдания NFA, на которую мы тут с вами обратили внимание.

Вообще, вот здесь очень много об этом и не только: swtch.com/~rsc/regexp

Обратите внимание на пункт «Caching the NFA to build a DFA» в первой части статьи.
0
Кроме того, мы ж в данном случае контролируем компилятор, то есть генерация адекватного байт-кода — наша ответственность.
0
Тут ничего не сделаешь, это проблема самого принципа.
Например, регулярное выражение (a|a|a)* и входная строка aaaaaaaaaaa… будут утраивать число потоков на каждом шаге.
0
Конкретно в данном случае регулярное выражение можно сжать на этапе преобразования дерева.

Опять же, предложенная оптимизация здесь будет работать, нет?
0
Сжатия — это эвристики, которые всегда можно обмануть. Например, если удаляются одинаковые под-выражения, то (a|a*)* уже не сожмёшь, потому что формально подвыражения неодинаковые.
0

Эт точно.


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


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

Only those users with full accounts are able to leave comments.  , please.