автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка инструментальных средств автоматизации проектирования трансляторов перспективных языков программирования для векторно-конвейерных ЭВМ

АКАДЕМИЯ НАУК СССР

НАУЧНЫЙ СОВЕТ ПО КОМПЛЕКСНОЙ ПРОБЛЕМЕ «КИБЕРНЕТИКА»

На правах рукописи

УДК 681.3.068:681.325 ЗЕВИНА Светлана Георгиевна

РАЗРАБОТКА ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ТРАНСЛЯТОРОВ ПЕРСПЕКТИВНЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ДЛЯ ВЕКТ0РН0-К0НВЕЙЕРНЫХ ЭВМ

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин и систем

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

МОСКВА 1991

Работа выполнена в Научном совете по комплексной проблеме «Кибернетика»" Академшгнаук СССР

• Научный руководитель: доктор технических наук, профессор 10. Г. ДАДАЕВ

Официальные оппоненты: доктор технических наук, профессор О. Н. ПЕРМЕНОВ, кандидат физико-математических наук С. В. НЕСТЕРОВ

Ведущая организация: Институт точной механики 1 вычислительной техники Академии наук СССР

Защита состоится «_»_1991 г. в_часов на

заседании специализированного совета Д.002.82.01 Научного Со вета АН СССР по комплексной проблеме «Кибернетика» по адре су 117333 Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Совета.

Автореферат разослан «-ч>_1991 г.

Ученый секретарь специализированного совета Д 002.82.01,

кандидат физико-математических наук Г. П. АМИРДЖАНОЬ

I !

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Цель работы состоит в разработке н реализации атрибутной системы построения трансляторов (АСАПТ) для векторно-конвейерной ЭВМ, которая позволяет в значительной степени автоматизировать процесс написания транслятора, как в части синтаксического анализа, так и генерации кода. Разработанная система представляет собой программное средство поддержки разработки трансляторов для векторно-конвейерной ЭВМ и реализована на языке логического программирования Пролог. Входным языком системы является язык АЬУР, специально разработаный как средство для спецификаций АСАПТ и порождения трансляции в объектный язык.

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

ОС-граммагик. Это свойство ЬСЮ-грамматик устраняет существенный недостаток атрибутных грамматик, которые не являются порождающими.

На основе И)С-грамматик создана система построения трансляторов, ориентированная на вскторно-конвейерные ЭВМ. Предлагается язык АЬУР, который используется в системе построения трансляторов как средство для спецификации входного языка и схем трансляции в объектный язык.

Исследована эффективность применения атрибутных грамматик и средств логического программирования для создания систем построения трансляторов. Показано, что предложенный метод построения систем автоматизации проектирования трансляторов может быть эффективно использован для спецификации языков программирования для векторно-конвейерной ЭВМ (при помощи АСАПТ был разработан транслятор для подмножества машинно-ориентированного векторного языка УЕСЬАМ, а также транслятор подмножества Паскаля, для оценки производительности которого использовались Ливерморские инклы. Для некоторых из них был получен векторный код).

Практическая ценность. Предлагаемая система и язык АЬУР могут быть использованы разработчиками базового программного обеспечения векторно-конвейерных ЭВМ для создания трансляторов перспективных языков программирования и языков описания входных спецификаций систем моделирования векторно-конвейерной ЭВМ. Использование системы предполагает создание переносимого программного обеспечения и в случае модификации исходного языка позволяет легко перепрограммировать транслятор. Система также может быть использована для разработки трансляторов известных языков программирования. При этом для получения эффективной программы целесообразно использовать известные алгоритмы оптимизации.

Апробация работы. Основные результаты работы были доложены на семинаре отдела базового программного обеспечения Института проблем кибернетики АН СССР, научной школе-семинаре "Проблемы Кибернетики" (г.Киев, 1990), X Всесоюзном семинаре "Параллельное программирование и высокопроизводительные системы: Методы представления знаний в информационных технологиях" (г. Уфа, 1990).

Публикации. Представляемые к защите результаты опубликованы работах [1-3]

