28 мая 2014
Кравченко Виктор

Парсим HTML: Игнорирование подобных вложенных конструкций, или рекурсия в регулярных выражениях

VB.NET Регулярные выражения
регулярные выражения, Regex, RegExp, рекурсия, вложенные конструкции, сбалансированные определения групп, balancing group definition
01 На заметку:
Здесь и в других темах, касающихся использования регулярных выражений, очень сильно помогают Regex-помощники — простые программы по тестированию регулярных выражений. О такой программе, написанной автором, можно почитать в статье Codius RegexTester v1.0 - тестирование регулярных выражений. Также там её можно скачать и пользоваться. Абсолютно бесплатно.
02

Эта статья, обязана своим появлением, возникшей однажды необходимости распарсить HTML. Столкнулся я с этим при работе над статьей Пишем свой Code Highlighter (раскрашиваем код). После недолгих поисков было найдено регулярное выражение, с которым можно было работать — <div>(?><div>(?<DEPTH>)|</div>(?<-DEPTH>)|.?)*(?(DEPTH)(?!))</div>. Рассмотрим детально, как оно работает:

03 RegExp
1
2
3
4
5
6
7
8
9
10
<div> (?> <div> (?<DEPTH>) | </div> (?<-DEPTH>) | .? )* (?(DEPTH)(?!)) </div>
04
Номер строки Шаблон Результат
1 <div> Ищет открывающий тег <div>.
2 (?> Начинает выражение поиска без возврата или «жадного» поиска (Nonbacktracking (or «greedy») subexpression).
3.1 <div> Ищет вхождение вложенного открывающего тега <div>.
3.2 (?<DEPTH>) Самый интересный момент! Присваивает найденной группе имя DEPTH. Если стека с таким именем не существует, то он создается. В этот стек помещается вхождение — пустая строка (Empty).
Если стек уже содержит какие-либо элементы, то добавленный элемент добавляется в начало стека, и при вызове match.Groups("DEPTH").Value будет взято верхнее/первое значение, т. е. последнее добавленное.
4 | Или.
5.1 </div> Ищет вхождение вложенного закрывающего тега </div>.
5.2 (?<-DEPTH>) И снова магия! Удаляет из стека с именем DEPTH верхнее/первое значение, таким образом, что следующее станет первым. Теперь при вызове match.Groups("DEPTH").Value будет взято ранее второе — теперь первое значение.
6 | Или.
7 .? Ищет ничего или один любой символ.
8 )* Любое количество раз, в том числе 0.
9 (?(DEPTH)(?!)) Конструкция если-то-иначе — (? (if) then | else). Параметр else — опциональный — можно не указывать. Данная конструкция проверяет было ли найдено и сохранено совпадение в группу DEPTH, если да, тогда — отрицательное вперед смотрящее нулевой ширины (?!). Но поскольку подвыражение в группе (?!<subexpression>) отсутствует, то попытка поиска подвыражения при наличии группы DEPTH всегда будет терпеть неудачу и получается, что в случае нахождения вложенного одноименного тега — он будет пропускаться.
10 </div> Ищет вхождение закрывающего тега </div>.
05 На заметку:
Нельзя забывать об установке необходимых параметров: Singleline (s) — для игнорирования знаков переноса строки, IgnoreCase (i) — для игнорирования регистра и IgnorePatternWhitespace — для игнорирования пробелов.
06

Если попытаться очень упрощенно объяснить, что происходит в данном выражении, то получится примерно следующее: в третьей строке при нахождении вложенного тега — параметр глубины увеличивается на 1 (помещение значения в стек), при нахождении закрывающего тега — параметр глубины уменьшается на 1 (удаление последнего добавленного значения из стека), и в итоге происходит проверка — если количество открытых тегов равно количеству закрытых тегов (т. е. стек с именем DEPTH пуст/отсутствует), то вернуть найденное выражение. Пример:

07 HTML
1
2
3
4
5
6
7
<div> <div>Content 1</div> <div> Content 2 <div>Content 3</div> </div> </div>
08

Но при использовании данного выражения всплывает один неприятный момент — если закрывающих тегов будет больше, то это выражение «зацепит» и их, т. е. в ситуации:

09 HTML
1
2
3
4
5
6
7
8
9
<div> <div>Content 1</div> <div> Content 2 <div>Content 3</div> </div>
</div>
</div>
</div>
10

будет захвачена вся строка для поиска (включая лишние выделенные строки).

11

Обратимся к MSDN — Конструкции группировки в регулярных выражениях раздел «Сбалансированные определения групп». Там рассматривается подобный вариант работы с вложенными конструкциями. Изменим наше выражение в соответствии с материалом из MSDN (поскольку конструкция меняется, то для удобства именования групп будем использовать синтаксис с одинарными кавычками, а не угловыми скобками) — (((?'Open'<div>).*?(?=(</?div>)))+((?'Close-Open'</div>).*?)+)+(?(Open)(?!)):

