Навигация
4 Описание и решение задачи.
4.1 Постановка задачи.
В программе, написанной на языке Норма могут встречаться следующие специфические объекты:
параметры областей, задающие в неявном виде границы диапазонов при описании областей;
индексы областей, которые задают как бы имена различным кординатным направлениям в областях.
индексы распределения, служащие для отображения двух индексных направлений индексного пространства области задачи на матрицу процессорных элементов (ПЭ) распределенной системы;
индексные конструкции, служащие для сокращения записи сложных индексных выражений;
внешние функции и разделы;
области;
скалярные величины и величины на области
(синтаксис смотри приложение 2).
Как видно из вышеперечисленного, наиболее важным и информативным объектом является описание области. Дейсвительно, и индексы и параметры области являются лишь вспомогательными понятиями, делающими описания областей более удобочитаемыми или более гибкими. Для величин, определенных на области, их области являются тем множеством, на котором они существуют. Понятие области введено в языке Норма для представления понятия индексного пространства. Область - это совокупность целочисленных наборов {i1,...,in}, n>0, ij>0, j=1,...,n, каждый из которых задает координаты точки n-мерного индексного пространства. С каждым направлением (осью координат) n-мерного пространства задачи связывается уникальное имя - имя-индекса (имя оси координат индексного пространства). Следует отметить, что область определяет значения координат точек индексного пространства, а не значения расчетных величин в этих точках. Так же следует отметить то, что все множества должны быть конечны, т.к. конечно пространство памяти ЭВМ, на которое будут в последствии отображатся величины на области.
Разработчики языка Норма на основании опыта, накопленного ими при решении задач вычислительной математики, решили, что для решения большинства задач подобного класса достаточно ввести следующие разновидности областей:
прямоугольные;
диагональные;
условные.
В свете вышесказанного перед нами (группой разработчиков) встала задача напсания транслятора с языка Норма с использованием инструментальных средств языка программирования Си и библиотеки функций работы с оперативной памятью. Передо мной были поставлены задачи:
разработка структур для хранения данных, полученных в результате разбора описаний областей;
разработка алгоритмов и написание функций разбора описаний;
разработка алгоритмов для написания функций пересечения областей
4.2 Решение задачи. Выбор структуры данных
Проанализировав различия и сходство той информации, которую необходимо хранить для каждой разновидности области, мною, при согласовании с разработчиками языка и моими коллегами, были выбраны следующие структуры.(смотри приложение 4 ).
Во первых, главная таблица областей (далее просто таблица областей), в которой для всех областей хранится количество направлений (мерность множества), по каждому направлению имя индекса и значения левой и правой границ, тип области, ключ для поиска детальной информации в других таблицах. Решено было ввести четыре типа области: прямоугольная - она характерна тем, что проекцией на любую двумерную систему координат будет прямоугольник; диагональная - это область, границы которой по некоторым направлениям могут быть прямые под углом 45° к оси; положительно-условные - это часть родительской области, на которой логическое выражение, задающее эту область будет выдавать значение правда; отрицательно-условные - это то же, что и положительно-условные, только логическое выражение будет выдавать значение ложь. Получилось так, что таблица областей вышла неоднородной, так как могут существовать области с различным количеством направлений. Хранить эту таблицу в массиве с размером полей, расчитанным на максимально возможное количество направлений, я посчитал нерациональным. Была рассмотрена возможность реализации хранения на списках, но эта возможность мною тоже была отвергнута, потому что получился бы список с большим количеством мелких элементов, что затруднило бы работу менеджера памяти (которому на каждый такой элемент пришлось бы заводить рабочие структуры, что тоже использовало бы память), а так же увеличило бы время работы. Поэтому было решено хранить эти таблицы в одном большом буфере и иметь специальные функции, позволяющие производить запись и чтение из этого буфера. Этот способ экономен в использовании памяти (мало пустующего пространства), удобен менеджеру памяти (работает с одним блоком), достаточно быстрый доступ. Тем более что похожий механизм был ранее реализован моим коллегой при работе с таблицей имен на этапе лексического анализа, и он согласился реализовать эти функции.
Во-вторых, таблица диагональных областей, где хранится детальная информация, позволяющая полностью охарактеризовать диагональную область, а именно: количество диагональных плоскостей, по каждой диагональной плоскости имена индексов и константы пересечения диагоналей с осью, определенной первым индексом. Например, если индексы родительской области находятся в пределах 1Ј i Ј10 1Ј j Ј5, а условие имеет вид i < j то построение записи в таблицу будет таким :
j j
c2
5
1 c1
1 10 i i
Так как получается схожая с таблицей областей картина, а именно, записи в таблице диагональных областей могут иметь различную длину, решено было использовать тот же механизм хранения информации.
В-третьих, таблица условных областей, в которой хранится номер положительно-условной области, отрицательно-условной области, родительской области, ключ для поиска условия в таблице условий. Так как поля данной таблицы однородны, то она легко хранится в структуре массива. В основном данная таблица была заведена с целью сохранения связи положительно- и отрицательно-условных областях, имеющих общую родительскую область. Это впоследствии облегчает проведение таких операций, как пересечение над условными областями.
В-четвертых, на основе механизма, использовавшегося для хранения таблицы областей, была создана таблица условий, в которой хранятся логические выражения, заданные при описании условных областей.
Похожие работы
... ресурсы вычислительной машины, а именно оперативную память, что зачастую правильно написанную программы невозможно оттранслировать из за нехватки оперативной памяти. Поэтому было решено перевести транслятор с языка программирования Норма на язык программирования Си, который был выбран по следующим причинам: - язык Си позволяет гораздо более эффективно использовать ресурсы вычислительной ...
... озвончения в середине слова после безударного гласного в словах французского происхождения. Зав. кафедрой -------------------------------------------------- Экзаменационный билет по предмету ИСТОРИЯ АНГЛИЙСКОГО ЯЗЫКА И ВВЕДЕНИЕ В СПЕЦФИЛОЛОГИЮ Билет № 12 Дайте лингвистическую характеристику "Младшей Эдды". Проанализируйте общественные условия национальной жизни Англии, ...
... В таком словаре для всех глаголов (около 20 тыс. в русском языке) должно быть указано, какими падежами и с какими предлогами производится это управление. Вершиной компьютерного анализа текста является автоматическое реферирование. Наличие семантической сети понятий, соединенных глаголами, позволяет сформулировать основные идеи текста документа, отраженные в часто встречающихся понятиях и связях, ...
... » по Образовательной системе «Школа 2100» // Начальная школа плюс До и После. – 2006. - № 4. 9. Купров В.Д. Словарная работа на уроках русского языка // Начальная школа. – 1990. - № 3. 10. Львов М.Р. и др. Методика обучения русскому языку в начальных классах. – М., 1987. 11. Методика грамматики и орфографии в начальных классах. / Под ред. Н.С.Рождественского. – М., 1975. Задание 2. Путем ...
0 комментариев