Структура диссертации. Диссертация состоит из введения, че-ырех глав, заключения, приложений и списка литературы, включаю-iero 57 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В §1.1 рассматриваются некоторые хорошо известные методы ормальных описаний языков программирования, а именно: системы родукций, аксиоматический подход, денотационная семантика, пенсий метаязык, W-грамматикн и атрибутные грамматики, приводится ?авннтельный анализ, а также обуславливается выбор атрибутных >амматнк,

В §1.2 обсуждаются различные методы атрибутных трансляций, эторые были использованы в известных атрибутных системах построил трансляторов. Атрибутный подход лежит в основе многих' проек-эв систем построения трансляторов. Наиболее известными являются ктемы FOLDS, DELTA, MUGI н MUG2, COPS, HLP .Cynep. Рассматривать два класса алгорнмов вычисления атрибутов: детерминированные недетерминированные, которые были использованы при создании гих систем.

В $1.2.1 подробно рассматриваются недетерминированные алго-1тмы вычисления атрибутов, которые применялись при описания язы-1 Симула-67, в системах Супер н DELTA.

В §1.2.2 приведены алгоритмы работы детерминированного алго-1тма, которые подразделяются на алгоритмы с жесткой стратегией и

1-2

алгоритмы с гибкой стратегией обхода дерева.

Алгоритм с жесткой стратегией был использован при создании системы построения трансляторов HLP (Helsinki Language Processor), а также в системе MUGI и MUG2. Подробно рассматривается используемый в MUG2 аппарат модифицированных атрибутных и атрибутных трансформационных грамматик.

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

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

Вторая глава содержит описание атрибутной системы построения трансляторов для векторно-коивейерной ЭВМ (АСАПТ) и языка ALVP.

В §2.1. рассматривается назначение и структура АСАПТ, приведенная на рис.1.

В §2.2 представлен разработанный для АСАПТ генератор сканеров GSCAN.

Определение сканера имеет следующий вид:

определение сканера):: =de i _l Itera 1 (<oписание классов литер) ]

def_tokcn {<описание лексем>) comment symbol_com <символы комментар1 paren_com <скобки комментария> <описание классов литеру ::= <имя класса литер> => ксписок литер:

АСАПТ выходные программы

лексические правила генератор сканеров GSCAN —» сканер |

атрибутная грамматика ALVP метатранслятор синтаксический ана лизатор ---------- _ ...

b —» генератор кода

программа на ассемблер объектная программа

ассемблере

I

диагностические сообщения Рис. 1.

Имя класса литер будет представлять собой предикат Пролога в нерированном сканере, который распознает групп у литер.

Описание лексемы имеет вид: описание лексему ::= <имя лексемы> => <регулярное еыражение>. этом определении имя лексемы соответствует внутреннему предс-ленню лексемы в генерируемом сканере. Регулярное выражение дставляет собой шаблон, с которым сравниваются фрагменты вход-

0 потока. В случае успешного сравнения распознанной лексеме |сваиваетсл внутреннее имя. Символ » после имени класса литер ачает, что допускается произвольное количество повторений снм-а, принадлежащему этому классу литер.

Результатом обработки входных спецификаций является сканер языке Пролог. Ядром сканера является предикат tokl(CURSOR, 1ING, TOKL), который преобразует исходную программу (представ-ную строковой переменной STRING) в список TOKL распознанных :ем и значений курсора для каждой лексемы. Генератор GSCAN сет применяться для создания весьма сложных сканеров, при этом *ер легко специфицируется. Система снабжена удобным многоокон-

1 меню, позволяющим работать с файловой системой. Система GSCAN :ет использоваться автономно.

В качестве примера рассматриваются входные спецификации ска-i для векторного машинно-орнентнрованного языка VECLAN. Текст ерированного сканера приведен в приложении.

1-3

В <¡.2.3 подробно описан язык ALVP - язык определения входных спецификаций АСАПТ.

Любая программа, написанная на языке ALVP состоит из 4 основных разделов, заголовка, объявления типов атрибутов, описания терминальных и нетерминальных символов грамматики языка вместе с соответствующими им атрибутами, описания грамматических правил и семантических формул 'вычисления атрибутов. Ключевые слова program, atlrlbute_domalns, terminals, nonterminals и grammar_rule отмечают начала соответствующих разделов.

