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

ИНСТИТУТ ЭЛЕКТРОННЫХ УПРАВЛЯЮЩИХ МАШИН

На правах рукописи -УДК-681^-3-

ШВЕИН Алексей Анатольевич

П0ВЫ1ЕНИЕ ЭФХ£КТ ЯВНОСТИ ПРОГРАММНО-АППАРАТНЫХ ТРАНСЛЯТОРОВ И ИНТЕРПРЕТАТОРОВ НА ОСНОВЕ МЕТОДОВ ТЕОРИИ «ОРМАЛЬНЫХ ЯЗЫКОВ

05.13.13 - Вычислительные манины, комплексы, системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 1991

Работа выполнена в Институте электронных управляющих маоин

Научный руководитель: кандидат технических наук, старший научный сотрудник ЭОНИС Е С.

Официальные оппоненты: доктор технических наук,

профессор ХЕТАГУРОВ Я Л.,

кандидат технических наук, старший научный сотрудник ЕГОРОВ Г. Л.

Ведущая организация: Институт проблем информатики АН СССР

Защита состоится 1991 р. в _

часов на васедании специализированного совета К 115.04.01 при Институте электронных управляющих машин по адресу: 117812, Москва, ул. Вавилова, 24

С диссертацией можно ознакомиться в библиотеке Института электронных управлявших маоин.

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

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

Красовский ЕЕ.

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

Актуальность проблемы. Вычислительная техника находит

-все~6ол&е- широкое- применение-в, раз личных отраслях народного

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

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

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

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

Существующие методы теории формальных язьков, иоториэ успешно применяются в системах автоьатиаированного построения трансляторов (СПТ), позволяют автоматизировать значительна часть разработки ЯП. Однако, современные СНГ ориентированы на программную реализацию ЯП и их непосредственное испольвованпэ для построения программно-аппаратных ЯП вызывает значительны» трудности из-эа ограничений объема оборудования.

Целью работы является развитие и применение методов теории формальных языков для повышения эффективности программно-аппаратных трансляторов и интерпретаторов.

Методы исследования. Для исследования и решения постав-денных задач используются методы конструирования и оптимизации распознавателей контекстно-свободных языков на основе Ц?(к)-грамматик, метод трансляционных грамматик, а также -элементы теории автоматов и теории графов.

Научная новизна работы. На основе обобщения метода Щк)-грамматик разработана новая формальная модель распознавателя и?(к)-язьков, представленная в виде 1Шк)-автомата. Разработаны алгоритмы конструирования и оптимизации 1Щ к) -автомата по заданной Ц?(к)-грамштике, обеспечивающие повышение производительности и уменьшение объема транслятора.

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

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

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

Практическая ценность работы. Разработанные алгоритмы конструирования и оптимизации трансляторов Шк)-языков могут быть использованы для создания СИТ, обеспечивающих автоматизированное проектирование трансляторов и интерпретаторов с

существенно улу^цгенныд! показателями производительности и объема необходимого оборудования.

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

Разработанные с применением результатов настоящей работы систеш диалогового взаимодействия пользователей с инструментальными средствам}! проектирования аппаратуры на базе программируемых логических схем (ПЛС) и полузаказных больших интегральных схем (Б5!С) обеспечивает существенную экономию трудозатрат и вычислительных ресурсов в процессе автоматизированного проектирования.

Реализация результатов работа Результаты, полученные в диссертации, использовались в следующих темах, проводимых в ИНЭУЫ по планам важнейвих работ Цинприбора и в которых автор принимал активное участие:

- Управляющий вычислительный комплекс СШ420 на основе процессора с динамически изменяемой системой команд;

- вычислительный комплекс СШ700;

- система автоматизированного проектирования больсшх интегральных схем (ЗЫЙС).

Результаты разработки и экспериментальной проверки способа программно-аппаратной реализации трансляторов «а основе средств динамического микропрограммирования н дополнительного аппаратного модуля использовались при проведении межгосударственных испытаний управляющего вычислительного комплекса СШ420.

Разработанный способ проектирования прикладных объектно-ориентированных диалоговых интерпретаторов реализован в автоматизированной системе программирования интегральной логики (АСПИЛ), внедренной в 1ШВУЫ н в ЛПО "Сигма" (г. Вильнюс) , а такгэ - в систем автохатнаировакного проектирования полуааказных БИС (ЭНИС), внедренной в НКШТ (г. Винница) и в НПО "Импульс" (г. Северодонецк). Суьаарный годовой экоиоми-

