Регулярные выражения

Russian main discussion
  • Author
  • Message
Offline
Site Admin
Posts: 6311
Joined: Thu Jul 06, 2006 7:20 am

Post by Instructor »

DV
Для примера - как найти?

Code: Select all

.*
или

Code: Select all

[^\n]*

YuS
Offline
Posts: 512
Joined: Sun Sep 15, 2013 8:25 am
Location: 013 в Тентуре, семь по Спирали, налево от Большой Медведицы

Post by YuS »

DV wrote: Поясняю свою мысль картинкой:
Ваша мысль, как раз, понятна, но это ведь, всё равно, тот же поиск вперед только в определенных, ограниченных пределах, а здесь, как уже сказал Instructor:
Instructor wrote: Сложность не в определении области цикла, а в самом механизме сравнения.
К тому же, посчитайте сколько раз отработает парсер при таком поиске? Ведь каждая строка, кроме первой и последней будет парситься дважды (плюс ещё механизм сравнения с точками возврата), в отличие от одного прохода с начала текста и до курсора...
В чём тут плюс? Если искомое вхождение находится рядом с курсором - да, поиск будет более быстрым, но ведь это необязательно во всех случаях, искомое может находиться и в самом начале.
Кроме того, при реализации такого поиска придется ломать общую методику работы регэкспов, т.к. уже не будет работать многострочный поиск, как минимум и к тому же придется выключать из поиска подстроки неопределенного размера (квантификаторы *, + и т.п.). Стоит ли овчинка выделки?

DV
Offline
Posts: 1250
Joined: Thu Nov 16, 2006 11:53 am
Location: Kyiv, Ukraine

Post by DV »

YuS wrote:Ваша мысль, как раз, понятна, но это ведь тот же поиск только в определенных, ограниченных пределах
Напоминаю, с чего я всё это начал:

Code: Select all

if (IsVariableMultiLineRegEx(regEx)) 
{ 
  // ищем от начала файла - как сейчас 
} 
else 
{ 
  // ищем назад (снизу вверх) 
}
Другими словами, когда регулярка такова, что нельзя определить, со сколькими строками текста она может совпасть, то, несомненно, текущий подход к поиску является максимально правильным.
В том же случае, когда количество строк текста, с которыми совпадёт регулярное выражение, известно заранее - то есть является константой, полученной путём простого анализа регулярного выражения - то наиболее оптимальным будет предложенный мной поиск снизу вверх, потому что он будет просматривать не весь документ сразу, а будет просматривать его как бы "узкими окнами" от конца к началу.

P.S.
Если на практике окажется, что для константно-многострочных регулярок поиск снизу вверх окажется медленнее, чем поиск от начала документа вниз, условие в IsVariableMultiLineRegEx всегда можно будет подкорректировать. Как минимум, однострочные регулярки при поиске снизу вверх точно дадут куда лучший результат, чем при поиске от начала документа вниз. Что же касается двух и более -строчных регулярок, тут нужно проверить на практике. Полагаю, с двухстрочной регуляркой, даже если она совпадёт только с самой первой строкой в документе (а это худший случай для поиска снизу вверх), время поиска снизу вверх не будет сильно отличаться от поиска с начала документа вниз. Полагаю, критерием для сравнения можно выбрать совпадение посередине документа. При схожих временах поиска я бы отдал предпочтение поиску снизу вверх в таком случае - поскольку если уж пользователь ищет снизу вверх, то он же предполагает, что искомая строка находится ближе к текущей строке, чем к началу документа, не так ли?

Функция анализа регулярного выражения будет выглядеть как-то так:

Code: Select all

// TODO: consider "(\n|abc)*" situations

