Разработка алгоритмов и реализация функций разбора описаний областей

4.3 Разработка алгоритмов и реализация функций разбора описаний областей

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

Чтобы учесть эти два случая при описании области без имени я решил заводить новые имена в таблице имен и отождествлять их с этими областями. Для этого строится расширение уже существующей таблицы имен. При разборе мною был использовался метод прямого анализа. Разбор осуществляется последовательным сканирование цепочки лексем слева направо. По ходу сканирования происходит проверки как синтаксических конструкций, так и ряда семантических правил, при этом происходит постепенное накопление в рабочих структурах информации об объекте, которая в случае успешного окончания разбора заносится в таблицы общего назначения. Разбор описания области осуществляет функция razb_obl (см. приложение 3). Функция, путем нахождения “уникальных” лексем или их сочетаний, вызывает для разбора каждой разновидности области свою функцию (например, razb_multobl разбирает описание многомерной области). Затем каждая отдельная функция разбирает описание своей области и при успешном окончании заполняет нужные таблицы (областей, диагональных областей и т.д.), а так же таблицу имен. В случае неудачного разбора выдается сообщение об ошибке.

4.4 Разработка алгоритмов для фукций работы с областями

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

FOR B ASSUME X=F(Z,Y[i+1,j]...)

S_треб

FOR C ASSUME Y=F(P,K[i-1,j]...)

области С пустое множество. Если дает, то данные операторы не связаны между собой, иначе второй оператор необходимо вычислить раньше первого.

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

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

Помимо пересечения областей часто требуется найти объединение. Эту задачу аналитическими методами решить очень сложно, поэтому планируется реализовать ее методом перебора

5. ЗАКЛЮЧЕНИЕ

В результате проделанной работы мною были достигнуты следующие цели:

разработаны сновные структуры для хранения данных, полученных в результате разбора описаний областей;

разработаны алгоритмы и написаны функции разбора описаний областей;

разработаны алгоритмы для написания функций пересечения областей

Некоторые функции находится на стадии доработки и отладки. Завершение работы над ними планируется в следующем семестре. Задание на УИР и КП выполнил практически полностью.

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

А.Н. Андрианов, К.Н. Ефимкин, И.Б. Задыхайло, Н.В. Поддерюгина "Язык Норма"

А.Н. Андрианов, К.Н. Ефимкин, И.Б. Задыхайло "Непроцедурный язык Норма и методы его реализации"

А.Б. Бугеря "Реализация математических функций языка Норма для распределенных высислительных систем"

Ф.Льюис “Теоретические основы проектирования компиляторов”

* Квант - семантически законченный фрагмент текста программы(например, описание области)

Приложение1 Структура транслятора с языка программирования Норма

Вход: Диагностика, ошибки

Исходный текст Лексический и частично Синтаксический анализ

программы + синтаксический анализ и частично семантический

опции командной Выделение Групприровка анализ описаний и операторов

строки лексем лексем заполнение всех таблиц

начальное заполнение таблиц

Интерфейсные функции

ТАБЛИЦЫ ТАБЛИЦЫ