В §2.3.1 рассматривается объявление типов атрибутов.

Язык ALVP имеет следующие основные типы атрибутных доменов: char, Integer, real, string, symbol, которые являются простыми типами. Вводится понятие структурного атрибутного домена и тип code, имеющий особенно важное значение при генерации кода.

Синтаксис описания типов атрибутов представлен синтаксическими диаграммами.

<раэдел-типоа> :: = altrlbute_domains объявление типов*. <о6ъявлеше-типов> -.:= <объявление-тапа>

! <объявление-типа> <объявление-тапоа>. <о6ъявлгкие-типа> ::= <список-идентификаторов> = <тип>. <список-идекгификаторос> ::= <идектификатор>

! <идентификатор>,<список идентификаторов>. <тип> ::= <простой> ! <структурный> ! codc. <простой> ::= char ! integer ! real ! string ! symbol. <структурный> ::= <идектификатор> \<идектификатор>* ! <иденгификатор>{<список-типов>). <списак-типов> ::= <тип> 5 <тип>,<список типов>. Структурный тип может быть также списком (правило <иденгифакатор>*). Для обозначения списка в синтаксических правилах применяется символ В обшей случае структурный тип соответствует структурированным типам данных языка Пролог.

Атрибутные домены типа code представляют собой специальным образом записанные операторы объектного языка. Если объектным языком является ассемблер векторно-конвейерной ЭВМ, то тип code имеет вид команды ассемблера в специальном формате,который будет рассмотрен при описании объектного языка системы. Если же в качестве объектного используется язык высокого уровня, конструкции

этого языка представляются в виде структуры, которой приписывается тип code. Например, оператор присваивания языка VECLAN, который имеет следующий синтаксис.

<присваивание> ::= <идентификатор> = <выражение>, может быть объявлен следующим образом:

asslgn(NAME.EXP) = code, где NAME соответствует идентификатору, а ЕХР - выражению. После такого объявления эта структура может быть использована в разделе описания грамматических правил и" семантических формул gramma r_rule для генерации кода.

Объявление типов в основном соответствует схеме описания доменов в языке Пролог.

В §2.3.2 приведены описания терминальных и нетерминальных . символов. В этом разделе описываются все символы языка. Каждому нетерминальному символу языка ставится в соответствие список атрибутов, а также приводится список терминальных символов, используемых в правилах.

кописание символов языка> <терминалы> <нетерминалы>. написание символов яэыка> ::= <терминалы> ::= terminals <список-терминалов>. <нетерминалы> :.= nonterminals <список-нетерминалав>. В список-терминалов могут входить лишь лексемы, распознаваемые сканером, который генерируется системой GSCAN. Они должны быть описаны в разделе def_$ymbol входных спецификаций генератора сканеров.

<список-герниналов> .:=

<терминал>\<терминал><список-терминалов>. <терминал> ::= <лексемам. <список-нетерминалов> :> <петерминал>

! <нетерминал> <список-негерминалов>. <нетерминал> ::= <идекгификатор>{<список-атрибутоя>). <список-атрибутов> ::= <атрибут> ! <атрибуг> <список-атрибутое>. <атрибут> ::= <тип>.

Определенные таким образом терминальные и нетерминальные символы языка используются при написании синтаксических и семантических формул.

В §2.3.3 рассматриваются грамматические правила н семантические формулы вычисления атрибутов.

1-4

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

<синтакс-и-семантические-формулы>: :=grammar_rule <список-праеил>. <список-правил> ::= <правило> ! <праеило> <список-правил>. <правило> ::= <сингаксио : <семакгика>. <правило> ::= <синтаксио. ■ <синтаксио ::= <нетерм-симеол> -> <символы-яэыка>

=> <вн-представление>.

Имена и список аргументов нетерминальных симюлов, входяшн в синтаксическое правило, должны соответствовать описанию нетер мннального символа в разделе nonterminals. Если это требование н будет выполнено, система выдаст сообщение об ошибке. <вн-п редставленио:: = <идентификатор>{<список-идекгифимторов>). Внутреннее представление имеет вид предиката Пролога, гд <иденгификатор> - это имя предиката, а аргументы - эт <список-идекгификаторов>, который представляет собой список кие, : символов языка, причем между нетерминальными символами, содержа шнмнея в синтаксическом правиле, и аргументами предиката доллш устанавливаться однозначное соответствие.