// returns max lines that the cszRegExp matches
// -1 means unpredictable multi line match (e.g. "[\n]+")
int AnalyzeRegExp(const wchar_t* cszRegExp, int isDotMatchingNewLine)
{
    enum eStateFlags {
        reNormal           = 0,
        reEscapedJustFound = 0x0001, // just encountered '\'
        reEscaped          = 0x0002, // current char is escaped (after '\')
        reCharSet          = 0x0010, // inside [...]
        reNewLineJustFound = 0x0100, // just encountered '\n' or '\r' (or '.')
        reNewLineChar      = 0x0200, // previous char is a new line char
        reNewLineInCharSet = 0x0400, // a new line char inside [...]
        reDone             = 0x8000  // done
    };
    
    int nRegExpLines = 1;
    unsigned int state = reNormal;

    for (; state != reDone; ++cszRegExp)
    {
        const wchar_t ch = *cszRegExp;
        if (ch == 0)
        {
            state = reDone;
        }
        else if (ch == L'\\')
        {
            if (!(state & reEscaped))
                state |= reEscapedJustFound;
        }
        else if (ch == L'n' || ch == L'r')
        {
            if (state & reEscaped)
                state |= reNewLineJustFound;
        }
        else if (!(state & reEscaped))
        {
            if (ch == L'[')
            {
                state |= reCharSet;
            }
            else if (ch == L']')
            {
                if (state & reCharSet)
                {
                    state ^= reCharSet;
                    if (state & reNewLineInCharSet)
                    {
                        state ^= reNewLineInCharSet;
                        state |= reNewLineJustFound;
                    }
                }
            }
            else if (ch == L'+' || ch == L'*')
            {
                if (state & reNewLineChar)
                {
                    nRegExpLines = -1;
                    state = reDone;
                }
            }
            else if (ch == L'.')
            {
                if (isDotMatchingNewLine)
                    state |= reNewLineJustFound;
            }
        }

        if (state & reNewLineJustFound)
        {
            state ^= reNewLineJustFound;
            if (state & reCharSet)
            {
                state |= reNewLineInCharSet;
            }
            else
            {
                state |= reNewLineChar;
                ++nRegExpLines;
            }
        }
        else if (state & reNewLineChar)
            state ^= reNewLineChar;

        if (state & reEscapedJustFound)
        {
            state ^= reEscapedJustFound;
            state |= reEscaped;
        }
        else if (state & reEscaped)
            state ^= reEscaped;
    }

    return nRegExpLines;
}

DV
Offline
Posts: 1250
Joined: Thu Nov 16, 2006 11:53 am
Location: Kyiv, Ukraine

Post by DV »

Что-то реализация функции IsVariableMultiLineRegEx на практике перестаёт казаться мне удачной идеей. При написании такой функции с нуля я остановился на группировке () и альтернативах |. Обработка и того, и другого попахивает либо рекурсией, либо вложенными циклами, что, хм, всё усложняет. К тому же я не уверен, что не осталось других синтаксических конструкций, которые тоже надо учесть.
Так что если достоверную информацию о максимальном количестве строк, с которыми совпадёт регулярка, нельзя извлечь после PatCompile, то идею с IsVariableMultiLineRegEx придётся отложить.
Но у меня есть другая гениальная идея.
Почему бы при поиске с регулярками снизу вверх не обрабатывать большие файлы по частям? Грубо говоря, делим файл, к примеру, на 10 частей - и сначала ищем в последней части снизу, затем в предпоследней (в случае мультистрочного поиска захватывая и строки из частей, находящихся ниже, если это необходимо) и т.д.? При этом при каждом переходе на часть, находящуюся выше, мы запоминаем позицию начала предыдущей части, чтобы первая строка текста, совпавшая с регуляркой, никогда не была ниже позиции начала предыдущей, уже обработанной части.
Говоря проще, при переходе от одной части к другой мы как будто смещаем начало документа всё выше. А поскольку мы каждый раз запоминаем позицию начала предыдущей части, то мы не повторяем поиск в уже обработанной ранее части документа.
Важное примечание: это будет работать при отключенной настройке ". совпадает с \n". Если же эта настройка включена, то элементарное ".+" совпадёт со всем документом, и поэтому должен использоваться поиск от начала документа, как сейчас. А с другой стороны, если в регулярке не встречается ни .+, ни .*, ни \n или \r, то какой смысл в поиске от начала документа? В этом случае лишь пустая трата времени.