2 Зак.ЬйО

- б -

ческий эффект от внедрения результатов диссертации составляет 86 тыс. руб.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на Всесопаном научно-техническом совещании "Перспективы развития и опыт применения мини и микро-ЭВМ (СИ ЭВМ)" (г. Орел, 1982 г.), Всесоюзном семинаре "Технические средства СМ ЭВМ семейства СМ4 (СШ420, СШЗОО) и вопросы их применения" (г. Москва, 1983 г.), Третьем Симпозиуме по применению микро-ЭВМ и микропроцессоров - г. Будапешт, 1983 г., III Всесоювной вколе-семинаре "Разработка и использование технических и программных средств системы малых ЭВЫ (СМ ЭВМ)", (г. Тбилиси, 1986 г.), Всесоювной конференции "Мини ЭВМ СШ700. Технические и программные средства" (г. Суздаль, 1988 г.). Международной конференции SVEP'88 (г. фага, 1988 г.) и I Международной научно-практической конференции САПР СОТ'89 ( г. Ленинград, 1989 г).

Публикации. По теме диссертации опубликовано 11 печатных работ, получено одно авторское свидетельство.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, издоменных на 151 стр. машинописного текста, содержит список литературы из 77 наименований, включает 40 страниц рисунков и таблиц.

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

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

Для оценки возможности повышения эффективности ЯП, реализуемых в современных ЭВЫ массового применения, проанализированы основные тенденции развития архитектуры ЭШ и методов

проектйрсщшпвгЯП.--------

Анализ тенденций развития архитектуры ЭВЫ массового применения показывает, что одно из перспективных направлений связано с реализацией в аппаратуре ЭШ данного класса специальных средств, ориентированных на компиляцию и интерпретацию программ, разрабатываемых на языках высокого уровня. Основными техническими предпосылками такого подхода является развитие динамического »микропрограммирования и появление полупроводниковых микросхем с высокой степенью интеграции, включая ПЛС и СБИС.

Указанное обстоятельство позволяет рассматривать задачу создания ЯП для ЭВМ кассового применения как задачу разработки программно-аппаратного комплекса.

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

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

Характерной особенностью сиитакс кчески-ориентированных формальных методов построения трансляторов является наличие

2х

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

Аппаратная реализация ЯП в силу конструктивных и технологических ограничений требует повышенного внимания к методам оптимизации трансляторов с целью уменьшения размеров таблиц синтаксического разбора и, следовательно, объема необходимого оборудования. В последние годы предлагались различные подходы к оптимизации Щк)-трансляторов, которые однако не получили пока широкого распространения в СП? и ориентированы, главным образом, на программную реализацию.

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

В результате проведенного анализа современных методов разработки и реализации ЯП (формулированы еяедующие основные гадачи диссертационное работы:

- разработка метода конструирования и оптимизации трансляторов на основе ШЮ-грашатик, ориентированного на прог-

' раымно-аппаратную реализацию в составе ЭВМ общего назначения;

- разработка и экспериментальное исследование способа и средств реализации программно- аппаратных трансляторов в составе опытной модели ЭВЫ общэго назначения;

- исследование возможности применения разработанного метода для реализации диалоговых ЯП в прикладных системах.

Во второй главе излагаются результаты разработки и исследования метода индексированных 1Ж к)-автоматов (ИЖ к)-автоматов) .

В основу предлагаемого метода положены следующие известные результаты из теории формальных язиюв: классический под-

ход к построению распознавателей Ц?( к)-языков, предложенный Д. Кнутом. 0)-подход, исследованный ДеРемером и существенно _упроаа»ашй процедуру построения ЬЯ-распознавателя, метод оптимизации ьк-распознавателей;—разработанный—АЛ1,Щушем_и.

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

ШЧ к)-автомат представляет собой автомат с магазинной памятью, выполняется распознавание языка, заданного Шк)-грамматикой. Ш!( к)-автомат имеет конечное множество состояний, разбитое на два непересекающихся подмнонэства в зависимости от того, следует ли данное состояние заносить п магазин (запоминаемое состояние) при переходе 1и?(к)-ивтоиата в это состояние или не следует (незаломшаеыое состояние). 1Щ к)-автомат воспринимает на входе терминальные симзолы входной цепочки и ыошт выполнять два вида операций: индекс и-рованнный сдвиг или индексированную свертку.