12 RegExp
1
2
3
4
5
6
7
8
9
10
11
12
( ( (?'Open'<div>) .*? (?=(</?div>)) )+ ( (?'Close-Open'</div>) .*? )+ )+ (?(Open)(?!))
13
Номер строки Шаблон Результат
1 ( Открывает первую неименованную группу.
2 ( Открывает вторую неименованную группу.
3 (?'Open'<div>) При нахождении открывающего тега <div> создается группа с именем Open, если группа уже есть, то найденное значение добавляется вверх стека.
4 .*? Ищем любой символ. ? — «жадный» квантификатор.
5 (?=(</?div>)) Положительное вперед смотрящее — поиск останавливается, если впереди открывающий (<div>) или закрывающий (</div>) тег.
6 )+ Один или более раз.
7 ( Открывает третью неименованную группу.
8 (?'Close-Open'</div>) При нахождении закрывающего тега </div> удаляем из группы Open. Поскольку в выражении (?'name1-name2' [i]<subexpression>[/i]) параметр name1 является опциональным, в нашем случае — Close — его можно опустить, т. е. (?'-Open'</div>).
9 .*? Ищем любой символ. ? — «жадный» квантификатор.
10 )+ Один или более раз.
11 )+ Один или более раз.
12 (?(Open)(?!)) Конструкция если-то-иначе — (? (if) then | else). Параметр else — опциональный — можно не указывать. Данная конструкция проверяет было ли найдено и сохранено совпадение в группу Open, если да, тогда — отрицательное вперед смотрящее нулевой ширины (?!). Но поскольку подвыражение в группе (?!<subexpression>) отсутствует, то попытка поиска подвыражения при наличии группы Open всегда будет терпеть неудачу и получается, что в случае нахождения вложенного одноименного тега — он будет пропускаться.
14

Это выражение будет работать уже корректно — будет захвачено только то, что нужно:

15 HTML
1
2
3
4
5
6
7
8
9
<div>
<div>Content 1</div>
<div>
Content 2
<div>Content 3</div>
</div>
</div>
</div> </div>
16

Доработаем данное регулярное выражение таким образом, чтобы оно искало не только теги <div>, а и любые другие теги, а также чтобы оно нормально работало с тегами, у которых указаны какие-либо атрибуты — <div class="content">.

17

Для поиска любых тегов внесем следующие изменения:

18 RegExp
1
2
3
4
5
6
7
8
9
10
11
12
( ( (?'Open'<b><(?'tag'[\w-]+)</b>) .*? (?=(</?<b>\k'tag'</b>>)) )+ ( (?'Close-Open'</<b>\k'tag'</b>>) .*? )+ )+ (?(Open)(?!))
19
Номер строки Шаблон Результат
...
3 (?'tag'[\w-]+) При нахождении первого вхождения любого тега, создается именованная группа с именем tag, которая будет содержать наш тег.
...
5, 8 \k'tag' Берет и сравнивает на соответствие значение сохраненного тега из именованной группы tag.
...
20

Теперь добавим фрагмент, который позволит не обращать внимание на атрибуты тегов:

21 RegExp
1
2
3
4
5
6
7
8
9
10
11
12
( ( (?'Open'<(?'tag'[\w-]+)(\s+[\w-]+="[^"]*")*) .*? (?=(</?\k'tag'>)) #Удаляем символ '>' - он нам не нужен )+ ( (?'Close-Open'</\k'tag'>) .*? )+ )+ (?(Open)(?!))
22
Номер строки Шаблон Результат
...
3 (\s+[\w-]+="[^"]*")* Ищет пробельный символ (1 или больше), далее буквенный символ или тире (1 или больше), далее равно и значение в кавычках — все это выражение любое количество раз, включая ноль.
...
23

Итоговое выражение — (((?'Open'<(?'tag'[\w-]+)(\s+[\w-]+="[^"]*")*).*?(?=(</?\k'tag')))+((?'Close-Open'</\k'tag'>).*?)+)+(?(Open)(?!)).

24 RegExp
1
2
3
4
5
6
7
8
9
10
11
12
( ( (?'Open'<(?'tag'[\w-]+)(\s+[\w-]+="[^"]*")*) .*? (?=(</?\k'tag')) )+ ( (?'Close-Open'</\k'tag'>) .*? )+ )+ (?(Open)(?!))
25
26

Похожие запросы:

  • .NET — Regexp — поиск «вложенных» match
  • Поиск вложенных конструкций в регулярных выражениях
  • Головоломка с Regex
  • Как распарсить HTML при помощи регулярных выражений
  • Как проверить баланс открывающих/закрывающих знаков (круглые, угловые скобки) с помощью регулярных выражений
  • Recursive regex for div tags
  • Trying to parse html with regex
  • Javascript RegEx wont work, but works in c# (atomic subexpression)
  • Regex to parse functions with arbitrary depth
comments powered by HyperComments

Яндекс.Метрика