gatoazul (gatoazul) wrote,
gatoazul
gatoazul

Category:

Внутренняя жизнь регулярных выражений

Реализация регулярных выражений - интересно только программистам, да и то не всем


1. Затянувшееся предисловие


Сопоставление с образцами в строках меня всегда интриговало и казались страшно интересным. Возможно потому, что с налета написать такое не получается. Еще в староглиняные времена я пытался проверить, что имя файла похоже на "*a.*". Как проверить, что это "а" - понятно, но вот что делать со звездочкой? Проверять все подряд? А когда остановиться? В общем, не получилось.

Потом я дизассемблировал DIR.SAV от RT-11. Очень быстро нашел функцию, которая делала как раз то, что я хотел. И была она совсем небольшая, но... непонятная. Что-то с кучей хитрых зацикленных переходов.

Чуть позже попалась в библиотеке книжка по Сноболу (я тогда читал все подряд). Я был просто очарован, как легко в этом языке решались такие задачи. Но как работало сопоставление - так и осталось загадкой.

Потом я нашел Перл и принял местные регулярные выражения за данность, уже не пытаясь их понять.

После этого откопал реализацию Снобола (а она сделана весьма любопытно - сначала определялся некий язык, который предполагалось делать с помощью макросов ассемблера, а потом на нем писался интерпретатор). Но и тут ничего не прояснилось, тем более, что описания самого языка нигде не было.

В общем, вечный вопрос, что-то типа смысла жизни, к которому возвращаешься снова и снова.

И, что любопытно, - как-то не попадалось ни одной книжки, в котором этот вопрос ясно бы освещался. О чем угодно можно узнать, но только не о сопоставлении с образцом.

И только со временем опыт взял свое и истина, наконец, мне открылась. Совсем недавно. В сущности, позавчера.

На самом деле, в реализации нет ничего сложного, она проста и достаточно понятна. Но сам стиль программирования отличается от мейнстрима, поэтому и в книжки тема не очень-то попадала. Достаточно специализированная вещь.

Кроме того, поиск по образцу в том виде, как он сейчас понимается, имеет ужасный синтаксис, тянущийся от реализации в системе Юникс. Там, собственно, взяли идеи все того же Снобола, только добавили фирменный стиль - синтаксис, напоминающий помехи на линии связи - звездочки, собачки и прочее. Он, конечно, компактен, но это единственное его достоинство. Компактность традиционна для Белл Лабс - похоже, что там программистам приходилось покупать бумагу для принтеров за свой счет.

Однако этот синтаксис в больших дозах совершенно сбивает с толку и его приходится разбирать как вавилонскую клинопись. И - что еще хуже - его совершенно невозможно расширить, отчего сразу же пропадает выразительность в сложных задачах. Сравните со Сноболом. Вот регулярное выражение, которое разбирает имя переменной, начинающееся с буквы и состоящее из букв и цифр:

/[A-Za-z][A-Za-z0-9]*/

(Разумеется, я знаю о макросах \w и \d, но ведь программист не может ввести новые. Представьте, например, что цифры должны быть только китайские)

А вот это Снобол, который имеют полноправный тип данных образец, переменные этого типа и операции сборки большого образца из нескольких других:

digit = ANY('0123456789')      * any - элементарная функция, сопоставляющая один символ с любым из написанных в аргументе
letter = &lcase &ucase             * &lcase и &ucase - системные переменные, в которых перечислены все большие и маленькие латинские буквы
name = letter ARBNO(letter|digit)   * arbno - фукнция, аналогичная звездочке в регулярных выражениях - повторять шаблон ноль или более раз

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

2. Общая организация

В общем-то, если подойти с правильной стороны, то все становится достаточно просто. Есть строка, которую мы будем изучать.

VAR subject

И есть позиция в этой строке, где мы находимся в данный момент

VAR pos

Образец - это массив, в котором перечислены функции, каждая из которых отвечает за свою часть проверки. Соответственно, сам образец перед началом сопоставления должен быть разобран и преобразован в нечто вроде

/abc[0-9]$/ ->

[
  str("abc"),
  any("0123456789"),
  at_end()
]

