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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра 22Пояснительная записка к КУРСОВОЙ РАБОТЕна тему Синтаксический анализ языка НОРМА. Разбор описаний студента группы К8-02аЖучковаАлександра ВикторовичаНаучныйруководитель Комиссия Оценка Москва 1995г.1.

ВВЕДЕНИЕЗадание, полученное мной на УИР и КП в данном семестреявлялось продолжением работы, начатой в прошлом семестре, и состояло в следующем тщательно изучитьраздел описаний языком программирования Норма разработать структуруданных и алгоритмы для разбора описаний языка программирования Норма написать функции разборараздела описаний.2. Общее описание языка НормаЯзык программирования Норма является декларативным непроцедурным языком и предназначен для спецификации

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

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

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

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

Понятно, что многие из этих вопросов появляются снова на этапе синтезарабочей программы. Однако, здесь они решаются автоматически по строгим правилам,гарантирующим правильность синтезируемой программы.Непроцедурность языка Норма позволяет преодолеть еще однутрудность, связанную с распараллеливанием алгоритма при счете на ЭВМ, допускающихсовмещение операций. Известные методы распараллеливания последовательных алгоритмовоснованы на выявлении, при некоторых

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

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

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

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

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

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

ЭВМ ЕС-1191 и Фортран JNS. Трансляция каждого раздела, входящего в Нормапрограмму, проводится автономно для каждого раздела либо выдается программа навыходном языке, либо, если были обнаружены синтаксические или семантические ошибки,выдается сообщение об ошибке, после чего осуществляется переход к трансляции очередногораздела. Структура транслятор с языка программирования Норма.

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

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

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

Си и библиотеки функций работы с операивной памятью.Передо мной была поставлена задача разработки алгоритмов и написания функций разбораописаний.4.2 Решение задачи. Выбор структуры данныхОдной из конструкций языка Норма являются описания, определяющиеобъекты программы, например, области, индексы, величины, которые необходимы прирешении задачи. В Норме могут быть описаны следующие объекты области, скалярныевеличины

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

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

По ходу сканированияпроисходит проваерки как синтаксических конструкций, так и ряда семантических правил,при этом происходит постепенное накопление в рабочих структурах информации об объекте,которая вслучае успешного окончания разбора заносится в таблицы общего назначения.4.2.1 Разбор параметров областей.Границы диапазонов при описании областей могут задаватьсянеявно - при помощи параметров области. Значения этих параметров должны быть определеныв разделе в описании параметров области.

Параметры области могут входить в арифметические выражения и константныевыражения. Иных способов параметризрвать границы области нет. Разбор параметров области осуществляет фукцияrazb par obl см приложение 3 . При успешном разборе в таблицу имен заносится информацияо идентификаторе, что он есть параметр области и позиция в таблице параметров области,где будет храниться значение параметра, в случае неудачного разбора

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

описания индексов областей.Порядок направлений индексного пространства совпадает с порядком перечисления имениндексов в описании индексов слева направо . Иначе индексы упорядочиваются в порядкепоявления их в различных описаниях. Разбор описаний индексов областей осуществляет фукцияrazb index см приложение 3 . При успешном разборе в таблицу имен заносится информацияо идентификаторе, что он есть индекс области и в таблице индексов происходит упорядочеваниев соответстии с описанием, в случае неудачного разбора

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

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

Считается, что элементы матрицыПЭ нумеруются, начиная с 1. Разбор индексов распределения осуществляет функцияrazb ind rasp см. приложение 3 . При успешном разборе заполняется единственнаядля каждого раздела таблицу индексов распределения туда заносятся имена индексови диапазон , в случае неудачного разбора выдается сообщение об ошибке.4.2.4.Описание индексной конструкцииИндексная конструкция служит для сокращения записи сложныхиндексных выражений и

является простейшим случаем макроопределения. Разбор индексной констркции осуществляет функцияrazb mac ind см. приложение 3 . При успешном разборе в таблицу имен заносится информацияо идентификаторе, что он есть индексная конструкция и в позиция в таблице индексныхконструкций, в которой хранится сама конструкция в виде строки текста, в случаенеудачного разбора выдается сообщение об ошибке.4.2.5.Описание внешних имен функций и раделов.В описаниивнешних имен обязательно указываются имена функций или разделов, которые

