МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) Кафедра 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>0, ij>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 (конст-выражение) имя-прямоугольной-области имя-одномерной-области имя-многомерной-области имя-нов-области описание-диагональной-области имя-диагональной-области : имя-безусловной-области / список-условие-на-индекс Описание условной области описание-условной-области имя-условной-области , имя-условной-области: имя-области / условие-на-область Описание величин описание-скалярных-величин 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 .... .... .... ....