На главную > Программисту> Статьи > Конвертирование текста в структуры данных

Конвертирование текста в структуры данных

Журнал ВАНТ

УДК 681.3.06

Конвертирование текстовых форм директив в табличные

Н.П.Вельдяксов

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


В настоящее время во многих вычислительных системах общение пользователя с компьютером происходит посредством директив или команд - строк текста определенного формата, задаваемых с клавиатуры. Для анализа директив и выбора их программ-исполнителей в программном обеспечении ЭВМ имеются специальные компоненты. Например, в операционной системе ОС РВ для СМ ЭВМ это программа интерпретации командных отрок. Будем такую программную компоненту называть конвертором. Рассмотрим принципы создания конвертора.

Программы-испшшители директив на основе заданных в директивах параметров производят те или иные действия. Очевидно, эти программа писать легче, если рассчитывать на входную информацию для них не в виде символьной строки текста директивы, а в виде некоторой структуры данных, таблицы, для обработки которой в используемом языке программирования есть необходимые средства. Табличные формы директив будем называть в дальнейшем заявками. Конвертор анализирует тексты директив, строит заявки и обеспечивает запуск программ-исполнителей директив. Возможны разные подходы к созданию конверторов. Конвертор может быть специализированным, когда он выполняет перевод директив известного ему фиксированного формата в заявки наперед заданной структуры. Анализ текста директивы в конверторе может быть сделан универсальным. В этом случае конвертор использует некоторое описание формата директивы. Аналогично универсальным может быть сделано и построение заявки. В этом случае заявка строится на основе описания ее структуры. Если трудоемкость ввода новых описаний или изменения старых описаний ниже, чем модификация программы неуниверсального конвертора, то создание универсального конвертора оправдано.

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

Рассмотрим вопросы анализа текста директивы.

Директивы содержат код операции и набор необходимых операндов (параметров), отделенных друг от друга определенными разделителями. Например, директивы открытия и закрытия файлов могут иметь вид:
ОТФ 1; ММ1.ММ2/Ф1;Т/22
ЗКФ 22

По коду операции конвертор определяет программу-исполнителя данной директивы.

Операнды задаются в позиционной форме, порядок их существен. Код операции отделяется от поля операндов не менее чем одним пробелом. В коде операции пробелы недопустимы. В поле операндов пробелы могут быть где угодно, конвертор перед обработкой поля операндов их удалит.

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

Аналогичным образом в графической форме можно описывать формат директив. При этом задается весь набор операндов, а рядом с каждой вершиной дерева указывается обязательность вхождения операнда в директиву. Операнды, входящие в операнд типа массива, должны задаваться в директиве один или более раз. Операнды, входящие в операнд типа записи, могут быть обязательными к заданию в директиве или необязательными. Для необязательных операндов могут предусматриваться правила умолчания. Но возможны необязательные операнды и без умолчаний. В последнем случае будем говорить,что операнд имеет пустое значение. Например, в директиве открытия файла имя файла – обязательный операнд, режим обработки файла имеет значение по умолчанию, а пароль может отсутствовать (пусто), для него умолчаний нет. В директиве закрытия файлов, формат которой приведен на рис.1, все поле операндов (операнд М01) есть операнд типа массива, диапазон кодов открытия (операнд 311) есть элемент этого массива, а коды открытия (операнды Т21 и Т22) есть элементы записи (операнда 311).


Рис.1. Пример формата директивы закрытия файлов

Примерами директив закрытия файла, соответствующих приведенному на рис.1 формату, могут быть следующие директивы:
ЗКФ 1-3
ЗКФ 1-3, 5-7
ЗКФ 1-3, 5-7, 10, 12
ЗКФ

На рисунках приняты следующие обозначения:
УР – уровень;
ОБ – обязательный операнд;
ПУ – есть пустое значение;
УМ: N1-N2 – имеется умолчание: N1-N2;
ЭМ – элемент массива;
3 – запись;
М – массив;
Т – простое поле (терминал).

Графическое представление формата директивы, имеющей операнды типа записей с вариантами, выглядит не намного сложнее.

Дерево, задающее структуру поля операндов конкретной директивы будем сокращенно называть деревом структуры, а дерево, задающее формат директивы, – деревом формата.

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

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

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

(А, Б, В), Г

=

(Т21, Т22, Т23), Т12

(А, , В), Г

=

(Т21, , Т23), Т12

(А, Б), Г

=

(Т21, Т22), Т12

А, Г

=

Т21, Т12

Варианты неправильного задания операндов директивы:

А, Б, В, Г

=

Т21, Т12 + лишние операнды

А, , В, Г

=

Т21, пропущен обязательный + лишние операнды

А, Б, Г

= Т21, Т12+ лишний операнд


Рис.2. Пример формата директивы

В директивах файловой системы разрешено использовать круглые и квадратные скобки. Оба типа скобок равноправны. Необходимо лишь следить, чтобы парные скобки были одного типа. Например, конструкции "(([()]))" и "([[()]])" корректны, а конструкция "(([()))]" некорректна.

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

Одновременно с анализом текста директивы конвертор строит необходимую заявку, опираясь на описание структуры заявки. Заявка описывается при помощи специально разработанного аппарата поддержки структур данных на основе макросредств ассемблера MACRO-11 для СМ ЭВМ [1]. Структура заявки аналогична структуре поля операндов. В ней могут быть терминальные поля, массивы, записи, как обычные, так и с вариантами. Структура заявки представима в виде дерева, листовые вершины которого соответствуют простым полям (терминалам), а нелистовые - массивам или записям. На рис.3 приведен пример структуры заявки.


Рис.3. Пример структуры заявки

Построение заявки осуществляется в том же порядке, что и построение дерева структуры поля операндов директивы – сверху вниз, слева направо.

Отметим еще один момент, также отражающий степень универсальности конвертора. Структура заявки и структура поля операндов представимы в виде деревьев. Между формами этих деревьев связь есть, однако иногда нежелательно, чтобы они в точности повторяли друг друга. Допустим, директива имеет три параметра: A, B и C. По смыслу их желательно задавать в порядке A, B, C. Пусть операнды A и C обязательны, а для операнда В возможно умолчание. Тогда объединение операндов A и B в один операнд и назначение в нем нового разделителя позволяет упростить текст директивы при использовании умолчаний. Покажем это на примерах.

В директиве, формат которой представлен на рис.4.а, операнды A и B в один операнд не объединены. Полная форма записи операндов имеет вид A, B, C, а пропуск операнда B записывается как A, , C.

В директиве, формат которой представлен на рис.4.6, операнды A и B объединены в один операнд З11. Полная форма записи операндов в этом случае имеет аналогичный вид A ; B, C, а пропуск операнда B записывается проще, чем в предыдущем случае: A, C.


Рис.4. Пример формата директивы:
а - операнды A и B не объединены в один операнд;
б -операнды A и B объединены в один операнд

В заявке, напротив, такое объединение полей, соответствующих операндам A и B, в одно поле (запись) делать не всегда целесообразно, так как это может привести к усложнению ее обработки.

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

Схема взаимосвязи структуры заявки и структуры поля операндов для рассматриваемого конвертора следу кщая: терминальным полям заявки соответствуют терминалы поля операндов, массивам в заявке соответствуют операнды типа массивов, записям в заявке – операнды типа записей. Однако не для каждого операнда типа записи есть соответствующая запись в заявке. Например, для операнда типа записи З11 на рис.4.б нет соответствующей записи в заявке на рис.5.


Рис.5. Пример структуры заявки

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

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

Подготовка конвертора к работе происходит в несколько этапов. Первоначально готовятся необходимые макроопределения описаний и затем оформляется вызов этих описаний путем обращения к соответствующим макрокомандам. Трансляция и построение этого вызова готовят необходимую для обработки директивы информацию в доступной конвертору форме. После этого конвертор готов к обслуживанию потока директив.

Конвертор текстов директив написан на ассемблере MACRO-11 СМ ЭВМ с широким использованием макросредств. Программа отлажена и работает в среде специализированной операционной системы (ОС) процеосора управления данными [2]. В этой ОС допустимы только программы, написанные на ассемблере. Поэтому для работы, например, в среде языков высокого уровня данный конвертор не предназначен. Перенос конвертора в другие ОС на СМ ЭВМ принципиальных трудностей не составит. В настоящее время конвертором обслуживаются десятки директив некоторой файловой системы. Объем реализации следующий. Программа конвертирования содержит 868 строк, занимает в памяти 5614 байтов. Таблица. дешифрации директив и вызовы описаний директив содержат практически по одной строке на директиву. Форматы 40 директив описываются 226 макроопределениями общим объемом 1474 строки. Средства описания форматов директив содержат 20 макроопределений общим объемом 228 строк. Заявки к 40 директивам описываются 92 макроопределениями общим объемом 348 строк. Средства описания заявок к директивам содержат 23 макроопределения общим объемом 268 строк. Строки комментарии, .MACRO и .ENDM не учитывались.

Приведем в заключение пример описания формата одной директивы файловой системы и заявки к ней. Макросы, посредством которых производятся описания, из-за их большого объема в данной статье не приводятся.

