ВЛАДИМИР ЦАРЬКОВ, инженер, фрилансер, vb-tennis@mail.ru

Построение регулярных выражений
с помощью синтаксических диаграмм. Часть 2

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

В первой статье:

• излагались причины нашего внимания к РВ;
• рассматривались механизм обработки РВ и особенности РВ как метаязыка;
• критиковались традиции изложения информации о РВ;
• уточнялся понятийный аппарат для описания содержимого РВ.

Сейчас речь пойдет о методике построения РВ и алгоритме построения РВ с помощью синтаксических диаграмм.

Методика построения РВ

РВ – это метаязык для описания регулярных множеств, который имеет высокую степень формализации. Для неподготовленного человека синтаксис РВ сложен (отсутствует простая структура), выглядит непривычно и непонятно.

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

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

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

В разделе «Построение РВ с помощью синтаксических диаграмм: алгоритм» мы займемся наглядным символическим моделированием: создадим логический объект, замещающий РВ и выражающий основные его свойства через систему знаков и символов.

Формализация – это путь исследования каких-либо объектов (в данном случае явлений языка РВ), когда их содержание познается с помощью выявленных элементов их формы. За счет варьирования уровня детальности формализации возможно изменять уровень сложности восприятия одного и того же материала.

Процедура формализации в нашем случае может быть разбита на следующие этапы:

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

Удобство использования синтаксических диаграмм (СД) заключается в том, что РВ, записанные в виде СД, гораздо нагляднее, чем РВ в текстовом виде. СД просто анализировать и проверять на наличие ошибок. Конкретные правила, предлагаемые нами для построения синтаксических диаграмм РВ, будут рассмотрены в разделе «Построение РВ с помощью синтаксических диаграмм: алгоритм».

Построение РВ с помощью синтаксических диаграмм: алгоритм

Модель РВ должна содержать следующие компоненты:

• синтаксическую диаграмму;
• элементы естественного языка;
• элементы математических условных обозначений.

Разберемся с тем, что собой представляет синтаксическая диаграмма. СД, называемая некоторыми авторами синтаксическим графом или рельсовой диаграммой, является ориентированным графом с одним входным ребром и одним выходным ребром и используется для наглядного задания правил подстановки, используемых в грамматике языка-объекта.

По выразительным возможностям СД не уступает Форме Бэкуса-Наура (Backus-Naur Form) и Расширенной форме Бэкуса-Наура (Extended Backus-Naur Form).

Основное достоинство СД – наглядность. Никлаус Вирт поспособствовал вводу СД в широкое пользование, включив их в одну из своих книг о языке Pascal, опубликованную в 1973 году.

В статье [1] рассказывается об успешном опыте применения таких диаграмм для решения проблем обработки текста: студентам стало гораздо легче составлять программы для работы с текстом; у преподавателя, в свою очередь, появилась возможность расширить учебный материал.

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

В СД терминальные символы помещаются в овалы, а нетерминальные – в прямоугольники. Символы метаязыка РВ служат средствами описания синтаксических конструкций языка-объекта, а потому относятся к нетерминалам ипомещаются в прямоугольники.

Вывод о том, что исследуемая распознающей грамматикой строка принадлежит языку-объекту, делается, если строка, направленная на вход СД, «дойдет» до выходного ребра синтаксического графа.

Любое регулярное множество может быть задано с использованием трех алгебраических операций над произвольными языками X и Y.

• Операция объединения: (X|Y). Такой язык принадлежит либо X, либо Y, либо обоим языкам.
• Операция умножения, другими словами, конкатенации: (XY). Язык образуется дописыванием к любой цепочке из X любой цепочки из Y.
• Операция итерации, другими словами, замыкания Клини (X*). Результирующий язык образуется путем конкатенации любого количества цепочек из X (цепочка из X может быть взята для конкатенации более одного раза).

Таким образом, любое РВ может быть упрощено до вида, в котором используются только обозначенные выше операции над языками.

«Для произвольной синтаксической диаграммы может быть построен эквивалентный, то есть порождающий тот же язык, набор диаграмм, содержащих только параллельное и последовательное соединения» [2, с. 3].

Наша методика построения РВ основывается на наборе выразительных средств базовых РВ (Basic Regular Expressions, BRE) с добавлением единственного дополнительного выразительного средства – знака операции объединения «|».

Мы теперь можем создавать базовые РВ средствами СД. СД при этом должны содержать только параллельное (операция объединения) и последовательное (операции конкатенации и итерации) соединения.

Каждая беспрерывная конкатенация в СД должна сопровождаться пояснительной фразой на естественном языке, содержащей глагол совершенного вида («найден», «выполнен» и т.п.). Совершенный вид глагола наглядно словесно выражает логическую законченность того или иного элемента СД, позволяя пользователю лучше представить себе процесс решения задачи средствами РВ. Логично, что в книге [3, с. 20] предлагается использовать глаголы совершенного вида при описании событий в сетевом графике. Результат конкатенации нескольких автоматных (регулярных) языков также является событием.

Итак, у нас получился алгоритм построения РВ.

