4
3
Самарский Государственный Аэрокосмический Университет имени академика С.П. Королева
Пояснительная записка к дипломной работе
по информационным технология
Система поддержки гипертекстов
Выполнил: студент группы 621
Хайрутдинов Андрей
Самара
2007 г
Задание
гипертекстовый транслятор перекрестная ссылка
Реализовать гипертекстовый транслятор, позволяющий на основе исходного текстового файла формировать гипертекстовую базу данных.
Реализовать гипертекстовый интерпретатор, позволяющий использовать гипертекстовую базу данных для просмотра исходного текстового файла с помощью перекрестных ссылок.
Реферат
Дипломная работа.
Пояснительная записка: 43 с., 5 рис., 3 табл., 3 приложения, 3 источника.
СИНТАКСИЧЕСКИЙ АНАЛИЗ, ДЕРЕВО РАЗДЕЛОВ, ТЕГОВАЯ РАЗМЕТКА, ДВУХПРОХОДНЫЙ АНАЛИЗАТОР, ГИПЕРТЕКСТ, ТРАНСЛЯЦИЯ, ИНТЕРПРЕТАЦИЯ, СИСТЕМА КОНТРОЛЯ ОШИБОК.
Разработан алгоритм, составлена и отлажена программа анализа текстового файла, содержащего теговую разметку, и его трансляции в разработанный формат базы данных. Выполняются проверки на правильность структуры разметки, на уникальность идентификаторов одного уровня в дереве разделов, на отсутствие неправильных ссылок. В случае определения ошибки, система контроля выдает тип ошибки, а также строку и позиции в строке в исходном файле – место расположения ошибки.
Разработан алгоритм интерпретации файла базы данных. Строится дерево разделов, результат визуализируется.
Язык программирования Object Pascal, операционная система MS Windows.
Обоснование и выбор методов решения
Алгоритмам синтаксического анализа посвящено достаточно большое число источников. В одном из самых известных – /1/ – описывается алгоритм нисходящего разбора, аналог которого я использовал для разбора входного файла.
Структура исходного файла определяется тремя видами специальных парных наборов символов – тегов (&…& трактуется как имя в кавычках):
· <! &…&> … </!> – тег объявления нового раздела – именованного текста, играющего смысловую самостоятельную роль.
· <* &…&&…&…&…&> … </*> – тег объявления ссылки.
· <|> … </|> – тег комментариев.
Результатом разбора является древовидная структура, имеющая в качестве вершин разделы, причем последние хранят также информацию о расположении во входном файле полезной информации и ссылок. Корневая вершина является фиктивной и вводится для возможности применения алгоритмов обхода деревьев. Во время обработки происходит проверка на правильность объявления текущего идентификатора: не допускается какому-либо разделу иметь потомков с одинаковыми именами, в это же время, две различные вершины могут иметь потомков с одинаковыми идентификаторами; таким образом выполняется принцип «области видимости» идентификаторов.
4
3
Рисунок 1 – Пример дерева разделов
После построения дерева происходит проверка на отсутствие ссылок, указывающих на несуществующие разделы. На всем протяжении работы анализатора проверка на правильность тега осуществляется автоматом анализа. Если на каком-либо шаге обнаруживается ошибка, то выполнение алгоритма приостанавливается, ошибка классифицируется в соответствии с табл. 1, и выводится сообщение о типе ошибки и ее положении в исходном файле (номер строки и позиции в ней).
Таблица 1 – Соответствие кодов ошибок в программе их значениям
|
Код ошибки в программе |
Значение |
|
|
0 |
Неправильный синтаксис тега |
|
|
1 |
Повторяющийся на одном уровне идентификатор |
|
|
2 |
Отсутствие закрывающего тега |
|
|
3 |
Неизвестный тег |
|
|
4 |
Отсутствие идентификатора |
|
|
5 |
Неправильная ссылка |
|
|
6 |
Ссылка не принадлежит ни к какому разделу |
Если ошибок не выявлено, то формируются файлы базы данных и ее заголовка. В файле базе данных (*.gdb) хранится полезная информация, т.е. текст, очищенный от теговой разметки, за исключением ссылок. В файле заголовка базы данных (*.dbh) хранится структура дерева, построенного в результате синтаксического разбора исходного файла: номер вершины (согласно внутрипрограммной индексации), ее идентификатор (имя, объявленное в теге), смещение относительно начала файла базы данных и размер фрагмента текста, который относится к данному разделу, и номера вершин-потомков.
На этапе трансляции файл базы данных и ее заголовка считываются, и формируется древовидная структура, аналогичная той, что строилась при разборе. Через интерфейс пользователь может использовать гиперссылки; при этом запускается алгоритм поиска вершины с заданным индексом в дереве (то, что он существует гарантируется на этапе проверки на ссылки на пустые разделы). После нахождения этой вершины пользователю выводится информация, относящаяся к разделу, этой вершиной представляемому.
Описание программы
Общие сведения
Обозначение и наименование: «Гипертекстовый транслятор/интерпретатор».
ПО, необходимое для функционирования: операционная система MS Windows 98 или ее более поздние релизы.
Язык программирования: Object Pascal.
Необходим IBM PC компьютер; специальные устройства не нужны; размер исполняемого файла 455 Кб, 7 Мб оперативной памяти.
Функциональное назначение
Программа выполняет операции обработки, транслирования и интерпретации определенным образом оформленных данных.
Программа предназначена для преобразования исходного файла в базу данных со специальным форматом. Интерпретация этой базы данных позволяет использовать возможности гипертекста – перемещение по базе данных при помощи тематических ссылок.
Программа может оперировать только тремя видами тегов, работает только с текстовыми данными. Иных функциональных ограничений нет.
Структуры данных
Выбор структур данных для вершин дерева анализа определяется следующими факторами. Необходимо хранить следующие данные:
· отрывки текста (пользователь имеет право вставлять подразделы между текстом раздела);
· ссылки, встречающиеся в данном разделе.
Отрывки текста хранятся с использованием двух параметров: смещения относительно начала исходного файла и размера отрывка. Ссылки, кроме этих двух параметров, должны еще хранить имена разделов, на которые они ссылаются.
Т.к. количество ссылок и отрывков для пользователя не регламентируется, то стоит использовать динамическую структуру данных. Т.к. не понадобится извлекать элементы из середины этой структуры и удалять их, то целесообразно предпочесть структуру «динамический массив» структуре «динамический список» в силу простоты реализации и использования.
Использование средств объектно-ориентированного программирования оправдано по следующим причинам:
· размер исходного кода достаточно велик, класс же позволяет замкнуть код, относящийся к нему, внутри себя; т.о. уменьшается вероятность ошибки;
· классы хранят однородную информацию; инкапсуляция полей дает возможность освободить глобальное пространство имен, а также уменьшает вероятность ошибки вследствие неосторожного обращения с полями.
Описание логической структуры программы
Иерархия классов
1. Отношение наследования
4
3
Класс TForm1, описывающий интерфейс, наследуется от системного класса TForm.
2. Отношение агрегирования
4
3
Класс TForm1 агрегирует в себе другие системные классы, используемые в графическом интерфейсе.
Класс TForm1
TForm1 = class(TForm)
TreeView1: TTreeView; // компонент, рисующий дерево
MainMenu1: TMainMenu; // компонент главного меню
N1: TMenuItem; // * кнопки,
N2: TMenuItem; // * используемые
N3: TMenuItem; // * в меню
MenuIm: TImageList; // компонент для упорядоченного хранения
// изображений, используемых в программе
StatusBar1: TStatusBar; // компонент статусной строки
TranslateDialog: TOpenDialog; // * компоненты
OpenDB: TOpenDialog; // * диалоговых
OpenHead: TOpenDialog; // * окон
SaveDB: TSaveDialog; // * ************
Label1: TLabel; // * компоненты
Label2: TLabel; // * надписей
procedure N3Click(Sender: TObject);
procedure FormActivate(Sender: TObject);
procedure N1Click(Sender: TObject);
procedure N2Click(Sender: TObject);
procedure Timer1Timer(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure TreeView1Change(Sender: TObject; Node: TTreeNode);
procedure LinkOnClick(Sender: TObject);
private
ostream: array of TLabel; // * динам. массив объектов класса
// * TLabel (исп. при выводе базы дан.)
procedure FormTreeView;
procedure ClearOstream;
procedure NewOstream(node: pointer);
procedure NewLink(var A: TLabel; ind: integer);
end;
Класс TTitle
Для чтения из базы данных используется следующий класс, образующий древовидную структуру и представляющий собой тип вершины этой структуры.
TTitle = class
ind,offs,size: integer; // * внутренний индекс вершины, смещение
// * информации о ней в файле базы данных
// * и размер текста
name: ansistring; // символьное название вершины
public
list: array of PTitle; // динамический массив ссылок на потомков
// список информации о ссылках в тексте
links: array of record ind,offs,size: integer; end;
procedure DeleteNet; // метод, удаляющий дерево
procedure NewListItem; // метод, добавляющий потомка
procedure NewLink(ind,offs,size: integer); // метод, добавляющий ссылку
property GetOffs: integer read offs; // * свойства скрытых членов
property GetSize: integer read size; // *
property GetInd: integer read ind; // *
property GetName: ansistring read name; // *
property SetOffs: integer write offs; // *
property SetSize: integer write size; // *
property SetInd: integer write ind; // *
property SetName: ansistring write name; // *
end;
Класс TNode
Для хранения информации, прочитанной из исходного файла, используется следующий класс. Также описаны вспомогательные типы.
// запись для хранения информации о ссылке
TLink = record
entry_point,offs,size: integer;
ind: integer;
name: ansistring;
end;
// запись для хранения позиции текста в исходном файле
TPosit = record
offs,size: integer;
end;
TNode = class
ind,offs,size: integer; // информация о положении в исходном файле
// данного раздела и его индекс
procedure GetName(var s: ansistring);
procedure GetLinkName(var s: ansistring);
public
posit: array of TPosit; // динамический массив отрывков текста
name: ansistring; // символьное название раздела
subnodes: array of PNode;// динамический массив ссылок потомков
links: array of TLink; // динамический массив ссылок
// метод, проводящий инициализацию уже созданной вершины
procedure NewNode(var index: integer; var s: ansistring);
// метод удаления дерева
procedure DeleteNet;
// метод, добавляющий новую ссылку
procedure NewLink(var s: ansistring; globalPosition: integer);
// метод, добавляющий в массив потомков новую ссылку и
// инициализирующий ее как NIL
procedure NewListItem;
property GetInd: integer read ind; // * свойства скрытых
property SetInd: integer write ind; // * данных
property GetOffs: integer read offs; // *
property SetOffs: integer write offs; // *
property GetSize: integer read size; // *
property SetSize: integer write size; // *
constructor Create; // * конструктор, производящий
// * начальную инициализацию
end;
Описание физической структуры программы
Иерархия модулей
Иерархия модулей представлена на рис. 2.
4
3
Рисунок 2 – Иерархия модулей
Описание модулей
1. Модуль main.
Содержит вызовы всех процедур обработки исходного файла и содержит вызовы процедур других модулями. Основные функции и процедуры:
· procedure WriteError(var f: text; from,_to,code: integer);
Процедура вывода ошибки кода code. Ошибочные данные содержатся в файле f в позициях с from до _to.
· function Verify(var s: ansistring; var TagType: integer; var ErrorCode, posit1, posit2: integer): boolean;
Функция проверки правильности тега, записанного в строке s. Если синтаксических ошибок не обнаружено, то функция возвращает значение true, а в TagType записывается тип тега; если иначе – false, а в CodeError записывается тип ошибки, расположенной в промежутке между posit1 и posit2 входной строки.
· procedure Dig (var f: text; Root: PNode; var Net: PNode; TagType, globalPos: integer; var len, index: integer; var s: ansistring; var flag: boolean);
Процедура рекурсивной обработки раздела. Root – корневая вершина, Net – текущая вершина дерева раздела. globalPos – переменная, хранящая позицию символа в исходном файле (используется для оповещения системы вывода ошибок). После завершения работы процедура записывает в len количество символов в данном разделе. В flag записывается true, если в процессе обработки ошибок не обнаружено, и false, если иначе.
· procedure FormDB(var f,db,head: text; Net: PNode);
Процедура создания файлов базы данных на основе древовидной структуры, имеющей корень Net.
· function CheckLinks (root, node: PNode; var pos1, pos2: integer): boolean;
Функция проверки ссылок раздела node на отсутствие ссылок на несуществующие разделы (возвращается true) или их присутствие (false). В последнем случае в pos1 и pos2 записываются позиции в исходном файле начала и конца ошибочной ссылки.
· procedure Parser(var f,db,head: text; var index: integer);
Процедура обработки исходного файла (f) и формирования базы данных(db и head). Переменная index – счетчик номеров вершин (используются для внутренней идентификации).
2. Модуль DBInterpretator
Модуль для создания дерева разделов из информации, хранящейся в базе данных. Все процедуры реализованы как методы класса TTitle и описаны в разделе 4.3.
3. Модуль TextTree
Модуль, описывающий древовидную структуру, создаваемую в процессе обработки исходного файла. Процедуры для работы с деревом реализованы как методы класса TNode и описаны в разделе 4.4. Единственная отдельная функция модуля:
· function CheckNames(root, node_to_find: PNode): boolean;
Функция проверки допустимости текущего идентификатора для текущей вершины (node_to_find). Функция возвращает true, если идентификатор допустим, и false в противном случае.
Основные алгоритмы
Алгоритм опознания и проверки тега
Алгоритм выполняется синтаксическим автоматом. На вход автомат получает строку s длины L из исходного файла. Состояние 0 – состояние успеха; -1 – неудачи.
Символ % следует интерпретировать как «все прочие символы из алфавита».
Переменные:
· position – переменная, хранящая текущее состояние автомата;
· TagType – переменная – выходной параметр процедуры – в которую записывается тип тега, определяемый табл. 2;
· i – переменная, хранящая текущую позицию в строке.
Таблица 2 – Типы тегов
|
Числовой тип тега |
Название тега |
|
|
1 |
Тег раздела |
|
|
2 |
Тег ссылки |
|
|
3 |
Тег комментариев |
Лист 001
4
3
Лист 002
4
3
Лист 003
4
3
Лист 004
4
3
Алгоритм трансляции исходного файла
Лист 001
4
3
Лист 002
4
3
Алгоритм обработки части файла, начинающейся с тега
Лист 001
4
3
Лист 002
4
3
Руководство пользователя
Входные данные
Программа получает файл с информацией, организованной соответственно заданной теговой структуры. Внутри теговых скобок незначащим символом является пробел. Между тегами разделов верхнего уровня незначащими символами являются пробел и символ перевода строки.
В комментариях разрешены любые символы (т.к. они игнорируются), но в остальных частях файла запрещены символы, перечисленные табл. 3. Там же обозначены их заменители.
Таблица 3 – Зарезервированные символы
|
Зарезервированные символы |
Заменяющие комбинации |
|
|
& |
&& |
|
|
< |
&1; |
|
|
> |
&2; |
Пример входного файла:
<! &Programming&>Обзор 2-х языков программирования<|>
</|><! &Pascal&>Язык для изучения алгоритмов<|>
</|><! &Author&>Никлаус Вирт</!><|>
</|><! &Birth&>19xx</!>
<|> </|><* &Programming&&Pascal&&Author&>Автор</*>
<|> </|><* &Programming&&Pascal&&Birth&>Год создания</*></!><|>
</|><! &C++&>Язык для профессионального программирования<|>
</|><! &Author&>Бьярн Страуструп</!><|>
</|><! &Birth&>Печатаю для различия 19xx</!>
<|> </|><* &Programming&&C++&&Author&>Автор</*>
<|> </|><* &Programming&&C++&&Birth&>Год создания</*></!><|>
</|></!>
<! &Trigon. Expression&>Рассмотрим уравнение: <* &Trigon. Expression&&cos&>Cos(0)</*> + <* &Trigon. Expression&&sin&>Sin(0)</*> = 1
Как легко видеть, синус и косинус не равны 0 одновременно!<|>
</|><! &cos&>Cos(0) = 1</!><|>
</|><! &sin&>Sin(0) = 0</!></!>
<! &Main&>Верхний уровень<|>
</|><! &Level1&>Уровень 1
<|> </|><* &Main&&Level2&&Level2&>Ссылка на Уровень 2.2</*><|>
</|><! &Level1&>Уровень 1.1
<|> </|><* &Main&>Ссылка на Верхний уровень</*></!><|>
</|><! &Level2&>Уровень 1.2
<|> </|><* &Main&&Level1&>Ссылка на Уровень 1</*></!><|>
</|><! &Level3&>Уровень 1.3
<|> </|><* &Main&&Level2&&Level2&&Level1&>Ссылка на уровень 2.2.1</*></!></!><|>
</|><! &Level2&>Уровень 2
<|> </|><* &Main&&Level1&&Level2&>Ссылка на Уровень 1.2</*><|>
</|><! &Level1&>Уровень 2.1
<|> </|><* &Main&>Ссылка на Верхний уровень</*></!><|>
</|><! &Level2&>Уровень 2.2
<|> </|><* &Main&&Level2&>Ссылка на Уровень 2</*><|>
</|><! &Level1&>Уровень 2.2.1</!><|>
</|><! &Level2&>Уровень 2.2.2</!></!><|>
</|><! &Level3&>Уровень 2.3
<|> </|><* &Main&&Level2&&Level2&&Level1&>Ссылка на уровень 2.2.1</*></!></!></!>
Вызов программы
Программа вызывается как обычное Win32-приложение. Никаких аргументов через консоль получать не предусмотрено.
Описание пользовательского интерфейса
Внешний вид программы представлен на рис. 3.
Рисунок 3 – Внешний вид программы при запуске
Пользовательское меню представлено двумя кнопками: «Транслировать» и «Загрузить БД».
При нажатии на любую из них вызывается диалоговое окно с предложением выбрать файл для открытия. Кроме того, при нажатии на «Транслировать» и после удачной трансляции вызывается диалоговое окно для выбора названия файла сохраняемой базы данных.
Если при трансляции произошла ошибка, то система контроля выдаст сообщение о ней с указанием строки и позиции в ней: см. рис. 4.
Рисунок 4 – Сообщение системы контроля ошибок
После загрузки файла базы данных внешний вид программы становится аналогичным представленному на рис. 5.
Рисунок 5 – Интерфейс после загрузки базы данных
Между разделами передвигаться можно с помощью дерева разделов в левой части или же с помощью ссылок справа (если таковые присутствуют).
Выходные данные
Исходный файл транслируется в два файла: файл базы данных (*.gdb), содержащий полезную информацию, и файл заголовка этой базы данных (*.dbh), содержащий дерево разделов и их потомков.
Пример файла базы данных:
Обзор 2-х языков программированияЯзык для изучения алгоритмов
<3<Автор<
<4<Год создания<Никлаус Вирт19xxЯзык для профессионального программирования
<6<Автор<
<7<Год создания<Бьярн СтрауструпПечатаю для различия 19xxРассмотрим уравнение: <9<Cos(0)< + <10<Sin(0)< = 1
Как легко видеть, синус и косинус не равны 0 одновременно!Cos(0) = 1Sin(0) = 0Верхний уровеньУровень 1
<18<Ссылка на Уровень 2.2<Уровень 1.1
<11<Ссылка на Верхний уровень<Уровень 1.2
<12<Ссылка на Уровень 1<Уровень 1.3
<19<Ссылка на уровень 2.2.1<Уровень 2
<14<Ссылка на Уровень 1.2<Уровень 2.1
<11<Ссылка на Верхний уровень<Уровень 2.2
<16<Ссылка на Уровень 2<Уровень 2.2.1Уровень 2.2.2Уровень 2.3
<19<Ссылка на уровень 2.2.1<
Символ “<” – зарезервированный разделитель ссылок от остального текста (в тексте этого символа быть не может, т.к. там используется заменитель &1;). Числа, находящиеся между двумя разделителями, – индекс вершины, адресуемой данной ссылкой.
Пример файла заголовка базы данных:
0 #1 0 33 8 219 119 11 358 15
1 Programming#2 33 57 5 106 72
2 Pascal#3 90 12 4 102 4
3 Author#
4 Birth#
5 C++#6 178 16 7 194 25
6 Author#
7 Birth#
8 Trigon. Expression#9 338 10 10 348 10
9 cos#
10 sin#
11 Main#12 373 37 16 531 37
12 Level1#13 410 43 14 453 37 15 490 41
13 Level1#
14 Level2#
15 Level3#
16 Level2#17 568 43 18 611 37 21 674 41
17 Level1#
18 Level2#19 648 13 20 661 13
19 Level1#
20 Level2#
21 Level3#
Каждая строка начинается с числа – индекса данной вершины, затем через пробел и до символа “#” записывается символьное имя вершины. После символа “#”, играющего роль разделителя, записываются вершины-потомки в соответствии со следующим правилом: каждый потомок характеризуется тройкой чисел, первое из которых – индекс вершины; второе – смещение от начала файла базы данных информации, относящейся к этому потомку; третье – размер в байтах информации, читаемой от смещения.
Список использованных источников
1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции т. 1. -М.: Мир, 1978.-613 с.
2. Курковский С. Гипертексты с практической точки зрения. Часть 1. ж. «Монитор», № 4 1993.
3. Курковский С. Гипертексты с практической точки зрения. Часть 2. ж. «Монитор», № 5 1993.
Приложение А
Код модуля TextTree
unit TextTree;
interface
type
PNode = ^TNode;
// запись для хранения информации о ссылке
TLink = record
entry_point,offs,size: integer;
ind: integer;
name: ansistring;
end;
// запись для хранения позиции текста в исходном файле
TPosit = record
offs,size: integer;
end;
TNode = class
ind,offs,size: integer; // информация о положении в исходном файле
// данного раздела и его индекс
procedure GetName(var s: ansistring);
procedure GetLinkName(var s: ansistring);
public
posit: array of TPosit; // динамический массив отрывков текста
name: ansistring; // символьное название раздела
subnodes: array of PNode;// динамический массив ссылок потомков
links: array of TLink; // динамический массив ссылок
// метод, проводящий инициализацию уже созданной вершины
procedure NewNode(var index: integer; var s: ansistring);
// метод удаления дерева
procedure DeleteNet;
// метод, добавляющий новую ссылку
procedure NewLink(var s: ansistring; globalPosition: integer);
// метод, добавляющий в массив потомков новую ссылку и
// инициализирующий ее как NIL
procedure NewListItem;
property GetInd: integer read ind; // * свойства скрытых
property SetInd: integer write ind; // * данных
property GetOffs: integer read offs; // *
property SetOffs: integer write offs; // *
property GetSize: integer read size; // *
property SetSize: integer write size; // *
constructor Create; // * конструктор, производящий
// * начальную инициализацию
end;
// функция проверки допустимости идентификатора
function CheckNames(root,node_to_find: PNode): boolean;
implementation
constructor TNode.Create;
begin
inherited;
SetLength(links,0);
SetLength(posit,0);
SetLength(name,0);
SetLength(subnodes,0);
end;
procedure TNode.NewNode(var index: integer; var s: ansistring);
begin
inc(index);
ind:=index;
GetName(s);
end;
procedure TNode.DeleteNet;
var
i,l: integer;
begin
l:=Length(subnodes);
for i:=0 to l-1 do
subnodes[i]^.DeleteNet;
SetLength(Self.links,0);
SetLength(Self.posit,0);
SetLength(Self.name,0);
SetLength(Self.subnodes,0);
Self.Free;
end;
procedure TNode.NewListItem;
var
l: integer;
begin
l:=Length(subnodes);
SetLength(subnodes,l+1);
subnodes[l]:=NIL;
end;
procedure TNode.GetName(var s: ansistring);
var
i,j: integer;
begin
j:=Pos(‘>’,s)-1;
while (s[j] <> ‘&’) do
dec(j);
i:=Pos(‘&’,s)+1;
name:=Copy(s,i,j-i);
end;
procedure TNode.NewLink(var s: ansistring; globalPosition: integer);
var
i,j,l: integer;
begin
i:=Pos(‘>’,s);
j:=Pos(‘</*>’,s);
l:=Length(links);
SetLength(links,l+1);
with links[l] do begin
offs:=globalPosition+i;
size:=j-i-1;
entry_point:=globalPosition;
end;
GetLinkName(s);
end;
procedure TNode.GetLinkName(var s: ansistring);
var
i,j,l: integer;
begin
l:=Length(links)-1;
i:=Pos(‘&’,s);
j:=Pos(‘>’,s)-1;
while (s[j] <> ‘&’) do
dec(j);
with links[l] do begin
name:=Copy(s,i+1,j-i-1);
i:=Pos(‘ ‘,name);
while (i <> 0) do begin
Delete(name,i,1);
i:=Pos(‘ ‘,name);
end;
i:=Pos(‘ ‘,name);
while (i <> 0) do begin
Delete(name,i+1,1);
i:=Pos(‘ ‘,name);
end;
i:=Pos(‘&&’,name);
while (i <> 0) do begin
Delete(name,i,3);
Insert(#0,name,i);
i:=Pos(‘&&’,name);
end;
end;
end;
function CheckNames(root,node_to_find: PNode): boolean;
var
flag: boolean;
p: PNode;
i,l: integer;
// поиск вершины-предка данной
function Go(node: PNode): PNode;
var
i,l: integer;
q: PNode;
begin
l:=Length(node^.subnodes);
i:=0;
while (i<l) and flag do begin
if (node^.subnodes[i]<>node_to_find) then begin
q:=Go(node^.subnodes[i]);
inc(i);
end
else begin
flag:=false;
q:=node;
end;
end;
if flag then
Result:=NIL
else
Result:=q;
end;
function NotEq(A,B: PNode): boolean;
var
i,l1,l2: integer;
begin
l1:=Length(A^.name);
l2:=Length(B^.name);
if (l1 <> l2) then
Result:=true
else begin
i:=0;
while (i<l1) and (A^.name[i]=B^.name[i]) do
inc(i);
Result:=(i<l1);
end;
end;
begin
flag:=true;
p:=Go(root); // ищем предка, далее просматриваем
// список его потомков на предмет
// повторяющихся идентификаторов
l:=Length(p^.subnodes);
i:=0;
while (p^.subnodes[i] <> node_to_find) and
(p^.subnodes[i]^.name<>node_to_find^.name) do
inc(i);
if (p^.subnodes[i] <> node_to_find) then
Result:=false
else begin
inc(i);
while (i < l) and (p^.subnodes[i]^.name <> node_to_find^.name) do
inc(i);
if (i<l) then
Result:=false
else
Result:=true;
end;
end;
end.
Приложение Б
Код модуля DBInterpretator
unit DBInterpretator;
interface
type
PTitle = ^TTitle;
TTitle = class
ind,offs,size: integer; // * внутренний индекс вершины, смещение
// * информации о ней в файле базы данных
// * и размер текста
name: ansistring; // символьное название вершины
public
list: array of PTitle; // динамический массив ссылок на потомков
// список информации о ссылках в тексте
links: array of record ind,offs,size: integer; end;
procedure DeleteNet; // метод, удаляющий дерево
procedure NewListItem; // метод, добавляющий потомка
procedure NewLink(ind,offs,size: integer); // метод, добавляющий ссылку
property GetOffs: integer read offs; // * свойства скрытых членов
property GetSize: integer read size; // *
property GetInd: integer read ind; // *
property GetName: ansistring read name; // *
property SetOffs: integer write offs; // *
property SetSize: integer write size; // *
property SetInd: integer write ind; // *
property SetName: ansistring write name; // *
end;
implementation
procedure TTitle.DeleteNet;
var
i: integer;
begin
for i:=Length(list)-1 downto 0 do list[i]^.DeleteNet;
SetLength(list,0);
SetLength(links,0);
SetLength(name,0);
Self.Free;
end;
procedure TTitle.NewListItem;
var
l: integer;
begin
l:=Length(list);
SetLength(list,l+1);
end;
procedure TTitle.NewLink(ind,offs,size: integer);
var
l: integer;
begin
l:=Length(links);
SetLength(links,l+1);
links[l].ind:=ind;
links[l].offs:=offs;
links[l].size:=size;
end;
end.
Приложение В
Код модуля main
unit man;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ComCtrls, Menus, ImgList, StdCtrls, ExtCtrls, TextTree, DBInterpretator, ActnList;
type
TForm1 = class(TForm)
TreeView1: TTreeView; // компонент, рисующий дерево
MainMenu1: TMainMenu; // компонент главного меню
N1: TMenuItem; // * кнопки,
N2: TMenuItem; // * используемые
N3: TMenuItem; // * в меню
MenuIm: TImageList; // компонент для упорядоченного хранения
// изображений, используемых в программе
StatusBar1: TStatusBar; // компонент статусной строки
TranslateDialog: TOpenDialog; // * компоненты
OpenDB: TOpenDialog; // * диалоговых
OpenHead: TOpenDialog; // * окон
SaveDB: TSaveDialog; // * ************
Label1: TLabel; // * компоненты
Label2: TLabel; // * надписей
procedure N3Click(Sender: TObject);
procedure FormActivate(Sender: TObject);
procedure N1Click(Sender: TObject);
procedure N2Click(Sender: TObject);
procedure Timer1Timer(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure TreeView1Change(Sender: TObject; Node: TTreeNode);
procedure LinkOnClick(Sender: TObject);
private
ostream: array of TLabel; // * динам. массив объектов класса
// * TLabel (исп. при выводе базы дан.)
procedure FormTreeView;
procedure ClearOstream;
procedure NewOstream(node: pointer);
procedure NewLink(var A: TLabel; ind: integer);
end;
var
Form1: TForm1; // объект класса интерфейса – главное окно
struct: PTitle;
flag_enabled: boolean;
source,db,db_head: text;
implementation
{$R *.dfm}
{ *
* функция читает в строку N байт из файла, который д.б. открыт,
* а курсор установлен в нужное место
* }
function GetNStr(var f: text; N: integer): ansistring;
var
ch: char;
begin
Result:=”;
while (N>0) do begin
read(f,ch);
Result:=Result+ch;
Dec(N);
end;
end;
// процедура «перемотки» файла с его начала на n байт. Файл д.б. открыт
procedure FF(var f: text; n: integer);
var
ch: char;
begin
while (n>0) do begin
read(f,ch);
dec(n);
end;
end;
// процедура посимвольного чтения файла
procedure GetFileStr(var s: ansistring; var f: text);
var
ch: char;
begin
reset(f);
s:=”;
while not eof(f) do begin
read(f,ch);
s:=s+ch;
end;
close(f);
end;
// функция, возвращающая указатель на вершину дерева,
// являющуюся предком вершины с индексом ind
function FindTitle(root: PTitle; ind: integer): PTitle;
var
i,l: integer;
begin
l:=Length(root^.list); // кол-во потомков
if l=0 then
Result:=NIL
else begin
i:=0;
// перебир. потомков пока они не закончатся, или ответ не б. получен
repeat
Result:=FindTitle(root^.list[i],ind);
inc(i);
until (i=l) or (Result<>NIL);
end;
end;
// процедура, выводящая на экран информацию об ишибке
procedure WriteError(var f: text; from,_to,code: integer);
const
Error: array [0..6] of string = (‘Неправильный синтаксис тега.’, ‘Повторяющийся внутри одного раздела индентификатор.’, ‘Отсутствие закрывающего тега.’, ‘Неизвестный тег.’, ‘Пустое имя идентификатора.’, ‘Нерабочая ссылка.’, ‘Ссылка не прикреплена ни к какому разделу.’);
var
i,posit,str_num: integer;
ch: char;
s: ansistring;
begin
reset(f);
// *** считаем посимвольно файл; определяем номер строки с ошибкой
// и позицию в ней
i:=0; posit:=0; str_num:=1;
while (i < from) do begin
read(f,ch);
if (ch in [#10,#13]) then begin
read(f,ch);
inc(i);
posit:=1;
inc(str_num);
end
else begin
inc(i);
inc(posit);
end;
end;
// ***
s:=”;
for i:=from to _to do begin
read(f,ch);
s:=s+ch;
end;
inc(posit,Length(s));
MessageDlg(‘Ошибка: ‘ + Error[code] + ‘ Строка ‘ + IntToStr(str_num) + ‘ позиция ‘ + IntToStr(posit)+’: ‘+s+#10#13+’Файл базы данных не создан!’, mtError,[mbOK],0);
end;
// функция проверки правильности тега
function Verify(var s: ansistring; var TagType: integer; var ErrorCode,posit1,posit2: integer): boolean;
var
position,i,l: integer;
begin
l:=Length(s);
position:=1;
i:=1;
while (i<=l) do
case (position) of
-1: i:=l+1;
0: i:=MaxInt;
1: begin
if s[i]='<‘ then position:=2
else position:=-1;
inc(i);
end;
2: case s[i] of
‘ ‘: inc(i);
‘!’: begin inc(i); position:=3; end;
‘|’: begin inc(i); position:=10; end;
‘*’: begin inc(i); position:=11; end;
else begin
position:=-1;
ErrorCode:=3;
posit1:=1;
posit2:=i;
end;
end;
3: case s[i] of
‘ ‘: inc(i);
‘&’: begin inc(i); position:=4; end;
else begin
position:=-1;
ErrorCode:=0;
posit1:=1;
posit2:=i;
end;
end;
4: case s[i] of
‘>’: begin position:=-1; posit1:=1; posit2:=i; ErrorCode:=0;
end;
‘&’: begin inc(i); position:=6; end;
else begin
inc(i);
position:=5;
end;
end;
5: case s[i] of
‘>’: begin position:=-1; posit1:=1; posit2:=i; ErrorCode:=0;
end;
‘&’: begin inc(i); position:=7; end;
else
inc(i);
end;
6: case s[i] of
‘&’: begin inc(i); position:=5; end;
‘1’,’2′: begin inc(i); position:=18; end;
else begin
position:=-1;
posit1:=1;
posit2:=i;
ErrorCode:=0;
end;
end;
7: case s[i] of
‘1’,’2′: begin inc(i); position:=9; end;
‘&’: begin inc(i); position:=8; end;
‘ ‘: inc(i);
‘>’: begin TagType:=1; position:=0; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=i;
position:=-1;
end;
end;
8: case s[i] of
‘&’: begin inc(i); position:=7; end;
‘>’: begin position:=-1; ErrorCode:=0; posit1:=1; posit2:=i;
end;
else begin
inc(i);
position:=5;
end;
end;
9: case s[i] of
‘;’: begin inc(i); position:=5; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=i;
position:=-1;
end;
end;
10: case s[i] of
‘ ‘: inc(i);
‘>’: begin TagType:=3; position:=0; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=i;
position:=-1;
end;
end;
11: case s[i] of
‘ ‘: inc(i);
‘&’: begin inc(i); position:=12; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=2;
position:=-1;
end;
end;
12: case s[i] of
‘>’: begin ErrorCode:=0; posit1:=1; posit2:=i; position:=-1;
end;
‘&’: begin inc(i); position:=13; end;
else begin
inc(i);
position:=14;
end;
end;
13: case s[i] of
‘&’: begin inc(i); position:=14; end;
‘1’,’2′: begin inc(i); position:=19; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=i;
position:=-1;
end;
end;
14: case s[i] of
‘>’: begin ErrorCode:=0; posit1:=1; posit2:=i; position:=-1;
end;
‘&’: begin inc(i); position:=15; end;
else
inc(i);
end;
15: case s[i] of
‘1’,’2′: begin inc(i); position:=17; end;
‘&’: begin inc(i); position:=16; end;
‘ ‘: inc(i);
”: begin inc(i); position:=11; end;
‘>’: begin TagType:=2; position:=0; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=i;
position:=-1;
end;
end;
16: case s[i] of
‘&’: begin inc(i); position:=15; end;
‘>’: begin ErrorCode:=0; posit1:=1; posit2:=i; position:=-1;
end;
else begin
inc(i);
position:=14;
end;
end;
17: case s[i] of
‘;’: begin inc(i); position:=14; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=i;
position:=-1;
end;
end;
18: case s[i] of
‘;’: begin inc(i); position:=5; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=i;
position:=-1;
end;
end;
19: case s[i] of
‘;’: begin inc(i); position:=14; end;
else begin
ErrorCode:=0;
posit1:=1;
posit2:=i;
position:=-1;
end;
end;
end;
Result:=(i = MaxInt);
end;
// рекурсивная процедура обработки раздела
procedure Dig(var f: text; Root: PNode; var Net: PNode;
TagType,globalPos: integer;
var len,index: integer; var s: ansistring;
var flag: boolean);
var
s2: ansistring;
k,i,l,t,code,p1,p2,d: integer;
begin
case TagType of
1: begin
New(Net);
Net^ := TNode.Create;
Net.NewNode(index,s);
if CheckNames(Root,Net) then begin
k:=Pos(‘>’,s);
i:=k+1;
l:=Length(s);
while (i<=l) do begin
if (s[i]='<‘) then begin
d:=Length(Net^.posit);
SetLength(Net^.posit,d+1);
Net^.posit[d].offs:=globalPos+k;
Net^.posit[d].size:=i-k-1;
s2:=Copy(s,i,l-i+1);
if Verify(s2,t,code,p1,p2) then begin
case t of
1: begin // нашли подраздел, добавляем потомка
Net^.NewListItem;
Dig(f,Root,Net^.subnodes[Length(Net^.subnodes)-1],t,globalPos+i-1,d,index,s2,flag);
end;
// нашли ссылку
2: Dig(f,Root,Net,t,globalPos+i-1,d,index,s2,flag);
// нашли комментарий
3: Dig(f,Root,Net,t,globalPos+i-1,d,index,s2,flag);
end;
if flag then begin // если в рекурсии ошибок не было
inc(i,d); // увеличиваем счетчик позиции
k:=i-1; // на длину участка (возвр. рекурс.)
end
else begin
i:=l+1;
end;
end
else
if (i<l-2) then begin // проверяем на закрывающий тег
if (s[i+1]=’/’) and (s[i+2]=’!’) and (s[i+3]=’>’) then
begin
len:=i+3;
i:=l+1;
end
else begin
flag:=false;
WriteError(f,globalPos+i+p1-1,globalPos+i+p2,code);
i:=l+1;
end;
end
else begin
flag:=false;
WriteError(f,globalPos+i-1,globalPos+l-1,3);
i:=l+1;
end;
end
else
inc(i);
end;
end
else begin
flag:=false;
WriteError(f,globalPos,globalPos+Length(Net^.name)+
Pos(‘&’,s)+1,1);
end;
end;
2: begin
i:=Pos(‘>’,s);
l:=Pos(‘</*>’,s);
if i=0 then begin
flag:=false;
i:=Length(s);
WriteError(f,globalPos+i-5,globalPos+i-1,code);
end
else begin
inc(i);
dec(l);
while (i<=l) and not (s[i] in [‘<‘,’>’]) do
inc(i);
if (i>l) then begin
len:=l+4;
Net^.NewLink(s,globalPos);
end
else begin
flag:=false;
WriteError(f,globalPos+i-1,globalPos+i-1,0);
end;
end;
end;
3: begin
i:=Pos(‘</|>’,s);
if i=0 then begin
flag:=false;
i:=Length(s);
WriteError(f,globalPos+i-5,globalPos+i,3);
end
else begin
len:=i+Length(‘</|>’)-1;
end;
end;
end;
end;
function NumLen(n: integer): integer;
begin
Result:=0;
repeat
n:=n div 10;
inc(Result);
until (n = 0);
end;
// процедура создания заголовочного файла
procedure CreateHeadFile(root: PNode; var f: text);
procedure Go(node: PNode);
var
i,l: integer;
begin
write(f,node^.GetInd,’ ‘,node^.name,’#’);
i:=0;
l:=Length(node^.subnodes);
while (i < l) do begin
with node^.subnodes[i]^ do
write(f,GetInd,’ ‘,GetOffs,’ ‘,GetSize,’ ‘);
inc(i);
end;
writeln(f);
i:=0;
while (i < l) do begin
Go(node^.subnodes[i]);
inc(i);
end;
end;
begin
rewrite(f);
Go(root);
close(f);
end;
// процедура создания базы данных
procedure FormDB(var f,db,head: text; Net: PNode);
var
i,posit: integer;
procedure Go(root: PNode);
var
i,j,k,t,w,last: integer;
ch: char;
begin
root^.SetOffs(posit);
{ *
* Далее идет некий аналог MergeSort: происходит слияние
массивов, содержащих текст и ссылки с порядке их появления.
Т.о. получается последовательность с правильным порядком.
* }
i:=0; j:=0;
k:=Length(root^.posit);
t:=Length(root^.links);
reset(f);
last:=0;
while (i<k) and (j<t) do begin
if root^.posit[i].offs<root^.links[j].offs then begin
FF(f,root^.posit[i].offs-last);
for w:=1 to root^.posit[i].size do begin
read(f,ch);
write(db,ch);
end;
last:=root^.posit[i].offs + root^.posit[i].size;
inc(posit,root^.posit[i].size);
inc(i);
end
else begin
FF(f,root^.links[j].offs-last);
write(db,'<‘,root^.links[j].ind,'<‘);
for w:=1 to root^.links[j].size do begin
read(f,ch);
write(db,ch);
end;
write(db,'<‘);
last:=root^.links[j].offs + root^.links[j].size;
inc(posit,root^.links[j].size+3+NumLen(root^.links[j].ind));
inc(j);
end;
end;
if (i = k) then begin
for i:=j to t-1 do begin
FF(f,root^.links[i].offs-last);
write(db,'<‘,root^.links[i].ind,’ ‘,'<‘);
for w:=1 to root^.links[i].size do begin
read(f,ch);
write(db,ch);
end;
write(db,'<‘);
last:=root^.links[i].offs + root^.links[i].size;
inc(posit,root^.links[i].size+4+NumLen(root^.links[j].ind));
end;
end
else
for j:=i to k-1 do begin
FF(f,root^.posit[j].offs-last);
for w:=1 to root^.posit[j].size do begin
read(f,ch);
write(db,ch);
end;
last:=root^.posit[j].offs + root^.posit[j].size;
inc(posit,root^.posit[j].size);
end;
close(f);
{***}
root^.SetSize(posit-root^.GetOffs);
for i:=0 to Length(root^.subnodes)-1 do // рекурсивно применяем
// к потомкам
Go(root^.subnodes[i]);
end;
begin
posit:=0;
rewrite(db);
// запускаем рекурсию для всех разделов верхнего уровня
for i:=0 to Length(Net^.subnodes)-1 do
Go(Net^.subnodes[i]);
close(db);
CreateHeadFile(Net,head); // создаем файл заголовка
Net^.DeleteNet; // удаляем дерево
end;
// вспомогательная функции проверки ссылок функция
function Check(root: PNode; var name_to_find: ansistring; var ind: integer): boolean;
var
t,s: ansistring;
i,iter,l: integer;
begin
t:=name_to_find;
Result:=true;
while (t<>”) and Result do begin
i:=Pos(#0,t);
if (i = 0) then i:=Length(t)+1;
s:=Copy(t,1,i-1);
iter:=0;
l:=Length(root^.subnodes);
while (iter < l) and (s <> root^.subnodes[iter]^.name) do
inc(iter);
if (iter = l) then Result:=false
else begin
root:=root^.subnodes[iter];
ind:=root^.GetInd;
Delete(t,1,i);
end;
end;
end;
// функция проверки ссылок (чтобы ссылались на существующие разделы)
function CheckLinks(root,node: PNode; var pos1,pos2: integer): boolean;
var
i,l: integer;
begin
l:=Length(node^.links);
i:=0;
// сначала проверяем ссылки текущей вершины
while (i<l) and Check(root,node^.links[i].name,node^.links[i].ind) do
inc(i);
if (i = l) then begin
// теперь рекурсивно вызываем проверку для всех потомков
i:=0;
l:=Length(node^.subnodes);
while (i <> l) and CheckLinks(root,node^.subnodes[i],pos1,pos2) do
inc(i);
Result:=(i = l)
end
else begin
pos1:=node^.links[i].entry_point;
pos2:=node^.links[i].offs;
Result:=false;
end;
end;
// главная процедура для обработки входного файла
procedure Parser(var f,db,head: text; var index: integer);
var
posCounter,tag,code,p1,p2,len: integer;
s: ansistring;
flag: boolean;
Net: PNode;
Begin
// создаем фиктивную корневую вершину
s:=’&&>’;
New(Net);
Net^:=TNode.Create;
Net^.NewNode(index,s);
GetFileStr(s,f);
flag:=true;
posCounter:=0;
while (s<>”) and flag do begin
// пропуск незначащих символов
while (s<>”) and (s[1] in [#10,#13,’ ‘]) do begin
Delete(s,1,1);
inc(posCounter);
end;
if (s<>”) then begin
if s[1]<>'<‘ then begin
WriteError(f,posCounter,posCounter,0);
flag:=false;
end
else
if Verify(s,tag,code,p1,p2) then
case tag of
1: begin
Net^.NewListItem;
Dig(f,Net,Net^.subnodes[Length(Net^.subnodes)-1],tag,
posCounter,len,index,s,flag);
if flag then begin
inc(posCounter,len);
Delete(s,1,len);
end;
end;
2: begin
WriteError(f,posCounter,posCounter+3,6);
flag:=false;
end;
3: begin
Dig(f,Net,Net,tag,posCounter,len,index,s,flag);
if flag then begin
inc(posCounter,len);
Delete(s,1,len);
end;
end;
end
else begin
WriteError(f,posCounter+p1-1,posCounter+p2-1,code);
flag:=false;
end;
end;
end;
if flag then
// если синтаксических ошибок нет…
if CheckLinks(Net,Net,p1,p2) then // …проверяем ссылки
FormDB(f,db,head,Net)
else begin
WriteError(f,p1,p2,5);
Net^.DeleteNet;
Net:=NIL;
end
else begin
Net^.DeleteNet;
Net:=NIL;
end;
// процедура создания древовидной структуры при чтении базы данных
procedure ShowDB(var f,h: text);
var
temp: PTitle;
s,name: ansistring;
t,n,l,w,ind,offs,size: integer;
function Go(node: PTitle; n: integer): PTitle;
var
i,l: integer;
t: PTitle;
begin
if (node^.GetInd = n) then Result:=node
else begin
l:=Length(node^.list);
i:=0;
t:=NIL;
while (i<l) and (t=NIL) do begin
t:=Go(node^.list[i],n);
inc(i);
end;
if (t = NIL) then Result:=NIL
else
Result:=t;
end;
end;
begin
New(struct);
struct^:=TTitle.Create;
struct^.SetInd:=0;
reset(h);
while not SeekEOF(h) do begin
readln(h,s);
t:=Pos(‘ ‘,s);
Val(Copy(s,1,t-1),n,l);
Delete(s,1,t);
name:=”;
t:=Pos(‘#’,s);
name:=Copy(s,1,t-1);
Delete(s,1,t);
temp:=Go(struct,n);
temp^.SetName:=name;
if (s <> ”) then begin
l:=Length(temp^.list);
while (s <> ”) do begin
SetLength(temp^.list,l+1);
New(temp^.list[l]);
temp^.list[l]^:=TTitle.Create;
t:=Pos(‘ ‘,s);
Val(Copy(s,1,t-1),w,n);
temp^.list[l]^.SetInd:=w;
Delete(s,1,t);
t:=Pos(‘ ‘,s);
Val(Copy(s,1,t-1),w,n);
temp^.list[l]^.SetOffs:=w;
Delete(s,1,t);
t:=Pos(‘ ‘,s);
Val(Copy(s,1,t-1),w,n);
temp^.list[l]^.SetSize:=w;
Delete(s,1,t);
reset(f);
FF(f,temp^.list[l]^.GetOffs);
name:=GetNStr(f,temp^.list[l]^.GetSize);
close(f);
t:=1;
n:=Length(name);
while (t<n) do begin
if (name[t]='<‘) then begin
offs:=t-1;
inc(t);
w:=t;
while (name[t]<>'<‘) do
inc(t);
Val(Copy(name,w,t-w),ind,size);
inc(t);
while (name[t]<>'<‘) do
inc(t);
size:=t-w+2;
temp^.list[l]^.NewLink(ind,offs,size);
end;
inc(t);
end;
inc(l);
end;
end;
end;
close(h);
end;
end.
