расширение / расслабление regexp

яннп, ты про группы? ()

И группы тоже. Формально задача именно такова как описано. И это реально прод задача (а не из пальца высосано). При «правильных» наводящих вопросах - я уверен я смогу упростить её дальше.

Правильно ли я понял, что в общем виде задача выглядит так:

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

Но должно легко программно проверяться.

нет легко не получится, имхо это вообще задача не решаемая за разумное время

Надо для каждого регекспа сгенерировать другой регексп, отличающийся от изначального так что результат матчинга подчиняется некоторому правилу?

Именно. Домен того с чем матчат заранее известен: каждый раз это будет одно слово содержащее от 1го до 4ёх символов из набора [0-9A-Z]. Мы уже договорились что оригинальные regexps будут начинаться с ‘^’. Я готов обсудить любые другие предлагаемые ограничения - что-то будет приемлемо, что-то не очень. «Легко проверяться» относилось именно к этому - к проверке того что оригинальный regexp является regexp’ом определённого вида.

Расширьте ваши сфинктеры

Я готов обсудить любые другие предлагаемые ограничения

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

Можно ли сформулировать эту задачу так: определить, существует ли строка, начинающаяся с символа A, которая матчится regexp X?

Хоть автор и написал, что полный перебор не устраивает, но кажется, что здесь нужно сделать заранее таблички соответствия, и по ним сразу выдавать ответ. Это если количество возможных X конечно :)

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

Можно ли сформулировать эту задачу так: определить, существует ли строка, начинающаяся с символа A, которая матчится regexp X?

Почти. То что вы называете символом ‘A’ это на самом деле один конкретно взятый из набора [0-9A-Z]. Точнее имеет место быть лупчик, и для каждого символа нужно понять - существует ли хотя бы для одного слова с него начинающегося матч с данным regexp или нет.

Пятый пункт требований невыполним

Забудьте про него, конкретно этот случай не интересен. Пусть все regexps начинаются с ‘^’.

В принципе, задача решаемая.

User:

Для регулярного выражения ^[ABC]DEF какой будет совместимый паттерн для матчинга только первого символа строки?

AI:

Регулярное выражение ^[ABC]DEF начинается с символа ^, что означает начало строки. Далее идёт символьный класс [ABC], который соответствует одному символу из перечисленных: ‘A’, ‘B’ или ‘C’. Затем следуют буквы ‘D’, ‘E’, ‘F’ в точно такой последовательности.

Если вы хотите создать регулярное выражение, которое будет матчить только первый символ строки из тех же опций (‘A’, ‘B’, ‘C’), то вам нужно убрать ‘DEF’ из исходного выражения. Получится следующее регулярное выражение:

^[ABC]

Это выражение совпадёт с первым символом строки, если он является ‘A’, ‘B’ или ‘C’, и не будет учитывать остальную часть строки.

В принципе, задача решаемая.

Осталось обобщить. С разумными ограничениями на виды regexp: случай «сферического коня в вакууме» меня не интересует, от слова совсем.

Осталось обобщить.

Обобщаю:

1. Определитесь с ЯП на котором будете писать код
2. Найдите для этого языка парсер регекспов в AST
3. Определите набор правил преобзования из AST до в AST после
4. Для вашего языка найдите тулзу конвертирующую AST в регексп если тулза из п2 этого не умеет
5. Profit

Не знаю, пригодится или нет, но в libfsm есть утилита re.
Для компиляции необходим bmake.

Обобщаю:

Дайте мне ответ на #3, и я от вас сразу отстану, обещаю :)

Дайте мне ответ на #3, и я от вас сразу отстану, обещаю :)

в смысле вот на это?

Определите набор правил преобзования из AST до в AST после

Это же ваша бизнес логика, я то её откуда знаю?

Это же ваша бизнес логика, я то её откуда знаю?

Ваш #3 это мой изначальный вопрос в закамуфлированном виде, ни больше ни меньше.

Осталось обобщить.

Так мой пример как раз и есть самый генерализованный из всех возможных.

Дайте мне

По губе.

Так мой пример как раз и есть самый генерализованный из всех возможных.

Да вы что, серьёзно? Покрыт всего один входной regexp, подчеркиваю - один, Карл.

Если тебе работать и это не Питон, то напиши лексер/парсер руками. А если теория, то ладно.

Дурик, это же пример. За тебя никто твои высосанные из пальца задачи решать не будет.