Как вариант, можно взять приведенную выше функцию AnalyzeRegExp, и использовать поиск снизу вверх только если она возвращает 1. При этом саму функцию можно упростить, поскольку мы уже не ставим перед собой цель цель подсчитать точное количество строк, с которым может совпасть регулярка, а лишь проверяем её на наличие конструкций, которые делают её неоднострочной.
Это уже вторая гениальная идея за сегодня :)

Offline
Posts: 176
Joined: Sat Dec 24, 2011 4:05 pm

Post by F. Phoenix »

Как в coder-файле проверить кол-во символов на четность?

Составил регулярку для подсветки строк между кавычками с учетом экранирования (нужно именно через QuotesRE):

Code: Select all

1	`(")("|.*[^\\]")`                `\0=(0,${STR},0)`
и все бы ничего, да глючит, к примеру, при двух слешах перед закрывающей кавычкой: "блаблабла\\".

YuS
Offline
Posts: 512
Joined: Sun Sep 15, 2013 8:25 am
Location: 013 в Тентуре, семь по Спирали, налево от Большой Медведицы

Post by YuS »

F. Phoenix wrote:Как в coder-файле проверить кол-во символов на четность?
Посчитать символы и разделить на 2?
F. Phoenix wrote: Составил регулярку для подсветки строк между кавычками с учетом экранирования (нужно именно через QuotesRE):

Code: Select all

1	`(")("|.*[^\\]")`                `\0=(0,${STR},0)`
и все бы ничего, да глючит, к примеру, при двух слешах перед закрывающей кавычкой: "блаблабла\".
QoutesRE работает построчно, т.е. проверка идет по очереди в каждой строке.
Регулярка означает следующее:

Code: Select all

Совпадает если: 
присутствует символ двойная кавычка '"', за ним сразу следует либо ещё одна кавычка '"', либо несколько любых символов (квантификатор жадный, т.е. захватывается максимально возможная строка) и любой символ кроме обратного слеш '\', за которым сразу следует двойная кавычка '"'.
Т.е. непонятно определение "глючит" - что не так-то?
У меня всё подсвечивает так, как написано в регэкспе.

Offline
Posts: 176
Joined: Sat Dec 24, 2011 4:05 pm

Post by F. Phoenix »

\ - символ экранирования, означающий, что следующий за ним символ должен по особому обрабатываться. В том числе последовательность \" означает, что данная кавычка является частью строки, а не маркером ее завершения. Последовательность \\ преобразуется в сам символ \.

К примеру, вывод строки на консоль в C#:

Code: Select all

Console.WriteLine("Ошибка при открытии файла \"C:\\MyFile.txt\"");
Выведет фразу:
Ошибка при открытии файла "C:\MyFile.txt"
Ну и вот, для подсветки строки нужно определить, экранирована ли закрывающая кавычка. А экранирована она будет при условии нечетного кол-ва обратных слешей перед ней.

Такое правило без регулярок работает прекрасно:

Code: Select all