При выполнении индексированного сдвига п(д,1) с индексом 1 Ш?( О)-автомат, находящийся в некотором состоянии я, считывает из входной цепочки очередной терминальный символ Ь, удаляет из магазина 1 элементов и переходит в следующее состояние ч", занося это состояние в магазин в том случае, если око является запоминаемым.

Индексированная свертка г(ч) с индексом j к нетерминальному символу А выполняется Ш?(0)-автоматом, находящийся а состоянии ч, следующим образом: из магазина удаляются 1 элементов, 1ЩО)-автомат переходит в состояние ч*, стояезз в вершине магазина и выполняет операцию индексированного сдвига с(ч* ,Л) йэ состояния ОТ по символу А.

В случае, если к>0, операции 1Щк)-автомата могут вы-, подняться по-разному в зависимости от цепочки и на к с/.едущих за очереднш терминальных символов.

1Щк)-автомат начинает работу в начальном состоянии ф и заканчивает либо в состоянии допуска ф, либо в состоянии ошибки чЕ.

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

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

Оптимизация построенного 1Щк)-автоыата производится с помоиыо эквивалентных преобразований. Главное из этих преобразовал иА состоит в сокращении состояний, содержащих свертки с нулевши индексами. При удалении таких сверток иэ некоторых состояний 1Щ к)-автомата исчезают все переходы по нетерминальным символам, поэтому такие состояния можно не записывать в магазин. Следовательно, данное состояние можно перевести в {»вряд невапоминаемых и уменьшить на единицу все ненулеваэ индексы в данном состоянии и во всех состояниях, достижишх иэ данного состояния при помоги операций индексированного сдвига. В свою очередь, такая операция мояет привести к появлению новых сверток с нулевыми индексами, и процесс повторяется заново. В результате подобных преобразований можно получить 1Щк)-автомат, объем которого в два-три раза меньше исходного.

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

множество терминальных скшолов разбито на множество входных_

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

По заданной трансляционной гракыатике иоко постро:1ть 1Щк) -преобразователь, представлягвдй собой преобразователь с магазинной памятью, на вход которого поступает входим часть активной цепочки, а на выходе формируется операционная часть активной. цепочки. Процедура построения 1Щк)-просбра-вователя аналогична процедуре построения 1Щ к)-автомата по заданной контекстно-свободной грамматике. Отличив состсгтт в том, что 1Щ к) -преобразователь при выполнении индексированных операций сдвига и свертки иокэт выдавать на выход цэпочзш операционных символов. В процессе построения 1Щ к) -преобразователя несводимо следить ва сохранением его дэтер^жро-ванности, так как мояет оказаться, что в некоторые состояшш различным индексированным и?( к) -ситуациям, опрэлел!к^:м сдалг.. по одному и тому ей входному сгадюлу, соответствует выдача различных операционных сиизолов.

Процедура оптимизации 1Щк)-преобрааовател9П строится аналогично процедуре оптимизации 1Ц?( к)-автомата с учэтои пэ-обходиыости совладения правильной последовательности сэдата операционных цепочек.

Таким образом, конструирование управлягого блока синтаксически-ориентированного транслятора (или тгеврпретатора) производится в три этапа. На первом этапе строится кшкнигсес-кий 1Щ0) -преобразователь. На втором этапе при налички ЩО)- конфликтов анализируются аванцепочкн га к тердоиашш

- и -

символов. При соблюдении Щк)-условия неоднозначные состояния расщепляются н канонический IЩ 0)-преобразователь превращается в 1Ц?( к)-преобразователь. На третьем этапе к полученному 1Щ к)-преобразователю применяются эквивалентные пре-' образования, обеспечнваюиие сокращение количества состояний и операций, необходимых для выполнения трансляции или интерпретации.

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

В третьей главе исследуется метод программно-аппаратной реализции 1Щ к)-трансляторов в составе экспериментального варианта модели управляющего вычислительного комплекса СШ420. Наряду с базовой системой микропрограммирования, реализующей стандартную систему команд СУ ЭВМ. процессор ОД 420 содержит систему динамического микропрограммного управления, включающую динамически загружаемые дешифратор команд и динамическую управляющую память объемом 1024 64-разрядных слов, обеспечивающую возможность реализации новых команд. В состав зкспериментальной модели СШ420 входит также дополнительный аппаратный модуль яэжовых команд (МАЯК), содержащий сверхо-■ перативную память данных (1024 16-разрядных слова) и матрицу ^ переходов. Матрица переходов представляет собой специальны* образом организованную память, которая обеспечивает формирование относительного адреса следующего состояния. Элементом ' матрицы является величина смещения адреса Матрица переходов обеспечивает ветвление за один такт по одному из 4, 8, 16 или 32 направлениям и позволяет закодировать до 128 состояний 1Щ к)-автомата

