Опыт портирования библиотеки регулярных выражений


SAGE


Структуры данных в свете парадигм

Найдя в интеренте качественную статью [1, 2, 3, 4, 5, 6] с алгоритмами построения детерминированных конечных автоматов (DFA), реализующих регулярные выражения, я приступил к портированию исходников с С++ на Активный Оберон. Исходники к 5-ой части статьи не вызвали затруднений. Типичный, тривиальный и довольно качественный С++ код, с минимальными вкраплениями ООП. Портирвание кода прилагаемого к 6-ой части статьи вызвало некоторые затруднения ввиду активного использования STL-шаблонов. В двух маленьких процедурах использовались списки, списки списков и карты вместе взятые (vector<>, set<>, set<set<>>, map<>, map<set<>>).

Захотелось найти интересное решение проблемы, с минимальным изменением способа работы с подобными конструкциями в С++. В наличии были лишь реализации списка и сортированного списка предоставленные Томасом Фреем в модуле TFClasses.Mod.

Первое решение в духе ООП, которое напрашивалось, — унаследовать новые классы от этих сортированного или несортированного списков и добавить нужный функционал. Это решение имеет массу недостатков, поскольку в Активном Обероне нет средств для гибкого переопределения и скрытия родительских методов. Работа с такими классами сопровождалась бы постоянными приведениями типов извлечённых из списков элементов, а реализация карт вообще была бы далёкой до элегантной, не говоря уже о типо-безопасности использования таких классов.

Но, решение пришло. Я решил проверить, что можно было-бы реализовать в этом случае, отойдя от парадигмы ООП в сторону компонентной. Я написал пустое определение класса и добавил в него экземпляр класса списка. С точки зрения компонентной парадигмы программирования я добавил список в качестве компонента в новый класс. И тут меня осенило :) Теперь оставалось написать недостающие методы для операций над этим экземпляром списка с нужными типами параметров и возвращаемых значений и, вуаля! Попутно было принято решение написать реализацию универсального списка с возможностью сортировки и проверки на уникальность вставляемых значений. При выключенной сортировке также была бы полезной возможность добавления элементов в конец списка либо в любую заданную позицию, для удобства последующей реализации класса StringList, к примеру. Функция сортировки, наличие или отсутствие сортировки и проверка уникальности вставляемых элементов передаются в качестве параметров констуктора универсального списка.

Реализовав базовый компонент-список, я быстро написал список для элементов типа LONGINT и список списков элементов типа LONGINT. Код класса списка для типа LONGINT:

TYPE
 	LongintItem = POINTER TO RECORD
		value: LONGINT;
	END;
	
	LongintList = OBJECT
		VAR
			list: List;
			
		PROCEDURE &New(options: SET);
		BEGIN
			NEW(list, Compare, options)
		END New;
		
		PROCEDURE Compare(first, second: ANY): LONGINT;
		VAR
			nFirst, nSecond: LONGINT;
		BEGIN
			nFirst := first(LongintItem).value;
			nSecond := second(LongintItem).value;
			IF nFirst < nSecond THEN
				RETURN -1
			ELSIF nFirst > nSecond THEN
				RETURN 1
			ELSE
				RETURN 0
			END
		END Compare;
				
		PROCEDURE Add(x: LONGINT);
		VAR
			item: LongintItem;
		BEGIN
			NEW(item);
			item.value := x;
			list.Add(item)
		END Add;
		
		PROCEDURE Insert(pos: LONGINT; x: LONGINT);
		VAR
			item: LongintItem;
		BEGIN
			NEW(item);
			item.value := x;
			list.Insert(pos, item)
		END Insert;
		
		PROCEDURE Remove(i: LONGINT);
		BEGIN
			list.Remove(i)
		END Remove;
		
		PROCEDURE IndexOf(x: LONGINT): LONGINT;
		VAR
			item: LongintItem;
		BEGIN
			NEW(item);
			item.value := x;
			RETURN list.IndexOf(item)
		END IndexOf;
		
		PROCEDURE GetCount(): LONGINT;
		BEGIN
			RETURN list.GetCount()
		END GetCount;
		
		PROCEDURE GetItem(i: LONGINT): LONGINT;
		VAR
			item: ANY;
		BEGIN
			item := list.GetItem(i);
			RETURN item(LongintItem).value
		END GetItem;
			
	END LongintList;

