Глава 35. Соответствие шаблону

Разработка
	Глава 35. Соответствие шаблону

Разработка

Неспортивное решение

Определим процедуру matches, принимающую два параметра — шаблон и строку. Процедура будет возвращать истинное или ложное значение в зависимости от успешности сопоставления строки с шаблоном. Остаток программы будет состоять из вызова этой процедуры для двух параметров из командной строки. В зависимости от возвращённого значения программа выводит 'Да' или 'Нет':

Perl
sub matches
{
	…
}

print matches(@ARGV)? "Да\n": "Нет\n";

Теперь займёмся телом процедуры. Отправим переданные параметры в переменные $template и $string:

Perl
my $template=shift;
my $string=shift;

Затем объявим переменную $re. Сначала она будет содержать пустую строку, но впоследствии в ней будет строиться регулярное выражение. Для этого в цикле перебираем символы из строки $template. При переборе выделим четыре случая. Это случай, когда символ равен *, когда равен ?, когда символ нуждается в защите в составе регулярного выражения, и, наконец, когда не нуждается:

Perl
my $re='';
for(split '', $template)
{
	if($_ eq '*')
	{
		$re.='.*';
	}
	elsif($_ eq '?')
	{
		$re.='.';
	}
	elsif(m/[\w\[\]]/)
	{
		$re.=$_;
	}
	else
	{
		$re.="\\$_";
	}
}

В первом случае в конец строки $re добавляется '.*', во втором — '.'. В третьем, самом простом случае символ добавляется как есть. В четвёртом случае добавляется сам символ с предшествующим знаком бэкслэш. Мы считаем не нуждающимися в защите словные символы и квадратные скобки. Очень важно использовать квадратные скобки без защиты, раз мы хотим использовать символьные классы, заданные перечислением символов.

Завершает тело процедуры сопоставление строки $string с регулярным выражением $re и возврат значения, вычисляемого при сопоставлении:

Perl
return $string=~m/^$re$/;

Рекурсивное решение

После громадной подготовительной работы построение программы не представляет никаких трудностей. Вот процедура, которая обрабатывает все восемь случаев:

Perl
sub matches
{
	my $t=shift;
	my $s=shift;

	if($s eq '')
	{
		if($t eq '')
		{
			return 1;
		}
		elsif(substr($t, 0, 1) eq '?')
		{
			return 0;
		}
		elsif(substr($t, 0, 1) eq '*')
		{
			return matches(substr($t, 1), $s);
		}
		else
		{
			return 0;
		}
	}
	else
	{
		if($t eq '')
		{
			return 0;
		}
		elsif(substr($t, 0, 1) eq '?')
		{
			return matches(substr($t, 1), substr($s, 1));
		}
		elsif(substr($t, 0, 1) eq '*')
		{
			return (matches(substr($t, 1), $s) or matches($t, substr($s, 1)));
		}
		else
		{
			return (substr($t, 0, 1) eq substr($s, 0, 1) and matches(substr($t, 1), substr($s, 1)));
		}
	}
}

Однако не будем забывать, что мы пока не занимались квадратными скобками. Скобки добавят ещё четыре случая: два для пустой строки и два для непустой.

Вспомним про встроенную процедуру index. Она принимает в качестве параметров две строки и пытается найти вторую строку внутри первой. В случае неудачи процедура возвращает значение -1, а если поиск удался, возвращается позиция, с которой с первой строке начинается найденная подстрока.

В случае, когда строка $s пуста, для обработки квадратных скобок перед первым else вставляем код

Perl
elsif(substr($t, 0, 1) eq '[')
{
	my $i=index $t, ']';
	if($i>0)
	{
		return 0;
	}
	else
	{
		die "Непарная открывающая квадратная скобка!\n";
	}
}
elsif(substr($t, 0, 1) eq ']')
{
	die "Непарная закрывающая квадратная скобка!\n";
}

Найдя открывающую скобку, сразу ищем после неё закрывающую. Положительное значение индекса $i свидетельствует об удаче. Но пустая строка не может подходить к шаблону, начинающемуся с перечисления символов, поэтому возвращаем 0. Закрывающая квадратная скобка в начале шаблона всегда означает ошибку.

Осталось рассмотреть случай непустой строки $s. Код чуть-чуть усложнится:

Perl
elsif(substr($t, 0, 1) eq '[')
{
	my $i=index $t, ']';
	if($i>0)
	{
		my $chars=substr($t, 1, $i-1);
		return (index($chars, substr($s, 0, 1))>=0
				and matches(substr($t, $i+1), substr($s, 1)));
	}
	else
	{
		die "Непарная открывающая квадратная скобка!\n";
	}
}
elsif(substr($t, 0, 1) eq ']')
{
	die "Непарная закрывающая квадратная скобка!\n";
}

Точно так же, как и раньше, обрабатываются ошибки в шаблоне. Если же с квадратными скобками всё в порядке, символы между ними отправляются в переменную $chars. Возвращаемое выражение истинно тогда и только тогда, когда первый символ $s принадлежит символьному классу и хвост $s подходит к остатку шаблона после закрывающей квадратной скобки.


Идеи реализации		Готовая программа