В каждый момент времени процессор СШ420 работает в одном из двух режимов: в базовом режиме или в динамическом режиме. Текущий режим определяется словом состояния процессора Вазовые микрокоманды имеют 48 разрядов и управляют работой

путей данных центрального процессора Динамические микроко-галды распирены до 64 разрядов п могут управлять как базовой частью процессора, так и дополнительной аппаратурой. Дополнительная—аппаратура7-вкгстая-д:;иаиическуд_управляст^ю память. располагается на двух платах в составе центрального процессора

Основная идея метода програшно-аппаратной реализации 1Щ к)-трансляторов в экспериментальной модели СШ420 состоит в следующем. ПЯС к)-преобразователь, построенный и оптимизированный в соответствии с разработанной методикой, представляется в виде последовательности специальных команд. Каждая кз этих коканд реализуется о виде микропрограммы, загружаемой в дга!0!с1чес!сую пампть. Указенньй набор команд Ш?( к)-транслятора является универсальные и используется без изменений в любом реализуемой ЯП. Сяещфзса язьга отображается в ЯП-преградив, загруггешй в оперативную понять ОД 420, и в управляю-сэй таблице ЯП, которая загружается в матрицу переходов.

Кодирование переходов к)-автомата в виде матрицы сиеегний относительно начальных адресов его состояний позволяет умзньЕггь количество разрядов, требуемых для хранения элементов штрицы, п создает основу для дальнейшей оптимизации. Так как у некоторых состояний строки сьгедатй совпадают пз-аа одинаковой структуры переходов, заданных в этих состояниях, таким состояниям воюю присвоить одинаковый код и объединить эти строки в одну.

Сешнтде&скке функции 1Щ к)-транслятора реализуются путем подстановки в ЯП-програшу адресов процедур, выполняющих такие действия. Гибкий переход кз динамического реяша в базовый режим СШ420 и обратно позволяет реализовать семантические процедуры как на програшнои уровне - в стандартной системе команд СМ ЭВУ, так и на микропрограммной уровне - за счет реализации специальных команд, загруяаешх в динамическую память.

Для оценки эффективности програг&шой и программно-аппаратной реализации 1Щ к)-трансляторов в опытной модели СШ420

проведены экспериментальные исследования на небольших примерах. Операции ILR(к)-транслятора реализованы в виде набора из шести специальных команд. Для этого потребовалось около 40 64-разрядных слов динамической управляющей памяти.

Для ряда примеров, включая небольшой фрагмент языка Pascal, были построены ILR( к)-автоматы, которые ватем были оптимизированы в соответствии с методикой, разработанной во второй главе. Полученные 1LR( к)-автоматы были в дальнейюем реализованы на СШ420 тремя способами:

- программная реализация неоптимиаированных ILR(к)-трансляторов;

- программная реализация оптимизированных 1Щк)-транс-лятров;

программно-аппаратная реализация оптимизированных ILRC к) -трансляторов.

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

- оптимизация ILR(к)-автомата обеспечивает сокращение количества состояний в 1,3-3 pasa и в случае программной реализации позволяет повысить производительность транслятора на этапе синтаксического анализа на 20-30% ;

прог рашно-аппаратная реализация оптимизированного ILR(к)-автомата увеличивает его производительность в 6-12 раз по сравнению с программной реализацией ;

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

Экспериментальные работы на СШ420 по реализации трансляторов на программно-аппаратном уровне показали такие, что подобный подход к реализации ЯП требует наличия развитых средств автоматизированного проектирования, включая программ-

