23.03.2011Рекурсия в регулярных выражениях

Пролог

Что-то большие перерывы в написании статей входят в привычку. Способность некоторых коллег по цеху регулярно выдавать что-нибудь полезное и интересное вызывает уважение.

Введение

С тех самых пор, как я только узнал про регулярные выражения, я слышал об их несовершенстве и моральном устаревании. Регулярные выражения продолжали использоваться, а недовольные теоретики — сетовать. Основной претензией было то, что регулярные выражения не позволяют исследовать вложенности паттернов в виду своей линейности. Действительно, соглашался я, невозможно проверить правильность открытия и закрытия тегов или получить выражение в самых внутренних скобках.

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

Именованные группы

В регулярных выражениях руби 1.9 появились именованные группы. Вот, как выглядит их элементарное использование:

if /\A(?<first>[a-zA-Z]+)\s+(?<last>[a-zA-Z]+)\Z/ =~ "Vassily Poopkine"
  puts [first, last].inspect
end

if md = /\A(?<first>[a-zA-Z]+)\s+(?<last>[a-zA-Z]+)\Z/.match("Vassily Poopkine")
  puts [md[:first], md[:last]].inspect
end

То есть мы не только выделяем группу скобками, как обычно, назначая ей тем самым порядковый номер (по номеру открывающей скобки), но и даём имя. И использовать его можно не только в локальных переменных и объекте MatchData, но и в самом регулярном выражении.

Более того, обращение к объявленным группам внутри может быть рекурсивным. Мне сразу же захотелось написать давнишнюю мою задумку о функции, раскрывающей вложенные скобки. Вот так:

str = "1 + 2 * (3 - 4 / {5 + 6} + [7 - 8 * (9 + 10 * 11) + 12 * {13 - 14}] + 15) + 16 * (17 + 18)"

re = %r{
        (?<fill>[0-9+\-*/\s]+){0}
        (?<expression>\g<fill>*\g<brackets>\g<fill>*|\g<fill>){0}
        (?<braces>\{\g<expression>+\}){0}
        (?<squarebrackets>\[\g<expression>+\]){0}
        (?<parentheses>\(\g<expression>+\)){0}
        (?<brackets>\g<braces>|\g<squarebrackets>|\g<parentheses>)
}x

def calculator(str)
  if str =~ /\A[0-9+\-*\/\s]+\Z/
    eval str
  else
    raise "Invalid expression: #{str}"
  end
end

f =-> s do
  if $~[:expression] == $~[:fill]
    calculator($~[:fill])
  else
    calculator($~[:brackets][1..-2].gsub(re, &f))
  end
end

puts calculator(str.gsub(re, &f))
puts eval(str.gsub(/(?<left>\{|\[)|\}|\]/) { |s| $~[:left] ? "(" : ")" })

Итак, в регулярном выражении присутствует 6 именованных групп: fill (заполнения пространства между скобками), expression (выражение, содержащее одни или ни одних нераскрытых скобок), braces (фигурные скобки), squarebrackets (квадратные скобки), parentheses (круглые скобки), brackets (любые скобки). Как видите, выражение описывается через скобки, а скобки — через выражение.

Для проверки правильности расчёта, используем обычный eval, заменив все скобки на круглые.

Сделав этот пример, я был доволен, как стадо слонов, но потом решил проверить, а что будет, если скобки расставлены неправильно?

str = "1 + 2 * (3 - 4 / {5 + 6} + [7 - 8 * (9 + 10 * 11) + 12 * {13 - 14]} + 15) + 16 * (17 + 18)"

re = %r{
        (?<fill>[0-9+\-*/\s]+){0}
        (?<expression>\g<fill>*\g<brackets>\g<fill>*|\g<fill>){0}
        (?<braces>\{\g<expression>+\}){0}
        (?<squarebrackets>\[\g<expression>+\]){0}
        (?<parentheses>\(\g<expression>+\)){0}
        (?<brackets>\g<braces>|\g<squarebrackets>|\g<parentheses>)
}x

str =~ re

И я не смог дождаться завершения работы оператора =~ для такого длинного выражения. Это, конечно, неприятно. В причины я вникал не особо, но похоже, это связано с поведением недетерминированной машины Тьюринга. По крайней мере вот ответ на похожую проблему. Для нас это всего лишь означает, что проверять правильность расстановки скобок нужно отдельно и другим способом. Чем я предлагаю заняться пытливому читателю самостоятельно.

Материалы для самостоятельного изучения

1. Исходный код статьи.
2. Новый синтаксис и прочие вкусняшки в руби 1.9. Для тех, кто заметил =->.
3. Глобальные переменные с непонятными именами. Для тех, кто заметил $~.
4. Ещё немного базовых приёмов в регулярных выражениях руби.