Ну хорошо, во что должно превратиться ^[A,B,C,D]{2}|[F,E,G]{3}?

Если тебе работать

Да что ж за день сегодня такой. Как только мне кто-нибудь расскажет на «простом русском» как из regexp X получить regexp Y удовлетворяющий условиям описанным в изначальной постановке задачи - я от вас всех отстану.

А пока что я ещё практически не одного уточняющего вопроса по делу не услышал: хотя бы имеем ли мы дело с posix regexps, перловыми или чем то ещё.

во что должно превратиться

В «^[A,B,C,D]».

как из regexp X получить regexp Y удовлетворяющий условиям описанным в изначальной постановке задачи - я от вас всех отстану

Этот вопрос ничем не хуже чем «Как из языка А получить язык Б, дайте мне краткий ответ и я отстану».

В «^[A,B,C,D]».

это противоречит условию «Y будет матчится на всех значениях где матчится X, но если подсунуть только первый символ аргумента»

В «^[A,B,C,D]».

Пациент совсем плох. Ты задачу эту сам себе из пальца высосал? Оно должно превратиться в ^[A,B,C,D]{2}|[F,E,G]{3} и никак иначе.

это противоречит условию

Я ‘|’ не заметил, и поправить не успел. «^[A,B,C,D,E,F,G]».

Опять мимо. ^[A,B,C,D] != ^[A,B,C,D]{2}. Второй паттерн будет матчится не на всех строках, на которых сматчится первый.

Может тебе по регуляр-очкам пойти почитать?

расширение / расслабление

Или порасширять-порасслаблять чего.

Или порасширять-порасслаблять чего

Вы нарываетесь на откровенную грубость. Ваши когнитивные способности и склонность к заднеприводности уже всем понятны. Брысь из этого треда.

А вот это? ^[ABCD]|FE|C.?D

Да не плачь. Ну сел ты в лужу - подумаешь. Всегда есть возможность реабилитироваться. Например, сказать: «извините, ребята, я ошибся». Попробуешь?

А вот это

^[ABCDF]

ПыСы. Помогло, если бы вы определились с синтаксисом: запятая это разделитель элементов в множестве, или нет?

Предположим имеется regexp X, можно ли из него получить regexp Y который будет матчится на всех значениях где матчится X

Кек:

$ echo OFFENDED | grep -E '^[ABCDF]' 
# нет ничего

$ echo OFFENDED | grep -E '^[ABCD]|FE|C.?D'
OFFENDED  # а тут есть

А Вы меня поймали. Ответ был на ^([ABCD]|FE|C.?D). На самом деле матчи «из середины» меня не интересуют. Да и ‘|’ по большому счёту сомнительную ценность имеет, но если легко покрывается - почему нет.

запятая это разделитель элементов в множестве, или нет?

а что стандарты говорят на этот счет? Синтаксис валиден

Вы, наверное, уже поняли, что так можно бесконечно продолжать? Регулярные выражения - это язык выражений, а не просто какой-то паттерн, нет никакого способа преобразовать выражение языка в другое выражение не определив все возможные преобразования для конкретного токена в синтаксическом дереве. Это я вам пытаюсь объяснить. Нельзя, не получится, забудьте. Вы скорее всего решаете задачу не с того конца вообще.

Вы, наверное, уже поняли, что так можно бесконечно продолжать?

В общем виде - наверное я соглашусь. Но меня интересует довольно узкое подмножество regexps X, и я склонен думать что при правильном выборе формальных ограничений на вид X - оно вполне себе решаемо. Например я могу гарантировать вид ^(something), где «something» не может содержать ‘.’, ‘*’, ‘?’. Это упрощает ситуацию? Вот это примерно то направление в котором хочется двигаться.

Это упрощает ситуацию? Вот это примерно то направление в котором хочется двигаться.

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

Если вы, как уже было сказано ранее, опишете свою проблему с самого начала

Хорошо, только тсс ;)

Задача очень прикладная. Имеется некий load-balancer с конфигурацией в виде routing-table. Каждое entry в этой табличке довольно сложного вида, и их под тысячу. Одно из полей entry это optional regexp, таких несколько сотен. По факту - все regexps сейчас матчат на первом символе. И для некоторых entries этого стало не хватать (надо разделять нагрузку дальше). И всё бы ничего - но часть софта хочет знать если есть потенциальные совпадения имея только первый символ. И я даже могу заставить это работать с минимальными изменениями добавив там где хочется большей гранулярности второй «relaxed regexp» «ручками». И наверное этим всё и кончится. Но было интересно можно ли малой кровью это сделать более operator friendly и менее error prone. Как-то так.