Главная функция, выполняющая сопоставление с образцом, будет принимать строку и шаблон, возвращать истину/ложь и выглядеть примерно так:

SUB regexp(string,patstr)
  VAR pattern := parse_pattern(patstr) -- разобрать строку-образец и сделать из нее настоящий образец
  subject := string
  pos := 0
  RETURN match(pattern)
END SUB

Функция match, которая, собственно и занимается сопоставлением, берет образец, которые представляет собой массив функций и их аргументов и просто вызывает по очереди все функции. Если хоть одна из них закончилась неудачей, сопоставления не вышло.

SUB match(pattern)
  FOREACH p IN pattern
    VAR f := get_function(p)           -- взять функцию от текущего образца
    VAR args := get_arguments(p) -- и аргументы функции
    IF NOT funcall(f,args)
      RETURN FALSE
    END IF
  END FOREACH
  RETURN TRUE
END SUB

3. Элементарные проверки

Каждая функция делает свою элементарную проверку, используя subject и учитывая текущее положение. Если проверка неудачна, возвращается ложь. Если проверка удачна, то функция должна подвинуть указатель на длину успешно сопоставленной подстроки.

Начнем с самого простого. Проверим, что мы находимся в начале строки (в скобках будем писать обозначение в регулярных выражениях, например, в данном случае - символ крышки "^")

SUB at_begin
  RETURN pos=0
END SUB

Не сложнее проверить, что мы в конце строки (знак доллара "$")

SUB at_end
  RETURN pos=length(subject)
END SUB

Остальные функции должны при необходимости двигать указатель, поэтому введем вспомогательную функцию, которая берет результат проверки и продвигает указатель, если это нужно

SUB test(result,len)
  IF result
    pos := pos + len
  END IF
  RETURN result
END SUB

И еще одну, дающую кусок строки с текущей позиции и нужной длины

SUB look(len)
  -- предполагается, что если запросили больше символов, чем есть в строке, то возвращается все до конца строки
  RETURN substring(subject,pos,len)
END SUB

Очень легко определить проверку на произвольный символ (символ точка "."). Поскольку он произвольный, то мы даже не будем ничего читать из строки, главное - знать, что строка не кончилась

SUB one_symbol
  RETURN test(NOT at_end(), 1)
END SUB

Проверяем, что строка сопоставляется с другой строкой (в регулярных выражениях это задается обычными символами, не имеющими особого значения. В Сноболе строки писались в кавычках)

SUB str(string)
  VAR len = length(string)
  RETURN test(string=look(len), len)
END SUB

Ну и наконец, проверим, что текущий символ равен любому необходимому (в р.в. обозначается квадратными скобками с символами внутри "[0-9]")

SUB any(chars)
  RETURN test(NOT at_end() AND isin(look(1),chars), 1)
  -- здесь предполагается, что функции isin, написание которой мы оставим в качестве упражнения
  -- передается символ и строка, и она разбирается, принадлежит ли этот символ множеству, указанному в строке
  -- специально для удобной реализации в язык Айкон (наследник Снобола) был введен тип данных "множество символов"
END SUB

Остальные элементарные функции, если они нужны, пишутся в том же духе.

4. Метасимволы

Как ни странно, но реализация метасимволов вроде звездочки или вопросительного знака, оказывается ничуть не сложнее. Здесь только надо сделать некий концептуальный переход и понять, что они не просто так называются мета. Соответствующие функции работают не со строками, а с другими образцами.

Как, например, сделать альтернативу ("a|b") ? Надо сначала проверить, что в строке стоит буква "а" (первый образец). Если этой буквы там нет, то надо вернуться назад и проверить, не стоит ли там "b" (второй образец). Если она там есть, то успех, иначе - неудача. Это можно выразить совершенно дословно:

SUB alt(pattern1,pattern2)
  VAR oldpos := pos -- сохраняем позицию, если вдруг придется к ней вернуться
  IF match(pattern1)
    RETURN TRUE
  END IF
  -- если не получилось, возвращаемся назад и проверяем второй шаблон
  pos:=oldpos
  RETURN match(pattern2)
