AL_UIR_9 (Синтаксический анализ языка НОРМА. Разбор описания), страница 2

S_треб

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

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

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

à â äðóãóþ îòðèöàòåëüíî-óñëîâíûå. Íà ðèñóíêå ïåðåñå÷åíèå äâóõ òåìíî çàêðàøåííûõ îáëàñòåé íå ïóñòî , à ïåðåñå÷åíèå òåìíî è ñâåòëî çàêðàøåííûõ - ïóñòî. Äðóãîé ñëó÷àé âîçíèêàåò, åñëè îáëàñòè íå èìåþò íè îäíîãî îáùåãî ïðåäêà (õîòÿ òàêîé ñëó÷àé î÷åíü ñòðàíåí â ñìûñëå ëîãèêè ïðîãðàììû). Òîãäà ìû ìîæåì ïðîâåðèòü íà ïåðåñå÷åíèå ñàìûõ ïåðâûõ ïðåäêîâ ýòèõ îáëàñòåé (îíè ÿâëÿþòñÿ ïðÿìîóãîëüíûìè). Åñëè îíè íå ïåðåñåêàþòñÿ, òî è óñëîâíûå íå ïåðåñåêàþòñÿ, èíà÷å ìû ñ÷èòàåì, ÷òî îíè ìîãóò ïåðåñå÷üñÿ.

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

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

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

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

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

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

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

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

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

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

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

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

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