понял мало честно говоря, обычно балансировщики распределяют нагрузку по одному из нескольких алгоритмов - round robin, hash by key, least connections. У вас хеш-функция что-ли основана на regexp?

Очень не хватает нормального описания того, что вам нужно.

Складывается впечатление, что у вас есть набор правил, для каждого из которых есть свой regex. Скажем, для правила №1 это «^[AB]CD», для правила №2 это «^[BC]CD», для правила №3 это «^[DE]JZ».

И вы хотите имея только первый символ узнать, какие из этих правил следует проверять.

Например, если пришел символ «A», то это правило №1 (т.к. «^[AB]CD»). Если пришел символ «B», то это и правило №1, и правило №2 (т.к. «^[BC]CD»).

В теме регулярок не копенгаген, мимо крокодил, но не смог удержаться, чтобы не посетовать на нечеткую постановку задачи :(

У вас хеш-функция что-ли основана на regexp?

Возможно load-balancer был неудачным термином. Пусть будет router. Конкретные данные заворачиваются туда где их ждут и готовы обработать, а не туда где в моменте нагрузка меньше.

Конкретные данные заворачиваются туда где их ждут и готовы обработать, а не туда где в моменте нагрузка меньше.

Давайте ещё проще. У вас есть некий поток сообщений. Есть некий пулл обработчиков этих сообщений. Есть некий роутер посередине, который для каждого сообщения выбирает обработчика из пулла и направляет сообщение ему. Правильно?

Например, если пришел символ «A», то это правило №1 (т.к. «^[AB]CD»). Если пришел символ «B», то это и правило №1, и правило №2 (т.к. «^[BC]CD»).

Да, именно так.

Ну построй конечный автомат и вытащи из него все состояния, достижимые из начального за один переход (вместе с самими переходами).

Ты же вроде не кодомакака (ну или по крайней мере усиленно себя им противопоставляешь на ЛОРе). Задача с точки зрения CS тривиальная.

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

Тогда «решение», что называется «в лоб»:

• вам нужен некий тестер regex-ов, который бы получив символ возвращал бы вам true, если regex-у нужен следующий символ, и false, если regex сразу отвергает полученный символ;
• для всех своих правил вы создаете такие «тестеры» однократно при старте;
• так же однократно при старте вы делаете цикл по символам [0-9A-Z] и для каждого символа проверяете каждый тестер. Те regex-ы, для которых тестеры вернули вам true, для i-го символа выстраиваете в цепочку (список, множество).

Тем самым у вас получается таблица, где индексом является символ, а значением – цепочка regex-ов для соответствующих правил (возможно, пустая цепочка).

Задача сводится к тому, как сделать такой «тестер» :)

Можно решить ее, например, самостоятельно написав regex парсер :)

Регулярки ограничены ASCII или используют полный набор Unicode-символов?

Если первое, то можно для каждого из 128 символов найти список регулярок, которым он потенциально удовлетворяет.

Регулярки ограничены ASCII

Не просто ASCII, а малым саб-сетом [0-9A-Z].

найти список регулярок, которым он потенциально удовлетворяет

Дык, как именно это сделать я целую страницу и пытаюсь выяснить.

Можно решить ее, например, самостоятельно написав regex парсер :)

У std::regex_search есть перегрузка, принимающая итераторы:

template< class BidirIt,
          class CharT, class Traits >
bool regex_search( BidirIt first, BidirIt last,
                   const std::basic_regex<CharT,Traits>& e,
                   std::regex_constants::match_flag_type flags =
                       std::regex_constants::match_default );

Можно сделать свою пару итераторов – один будет передаваться в качестве first, второй в качестве last.

Тот, который используется в качестве first, в своем operator* будет возвращать тестируемый символ. В своем operator++ будет выставлять булевый признак того, что следующий символ регулярке потребовался.

Тогда, для i-го проверяемого символа создаем first и last. Вызываем regex_search. Результат regex_search игнорируем. Но смотрим, выставил ли first признак того, что регулярке потребовался второй символ. Если выставил, значит эта регулярка в i-ом проверяемом символе заинтересована.

:)