1. Задача построения РВ описана на естественном языке.
2. Задача разбита на подзадачи, выражаемые только через операции конкатенации (умножение и/или итерацию).
3. Описание подзадач не содержит многоуровневых квантификаторов (...*)* (см. [4, с.185-186]).
4. РВ вида ТЕКСТ(.*)ТЕКСТ выражаются через две ветви СД: ТЕКСТТЕКСТ и ТЕКСТ(.+)ТЕКСТ.
5. Чтобы не возникало путаницы в действиях квантификаторов, каждый логически независимый отрезок текста, описываемого средствами СД, рекомендуется брать в скобки (см. СД для второго примера). Эти скобки сохраняются при составлении РВ (см. исходный код программы на языке Perl для второго примера).
6. Составлены СД, описывающие подзадачи.
7. Указаны пояснительные фразы для СД, описывающих подзадачи.
8. Параллельные ветви СД (в них описаны подзадачи) соединены между собой, а также с входным и выходным ребрами СД.
9. На основании полученной на предыдущем шаге СД построено РВ.
10. Полученное РВ протестировано.
11. Если в процессе тестирования были обнаружены ошибки, то СД, описывающие подзадачи, проанализированы и исправлены. Благодаря разбиению задачи построения РВ на подзадачи, а также наглядности средств описания подзадач, поиск и исправление ошибок в РВ значительно облегчается.
12. При необходимости на основании СД построен конечный автомат (см. [5, с. 168]).

Очень важно подчеркнуть, что конкатенация внутри подзадачи НЕ должна содержать операций объединения (см. выше про алгебраические операции над произвольными языками). Иначе предлагаемый алгоритм НЕ будет упрощать деятельность по построению РВ. Читателю следует помнить, что распространенная конструкция языка РВ (текст)? представима через объединение следующим образом: (текст|).

Проиллюстрируем процесс построения РВ с использованием предлагаемой нами методики на примерах.

Пример 1. Строим РВ для применения в программе поиска шестизначных телефонных номеров в тексте (см. рис. 1).

Рисунок 1. Поиск номеров телефонов. Синтаксическая диаграмма

Мы говорим «может», так как одна и та же грамматика язык-объекта может быть графически представлена по-разному.

Далее СД преобразуется в РВ, которое используется, например, в программе, реализованной на языке Perl:

#!/usr/bin/perl
print "Результаты поиска телефонных номеров в тексте:\n";
while(<>){
   foreach $phone (m/([1-9]\d\d-\d\d\d)
                   |([1-9]\d-\d\d-\d\d)
                   |([1-9]\d\d\d\d\d)
                   |([1-9]\d\s\d\d\s\d\d)/g){
        if(defined($phone)){
                print "\t$phone\n";
        }
   }
}

Сохранив представленный код в файле с произвольным именем, мы можем осуществлять поиск по команде:

./ИМЯ_ФАЙЛА.pl ИМЯ_ТЕКСТОВОГО_ФАЙЛА

Не забудьте только разрешить исполнение программы на Perl:

chmod 0755 ИМЯ_ФАЙЛА.pl

Полученное в результате применения нашей методики РВ может показаться читателю излишне громоздким.

Однако, во-первых, такое РВ быстро строится, легко проверяется на наличие ошибок и не создает неоднозначности в своей интерпретации.

Во-вторых, как только было получено громоздкое рабочее РВ, при желании его можно сократить вручную.

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

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

Рисунок 2. Поиск текста внутри HTML-тэгов. Синтаксическая диаграмма

В данном примере СД круглые скобки не относятся к терминальным символам.

Читатель может самостоятельно составить СД для текста, где имена CSS-классов содержат цифровые последовательности.

Полученную СД преобразуем в РВ и используем в программе на языке Perl:

#!/usr/bin/perl
print "Результаты поиска:\n";

$i=0;
$j=0;

while(<>){
   foreach $phone (m/(<(p)(\s+)(class="[aA-zZ]+")>(.+)(<\/p>))/g){
        if(defined($phone)){
                $line1[$i] = $1."\n";
                $i++;
        }
   }
   foreach $phone (m/(<(p)(\s+)(class="[aA-zZ]+")>(<\/p>))/g){
        if(defined($phone)){
                $line2[$j] = $1."\n";
                $j++;
        }
   }
}

sub uniqum{
        my %duplicate = ();
        my @uniqReturn = ();
        foreach $line (@_){
           if ($duplicate{$line} == 0){
                push(@uniqReturn, $line);
                $duplicate{$line} = 1;
           }
        }
        return @uniqReturn;
}

print uniqum(@line1), uniqum(@line2);

Использование предлагаемой нами методики упрощает процесс построения РВ, облегчает поиск ошибок в РВ, увеличивает переносимость построенных РВ между разными «платформами».

1. Chesnevar C. I. Syntactic diagrams as a tool for solving text-processing problems. ACM SIGCSE Bulletin, Vol. 26, No.4, Dec.1994, pp.35-40. ISSN 0097-8418. URL: http://cs.uns.edu.ar/%7Ecic/1994/1994-sigcse-2/1994-sigcse-2.pdf.
2. Свердлов С.З., Хивина А.А. О структурировании синтаксических диаграмм. // «Вестник Вологодского государственного педагогического университета», № 3, 2008. Серия «Физико-математические и естественные науки». URL: http://uni-vologda.ac.ru/~c3c/articles/About%20the%20structurization%20of%20syntactic%20diagrams.pdf.
3. Терехов А.Н. Технология программирования: Учебное пособие. – М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. – 148 с.
4. Фридл Дж. Регулярные выражения. Библиотека программиста. – СПб.: Питер, 2001. – 352 с.
5. Карпов Ю.Г. Теория автоматов. – СПб.: Питер, 2002. – 224 с.
6. Царьков В. Построение регулярных выражений с помощью синтаксических диаграмм. Часть 1. // «Системный администратор», № 7-8, 2018 г. – С. 50-52. URL: http://samag.ru/archive/article/3689.

Ключевые слова: методика построения РВ, метаязык, синтаксическая диаграмма.

Комментарии могут оставлять только зарегистрированные пользователи