Семантические формулы вычисляют значения атрибутов, которы приписываются соответствующим вершинам дерева разбора. Значени атрибута типа code, приписанное корню дерева, представляет собо сгенерированный код на ассемблере ВК (может быть только один ат I рибут типа codc).

<семангика> ::= <список-формул>. <семантика> ::=

<списор-формул> ::= <формула> ! <формула> <список-формул>. <формула> ::= <список-предложений>

\<список-предложений> 11 <.список-условий>. <список-предложений> <предложение>

\<предложение>; <список-предложений». <список-'условий> ::= <условие>

',<условие> , <списск-условий>.

<предложение> ::= присваивание*. <присваиваше> ::= <атрибуг> = <выражеше>. <выражение> ::= <простое-выражение>

I <арифметическое-выражение> ! <струкхурное-выражеше>.

Выражения могут быть простыми, арифметическими и структурны-и. Атрибуты, входящие в арифметические выражения, могут быть ншь двух типов: Integer и real. Элементами арифметического выра-;ения могут быть стандартные предикаты Пролога.

В меню системы включен модуль HELP, в котором подробно опи-зно, как пользоваться стандартными предикатами Пролога примени-:льно к ALVP.

Как следует из синтаксиса языка, определение семантики может гсутствовать. При этом система генерирует синтаксический аналн-iTop. Если же семантика определена, то после трансляции будет элучен код на объектном языке.