ную реализацию разработанного метода конструирования и опти-газацни 1Щ к)-автоматов* формирование специализированных программ и таблиц переходов в соответствии с выбранным спосо-оом реализации, а тиляв - раанообрааныэ-средства-разработки_и_ отладки (микропрограмм и аппаратуры.

!{деп использования динаигагского программирования в составе ЭВЫ обсего назначения подучила дальнейсее развитие при создании более поздней 32-разрядной модели СШ700, в которой вся LEiKponporpaiMian паьять выполпепа на динамически загруяа-еьан элементах. Ецэ больсее увеличение производительности программно-аппаратных ЯП могэт быть получено при использовании полупроводниковых элементов высокой степени интеграции, таких как ШЮ и специализированных СЕЯ.

В четвертой главе представлены результаты практического применения иетода ILR(к)-автоматов для разработки и реализации средств диалогового взаимодействия в составе прикладных систем автоматизированного проектирования. Эти работы позволили, с одной стороны, исследовать новую область применения разработанного формального аппарата ILR( к)-автоматов и, с другой стороны, - сделать определенные практические саги в направлении создания средств автодатизацки, требуемых • в том числе и для програьгязо- аппаратной реализация повых ЯП па современной элегантной базе.

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

Наиболее удачный подход к ресения данной задачи состоит з применении диалоговых средств, которкэ подучили особенно

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

В данной работе диалоговое взаимодействие формализуется в виде трансляционной грамматики, у которой входные терминальные символы являются элементами диалога, а операционные символы являются именами процедур, выполняющих семантические преобразования. Использовались три типа элементов диалога: меню.запрос или команда пользователя. Далее по трансляционной грамматике строится и оптимизируется в соответствии с разработанной методикой 1Шк)-преобразователь, который в данном случае представляет собой блок управления диалоговой системой взаимодействия.

Такой подход применялся при создании диалоговых средств автоматизированной системы программирования интегральной логики (АСПИЛ), предназначенной для кодирования, занесения, контроля и сопровождения информации, ааносимой в програишру-емые логические схемы (ПЛС). АСПИЛ представляет собой комплекс аппаратных и программных средств, ориентированный на разработчиков и наладчиков вычислительных устройств, проектируемых на основе ПЛС. Аппаратные средства АСПИЛ построены на стандартном вычислительном комплексе типа С1М, СШ420 или СШ.600, в конфигурацию которого включено специальное устройство - программатор, выполняюций функции занесения кода в ПЛС и считывания кода из ШЮ. Программные средства АСПИЛ функционируют под управлением операционной систем* ИНМОС.

В зависимости от категории объектов проектирования и характера действий, выполняемых над этими объектами, состояния преобразователя реализованы на различных уровнях. База данных АСПИЛ, содержащая коды ПЛС для проектируема устройств и блоков вычислительного комиекса, построена на основе иерархии, заложенной в файловой системе ШШОС. Операции над базой данных АСПИД и ряд вспомогательных операций по выбору режимов

диалога реализованы на уровне командного языка ИНКЮС. Операции кодирования и редактирования кодов ПЛС реализованы на программном уровне с использованием языка Си. Операции, свя-"ваяныэ—с—занесением- и- гонтроле1оюдов_в_плс, реализованы на программно-аппаратном уровне с использованием драйвера программатора, включенного в ядро операционной системы комплекса

Аналогичные дгаг-огосиэ средства, разработанные по той зга изтодюсэ, вклпчеиы в систему автоматизированного проектирования ЕГ!С - САПР ЕМГ'С.

Разработанные средства в составе АСПИЛ использовались при проецетировшпш и наладке вычислительного комплекса СШ.700 в ИВЗУЦ и Ж) "Ста" п позсолзш1 существенно сократить затраты на подготовку ПЛС.

Средства диалогового взшшодействия в составе САПР ЭМИС, впедреннкэ в ШИВТ? и в ИЮ "Илульс", обеспечивает удобный и эффективный интерфейс с пользователей - проектировщиком БИС па беге иатричпого кристалла 1516ХШ.

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

Основные результаты :

1. С целью сокраззиия объега управлявших таблиц транслятора на основе катода ЬК( к)-грамматик разработана формальная модель распознавателя контекстно-свободных языков, представ-лашюя в виде ПЖ к)-автомата

2. Разработан алгоритм конструирования 1Щ к) -автомата по заданной Щ к) -грамяяккэ с использованием ЩО)-подхода, согласно которому строится кадоппчгскиЯ ЩО)-автомат, и при наличии конфликтов в его состояниях применяются известные методы разрееэпкя конфликтов, в результате чего конструируется детерминированный 1Щ к)-автомат.

3. Разработан нэтод оптимизации 1Щ к)-автоматов, построенный на основе эквивалентных преобразований и обеспечивав

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