(имен, констант, (Имен, констант,

ключевых слов областей,

индексов и т. п.)

МЕНЕДЖЕР ПАМЯТИ

Выход:

Текст Генерация Организация Построение графа

программы Фортран параллельных информационных

на Фортране программы вычислений зависимостей опеаторов

программы

Приложение 2 Синтаксис описаний языка Норма

Нотация синтаксиса

В нотации синтаксиса, используемой в данном описании, применяется расширенная форма Бэкуса-Наура.

Обозначения {A}*,{A}⁺,{A₁...,A_n},[A] означают

{A}*	::=	Ж|A|AA...
{A}+	::=	A|AA...
{A1...,An}	::=	A1|...|An
[A]	::=	Ж|A

где A-некоторый объект языка, Ж- пусто, |- выбор одной из альтернатив, ...- и так далее.

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

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

Обозначение список-элемент заменяет непустой список элементов, перечисленных через запятую:

список-элемент

элемент{,элемент}*

В каждом конкретном случае определение элемента приводится.

Описания

описание:

описание-области

описание-индексов-областей

описание-скалярных-величин

описание-величин-на-области

описание-индексной-конструкции

описание-индексов-распределения

описание-параметров-области

описание-входных

описание-выходных

описание-внешних

Описание областей

описание-области:

описание-безусловной-области

описание-условной-области

описание-безусловной-области

описание-прямоугольной-области

описание-диагональной-области

область

новая область без имени

имя-области

безусловная-область

новая область без имени

имя-безусловной-области

имя-области

имя-безусловной-области

имя-условной-области

имя-безусловной-области

имя-прямоугольной-области

имя-диагональной-области

Описание параметров области

описание-параметров-области

DOMAIN PARAMETERS список-значение

значение

имя-параметра-области=целое без знака

Описание индексов областей

описание-индексов-областей

INDEX список-имя-индекса

Описание индексов распределения

описание-индексов-распределения

DISTRIBUTION INDEX имя-индекса = простой-диапазон

[имя-индекса=простой-диапазон]

простой-диапазон

цел-константа[..цел-константа]

Описание индексной конструкции

описание-индексной-конструкции

MACRO INDEX имя-индексной-конструкции

[список-явное-инд-выражение]

явное-инд-выражение

имя-индекса[{+,-}конст-выражение]

имя-индекса = конст-выражение

имя-индекса = имя-индекса [{+,-}конст-выражение]

Описание внешних имен

описание-внешних-имен

EXTERNAL FUNCTION список-имя-функции [тип]

EXTERNAL PART список-имя-раздела

Описание областей

описание-области

описание-безусловной-области

описание-условной-области

описание-безусловной-области

описание-прямоугольной-области

описание-диагональной-области

область

новая область без имени

имя-области

безусловная-область

новая область без имени

имя-безусловной-области

имя-области

имя-безусловной-области

имя-условной-области

имя-безусловной-области

имя-прямоугольной-области

имя-диагональной-области

Описание безусловной области

описание-прямоугольной-области

многомерная-область

новая-область

многомерная-область

одномерная-область

[ имя-многомерной-области ]: ( область-произведение )

область-произведение

составляющая-область { ; составляющая-область }⁺

составляющая-область

многомерная-область

имя-прямоугольной-области

одномерная-область

[ имя-одномерной-области ] : ( имя-индекса = значение )

значение

диапазон

конст-выражение

диапазон

конст-выражение .. конст-выражение

новая-область

[имя-нов-области :] новая-область-без-имени

новая-область-без-имени

имя-безусл-области / список-модификация

модификация

имя-индекса=значение

имя-одномерной-области {{+,-} функция-границ}⁺

функция-границ

LEFT (конст-выражение)

RIGHT (конст-выражение)

имя-прямоугольной-области

имя-одномерной-области

имя-многомерной-области

имя-нов-области

описание-диагональной-области

имя-диагональной-области :

имя-безусловной-области / список-условие-на-индекс

Описание условной области

описание-условной-области

имя-условной-области , имя-условной-области:

имя-области / условие-на-область

Описание величин

описание-скалярных-величин

VARIABLE список-имя-скаляра [тип]

описание-величин-на-областях

VARIABLE список-определение-величин-на-област [тип]

определение-величин-на-области

список-имя-величины-на-области

DEFINED ON безусловная-область

тип

{REAL , INTEGER , DOUBLE}

Приложение 4 Схема информационных таблиц областей.

ТАБЛИЦА ОБЛАСТЕЙ

2	i	1	5	j	10	40	...	1
1	k	0	100	...	...	...	...	3
5	j	5	15	t	1	50	...	2
....	...	...	...	...	...	...	...	...

Таблица условий

j c1 c2 i

Eps>1/2*(i-j)...

Таблица диагональных областей

2	i j c1 c1	...
...	...	...

Таблица условных областей

25	23	30	1
...	...	...	...