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

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: рефераты бесплатно, сочинение рассуждение
| Добавил(а) на сайт: Борисюк.

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

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

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

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. ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

Ф.Льюис “Теоретические основы проектирования компиляторов”
* Квант - семантически законченный фрагмент текста программы(например, описание области)