Quotes:
;=======================================================
;Флаги  Стиль   Цвет    Цвет   Начало     Конец   Символ
;       шрифта  текста  фона   диапазона  диапаз. экран.
;=======================================================
0       0       ${STR}  0      `"`        `"`     `\`
Но мне нужен аналог для секции QuotesRE.
Да никакой ошибки в обработке выражения-то нет. Проблема в составлении.

Offline
Posts: 176
Joined: Sat Dec 24, 2011 4:05 pm

Post by F. Phoenix »

Похоже, нашел выход:

Code: Select all

"([^\\]|\\.)*?"

Offline
Posts: 582
Joined: Mon Apr 08, 2013 9:50 pm
Location: Win7SP1x64, APx64

Post by Drugmix »

del.
Last edited by Drugmix on Tue Nov 29, 2016 9:57 am, edited 1 time in total.

YuS
Offline
Posts: 512
Joined: Sun Sep 15, 2013 8:25 am
Location: 013 в Тентуре, семь по Спирали, налево от Большой Медведицы

Post by YuS »

F. Phoenix wrote: Ну и вот, для подсветки строки нужно определить, экранирована ли закрывающая кавычка. А экранирована она будет при условии нечетного кол-ва обратных слешей перед ней.
А, это уже более понятно, а то ведь подумалось, что баг в AP...
F. Phoenix wrote: Но мне нужен аналог для секции QuotesRE.
Да никакой ошибки в обработке выражения-то нет. Проблема в составлении.
Да, тогда надо подумать над шаблоном.

Этот хорош:

Code: Select all

"([^\\]|\\.)*?"
но, вот тестовый массив, на котором этот шаблон не вполне правильно работает:

Code: Select all

"тест" проверка тест\" тест
"тест" проверка тест\" тест тест
"тест" проверка "тест\" тест тест"
abc"тест" проверка "тест" тест "тест"
abc\"тест" проверка "тест\" тест "тест"
abc\\"тест" проверка "тест\\" тест "тест"
abc\\\"тест" проверка "тест\\\" тест "тест"
abc\\\\"тест" проверка "тест\\\\" тест "тест"
abc\\\\\"тест" проверка "тест\\\\\" тест "тест"
Предлагаю вот такой:

Code: Select all

1	`(?<=[^\\])(?:(\\)\1)*\K"([^\\]|\\.)*?"`	`\0=(0,${STR},0)`

Offline
Posts: 176
Joined: Sat Dec 24, 2011 4:05 pm

Post by F. Phoenix »

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

Склоняюсь к варианту, что в целом не считать, т.к. свойство символа экранирования бекслеш обретает внутри строк, а за их пределами может работать, к примеру, в качестве оператора. Хотя это зависит от конкректного синтаксиса. Но в моем случае (синтаксис Gettext) бекслеш перед открывающей кавычкой вообще недопустим.

Offline
Posts: 582
Joined: Mon Apr 08, 2013 9:50 pm
Location: Win7SP1x64, APx64

Post by Drugmix »

del
Last edited by Drugmix on Tue Nov 29, 2016 9:57 am, edited 1 time in total.

YuS
Offline
Posts: 512
Joined: Sun Sep 15, 2013 8:25 am
Location: 013 в Тентуре, семь по Спирали, налево от Большой Медведицы

Post by YuS »

F. Phoenix wrote:Ну, такой шаблон по поведению ближе к тому, что я написал для секции Quotes, но единственная разница между ними, как я понимаю, это считать ли открывающую кавычку экранированной, если бекслеш стоит перед ней.
Не только. Это ещё и ответ на вопрос об определении четности символов, который был задан выше.
И если я правильно понял, то, как раз, и нужна была реализация работы на регэкспах близкая к возможностям Quotes. Полного соответствия получить, естественно, невозможно, в силу особенностей работы QuotesRE, но получилось то, что получилось. :)
F. Phoenix wrote:Но в моем случае (синтаксис Gettext) бекслеш перед открывающей кавычкой вообще недопустим.
Правила правилами, а вероятность ошибок никто не отменял...

Code: Select all

"тест" проверка тест\\"тест тест"
В общем, мое дело было предложить...
Last edited by YuS on Mon Nov 28, 2016 6:29 pm, edited 1 time in total.

YuS
Offline
Posts: 512
Joined: Sun Sep 15, 2013 8:25 am
Location: 013 в Тентуре, семь по Спирали, налево от Большой Медведицы

Post by YuS »

Drugmix wrote: Внутри диапазонов экранировать символы не надо.
Понимаю, что понедельник - день тяжелый, но дублировать посты не требуется.
Вы просто попробуйте не экранировать бакслеш... а потом уже отписывайтесь, что не надо. :)

Offline
Posts: 176
Joined: Sat Dec 24, 2011 4:05 pm

Post by F. Phoenix »

Code: Select all

Code:
"тест" проверка тест\\\"тест тест"
Вторая строка подсвечивается с шаблоном

Code: Select all

"([^\\]|\\.)*?"
но не подсвечивается с

Code: Select all

(?<=[^\\])(?:(\\)\1)*\K"([^\\]|\\.)*?"
и Quotes: `"` `"` `\`
Post Reply