END SUB

Эту функцию несложно обобщить на целый список переданных шаблонов, сделав ее более универсальной

SUB alt(patternlist)
  oldpos:=pos
  FOREACH patt IN patternlist
    pos:=oldpos
    IF match(p)
      RETURN TRUE
    END IF
  END FOREACH
  RETURN FALSE
END SUB

Фактически эта функция играет роль условного оператора IF (или CASE) по отношению к шаблонам. По аналогии можно догадаться, что должна быть и функция, позволяющая делать из шаблонов циклы. Так и есть, такая функция существует и даже не одна. Все они отличаются только тем, сколько раз эти самые циклы должны повторяться:

* повторять сколько угодно раз
+ повторить сколько угодно раз, но только не ноль раз
? только ноль или один раз
{n} ровно n раз
{m,n} от m до n раз

Все их легко реализовать с помощью одной универсальной функции, которая повторяет сопоставление с шаблоном (возможно, не более указанного числа раз) и считает, сколько раз это получилось

SUB repeat(pattern,max=0)
  VAR count:=0
  LOOP -- бесконечный цикл
   IF max>0 AND count>max
     -- мы превысили максимальное число итераций (если оно было задано)
     RETURN NULL
   END IF
   IF NOT match(pattern)
     RETURN count
   END IF
   count:=count+1
  END LOOP
END SUB

На ее базе несложно сделать все остальное. Звездочка вообще не должна интересоваться, сколько раз у нее получилось

SUB star(pattern)
  repeat(pattern)
  RETURN TRUE
END SUB

Плюсик проверит, что была хотя бы одна итерация

SUB plus(pattern)
   RETURN repeat(pattern)>0
END SUB

Вопросительный знак проверяет не более одной итерации

SUB question(pattern)
  VAR result := repeat(pattern,1)
  RETURN result<>NULL AND result>=0 AND result<=1
END SUB

Аналогично вопросительному знаку делаются фигурные скобки

Заключение


Как видите, ничего сверхъестественно сложного в сопоставлении с образцом нет. Осталось сделать только несколько заключительных замечаний.

1) Я описал поиск, который в Сноболе назывался заякоренным (anchored mode). Шаблон сопоставляется с самого начала строки. Сейчас обычно подразумевается, что подстрока, сопоставляющаяся с регулярным выражением, может быть где угодно в строке, не обязательно в начале. Для этого надо расширить функцию regexp, так чтобы она вызывала match в цикле, проходя все позиции от 0 до конца строки и завершалась после первого совпадения

2) Изложенный способ поиска отличается простотой и поэтому методически полезен. В реальной жизни на длинных строках он оказывается слишком медленным, поэтому применяются различные ухищрения, позволяющие сократить количество переборов. Эти ухищрения именуются эвристиками и варьируются от простых до весьма изощренных. Например, если шаблон начинается со строки символов, то мы можем сразу найти эти символы в изучаемой строке путем последовательного просмотра, не вызывая match. Можно так же проверять, хватит ли в оставшемся хвосте строки символов для текущего шаблона, и не вызывать сопоставление вообще, если их там мало. Ну и так далее, насколько хватит хитроумия.

3) Описанный здесь метод называется перебором с возвратами. Есть и альтернативный ему, когда по шаблону строится детерминированный конечный автомат, который и разбирает строку. Разбор автоматом более быстрый, но гораздо менее гибкий.

4) Здесь не затронуты многие вопросы, например, как запомнить части распознанного подвыражения или сделать поиск с заменой. Надеюсь еще вернуться к этой теме.

Tags: программирование
Subscribe

  • Ответ на загадку Новака

    Профессор Новак как-то предложил своим коллегам такую загадку: The poor have it, the rich need it, it is greater than God, more evil than devil,…

  • Загадка Новака

    Следующая загадка предназначется только для тех, кто очень хорошо знает английский язык. К сожалению, адекватно перевести ее на русский, так, чтобы…

  • Ответ на загадку с картинкой

    Этот коллаж иллюстрирует название довольно известной раньше книги. ====================================================== Карл Маркс.…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments