Содержание к диссертации
Введение
ГЛАВА І. Общесистемное обеспечение диалога 10
1.1. Общее описание специализированной операционной системы II
1.2. Файловая система 16
1.3. Директивы управляющей программы 17
1.4. Макровозможности спепдализированной операционной системы 20
1.5. Утилиты специализированной операционной системы 23
ГЛАЗА II. Метаязыковое обеспечение диалога 27
2.1. Лексический анализ 29
2.2. Синтаксический анализ 31
2.2.1. Двухмагазинный автомат и отношения предшествования Колмерауэра 32
2.2.2. Язык описания синтаксиса и его реализация 35
2.2.3. Организация хранения правіш грашяатики 38
2.3. Семантические вычисления 38
2.4. Структура управляющей программы 41
2.5. Историческая справка 42
ГЛАВА III. Структура терактивной графической системы "атлас" 44
3.1. Общее описание 45
3.2. Связь с банком данных 48
3.3. Графические объекты системы 48
3.4. Файл изображения системы "Атлас" 51
3.5. Подсистема шшишзапии 55
ГЛАЗА ІV. Входной язык интерактивной графической системы "атлас" 57
4. Ї. Подготовка файла данных 57
4.2. Загрузка системы, её внешние устройства 60
4.3. Язык диалога и основные команды системы "Атлас" 61
4.3.1. Команды присваивания значений текущим элементам изображения 61
4.3.2. Команды формирования изображения 68
4.3.3. Команды распечатки и графического построения изображения .' 71
4.3.4. Команды машшулпроваыия таблицами 75
4.3.5. Команды подсистемы шгаимизации 78
4.3.6. Дополнительные команды "Атлас" 80
4.4. Место "Атлас" среда интерактивных систем графики ." 81
Заключение
- Макровозможности спепдализированной операционной системы
- Двухмагазинный автомат и отношения предшествования Колмерауэра
- Графические объекты системы
- Команды присваивания значений текущим элементам изображения
Введение к работе
Быстрое развитие и совершенствование электронной техники в настоящее время позволяют создавать вычислительные комплексы необходимой конфигурации и мощности. Стали технически реализуемы и экономически выгодны системы, которые ранее не создавались из-за высокой стоимости оборудования. Одновременно совершенствуется и программное обеспечение вычислительных машин. Однако тенденции снижения стоимости и временных затрат на разработку программного обеспечения не наблюдается, наоборот, соотношение затрат на приобретение технических средств и разработку математического обеспечения непрерывно изменяется в сторону увеличе- /I 2/ кия затрат (денежных, временных) на программное обеспечение7 ' '
По этой причине разработка и внедрение новых методов создания программного обеспечения систем обработки данных, реализация систем с широким спектром применения, обеспечение возможности их функционального расширения, адаптации к изменяющимся условиям эксплуатации приобретают большое значение.
В последние два десятилетия в системах обработки данных получил значительное развитие диалоговый режим. Диалоговый режим "является существенно необходимым при реализации таких систем, где управление процессом обработки данных либо вообще не может быть полностью автоматизировано, либо такая автоматизация не эффективна" ' .
Диалоговый режим находит все большее применение и в автоматизированных системах обработки и анализа экспериментальных данных в физике высоких энергий. Сложность событий, регистрируемых современными экспериментальными установками, эвристичность алгоритмов анализа и обработки событий делает крайне актуальной реализацию диалогового режима при разработке алгоритмов анализа и при полуавтоматической обработке данных эксперимента.
В последние годы в различных лабораториях мира ' ' интенсивно развиваются автоматизированные системы, предназначенные для проведения феноменологического анализа экспериментальных данных. Поисковый характер анализа делает практически невозможным проведение таких исследований без гибкого графического интерактивного взаимодействия исследователя с ЭВМ и базами экспериментальных данных.
Перечисленные выше системы в физике высоких энергий, как правило, реализуются на языках Фортран и Ассемблер, которые практически не предоставляют программисту средств для организа ции диалога. По этой причине разработка программных средств, направленных на автоматизацию создания интерактивных программ, является первоочередной задачей обеспечения диалога. Программным средствам обеспечения диалога в ИФВЗ и посвящена настоящая дис сертация, j
В первой главе диссертации рассматривается системное обеспечение диалога, которое было создано диссертантом для ЭВМ ICL-1903A. Данное обеспечение представляет собой специализированную операционную систему, являющуюся надстройкой над штатным диспетчером ЭВМ, и включает в себя: средства поддержания архива дисковых файлов с двухуровневой организацией; базовый набор директив системы; интерпретатор с языка управления заданиями, поддерживающий механизм определения макродиректив, позволяющих неограниченно расширять базовый набор директив системы, адаптируя её к кон- кретным условиям функционирования; - широкий набор утилитов, таких, как контекстный редактор, програтшы для работы с дисковыми файлами, магнитными лентами и т.п.; - библиотеку макродиректив, которые совместно с утилитами предоставляют богатые сервисные возможности для программиста- разработчика.
Разработка языка управления заданиями велась в соответствии с принципом - структура языка управления заданиями и его конструкции должны быть аналогичны тем, которые используются в существующих алгоритмических языках программирования. При этом макродирективы операционной системы эквивалентны процедурам (подпрограммам) в языках программирования. Язык управления заданиями позволяет программировать динамическое переключение ввода/вывода с одного устройства (файла) на другое устройство (файл). Механизм перехвата сообщений о произошедшем программном событии, направляемых на операторский телетайп, позволяет программировать ту или иную реакцию на конкретное сообщение. Эта возможность предоставляет гибкое средство взаимодействия макродиректив с выполняемыми под управлением операционной системы программами пользователей.
Программное обеспечение, которому посвящена первая глава, ориентировано на общесистемную поддержку диалога. Этого недостаточно для автоматизации разработки диалоговых программ. Программное обеспечение диалога должно включать метаязыковое обеспечение, ориентированное на создание интерпретаторов языков диалога. Этому посвящена вторая глава диссертации.
Диалоговый режим использования интерпретаторов накладывает следующие требования на алгоритмы синтаксического и семантического анализа входных сообщений: алгоритмы анализа должны быть достаточно быстры; используемые алгоритмы должны находить и хорошо локализовать все ошибки во входном сообщении; программы, реализующие алгоритмы анализа, должны быть компактны.
Эти требования приводят к определенным ограничениям на массы грамматик, предназначенных для описания входных языков диалоговых программ. Из известных к настоящему времени классов грамматик практически удовлетворяет всем перечисленным требованиям класс грамматик полного предшествования или грамматик Колмерауэра. Программное обеспечение, рассматриваемое во второй главе, включает в себя: параметрически настраиваемый лексический анализатор; параметрически настраиваемый синтаксический анализатор для грамматик полного предшествования; процессор, преобразующий описание лексики, синтаксиса и семантики языка в матрицу предшествования и таблицы, управляющие лексическим, синтаксическим и семантическим анализами.
Метаязыковое обеспечение диалога представляет собой систему, автоматизирующую построение интерпретаторов проблемно-ориентированных языков. Предложен способ синхронизации построения вывода входной цепочки с обходом дерева в обратном порядке для грамматик Колмерауэра, приведен эффективный алгоритм вычисления матрицы предшествования для грамматики, реализована схема связи синтаксического анализа входной строки с семантическими вычислениями. п С .
На основе предложенных программных средств диалога разработана и реализована интерактивная система "Атлас", предназначенная дяя проведения феноменологических исследований экспериментальных данных.
В третьей главе рассматривается организация системы "Атлас", типы графических объектов, поддерживаемые системой, её назначение и функциональные возможности. Введен специальны!! тип данных, названный изображением, представляющий собой иерархическую структуру для хранения графических объектов. Определены понятия текущих элементов изображения, введены правила формирования изображения. Система "Атлас" предоставляет пользователю диалоговый язык высокого уровня. Язык "Атлас" предназначен для манипулирования двумерными графическими объектами, заданными аналитически или в виде дискретных таблиц экспериментальных зависимостей, хранящихся в банке данных экспериментов физики частиц ИФВЭ.
Система "Атлас" позволяет решить следующие задачи: формировать графические образы, соответствующие табличным данным; формировать проблемно-ориентированные графические обзоры-атласы содержания баз данных; организовывать визуальный сравнительный анализ данных при их отборе и поиске эмпирических закономерностей; организовывать сопоставление теоретических схем описания с экспериментом; организовывать сравнение конкурирующих моделей описания данных.
Последняя четвертая глава диссертации посвящена детальному описанию входного языка системы "Атлас" и технологии её использования в задачах изучения и сравнительного анализа данных. В этой главе описаны средства подготовки файла данных, структурно представляющего собой последовательность таблиц экспериментальных данных, информация о которых вынесена в отдельный каталог. Команда системы "Атлас" разбиты на следующие группы: команды присваивания значении текущим элементам изображения; команды формирования изображения; команды вывода на графические устройства; набор команд манипулирования таблицами экспериментальных данных; команды управления минимизацией; сервисные команды.
Команды системы допускают переменное число параметров, порядок аргументов не фиксирован, широко использовано правило задания значений параметров по умолчанию. Возможность генерации системы, подключения собственных библиотек пользователя позволяют создавать версии системы требуемой конфигурации, настраивать систему на решение конкретных проблем.
Данная система реализует почти все процедуры феноменологического анализа на единой технологической основе. "Атлас" используется в ИФВЭ в задачах поиска эмпирических закономерностей, для контроля ввода информации в базу данных, для организации сопровождения моделей описания данных и формирования соответствующих графических атласов.
Основные результаты диссертации докладывались на международной конференции в Падуе 1976 г., Втором Всесоюзном семинаре э. по обработке физической информации (Ереван, 1978), Втором Всесоюзном совещании "Диалоговые вычислительные комплексы" (Серпухов, 1979), Всесоюзной конференции "Диалог "Человек - ЭВМ" (Ленинград, 1982) и опубликованы в работах /у~16/.
Макровозможности спепдализированной операционной системы
Директивы, описанные в предыдущем разделе, позволяют производить управление задачей пользователя в "ручном" режиме. По мере эксплуатации системы возникло требование автоматизации работы программиста и оператора. Для этой цели в G0C был введен макропроцессор и созданы библиотеки макросов - процедур на языке управления заданиями. Язык управления заданиями позволяет запрограммировать стандартные реакции на различные события, которые возмошш при прохождении задания. Для обеспечения этой возможности в управляющей программе реализован механизм перехвата сообщений оператору, сигнализирующих о произошедшем программном событии. Процедура - макрос на языке управления заданиями представляет собой последовательность команд. Каждая команда занимает одну строку, первые четыре символа которой отведены под поле метки. В качестве параметров макросов могут быть использованы данные типа IITEGER ИЛИ символьные строки. Формальный параметр идентифицируется комбинацией %ы, где ЇЇ - номер параметра.
В теле макроопределения допустимы вызовы других макросов. Распознавание макровызова осуществляется по специальному предварительно определенному сиг/волу ":". Вслед за ним идет шля макроса и список параметров. Параметры отделяются друг от друга запятыми.
Когда с терминала введено сообщение, интерпретатор команд проверяет его на директиву управляющей программы. Если это директива, она выполняется, если нет - считается, что это макровызов. Производится загрузка макрогенератора, которому передается введенное сообщение. Макрогенератор осуществляет поиск макроопределения в текущей библиотеке макросов, если не находит, то ищет в библиотеке макросов общего назначения. Если макроопределение не найдено в этих библиотеках, выдается сообщение об ошибке. В том случае, когда макроопределение найдено, макрогенератор осуществляет подстановку параметров, поиск макровызовов, генерацию текста задания. Текст задания записывается в служебный файл, из которого макроинтерпретатор считывает строки и выполняет-их.
Нике описываются основные операторы языка управления заданиями, ядро которого составляют директивы управляющей программы.
Операторы передачи управления Существуют безусловные операторы передачи управления: GO МЕТКА - переход на метку; GO + IT - переход на ж операторов вниз; GO - її - переход на її операторов вверх. Условные операторы имеют вид: IP; событие & оператор безусловного перехода или IF г событие - текст оператор безусловного переходах Событием считается программное прерывание. Оно происходит по следующим причинам: останов программы, ошибка в программе, окончание её работы:
Событие := HALT/ ILLEGAL / DLTD Первый вариант команды производит передачу управления, если произошло указанное событие, второй - позволяет анализировать не только причину прерывания, но и сопроводительный текст.
В программах используются экстракоды вывода сообщений на операторский телетайп без приостановки программы. В некоторых случаях желателен анализ и зтих сообщений. Введены команды включения этих сообщений в разряд событий:
DiSpi - сообщение рассматривается как событие; HoDispi - появление сообщения не вызывает входа в макроинтерпретатор.
В качестве имени события используется СЛОВО "DISPL". Управление выдачей протокола работы
Существуют команды, с помощью которых производится слежение за выполнением глакродиректив: Но List - на термінал выводятся только сообщения об окончании макродиректив; Short List - на терминал выводятся все сообщения программы; Pull List - в дополнение к предыдущему выводятся все операторы языка управления заданиями. .
Оператор приостановки макродирективы Suspend Macro TEXT
На терминале появляется сообщение о приостановке макродирективы с соответствующим текстом. После этого возможно "ручное" управление заданием, а затем запуск его на продолжение командой Go Macro .
Двухмагазинный автомат и отношения предшествования Колмерауэра
Приведенные в этом разделе понятия, необходимые для дальнейшего изложения, в основном следуют работе / /.
Контекстно-свободная грамматика (КС-грамматика) задается четверкой G=(vn,vt,p,s), где: vn - словарь нетерминальных символов; vt- - словарь терминальных символов; Р - конечное подмножество множества vtx(v Uvt) . Элементы ( / ) множества Р называются правилами вывода и записываются в.виде с/.— /з, s=V. /3 ("V [) V, ) ; S - ВЫДелеННЫЙ СИМВОЛ ИЗ V . называемый начальным.
Двухмагазинный автомат для грамматики G состоит из двух стеков, содержащих части строки w, которые можно изобразить так: [_ v w2 -j , ГДЄ v/=w.W2; v/1 ,\72 . (\0 Vt) . Начальной конфигурацией автомата является 1-А v/ - где А _ пустая, w - входная строки, а конечной конфигурацией автомата для G h A s -\ где s - начальный символ грамматики. Работу автомата определяет конечное множество инструїсций з виде (х1 ,х2) —- (у1 ,у2) , где x Zg.y yg 6 (VnUvt) ._
Если в данный момент конфигурация автомата имеет вид -u1x1 х2и2 -) , где u1,u2,x1,x2 (VnUvt) , и существует инструкция (х.рх2)— (у15у2),то автомат выполняет эту инструкцию и переходит в новое состояние i-uiyi у2и2
Различаются детерминированные и недетерминированные двух-магазинные автоматы. Для первого автомата в каждом его состоянии существует только одна инструкция, которая может быть применена. Если .же существует конфигурация, в которой могут быть применены несколько инструкций, то такой автомат становится недетерминированным. В этом случае можно представить, что автомат распадается на несколько подавтоматов, которые продолжают работать параллельно. Подавтоматы останавливаются, если достигают конечной конфигурации, либо для данного состояния нет допустимой инструкции.
В приведенном определении ничего не говорится о том, каким образом инструкции автомата связаны с грамматикой G, порождаемые строки которой распознает данный автомат. Отношения предшествования дают простой и эффективный способ задания множества инструкций автомата.
Предположим, что между символами грамматики G определены три бинарных отношения , = ,. на объединенном словаре vn U vt. Введем три вспомогательных символа : - концевой символ, которым ограничивается анализируемая строка с обоих концов, а символы Г и ] используются для выделения сзер-тываемой конструкции при синтаксическом анализе входной строки. Тогда инструкции автомата вводятся следующим образом для пары символов А,В объединенного словаря и правил грамматики и— и: (А,В) — (А[В,Л), только в том случае, если А В или (А= # и В # ); (А,В) — (АВ,А), только в том случае, если А = В; (А,В) — (А],В), только в том случае, если А В или (А # иВ=#); { [и] ,А)-»(Л, и) только в том случае, если есть правило и—и.
Итак, для того чтобы полностью описать работу конкретного автомата, необходимо для заданной грашлатики G уметь строить отношения предшествования. Нике приводится способ построения отношений предшествования, принадлежащий Колмерауэру.
Дяя всех символов А,В объединенного словаря определим три вспомогательных отношения о ("сменность"), А ("слева") и /о ("справа"): А с . В, ЄСЛИ В Р ЄСТЬ ПраВИЛО U— хАВу; А X В, если в Р есть правило А- Ву; А /О В, если в Р есть правило в- хА, где х,у (vn U vt) .
Бинарные отношения U., \, о удобно представлять в виде булевых матриц, для которых определены операции умножения и все операции булевой алгебры.
Если R - отношение на множестве V/, то k-ая степень отношения R вводится следующим образом: і aR ъ только в том случае, когда aRb; у aR ъ только в том случае, когда существует такое otfW, ЧТО aR с и cRb. Транзитивное замыкание отношения R на множестве V/ обозначается R+ .и определяется так: R = U R1.
Графические объекты системы
В этом разделе вводятся графические объекты (типы данных), поддерживаемые системой. Наряду с такими простыми объектам!, как точка (РОШТ), отрезок прямой (ЫНЕ), прямоугольник (ВЕСТ), текстовая строка (TEXT), которые используются, главным образом, для оформления рисунков, введены более сложные объекты: экспериментальная точка с несимметричными ошибками по обеим координатам (GROSS), таблица экспериментальных данных (TABLE), аналитически заданная функция (РШГ).
Таблица экспериментальных данных - это совокупность отдельных экспериментальных точек (объектов CROSS), отражающая некоторую зависимость Y(X). TABLE определяется либо конкретной таблицей экспериментальных данных, хранящейся в файле данных, тогда она задается своим номером N, либо это вновь сформиро ванная таблица. Формируется таблица с помощью операций объединения и пересечения таблиц или объектов CROSS. Другой способ формирования таблицы - задание алгоритма вычисления таблицы, т.е. задание функции Y=P(T(N.,),... ,T(Nk)), где специальная функция т(и) соответствует N -ой таблице из файла данных.
Объект PUN задается в интерактивном режиме в виде алгоритма на языке системы, осуществляющего вычисление Y и/или X в виде: - У=Р(Х); - МЧУ); - в параметрическом виде Y=P(s) Х=Р (s).
При определении функции могут быть использованы Фортра-новские библиотечные функции и специальные функции, встроенные в систему. Среди специальных функций особое место занимает PT(N,X), соответствующая таблице экспериментальных данных с номером N. Эта функция для заданного х вычисляет значение У, интерполируя его методом Лагранжа по узлам таблицы.
Каждый графический объект определяется данными и значениями его атрибутов. Данные определяют объект - его положение, систему координат, в которой он задан, и т.п., а атрибуты управляют его визуализацией. Так, для объекта PUN данные - это алгоритм вычисления функции, количество параметров функции, значения параметров, признак системы координат, в которой она задана, а атрибуты - тип линии для её изображения, размеры штриха и промежутка между штрихаьж.
Объекты PUN, TABLE имеют сложную собственную структуру данных. Их введение позволяет обращаться с ними как с элементарными объектами, не зная, напршяер, формата хранения отдельных точек таблицы. Основные графические объекты, с которыми манипулируют команды "Атлас", представлены в таблице I. Графические объекты могут быть заданы в одной из трех систем координат: - система координат исходных данных, в которой заданы экспериментальные данные в файле данных; - система координат отображения - MAP; - система координат экрана обобщенного устройства вывода.
При разработке "Атлас" сделана попытка объединить два направления специализированных систем - систем, созданных для обработки данных, которые используют графический вывод только для представления результатов обработки, и графических систем, основным назначением которых является генерация изображения, манипулирование им. Дяя этих целей-в системе "Атлас" существует файл изображения, структура которого приведена на рис. 7.
Файл изображения состоит из упорядоченной последовательности картин (PICTURE), которые в свою очередь разбиваются на последовательность сегментов (SEGMENT). Сегмент делится на носитель (SUPPORT), который задает форму сегмента, и фрагмент (FRAGMENT) - содержательную часть сегмента. SUPPORT - носитель сегмента, определяется пятью элементами : VIEWPORT - поле индикации, т.е. область экрана, где будет размещаться изображение сегмента;
Команды присваивания значений текущим элементам изображения
Поле индикации определяется двумя точкаші (X1,Y1) и (X2,Y2), задающими диагональ прямоугольной области. Х1 , Y1 , Х2 , Y2 - арифметические выражения, допустимые в языке системы. Значения арифметических выражений должны лежать в пределах от 0. до 1023. тв _ точка должна быть введена с координатного устройства ввода.
Поле индикации, заданное директивой SET VPT..., можно раз бить на несколько одинаковых областей командой SET VPTL, Р1 , Р2 , РЗ Р1 - номер области разбиения; Р2 - число разбиений ПО ОСИ X; РЗ - число разбиений по оси Y. Области нумеруются последовательно слева направо и сверху вниз. Задание окна в поле исходных данных SET WINDOW, , Ошго) Х1 , Y1 ЇВ , Х2 , Y2 ТВ Две точки (X1,Y1) и (X2,Y2) определяют диагональ прямоугольной области в поле исходных данных.
Координатное устройство ввода ТВ используется только доія переопределения WINDOW, т.е. первоначально необходимо определить окно с помощью числовых значений координат. Другой вариант команды задания окна имеет вид: SET WINDOW , номер таблицы из файла данных (WIND)
Размеры окна выбираются так, чтобы все точки указанной таблицы попали в него. Команда SET WINDOWG,/список номеров таблиц (WINDG) введена для автоматического определения размеров окна для группы таблиц. Все точки указанных в списке таблиц попадают в него. Задание преобразования исходных данных: SET LIA.P,(X=F (X,Y) Y=P (X,Y))
Введенное преобразование действует на окно в поле исходных данных, которое пересчитывается и отображается в поле индикации, и на графические объекты, заданные в системе координат исходных данных. В некоторых случаях нежелателен автоматический пересчет WINDOW, поэтому введена команда, явно задающая размеры преобразованного окна. SET WINDOW!!, Х1 , Y1 Х2 , Y2 (WINDH)
Графические объекты, заданные в системе координат исходных данных, отсекаются заданным WINDOW, пропускаются .через преобразование MAP И преобразованные координаты объектов отсекаются WIND0WM. Задание обратного преобразования SET IMAP,(X=F (X,Y) Y=F (X,Y)) x у
Задание ІМАР необходимо при использовании координатного устройства ввода ТВ при введенном преобразовании MAP. о Задание осей координат SET AXES,і строка- х I J строка- у г ] KB KB ) строка-х и строка-Y определяют соответственно имена х и Y осей.
Параметр КБ означает выход на чтение соответствующего текста с клавиатуры. Существуют параметры, влияющие на рисование осей, такие, как выбор шкалы по осям, задание размера символов, шрифта, моды рисования и т.п.
Эта команда задает текстовую строку и точку начала рисования текста. Список параметров указывается для введения в строку текста вычисляемых выражений. В качестве параметров используются арифметические выражения действительного или целого типа. Символьное представление значения очередного параметра подставляется вместо очередного символа п%". В команде должно быть соответствие числа сш.юолов "%" и количества параметров в списке. Можно указать.число позиций для значения параметра комбинацией символов "%.И", где N - число позиций. Если значение занимает меньше позиций, чем указано в и, оно дополняется слева пробелами, в противном случае и не учитывается, и в строку вставляется значение параметра полностью.
CROSS можно задавать и с помощью координатного устройства ввода ТВ. Первым снимается центр точки, далее снимаются ветви креста. Порядок снятия ветвей несущественен, значение центра уточняется при снятии ветвей креста.
