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. Я забыл упомянуть про обратный ход. Есть такая движуха, когда алгоритм ничего не находит, двигаясь прямо :). По этому лучше вместо . использовать [^\\\\]. (см. последний пример) В этом случае, нахождения в строке "\" не произойдёт, как и должно быть.