Регулярные выражения

Двузначные НДКА

Пусть выделено некоторое подмножество T состояний НДКА. Будем называть состояния этого подмножества терминальными.

Будем говорить, что такой НДКА распознаёт текст X, если текст X переводит НДКА из начального состояния в подмножество, пересекающееся с T. Например, если взять автомат КМП, построенный по тексту Y, и объявить его наибольшее состояние терминальным, то такой автомат будет распознавать те и только те тексты, которые заканчиваются на Y.

Автомат с множеством терминальных состояний мы будем дальше называть двузначным.

Регулярные выражения, математическая сторона

Есть важный класс двузначных НДКА, называемый регулярными автоматами. Этот класс обладает следующими свойствами:

Регулярные автоматы обладают текстовым представлением.
Любой двузначный автомат эквивалентен (в смысле равенства множеств распознаваемых текстов) некоторому регулярному.

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

Регулярное выражение – это формула, составленная из букв алфавита и трёх операций:

бинарная конкатенация
бинарная дизъюнкция
звёздочка

Семантика этих операций такова:

выражение AB распознаёт те и только те тексты, которые имеют вид XY, где X распознаётся A, а Y распознаётся B
выражение A|B распознаёт те и только те тексты, которые распознаются хотя бы одним из A или B
выражение (A)* распознаёт те и только те тексты, которые можно представить в виде конечной (возможно, пустой) последовательности текстов, каждый из которых распознаётся A

Приведём несколько примеров.

Выражение aba распознаёт только текст aba.
Выражение ab*a распознаёт тексты aa, aba, abba, abbba и т.д. Стоит отметить, что если звёздочка относится только к одной букве, скобки традиционно не ставятся.
Выражение ab*|b*a распознаёт тесты a, ab, abb, abbb и т.д., а также – тексты ba, bba, bbba и т.д.

Осталось описать соответствие между регулярными выражениями и автоматами. Можно, например, применить алгоритм Томпсона для построения двузначного НДКА по регулярному выражению.

Регулярные выражения, практическая сторона

Почти во всех языках программирования есть поддержка того или иного диалекта регулярных выражений. Регулярные выражения используются для поиска в текстах подтекстов. Здесь мы поговорим о том варианте, который применяется в Javascript. Подробное описание можно найти в MDN. Поиграться с ними можно здесь.

Сперва отметим главную особенность регулярных выражений в большинстве языков программирования: поиск в тексте T по регулярному выражению R ищет какое-нибудь разбиение текста T=AXB, в котором X распознаётся выражением R. Выбрать конкретное разбиение в случае, если их несколько, нельзя (компромисс в целях скорости поиска), но можно ограниченным образом контроллировать искомое разбиение. Основные способы контроля следующие:

выражения ^R, R$ и ^R$ ищут разбиения вида XB, AX и X соответственно
есть два вида звёздочки * и *?: жадная и ленивая; выражение (S)*Q выбирает тот среди распознаваемых текстов, в котором часть, распознанная (S)*, распознаётся наибольшим возможным количеством повторений S; ленивая же звёздочка соответствует наименьшему возможному количеству повторений S
есть глобальный режим, позволяющий найти несколько непересекающихся разбиений (то есть таких, части которых, распознаваемые выражением, не пересекаются по положению)

Кратко опишем особенности синтаксиса регулярных выражений по сравнению с математической моделью:

обычные скобки – это пара (?: и ); пара же ( и ) – это т.н. захватывающие скобки; исполнитель выражения с захватывающими скобками запоминает ту часть текста, которая была распознана подвыражением, заключённым в эти скобки
есть целое семейство унарных операторов, называемых кванторами: {m} – ровно m вхождений, {m,n} – от m до n вхождений, {m,} – хотя бы m вхождений; в их терминах определяются *, +, ? как {0,}, {1,} и {0,1} соответственно
точка . распознаёт любую одну букву
т.н. классы символов, заключаемые в квадратные скобки, задают выражение, распознающее одну букву из некоторого подмножества алфавита
есть обратные ссылки (back references), распознающие участки, совпадающие с участками, захваченными скобками

Про последний пункт стоит сказать отдельно. Регулярные выражения не предназначены для разбора рекурсивных грамматик! Разбирать рекурсивные грамматики регулярными выражениями сложно и неэффективно! Если требуется разбор рекурсивных грамматик, следует прибегнуть к чему-то другому (например, к комбинаторам парсеров из 8-й главы). Ни при каких обстоятельствах не нужно использовать обратные ссылки!