;Описание заявки к директиве регистрации пользователя
;----------------------------------------------------
.MACRO$S.Z5;описание заявки к директиве
$SZAP Z5, C ;запись постоянной длины
$SELM Z5, S1, SP, D ;шифр группы
$SELM Z5, S2, SP, D ;шифр регистрируемого пользователя
$SELM Z5, FM, FM, D ;фамилия
$SELM Z5, RA, RA, D;ранг
$SELM Z5, PW, PW, D, F;пароль
$SKZAP Z5 
.ENDM   
;   
.MACRO $S.SP;описание поля шифр
$STER SP, 2, B;длина 2 байта
.ENDM
;
.MACRO $S.FM;описание поля фамилия
$STER FM, 20, B;длина 20 байтов
.ENDM
;
. MACRO $S.RA ;описание поля ранг
$SMNO RA, 2, B ;длина 2 байта
$SEM RA, PR ;прикладной программист
$SEM RA, SY ;системный программист
$SEM RA, AD ;администратор системы
.ENDM
;
.MACRO $S.PW ;описание поля пароль
$STER PW, 10, B;длина 10 байтов
.ENDM
;
;Описание формата директивы регистрации пользователя
;---------------------------------------------------
.MACRO$H.RPG ;описание формата директивы
$H.RPG:
$SSTR Z5;вызов описания заявки
$G$VTP $H.145 ;вызов описания операнда 0 уровня
.ENDM
;
.MACRO$H.145;описание операнда 0 уровня
$H.145:
$HZAP Z5, <,> ;подоперанды разделяются запятой
$HELM OB, Z5, S1, $H.034;шифр группы, обязателен
$HELMOB, Z5, S2, $H.034 ;шифр пользователя, обязателен
$HELM OB, Z5, FM, $H.147 ;фамилия, обязательна
$HELMUM, Z5, RA, $H.016, $A145A;ранг, есть умолчание
$HELMPU, Z5, PW, $H.048;пароль, может отсутствовать
$HKZAP
$G$VTP <$H.034, $H.147> ;вызов описаний подоперандов
$G$VTP <$H.016, $H.048>  
$G$VTP $A145A ;вызов описания умолчания
.ENDM
;
.MACRO$H.034 ;описание операнда шифр
$H.034:
$HTER SP, N2 ;числовой
.ENDM
;
.MACRO $H.147;описание операнда фамилия
$H.147:
$HTER FM, SIM, $D.FM ;символьный, указанной ОДЗ
$G$VTP $D.FM ;вызов описания ОДЗ
.ENDM
;
.MACRO $D.FM ;опис. ОДЗ симв.операнд фамилия
$D.FM:
$DSZ <ЮЧ, AZ, .., __> ;рус/лат буквы, точка, подчерк.
.ENDM
;
.MACRO $H.016 ;описание операнда ранг
$H.016:
$HTER RA, P, $D.RA ;перечислимый, указанной ОДЗ
$G$VTP $D.RA ;вызов описания ОДЗ
.ENDM
;
.MACRO$D.RA;опис. ОДЗ перечисл. операнд ранг
$D.RA:
$DPERA, PR, <ПРИ, ПРИКЛАДНОЙ_ПРОГРАММИСТ, PR1>
$DPERA, SY, <СИС, СИСТЕМНЫЙ_ПРОГРАММИСТ, SYS>
$DPEKRA, AD, <АДМ, АДМИНИСТРАТОР_ДАННЫХ, ADM>
.ENDM
;
.MACRO $A145A ;описание умолчания операнда ранг
$A145A:
$AUM ПРИ 
.ENDM
;
.MACRO $H.048 ;описание операнда пароль
$H.048:
$HTER PW, SIM, $D.P1;символьный, указанной ОДЗ
$G$VTP $D.P1 ;вызов описания ОДЗ
.ENDM
;
.MACRO$D.P1 ;описание ОДЗ симв. операнд пароль
$D.P1:
$DSZ <09, ЮЧ, AZ> ;десятичные цифры, рус/лат буквы
.ENDM

Список литературы

  1. Вельдяксов Н.П.
    Организация структур данных в ассемблере MACRO-11 СМ ЭВМ с помощью макросредств.
    Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 1989.Вып.2. С. 70-75.
  2. Мазурин Ю.Н., Охрименко Г.П., Петунин С.А.
    Функциональная структура операционной системы процессора управления данными.
    Вопросы атомной науки и техники. Сер. Методики и программы численного решения задач математической физики. 1983. Вып. 3(14). С. 59-61.

Статья поступила в редакцию 30.05.89.

Интернет-конкурс Золотой сайт