Regexp — это «язык программирования». Основы

    Несколько лет назад я думал, что regexp осуществляет линейный поиск по тексту, но какое моё удивление было, когда я понял, что это не так. Тогда я убедился на собственном опыте, что от простой смены местами а и b в схеме (...a...)|(...b...) поменялся полностью результат.

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


    Ветвления в regexp

    Регулярные выражения работают по схеме направленного дерева.
    Например ветвление (a ...)|(b ...)|(c ...) можно записать:
    If (char=='a'){
    ...
    }else if (char =='b'){
    ...
    }else if (char =='c'){
    ...
    }




    Именно поэтому перестановка местами 'b ...' и 'a ...' влияет на результат – потому что здесь расставляются приоритеты выполнения (в каком порядке поставишь, так и будет выполняться).

    Именно поэтому стоит следить за тем, что приоритетнее и стараться условия делать оптимально вытесняющими друг друга.
    Причём выполняться всё, что за 'a' будет при условии того, что всё до 'a' (включая 'a') выполнено.

    Пишем парсер кавычек

    Рассмотрим простой пример.

    Давайте возьмём подопытную строку 123"ABC\"D\EF"GHI""\"KEY и начнём над ней издеваться:

    Первое, что появляется в голове — /".*"/ выражение. Оно будет действовать по алгоритму:
    1) Производим поиск первой одной "
    2) Пока у нас любой символ (в том числе и "), мы проходим дальше
    3) В конце должна быть тоже "
    В результате, правильно, мы получили "ABC\"D\EF"GHI""\".
    То есть нашли первую кавычку. Дальше, пока выполнялось условие брали следующие символы (в том числе и ") и делали, пока последней не оказалась ".

    Теперь давайте усовершенствует алгоритм – сделаем, чтобы искался любой символ, исключая ".
    Наше регулярное выражение превратилось в /"[^"]*"/. Оно будет действовать по алгоритму:
    1) Производим поиск первой одной "
    2) Пока у нас любой символ не равный ", мы проходим дальше
    3) Наткнулись на " – конец.
    Результат стал более верным – были выбраны "ABC\", "GHI", "\".



    Теперь надо нам определять символы \" оставлять их внутри, не считая это концом.
    Для этого необходимо изменить условие [^"], добавив туда ещё одно сравнение с \".
    Выглядеть это будет теперь так — /"([^"]|(\\\\"))*"/.

    Мы добавили в условие \\\\". Почему четыре '\'? Потому что каждые две \\ в строке = одной \, то есть мы записали \\ в строку запроса, да и в regexp используются выражения \w,\d,\s итд, по этому, чтобы поставить одну \, необходимо использовать \\.

    Но наше выражение ещё не будет работать.
    Почему не будет? Не будет работать, потому что сначала происходит условие [^"], а затем, если оно не выполняется, то идёт сравнение с \":
    1) Производим поиск первой одной "
    2) Пока у нас любой символ не равный ", мы проходим дальше,
      если он равен " (не выполнилось предыдущее условие), мы сравниваем его c \ (само собою он не равен)
    3) Наткнулись на " – конец.

    По этому правильно будет поменять условия местами — /"((\\\\")|[^"])*"/, чтобы сначала проверялся \", а потом любой другой символ не ".
    Теперь всё правильно работает и результат выбирает "ABC\"D\EF", "". Похоже на магию, да? Алгоритм заработал правильно.



    Сразу скажу, что вариант [^"\\\\]|(\\\\") не подходит, потому что когда алгоритм найдёт \, он перейдёт ко втором условию \" (за \ должен быть "), что не выполнится в нашем случае \E. Для этого необходимо будет поставить условие — если после \ идёт ", то пропускаем символ, иначе идём дальше. То есть выражение приобретет вид /"([^"\\\\]|(\\\\(")?))*"/.

    Совершенствуем алгоритм

    Давайте добавим парсинг символа '.
    В регулярных выражениях можно использовать найденные символы в будующих проверках – этим мы и воспользуемся:

    Начнём наше выражение с поиска любого символа кавычек/апострофа /(["'])... – найденная кавычка попадёт у нас в спец-переменную \1, которую мы можем дальше использовать в проверке. В данном случае, у нас туда будет попадать один символ — либо ", либо '. В конце, чтобы проверить закрытие это кавычки, необходимо использовать ...(\1)/. Внутри, проверять не на отсутствие ", а на отсутствие \1.

    Оптимизируем немного код и получаем /(["\'])(\\\\\1|.)*?\1/. Надо заметить, что я использовал ? (lazy) в выражении – для добавления в условие последней \1 – то есть, сейчас ко всему прочему происходит ещё проверка на ".
    Почему я сделал это вместо [^\1]? Потому что \1 не работает в [].

    Сейчас код делает следующее:
    1) Производим поиск первой одной " или ' (записываем его в \1)
    2) Следующий символ " или '?
      если нет, тогда следующие два символа равны \" или \'(в зависимости от начала)
      если нет, тогда просто пропускаем символ
    3) Наткнулись на " – конец.
    И выражение 1'2'a3"A'BC\"DEF"GHI""\"KEY парсится в '2', "A'BC\"DEF", "".

    Данное выражение можно использовать для выделения строковых областей внутри любых объектов.
    Например, function:
    function a(){
    b="{}";
    }

    Добавляем фигурные скобки в выражение /{((["\'])(\\\\.|[^\\\\])*?\2|.)*?}/. Это выражение теперь выберет {b="{}";}. Так как появились ещё одни скобки в выражении, то \1 сдвинулось в \2 – следите за этим обязательно.

    Upd. Я забыл упомянуть про обратный ход. Есть такая движуха, когда алгоритм ничего не находит, двигаясь прямо :). По этому лучше вместо . использовать [^\\\\]. (см. последний пример) В этом случае, нахождения в строке "\" не произойдёт, как и должно быть.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 35

      0
      Я думаю регэксы надо вставлять в <code>
        0
        Спасибо. Уже исправил.
      • НЛО прилетело и опубликовало эту надпись здесь
          0
          Я считаю, что хорошо «открыть» блог именно с основ.

          Причём я несколько лет программировал, не понимая этих озов. Уверен, что есть люди, которые возможно тоже их не понимают до конца.

          p.s. Чем вам пример не понравился, объясните?
            0
            Во-первых, азов, а во-вторых, основы регулярных выражений надо учить по Хопкрофту, упомянутому тредом ниже. Или по Ахо-Ульману, не суть. Это не та тема, по которой можно что-то «примерно знать».
              +1
              B[ надо учить по книге человека, который их придумал — Дж.Фридл. Как называется книга думаю сами догатаетесь. А статья — да фигня полная. Автор еще сам толком не разобрался как оно работает, но уже других учит. Смешно, право слово.
                0
                Вадим, хабр нуждается в хороших статьях. Не надо смеяться над людьми, которые своими (возможно не полными) знаниями открывают другим путь на новые направления.

                Просто садьте и напишите хорошую статью — тем более раз вы разбираетесь лучше меня в этом вопросе:
                1) Она будет полезна для всех нас.
                2) Не будет появляться статей от менее осведомленных людей.

                p.s. Я за последний месяц видел всего 2-4 хороших статей по Web программированию. От нас зависит качество и количество этих статей.
                  +1
                  На счет качества статей, я полностью с вами согласен. Но это мне кажется, что это не статьи плохие, это аудитория хабра помолодела и пишет материалы, которые _ей_ интересны. Это во-первых, а во-вторых, я уже написал, что лучший способ изучить регулярные выражения, это прочитать книгу Фридла. Писать статью, которая будет заведомо хуже считаю мартышкиным трудом. Лучше автора я все равно этого не сделаю, а строчить заметки, в виде пересказа книги, да еще и сжатого (т.к. главы в оригинале немаленькие), это глупо, т.к. материал до читателя не донесет, а автор таких писулек только зря потеряет время.

                  Я конечно знаю, что на хабре присутствуют люди, которые обожают переписывать маны и выдавать тут за статьи, но я такой подход не одобряю: читатель интересующийся темой и так их найдет и прочитает, а остальным эти самые маны не нужны совершенно.
            • НЛО прилетело и опубликовало эту надпись здесь
              0
              Разжовывать нужно для тех, кто не знает, с чего начать. В числе таких людей — я.

              А автору — большое спасибо. Вы на редкость понятно пишете :)
              +2
              Для того чтобы действительно понять.
              www.ozon.ru/context/detail/id/3715578/
                +1
                Именно. Чтоб хорошо знать регэкспы, надо иметь хоть какое-то понятие об автоматах. Иначе ошибки неизбежны.
                По этой книге у нас преподавали теорию автоматов, и весьма неплохо преподавали.
                  –1
                  Согласен. Именно понятие, что regexp это система КА, мне поставило всё на свои места. :)
                    +1
                    Любое регулярное выражение, кстати, можно преобразовать в ДКА, причём в один, не систему :)
                    Ну и наоборот тоже. Я Вам настоятельно рекомендую почитать Хопкрофта и «Теорию синтаксического анализа» Ахо и Ульмана, там довольно понятно написано.
                      +1
                      Теоритически, конечно да, но пока вроде никто не предложил эффективного алгоритма работы с бэкреферренсами. Потому и перл, питон и пр. не используют ДКА в своих реализациях. Коротенькая статья Расса Кокса на эту тему.
                +3
                Во-первых, регулярные выражения никак не могут заменить язык программирования потому, что regexpы задают конечный автомат, а обычные языки задают машину Тьюринга. (конечный автомат, это машина Тьюринга, но только с одной ячейкой памяти)

                Во-вторых, очень жалко, что не расказано о действительно важных свойствах регулярных выражений. Например, если выражение R1 допускает строку S1, а выражение R2 допускает S2, то выражение R1R2 допускает S1S2. Иногда подобные вещи очень упрощают написание regexpoв, вот про это было бы интересно почитать.
                  +3
                  А еще с помощью регулярных выражений можно решать уравнения :)
                  blog.stevenlevithan.com/archives/algebra-with-regexes
                    +1
                    А я вот не понял откуда взялись 4 слэша :(
                    Как я себе представляю \\\" внутри регулярного выражения соответсвует символам строки \" так как \ и " не обозначают специальных групп.
                    Проверил свою догадку на приводимом в прошлом топике движке gskinner.com/RegExr/ — все заработало именно с тремя слэшами. Откуда 4й?
                      0
                      3 слеша тоже будут работать… \
                      Просто правильнее 4, потому что каждые 2 слеша преобразуются в 1, когда идёт преобразование в строку.
                        0
                        языки разные бывают, да и регулярные выражения можно и вне языков встретить
                          0
                          тогда стоит писать \\"
                      +4
                      По регулярным выражениям настоятельно рекомендую к прочтению Фридла www.ozon.ru/context/detail/id/4066500/. Эта книга действительно учит писать регулярки, после ее прочтения подход к их написанию радикально меняется. Если конечно вы еще не достигли просветления другими способами.
                        0
                        Да, мне повезло что знакомство с регялрными начал с этой книги. Советую всем.
                          –1
                          Спасибо за совет!
                          +3
                          а) ваше использование символов слеша и характер экранирования говорит о вашей привязке к некоторому инструменту, но вы не учитываете, что в других — выражения могут выглядеть по другому. Потом рациональнее было бы писать выражение в таком виде, как оно должно быть, а каждый уже, вводя в свой инструмент, по необходимости, занимался бы экранированием и пр.
                          б) не совсем логично учитывать экранированные символы кавычек, забыв о других экранированных последовательностях. пусть уже будет \. тогда и никаких проблем с \\"

                          мой вариант:
                          (['"])(\\.|.)*?\1
                            –1
                            Спасибо за ваш вариант, поучительно.

                            По поводу вашего первого замечания, я с вами согласен — в будующих статьях учту этот момент.
                              0
                              Снова «будующих»… :(

                              Исправьте хотя бы в статье на «будущих».

                              //PS: Сорри за «грамма наци»
                            +2
                            По этому правильно будет поменять условия местами — /"((\\\\")|[^"])*"/, чтобы сначала проверялся \", а потом любой другой символ не ".
                            Теперь всё правильно работает и результат выбирает «ABC\»D\EF", "". Похоже на магию, да? Алгоритм заработал правильно.

                            1. «Алгоритм» не заработал правильно.
                            Например, в строке
                            "\"
                            он найдет (будет соответствие регексу) следующее:
                            "\"
                            однако, здесь нет строки в кавычках, т. к. здесь есть открывающая кавычка, какой-то текст (\"), а вот закрывающей кавычки нет.

                            2. Вы пытаетесь из «неправильного» регекса сделать «правильный» перестановкой элементов в альтернативе (A|B). Создается впечатление, что вы не понимаете фундаментального принципа:
                            Цепочка c соответствует регексу
                            A|B
                            тогда и только тогда, когда она соответствует регексу
                            B|A

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

                            3. Ваше описание происходящего в «Сейчас код делает следующее: ...» опять-таки описывает ситуацию лишь в случае, когда соответствие будет найдено. И совершенно упускается из виду такая вещь, как «обратный ход» движка регексов. А ведь если движок регексов при движении «вперед» на каком-то этапе найдет соответствие альтернативе A|B в виде A, но затем дойдет до конца и не обнаружит соответствия всему регексу, то он вернется назад и будет в том же месте, где ранее нашел A, пытаться искать B. И непременно найдет в вашем случае, когда A == \", а B == [^"] (т. к. \ соответствует [^"] ). В общем, такая важная вещь, как обратный ход, полностью ускользает из поля зрения новичков (тех, кто из этой заметки мог бы, по вашему мнению, что-то полезное почерпнуть).
                              –1
                              Я был-бы рад, если вы напишете ещё одну статью, дополняющую мою.
                              Вы во всём правы, просто я попытался максимально ясно объяснить, что происходит. С обратным ходом, она у меня вызывала больше вопросов, нежели понимания. По этому я думал продолжить эту статью (как раз с вашего примера объяснить почему оно не работает или работает не верно).

                              Я считаю, что стоит объяснять сложные вещи по шагам.

                              p.s. Карма для того, чтобы вам написать статью, уже есть :)
                                0
                                Спасибо за карму.

                                Я мог бы попробовать написать небольшую заметочку. Не могу обещать, что сегодня или завтра, но постараюсь на этой неделе. Однако, мне не очень интересно писать статью для начинающих. Скорее, это будет для тех, кто уже кое-что знает.
                                  –1
                                  Главное, чтобы было всё понятно. А новички уже — разберуться )
                                    0
                                    Насколько я понял, с моей кармой я могу писать что-то только в личный блог, в «Регулярные выражения» не могу. Так что опубликовал свою заметку тут: antonshcherbinin.habrahabr.ru/blog/55863/
                                    Насчет «чтобы было всё понятно» — это вряд ли. Как говорится, «пишем как мОгем»… или «могЁм»… ;-)
                                      0
                                      Нормально могёте… и вполне понятно. Только раз пошла такая пьянка с Возвратами, я-бы остановился на них поподробнее и разобрал ещё пару примеров, где они себя проявляют :)
                              0
                              Так не проще?: ("|')(.*?[^\\])\1
                                0
                                В вашем случае:
                                "\\«b»с«d» => "\\«b», «d»

                                в случае (["\'])(\\.|[^\\])*?\1:
                                "\\«b»с«d» => "\\", «c»

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

                              Самое читаемое