являютсяфактическими или формальными параметрами раздела или функции. По умолчанию внешняяфункция имеет тип REAL. Разбор описание внешних имен осуществляют функцииrazb ext fun razb ext part соответсвенно см. приложение 3 . При успешном разборев таблицу имен заносится информация о идентификаторе, что он есть внешняя функцияили раздел и для фукции ее тип, в случае неудачного разбора выдается сообщение обошибке.4.2.6.Разбор описания

области.Понятие области введено в языке Норма для представленияпонятия индексного пространства. Область - это совокупность целочисленных наборов i1 in , n gt 0, ij gt 0, j 1 n, каждыйиз которых задает координаты точки n-мерного индексного пространства. С каждым направлением осью координат n-мерного пространства задачи связывается уникальное имя - имя-индекса имя оси координат индексного пространства .

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

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

операторах ASSUME,в описания входных или выходных величин, при задании областей фактических параметровв вызовах разделов или функций, в функциях редукции.Разбор описания области осуществляют функции razb obl см. приложение 3 . Функция, путем нахождения уникальных лексем или их сочетаний,вызывает для разбора каждой разновидности области свою функцию напримерrazb multobl разбирает описание многомерной области . При успешном разборе в таблицуимен заносится информация о идентификаторе, что он есть имя области

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

REAL, INTEGER или DOUBLE по умолчанию - типREAL Разбор описания области осуществляют функции razb var см. приложение 3 . Функция, путем нахождения уникальных лексем , вызывает дляразбора величин на области функцию razb var obl, а для скаляров функциюrazb var scal пример razb multobl разбирает описание многомерной области. При успешномразборе в таблицу имен заносится информация о идентификаторе, что он есть имя величиныили величины на области, а так же тип величины и номер области для величин определенныхна области, в случае

неудачного разбора выдается сообщение об ошибке.5. ЗАКЛЮЧЕНИЕВ результатепроделанной работы мною были достигнуты следующие цели тщательное изученилраздел описаний языка программирования Норма разработал структурыданных и алгоритмы для разбора описаний языка программирования Норма написал функции разборараздела описаний.Программанаходится на стадии доработки и отладки.Завершение работы планируется в следующем семестре.

Задание на УИР и КП выполнила полностью.Список литературы А.Н. Андрианов, К.Н. Ефимкин, И.Б. Задыхайло, Н.В. Поддерюгина Язык Норма А.Н. Андрианов, К.Н. Ефимкин, И.Б. Задыхайло Непроцедурныйязык Норма и методы его реализации А.Б. Бугеря Реализация математических функций языкаНорма для распределенных высислительных систем

Ф.Льюис Теоретические основы проектирования компиляторов Приложение1 Структуратранслятора с языка программирования Норма Вход Диагностика, ошибки Исходный текст Лексический и частично Синтаксический анализ программы синтаксическийанализ и частично семантический опции командной Выделение Групприровка анализ описаний и операторов строки лексем лексем заполнение всех таблиц начальное

заполнение таблиц Интерфейсные функции ТАБЛИЦЫ ТАБЛИЦЫ имен, констант, Имен, констант, ключевых слов областей, индексов и т. п. МЕНЕДЖЕР ПАМЯТИВыход Текст Генерация Организация Построение графа программы Фортран параллельных информационных на Фортране программы вычислений зависимостей опеаторов программыПриложение 2 Синтаксисописаний языка НормаНотация синтаксисаВ нотации синтаксиса, используемойв данном описании,

применяется расширенная форма Бэкуса-Наура.Обозначения A , A , A1 An , 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 конст-выражение имя-прямоугольной-областиимя-одномерной- областиимя-многомерной-областиимя-нов-об ластиописание-диагональной-областиимя-ди агональной-области имя-безусловной-области список-условие-на-индексОписание условной областиописание-условной-областиимя-усло вной-области , имя-условной-области имя-области условие-на-областьОписание величинописание-скалярных-величинVARIABL E список-имя-скаляра тип описание-величин-на-областях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 Таблица условий 45 j c1 c2 i Eps gt 1 2 i-j Таблица диагональных областей 2 i j c1 c1 Таблица условных областей 25 23 30 1