4. Для выполнения семантических действий в процессе распознавания ILR( к)-автомат обобщен на случай трансляционных грамматик, описывающих синтаксис языка и его семантику, представленную операционньыи символами. Разработан алгоритм конструирования ILR(к)-преобразователя, транслирующего строку исходного текста в строку операционных символов.

Б. Разработан алгоритм оптимизации ILR(к)-преобразователя, обеспечивающий сокращение объема транслятора или интерпретатора и повышение их производительности при сохранении правильной последовательности выдаваемых операционных символов.

6. Разработаны средства динамического микропрограммирования в составе экспериментальной модели СШ420, ориентированные на программно-аппаратную реализацию языков высокого уровня и обеспечивающие гиб1ше взаимодействие с базовой аппаратурой процессора

7. Разработан и экспериментально исследован метод программно-аппаратной реализации 1LR(к)-трансляторов в расширенной модели СШ420, предусматривающий представление ILR(к)-транслятора в виде последовательности специальных команд, использующих средства динамического микропрограммирования и матрицу смешений для одновременного ветвления по нескольким направлениям. Результаты экспериментальной проверки показали рост производительности транслятора на этапе распознавания в 6-12 раз по сравнению с программной реализацией.

8. Разработан способ применения метода ILRCк)-автоматов для построения диалоговых средств в составе прикладных систем. Разработанный способ использован в практических задачах по созданию автоматизированных систем программирования интегральной логики и проектирования больших интегральных схем.

Основные положения диссертации отражены в следующих работах:

1. \Ивеин A.A., П^мей A.C. Применение метода LR(к)-грамматик для автоматизации проектирования компиляторов и интерп-

ретаторов. - В сб. : "Перспективы развития и опыт применения мини и микро-ЭВМ (СИ ЭВМ), .1982, Орел". М.: 1982, с. 7-8.

_2._Швенн_А._А— Щумей А. С. О возможностях динамического

инкропрограммирования. - В сб.: "Вопросы проектирования и анализа комплексов CU ЭВН". LI : ИНЭУН, 1983, с. 68-73.

3. Zakharov V.a, Litvinov V. V., Rodionov V. V. , Shumey A.S., Zonls V.S., Shvein A.A. Hardware and firmware facilities for hlRh-level language lirplementation. In: Proceedings of the Third Slrrposlun on Mlcrocorrputer and Microprocessor. Application. Budapest, 18-21, October 1983, vol. 1". Budapest, OMIKK Techno Inforn, 1983, pp. 76-86.

4. Швенн А. А. Конструирование высокопроизводительных трансляторов на основе индексированных LR(к)-автоматов. - В сб. : "Вопросы проектирования и диагностики вычислительных устройств и комплексов". И. : ННЗУЫ, 1986, с. 90-105.

5. Ефшов А. В., Пятницкий А. А., Шаеин А. А. Автоматизированная систекэ программирования интегральной логики (АСПИД). - Там кг, с. 82-00.

6. Евеин A.A. Введение семантических действий в оптимизируемые LR(к)-трансляторы. - Веб.: "Технические и программные средства высокопроизводительных комплексов СИ ЭВМ". LL : ЙНЗУЫ, 1987, с. 159-176.

7. Пятницкий А. А., ЕЬеин А. А. Примененш языков высокого уровня в проектировании аппаратных средств на основе программируемой логики. - Так гв, с. 66-74.

8. Литвинов В В , Швеин А. А., Щумей А. С. 16вфопрограммное устройство управления. А. с. N 1315974.

9. ШВеин A.A. Разработка и применение системы программирования интегральной логики для СШ700. - В кн. : Тезисы докладов Всес. конференции "Минн-ЭШ СШ700. Технические и программные средства", 12-14 января 1968 г., г. Суздаль. Ы.: ИГО-УМ, 1988, с. 99-100.

10. Иеяибовский А. И , Раков С. А.Саг а Г., Швеин А. А. Система автоматизированного проектирования БИС на базе

32-разрядных мини-ЭШ. - SKEP'88, 1 dil II svazek, Praha, 1988, 481-487.

11. Раков С. А., Межибовский A. IL, Саг ИГ., Швеин А. А. ЭМИС - система автоматизированного проектирования БИС. - В сб.: "САПР СВГ 89. Секция 1: разработка и внедрение САПР СВТ. Ленинград, 17-21 апреле 1989 г." Ы.: 1989, с. 68-71.

ИНЭУЫ Тира« 100 эка. Заказ N 80