Почему Non-greedy (нежадный) RegExp не работает?

Question

[devdb]

Иногда сталкивался с тем, что регулярные выражения в JavaScript не работали как задумывалось. Списывал это на глючный RegExp в JavaScript. Но вот опять в JS столкнулся с тем, что non-greedy оператор не работает. Проверил в Python - и там тоже не работает. В чём объяснение?
Задача - получить числа из последней колонки в таблице с помощью Regexp. Сначала выдрать их из html, а потом уже отфильтровать от мусора. Но выдрать не получается из-за непонятной работы нежадного оператора (строка html и регулярка сильно упрощены для наглядности):

//JavaScript
s = '<tr><td>11</td><td>22</td></tr><tr><td>33</td><td>44</td></tr>';
s.match(/\d+.+?<\/tr/g);
// Array [ "11</td><td>22</td></tr", "33</td><td>44</td></tr" ]

#Python
s = '<tr><td>11</td><td>22</td></tr><tr><td>33</td><td>44</td></tr>'
import re
re.findall( r'\d+.+?<\/tr', s )
# ['11</td><td>22</td></tr', '33</td><td>44</td></tr']

Как видим, Regex захватывает лишние колонки таблицы вместо того, чтобы брать минимальную подстроку, удовлетворяющую условию.
Ожидался результат:
[ '22</td></tr', '44</td></tr' ]

Вопрос не в том, чтобы помочь решить задачу (я её и сам костылями решу), а в том, чтобы объяснить почему non-greedy оператор +? не срабатывает?

Comments

[Алексей Уколов]

Костылей тут не нужно, корректная регулярка такая: \d+[\D]+<\/tr>

[o5a]

devdb,

Вопрос не в том, чтобы помочь решить задачу (я её и сам костылями решу), а в том, чтобы объяснить почему non-greedy оператор +? не срабатывает?

Срабатывает, только не так, как думаете.
r'\d+.+?<\/tr'
Встречает \d+
Затем начинает собирать последовательность из любых символов, пока не встретит первое </tr
При greedy он бы выбирал всю последовательность символов до самого последнего </tr

[Kovalsky]

"Как видим, Regex захватывает лишние колонки таблицы вместо того, чтобы брать минимальную подстроку, удовлетворяющую условию" - минут 5 пытался понять что это значит и в чем конкретно проблема, наконец дошло. К тому же читаю вашу регулярку, вижу что результат поиска в вашем примере абсолютно закономерен, все происходит именно так как и записано вами. Не жадный .+? сработал, просто он работает не так как вы думаете. Регулярки выполняются слева направо, то есть с начала строки до её конца, последовательно. Конкретно ваша регулярка ищет цифры (11), потом все символы до включительно (22), получается 1122. Если вы планировали что нежадный поиск найдет все варианты подходящие под условие - '1122', '122', '22', '2' -, а потом выдаст вам то в котором количество символов до меньше всего, то к сожалению такого не произойдет, ибо регулярки и в частности нежадный поиск работают не так,

[devdb]

Kovalsky, нет, я рассчитывал на другое поведение регулярки. Улучшил вопрос, чтобы было понятнее.

o5a, Не понимаю, почему так - ведь это противоречит тому как описывается действие non-greedy оператора - минимальное количество символов между соединяемыми условиями.
А как добиться этого, есть ли такие приёмы, чтобы указать брать действительно минимум символов, как задумывалось?

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

[Kovalsky]

devdb, "Не понимаю, почему так - ведь это противоречит тому как описывается действие non-greedy оператора - минимальное количество символов между соединяемыми условиями" - ну вам же объяснили, что регулярки выполняются слева направо. Нежадный оператор не ищет минимальное количество символов, он ищет первое совпадение. И не продолжает поиск дальше,

[devdb]

Kovalsky, Это не всё, что я хотел узнать.

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

s = '<tr><td>11</td><td>22</td></tr><tr><td>33</td><td>44</td></tr>'
found = re.search( r'.*>(\d+).+?<\/tr', s )
print(found[1])
# 44

Вот такая нестабильность в работе.

[o5a]

devdb, потому что в таком случае все равно смотрит последовательность слева направо, но потом возвращается назад. Т.е. сначала выбирает последовательность пока находит последний <\/tr затем возвращается назад пока не найдет влево от него последовательность цифр.
И при таком шаблоне он найдет только самую последнюю - 44, а 22 не найдет, её съест последовательность .*

[Saboteur]

devdb,
Так в данном случае будет работать даже .*>(\d+)

[devdb]

Верно, что-то в этом есть...

Answer 1

[Александр]

UPD:
Действительно, в первый раз не верно прочитал вопрос. Можете достать число вот таким способом:

const string = '<tr><td>11</td><td>22</td></tr><tr><td>33</td><td>44</td></tr>';
const match = string.match(/(\d+)(?=<\/td><\/tr>)/g); 
// или так: string.match(/(\d+)(?=[^\d]+?<\/tr>)/g)
// или так: string.match(/(\d+)(?=\D+?<\/tr>)/g)

console.log(match); // [ '22', '44' ]

Comments

[Алексей Уколов]

Прямо по вашей ссылке показывается, что не работает так, как ожидает автор. Он хочет выбрать только 22 и 44.

[Александр]

Алексей Уколов, По ссылке его регулярка.

[Алексей Уколов]

Ну да. А ваша не решает его задачу получить числа из последней колонки в таблице.