В заключение дадим рекомендации по увеличению скорости поиска:

по возможности использовать незахватывающие скобки
в зависимости от конкретной реализации регулярных выражений, иногда имеет смысл заменить все жадные кванторы на ленивые (ленивые кванторы соответствуют стандартной семантике пошагового исполнения НДКА)
не пользоваться обратными ссылками: регулярные выражения не предназначены для разбора рекурсивных грамматик!

Примеры выражений

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

^http(?:|s):/+(.*?)(?:$|/)
^http(?:|s):/+([^/]*)

С некоторой осторожностью можно использовать выражение

^http(?:|s):/+([a-zA-Z0-9\-.]*)

Нечто подобное используют браузеры от Microsoft, в результате чего некоторые не удовлетворяющие стандарту имена серверов (например, использующие подчёркивание), воспринимаются некорректно.

Для распознания некоторого строгого надмножества почтовых адресов вида foobar@baz можно использовать выражение вида

^(.*)@([a-zA-Z0-9\-.]*)

Важно заметить, что первый квантор здесь жадный: внутри локальной части foobar вполне допустим символ @.

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

(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:
\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(
?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ 
\t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\0
31]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\
](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+
(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:
(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)
?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\
r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[
 \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)
?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t]
)*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[
 \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*
)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)
*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+
|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r
\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:
\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t
]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031
]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](
?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?
:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?
:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?
:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?
[ \t]))*"(?:(?:\r\n)?[ \t])*)*:(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|
\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>
@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"
(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?
:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[
\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-
\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(
?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;
:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([
^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\"
.\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\
]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\
[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\
r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]
|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \0
00-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\
.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,
;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?
:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[
^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]
]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)(?:,\s*(
?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(
?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[
\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t
])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t
])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?
:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|
\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:
[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\
]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)
?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["
()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)
?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>
@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[
 \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,
;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:
\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\[
"()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])
*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])
+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\
.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(
?:\r\n)?[ \t])*))*)?;\s*)

Следует отметить, что даже оно не удовлетворяет стандарту. В частности, оно не умеет обрабатывать вложенные комментарии.

Регулярные выражения в Javascript

Регулярное выражение можно создать двумя способами:

заключив его между двумя дробными чертами: /foobar/
выражением new RegExp("foobar")

У полученного объекта есть метод exec, позволяющий применить регулярное выражение к тексту. Результатом является массив, содержащий распознанную часть и захваченные части. Дополнительно этот массив имеет поле .index, в котором хранится смещение начала распознанной части от начала текста.

Глобальный режим работы регулярного выражения можно включить так:

написав g после закрывающей черты: /foobar/g
написав new RegExp("foobar", "g")

Метод exec в глобальном режиме перебирает распознанные части по циклу. Ещё раз отметим, что в глобальном режиме распознаются не все возможные части, а только некоторое их подмножество, отдельные элементы которого не пересекаются по положениям в тексте.

Практическое задание по анализу файла

В архиве по ссылке находится фрагмент реального журнала запросов к веб-серверу и файл с текстом задания.

Для того, чтобы загрузить файл в браузер, нужно сделать следующее:

добавить на страницу селектор файла <input type="file"> (если не нравится его внешний вид, его можно скрыть и управлять им программно)
у этого селектора есть поле .files; его нулевой элемент – путь к выбранному файлу (Это не просто текст! Его можно получить только от селектора файла.)
нужно создать объект типа FileReader, задать ему реакцию на событие load и вызвать один из методов вида .readAs... (этот метод асинхронный, он не ждёт, пока закончится чтение)

Вот – пример чтения файла (написанный в стиле передачи продолжений):

function readFile(selector_id, continuation) {
    let selector = document.getElementById(selector_id)
    let file = selector.files[0]

    if (!file) { return false }

    let reader = new FileReader()
    reader.onload = function() { continuation(reader.result) }

    reader.readAsText(file)
    return true
}

Чтобы разбить файл на строчки, можно воспользоваться функцией

function lines(text) {
    return text.split(/\r?\n/)
}

Необходимость такой функции связана с тем, что в силу исторических причин признаком конца строчки является не только \n, но и различные комбинации \r и \n (самая частовстречающаяся – \r\n). Комбинацию \r\n до сих пор используют ОС семейства Windows.