Для помещения значений типа LONGINT в универсальный список тип LONGINT оборачивается в структуру POINTER TO RECORD, для списков, элементы которых будут объектами, даже и это не требуетеся. Добавление значений в список и извлечение из списка не потребует при использовании экземпляров класса списка создания экземпляров записи и приведения безтипового указателя к типу записи соответственно, всё спрятано внутрь методов объекта. Как бесплатный бонус получаем полный статический (на этапе компиляции) контроль типов при использовании данных классов. Аналогичным образом реализуются списки для любых простых типов и для записей. Единственный код, который нужно будет фактически написать, это код процедуры сравнения элементов для обеспечения правильной работы сортировки, а сортировка обеспечит быструю работу метода IndexOf() и контроль уникальности вставляемых элементов при работе в режиме запрета дублирующихся значений. Отключение режима сортировки имеет смысл при работе со списком как со стеком и при реализации списка строк для обработки текстов.

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

TYPE
 	Transition = RECORD
		iState: LONGINT;
		iData: LONGINT;
	END;
	
	TransitionMapItem = POINTER TO TransitionMapItemDesc;
	TransitionMapItemDesc = RECORD
		trans: Transition;
		iState: LONGINT;
	END;
	
	TransitionMap* = OBJECT
		VAR
			list: Lists.List;

		...

		PROCEDURE Add(CONST trans: Transition; iState: LONGINT);
		VAR
			item: TransitionMapItem;
		BEGIN
			NEW(item);
			item^.trans := trans;
			item^.iState := iState;
			list.Add(item)
		END Add;

		PROCEDURE IndexOf(CONST trans: Transition): LONGINT;
		VAR
			item: TransitionMapItem;
		BEGIN
			NEW(item);
			item^.trans := trans;
			RETURN list.IndexOf(item)
		END IndexOf;
		
		PROCEDURE GetItem(i: LONGINT): TransitionMapItemDesc;
		VAR
			item: ANY;
		BEGIN
			item := list.GetItem(i);
			RETURN item(TransitionMapItem)^
		END GetItem;

	END TransitionMap;

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

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

Коментарии к портированной библиотеке регулярных выражений

  • Все структуры данных, предназначенные для хранения символов, объявлены как переменные типа LONGINT для последующего использования библиотеки со строками в четырёхбайтовой кодировке Unicode;
  • Я немного модифицировал метод Simulate класса DFA для поиска всех строк, удовлетворяющих заданному регулярному выражению во входном тексте.

Использованные источники:

[1] Algorithmic Forays Part 1.

[2] Algorithmic Forays Part 2.

[3] Algorithmic Forays Part 3.

[4] Algorithmic Forays Part 4.

[5] Algorithmic Forays Part 5.

[6] Algorithmic Forays Part 6.



Тип

Имя

Размер

Загрузок

zip

RegExp.zip

10 KiB

193

mht

Algorithmic Forays Part 1.mht

941 KiB

204

mht

Algorithmic Forays Part 2.mht

981 KiB

202

mht

Algorithmic Forays Part 3.mht

975 KiB

193

mht

Algorithmic Forays Part 4.mht

1 MiB

188

mht

Algorithmic Forays Part 5.mht

1 MiB

184

zip

Algorithmic Forays Part 5 source.zip

4 KiB

185

mht

Algorithmic Forays Part 6.mht

1005 KiB

192

zip

Algorithmic Forays Part 6 source.zip

8 KiB

177

mht

Regular Expression Matching Can Be Simple And Fast.mht

160 KiB

180

Дата последнего обновления: 24-1-16 19:14:08


 

Copyright © 2005-2017 SAGE. Все права защищены.