$2.4 содержит описание объектного языка АСАПТ. Объектным )ЫКом АСАПТ может являться ассемблер векторно-конвейерной ЭВМ, (бо язык высокого уровня.

Регистровая память векторно-конвейерной ЭВМ состоит нз пяти >упп быстрых регистров, которые представляются следующим обра-

iM:

8 адресных регистров: a(l), I « [0,7J;

64 буферных адресных регистра: b(l,J), I «[0,7], J « [0,7];

8 скалярных регистров: s(I), I е [0,7];

64 буферных скалярных регистра: t(I,J), I «[0,7], J в [0,7];

8 векторных регистров: v(I), I е [0,7].

Кроме того, в ассемблере имеются специальные регистры: регистр длины вектора: vi; регистр векторной маски: vm; счетчик реального времени: ri'; текущий адрес канала: са; флаг ошибки канала: се;

Если в операторе поле результата и поле операндов содержат [ражение, то вводится идентификатор ЕХР. Коды операций обозначайся следующим образом: +F(fptus), -F(fminus), *F(ímuH), plus), - (minus),» (mull), / (obr), +R(rplus), »(and), эг), !=(ne), »R(rmuH), <(lshift), >(rshtft).

1-5

Все команды ассемблера являются однослоговымн или двухслого-выми, что однозначно определяется по коду команды. Для однослого-вых команд в ALVP используется формат (1(G,H,I,J,K), а для двух-слоговых - формат f2(G,H,l,J,K,M). Каждая машинная команда представлена предикатом asvk, аргументом которого является список элементов ассемблера, составляющих команду. Каждой команде старится в соответствие машинный код в формате П или f2. Примеры обозначения некоторого подмножества символических машинных команд ассемблера векторно-конвейерной ЭВМ приведены в таблице 1 приложения, в таблице 2 приложения приведены псевдокоманды ассемблера, в таблице 3 - макросредства.

Третья глава посвящена проблемам синтаксического анализа и генерации кода в АСАПТ.

В обшсм случае работа АСАПТ состоит из следующих шагов:

1. Генерация сканера при помощи системы GSCAN.

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

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

parse(Source, Structure) обеспечивает взаимосвязь с представлением синтаксического анализатора в виде DC-грамматики. Source представляет собой исходный список лексем, a Structure является единственным аргументом DC-грамматики, соответствующим предложениям языка.

Грамматические правила в АСАПТ определяются средствами специально разработанного языка ALVP в разделе grammar_rule. Фактически правила, записанные в этом разделе, описывают LDC-грамматику.

3. Компиляция Пролог-программы, т.е. построение атрибутного дерева, его заполнение н получение кода.

Процесс построения заполненного атрибутного дерева разбивается на. несколько этапов: построение атрибутного дерева, построение графа зависимости атрибутов, удаление бесполезных атрибутов (те атрибуты вершин дерева вывода, из которых не достижим ни один

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

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

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

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

Например, предложение ALVP EXP{L,M,R,C)->TRM{Ll,M1,R1,C1},dpIus,EXP{L3,M3,R3,C3)i=> aexpr(dplus, EXP,TERM):

L1=YES. L3=NO.

R3=R+1; C=C1 11 C3 11 asvk([s(R),s(Rl),plus,s(R)]) If M3=0.

M=M1, R3=R+1; C=C111C311 asvk([s(R), s(R), pi us, s( R3)]) I! M1>M3.

M=M3; R1=R+1; C=C3MG1lasvk([s(R),s(R),plus,s(Rl)]) 11 M1<M3." приводится к следующему виду: ЕХР{ L, М, R, CI! 1СЗ11 asvk([s(R), s(Rl), pius,s(R)])} -> TRM{YES,Ml,Rl,Cl),dplus,EXP{NO,M3,R+1,C3}=>aexpr(dplus,EXP,TRM). EXP{L,M1,R,ClllC3!lasvk([s(R),s(R),plus,s(R+l)J)) -> . TRM{YES,M1,R1,C1},dplus,EXP{NO,M3,R+l,C3) => aexpr(dplus, EXP.TRM) : M3>M1. E X P{ L, M3, R, CI! I СЗ И as vk([ s( R), s( R), pi us, s( R+1)])) ->

ТРМ(УЕ5,М1,1М,С1>,<1р1и5,ЕХР{ЫО,МЗ,1*3,СЗ) => аехрг(с1р1и51ЕХР,Т1Ш) : МЗ>М1.

Такая подстановка выполняется для всех предложений, после чего начинается непосредственно процесс трансляции. Трансляция всей программы на- АЬУР заключается а последовательной трансляций

отдельных предложений языка. Предикат, реализующий процесс транс-

о

ляини, имеет вид:

<гапз1а1е((а1ур_рг(рго0гаш(Ыаше),а1г1Ьи1е_(1огпа1п5(АТР_ООМ_113Т),

(eгшlnals(TERM_LIST),nonteгm^na!s(NONтiRM_LIST), ^аттаг_ги!е(ОПАМ_НиЬЕ_Ь!ЗТ)),

1 гапзЫ е1(АТК_00М_ивТ, 00М_ИБТ1), I гапьЫ е2(ТЕИМ „ШТ, ООМ_и5Т2), 1гап51а1еЗ(МО^ЕШЛ_ЫЗТ(РНЕО_Ь15Т), 1 гапзЫ е4(й1*АМ_1Ш Се.ИБТ, а/шТ).

Предикаты 1гапз1а1с1 и 1гапзШе2 преобразуют список атрибутных доменов АТ^ООМ^ЫБТ и список терминальных символов ТЕКМ_Ь15Т в списки доменов Пролога ООМ_У5Т1 и ООМ_ИЭТ2.

Предикат ^апзШеЗ преобразует список нетерминальных символов М<ЖТЕШ_и5Т в список предикатов РЯБЕИ-ЮТ.

При реализации этих преобразований не возникает каких-либо сложностей, т.к. типы данных А1ЛФ н Пролога полностью совместимы.

° Процедура иапзШе4 преобразует правила 1ЛЗС-грамматнкн в заголовок и тело эквивалентного предложения на Прологе.

Основная идея программы преобразования грамматических правил в предложения Пролога состоит в добавлении разностного списка БиВЬ к каждому терминальному и нетерминальному символу (предикат иагиШе2). Нетерминальный символ преобразуется в бинарную структуру, функтором которой является символ, а аргументами -список атрибутов этого символа н присоединяемый разностный список. Терминальный символ преобразуется в унарную структуру, функторам которой является символ, а аргументом - разностный список.

.. Таким образом, трансляцию языка АЬУР можно представить следующей схемой:

- программа на АьУР внутреннее представление Пролог-программа

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

parser(Tokens1,Tokens2, Structure) преобразует список лексем Tokensl e структуру Structure. Каждому элементу структуры ставится в соответствие список атрибутов, который используется при генерации кода. Значение атрибута типа Code старшего элемента структуры представляет собой сгенерированный код для данной структуры. Tokens1/Tokens2 - это список лексем, полученный при работе сканера и являющийся разностным списком, который используется при генерации кода. Значение атрибута типа Code старшего элемента структуры представляет собой сгенерированный код для данной структуры. Tokensl/Tokens2 - это список лексем, полученный при работе сканера и являющийся разностным, списком.

В §3.2 приведен пример использования системы для разработки транслятора подмножества экспериментального векторного языка VECLAN. Рассматривается программа на ALVP, приведено, атрибутированное дерево' разбора.

В §3.3 генерируется транслятор для подмножества Паскаля и с его помощью генерируется код на ассемблере векторно-конвейерной ЭМВ для некоторых Ливерморскнх циклов. Некоторые из них удалось векторизовать.

В §3.4 рассматривается' возможность трансляции программ нэ ассемблере ВК ЭВМ в машинные коды. Приведены основные предикаты Пролога, реализующие ассемблер.

В четвертой главе приведены оценки эффективности реализации АСАПТ. *

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

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

° Следующий параметр - глубина вложенной рекурсии. Если в процессе выполнения программы глубина превысила максимально допустимую, программа прерывается. При практической реализации эта проблема является одной из самых трудноразрешимых. Хотя рекурсивные программы кажутся более привлекательными, чем их итерационные аналоги, они обладают очень существенным недостатком с точки зрения реализации. Рекурсия в общем случае требует линейно зависящий от числа рекурсивных обращений объем памяти ( для выполнения итераций объем памяти ограничен константой, не зависящей от числа итераций ). Однако существуют методы, позволяющие писать рекурсивные программы, использующие постоянный объем памяти. К ним относятся метод оптимизации остатка рекурсии или оптимизации последнего обращения и индексирование предложений.

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

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

В АСАПТ для организации таблиц были в основном использованы АВЛ-деревья. В §4.2 описывается реализация АВЛ-деревьев средствами Пролога.

На АВЛ-деревьях можно за логарифмическое время О(1о£ п) даже в худшем случае выполнить все основные операции, определенные на дереве: поиск, включение и удаление.

Рассматриваются две операции, выполняемые со справочником: поиск значения, записанного под определенным именем (ключом) и включение в справочник нового ключа и связанного с ним значения. Ясно, что при втом должно выполняться требование непротиворечивости, т.е. один и тот же ключ не может встретиться дважды. Оказывается, что обе эти операции выполняются с использованием одной

процедуры, в которой применяются неполные структуры данных.

Приводится алгоритм включения в сбалансированное дерево новой вершины. Структура дерева представлена в программе следующим образом:

trectype = trec(Key, Count, Bal, treetype.treetype); empty;

(((reetype.H) ,

где Key - ключ, Count - счетчик вхождений ключа Key, Bal - показатель сбалансированности, Н - индикатор изменения высоты дерева.

Процесс включения вершины фактически состоит из трех шагов:

1. Обход дерева, пока не убедимся, что ключа в нем нет. Если ключ уже имеется в дереве, увеличить значение счетчика Count.

2. Включение новой вершины и определение результирующего показателя сбалансированности.

3. Прохождение по пути поиска и проверка в каждой вершине показателя сбалансированности. Если необходимо - балансировка.

Приводится программа, реализующая этот алгоритм.

Алгоритм исключения из сбалансированного дерева является немного более сложным, чем включение, хотя алгоритм балансировки остается тем же, что и при включении. При удалении рассматриваются три случая:

1. Удаляемый ключ не найден.

2. Удаляемый ключ имеет не более одного потомка.

3. Удаляемый ключ имеет двух потомков.

Удаление терминальных 'узлов и узлов с одним потомком достаточно просто. Если же узел имеет два поддерева, то он заменяется самым правым узлом левого поддерева. При • удалении, как и прн включении используется индикатор изменения высоты поддерева Н.

Приводится процедура исключения из сбалансированного дерева.

Удаление, как и включение, может быть выполнено за" логарифмическое время. Однако между этими двумя процедурами имеется существенная разница, заключающаяся в том, что включение може+ вызвать лишь одну балансировку, а удаление может потребовать балансировки в каждом узле пути поиска. Но в целом это не'^очень существенно влияет на эффективность применения ЛВЛ-деревьев, так как эмпирические проверки показывают, что в среднем одйа балансировка вызывается двумя включениями и пятью удалениями. Кроме того, в ЛСЛПТ операция удаления из ABJl-дерева практически не приме-

няется. Что касается процедур поиска и включения, то они очень широко используется при написании компиляторов на Прологе.

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

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

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

В §4.4 подробно описаны интерфейс пользователя и система меню. В АСАПТ интерфейсом пользователя является двухуровневое "спускающееся" меню (pull down). Главное меню (или первый уровень меню) имеет вид, показанный на рис. 5.

Edit Se aneen Parsgen Codeeren Asm Files Quit

- tait - -uen-

--Message-

Рис.3.

Для задания команды достаточно нажать лишь первую букву ее названия (первые буквы каждой из команд выделены при помощи увеличенной яркости). Второй способ задания команды состоит в перемещении по меню при помоши стрелок и переход к работе

с выбранной командой осуществляется нажатием Enter, выбранная команда выделяется инверсным цветом. Для окончания работы с командой используется клавиша Esc.

Главное меню содержит 7 доступных пользователю команд:

1. Редактирование (Edit).

2. Генерация сканера (Scangen). •

3. Генерация синтаксического анализатора (Parsgen).

4. Генерация кода (Codegen).

5. Ассемблирование (Asm).

6. Работа с файловой системой (Files).

7. Выход из системы (Quit).

Главное меню имеет 3 окна: редактирования (Edit), сообщений (Message) и генерации (Gen). Переход в окно редактирования осуществляется при выборе элемента меню Edit. Текстовый редактор является совместимым с редактором системы Турбо-Пролог и позволяет выполнять над текстом следующие операции: поиск, замена, вставка, выделение блоков, перемещение и удаление блоков, вызов вспомогательного редактора, увеличение экрана н т.д.

Поместить файл в окно редактирования или запомнить уже отредактированный файл на диске можно при помощи команды Flies, которая имеет второй уровень меню (рис. 6).

Рис. в.

Выбор команд осуществляется аналогично главному меню, только следует использовать стрелки и "!". Чтобы' загрузить файл в редактор, необходимо выбрать команду Load file. При этом высвечивается окно с запросом имени файла (расширение имени '^файла по умолчанию . alv). Если ввести имя файла н нажать клавишу Enter, то файл загрузитися в редактор. Есть возможность при помоши клавиши Enter просмотреть каталог и при помоши стрелок выбрать нужный файл.

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

Вся информация о выполнении процесса генерации, а также информация об ошибках, найденных в процессе трансляции, выдается в окно сообщений Message.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработаны следующие программные средства: генератор сканеров GSCAN, транслятор языка ALVP, интерфейс пользователя, 'содержащий файловую систему и текстовый редактор. Все программы ¡записаны на языке логического программироания Пролог.

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

4. С помошью АСАПТ получея транслятор для подмножества экспериментального векторного языка VECLAN.

5. Сгенерирован транслятор для подмножества языка Паскаль.

По теме диссертации опубликованы следующие работы.

1. Зевнна С Г. "Подсистема генерации сканеров системы автоматизации проектирования трансляторов для векторно-конвейерной ЭВМ",

в кн. "Параллельное программирование и высокопроизводительные системы: Методы представления знаний в информационных технологиях", Тезисы докладов X Всесоюзного семинара. Институт кнбер-неткн им. В.М.Глушкова АН СССР, Киев, 1990.

2. Зевина С. Г. "Использование средств логического программирования в системах построения компиляторов". Препринт. Научный Совет по комплексной проблеме "Кибернетика" АН . СССР, М., 1991.

3. Зевина С. Г. "Использование средств логического программирования в атрибутных системах построения трансляторов", в кн. "Вопросы кибернетки", М., 1991,