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

РГ6 од

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ДПР 1993ОРЯЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНА№'ЧИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА

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

ПОДОЛЬСКАЯ Нина Аркадьевна

УЖ 681.03.06

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ИНСТРУМЕНТАЛЬНЫХ РЕДАКТОРОВ ПРОГРАММ

Специальность 05.13.II - математическое и программное обеспечение вычислительных машин и систем

Автореферат

дисс&рташш на соискание ученой степени кандидата физико-математических, наук

шичжБа юао

Работа выполнена на механико-математическом факультете МГУ им. М.В.Ломоносова

Научный руководитель:

кандидат физико-математических наук,

доцент А.Г.Кушниренко

Официальные оппоненты:

доктор физико-математических наук В.Б.Ботелин

кандидат физико-математических наук П.Л.ЕруеилоБский

Ведущая организация; Институт математических проблем

биологии г АН (г. Пущине-)

Защита состоится "ЛЗ" СЬМу^С^^*Л 1993 г. в И часов на заседании Специализированного совета Д.053.05.38 при МГУ по адресу: 119899, Москва, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, аудитория .

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан "ЛЗ" 1993 г.

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

Л.05° 05.38, профессор Н.П.Трифонов

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

АКТУАЛЬНОСТЬ ТЕШ. Развитие процессов информатизации общества, рост потребностей в программном обеспечении требует увеличения производительности труда программистов.

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

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

а) необходимость работать с двумя представлениями исходного текста;

б) увеличение количества файлов;

в) увеличение времени компиляции.

Компиляторы ряда языков программирования (МАЖО-П, С, РЬ/1) имеют встроенный механизм препроцессирования. Использование этого механизма позволяет избежать недостатков а), б). Однако недостаток в) по-прежнему имеет место.

В настоящей диссертации предложен практически применимый . подход, который снимает часть недостатков препроцессирования.

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

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

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

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

По сравнению с традиционной парой "редактор текстов н препроцессор" единый редактор-препроцессор обладает рядом преимуществ:

1) Возможность в основном работать с (одним) исходным (дс препроцессирования) текстом программы.

2) Уменьшение времени оборота за счет совмещения по времени процесса редактирования и препроцессирования.

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

4) Возможность визуализации результат? препроцессированш в любой момент редактирования.

Разработка настраиваемых редакторов-препроцессоров требует решения ряда взаимосвязанных проблем, б том числе исследование и разработки:

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

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

- специальных алгоритмов визуализации результатов препроцессирования ;

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

ЦЕЛИ РАБОТЫ состоят в следующем:

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

- разработка типочнх структур данных и методов их реализации для задач редактирования-препроцессирования;

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

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

- генерация конкрет..ых редакторов-препроцессоров для ми.... ОИЧА .. ^^ ... ..... „ ... ...... ГЛИ

ПИ-.-'ь-¡VI, ни¡л.-^палыжл VI и!Г имглил ..'ит .

Г'УчпАЯ НОВИЗНА. Расширена теория конечных преобразователей. Предложен и реализован новый тип инструментального средства: настраиваемый редактор-препроцессор.

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ. Предложен новый подход к разра-Зотке инструментальных редакторов программ. Разработан и реализован практически генератор редакторов-препроцессоров, проведе-ш генерация редакторов-препроцессоров для расширений языков ЛАКРО-П, Фортрана, Си и других.

ылчтшго гг..«...........~

шшдгшш, продлилоппми о д«и;(;о1)шции гвпврахир ¡)влаыи-

юв-препроцессоров* использовался при разработке программного збеспечения учебного процесса на механико-математическом <|п-

кулыетб МГУ, б частности, с его помощью были разработаны три синтаксически-орибнтйроБаппкх редактора для языков MACRO-II, Фортран и С. Кроме того, был сгенерирован редактор-препроцессор для структурного программирования на Ассемблере школьной ЭВМ УКНЦ. Редактор-препроцессор для MACK0-II используется в ряде организаций страны.

АПРОБАЦИЯ РАБОТЫ. Материалы работы докладывались на:

- Ломоносовских чтениях в МГУ (1987,1988,1989);.

- на ежегодной научной конференции НИВ". АН СССР (Пушино, 1987, 1988);

- на научных семинарах механико-математического факультета МГУ (1987-1992);

- на Всесоюзных семинарах "Разработка и применение программных средств ПЭВМ в учебном процессе" (1988, 1989).

ПУБЛИКАЦИИi Основные результаты диссертации изложены в работах [1-5].

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

Диссертация состоит из введения, 5 глав, .приложения и списка литературы из 53 наименований. Общий объем диссертации -134 страниц, из них 120 страниц основного текста, 7 страниц приложений.

ВО ВВЕДЕНИИ (3 ст£,) обосновывается актуальность исследования проблем разработки редакторов-препроцессоров. Излагается структура диссертации и основные полученные результаты.

В ПЕРВОЙ ГЛАВЕ (20 стр.) проводится исследование возможностей ускорения разработки программного обеспечения на базе совмещения процессов редактирования и препроцессирования.

Основное внимание при этом направляется на решение задачи ускорения разработки программ за счет ускорения процессов кодирования и гтлчдки.

Исследуется 3 пути ускорения этих этапов разработки программ:

1. Совершенствование языков программирования (п. 1.1 диссерта-

......\

ипп / .

2. Совершенствования интерфейса редакторов (п.1.2).

3. Сокращение времени оборота программ (п.1.3).

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

В п.1.2 анализируется интерфейс редакторов: текстовых, синтаксически ориентированных и синтаксически направленных. В синтаксически направленных редакторах возможен ввод програ»1мн как текста или командами. Рассматриваются преимущества и недос-татк« обоих способов. Делаются предложения по методу работы с синтаксическими конструкциями и по сочетанию синтаксически направленного редактирования с текстовым в синтаксически направленных редакторах.

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

- е -

На основании пр^ведеыюгс лгл'л&лоыпи'г: в п. 1.4 ставит-задача совмещения процессов редлктироьания и преп, онессиров. ния. Использование получаемых при таком совмещении редакт' ров-препроцессоров дает все преимущества использования прещи Цбссоров, но лишено многих его недостатков.

В п.1.5 рассматриваются дополнительные возможности, воэн] каюшие при совмещении редактирования с препроцессированием, частности, это

1. Совершенствование интерфейса редактора (отвечающее зада1 ускорения разработки программ), в сторону еинтаксичес! ориентированного редактирования, возможности которого анг лиэируются б п. 1.2.

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

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

ВО ВТОРОЙ ГЛАВЕ (16 страниц) разрабатывается и исследуетс практическая модель редактора-препроцессора:' редактор-препрс цессор для MACR0-.II, поддерживающий пакет макроопределем "Макро-85".

В п. 2.1 обосновывается выбор редактора и пакета макроог ределений, описывается внешний проект редактора-препроцессора В соответствие с п.1.5, описывается следующий дополнительнь сервис, реализованный ъ этом редакторе-препроцессоре:

I) элемента синтаксически ориентированного редактирования а) вставка шаблонов конструкций и удаление всего текст

- 7 -

энструкций с помощью функциональных клавиш; - б) автоматическое форматирование прогрчмы;

в) облегченное редактирование колонки комментариев;

2) элементы синтаксически направленного редактирования -лагностика синтаксических ошибок при оформлении конструкций;

3) прьлх шные программы, облегчающие работу с разделяемыми эременнкми: средство редактирования этих переменных и контроль а правильным их использованием.

Проведен анализ требований к редактору-препропяссору: к иособу хранения исходного текста и результата препроцессирова-ия, к визуализации результатов препроцессирования, к интерфей-/ с пользователем.

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

В п.2.7 описывается архитектура редактора-препроцессора, в оторой удается сохранить четкое разделение на редактирующую и репро:,ассирующую части.

Приведенные в п. 2.8 результаты измерений времени компиля-ии и времени оборота программы для препроцессора и редакто-а-препроцессора свидетельствуют о том, что использование р£-актора-препроцессора дает выигрыш в 2-3 раза во времени компи-яции и в 1,5-2 раза во времени оборота по сравнению с исполь-ованием стандартного препроцессора.

В ТРЕТЬЕЙ ГЛАВЕ (25 стр.) исследуются функции перевода, озвратные конечные -преобразователи и задача диалогового преп-оцессированля.

Пусть X*- пространство всех конечных последовательностей

.-„ „ —„. ...... —.. V

Перевод можно рассматривать как функцию р: X ->У

Препроцессирование можно рассматривать как перевод одной (входной)

последовательности с имволов в другую (выходную).

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

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

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

Такие функции в п. 3.2 названы возвратно-индуктивными. Для функций, не являющихся возвратно-индуктивными, в п. 3.2 вводится понятие возвратно-индуктивного расширения. Формулируется и доказывается критерий возвратной индуктивности, проверяется возвратная индуктивность и строятся возвратно-индуктивные расширения для нескольких функций перевода.

I) Кушнирекко А.Г., Лебедев Г.В. Программирование для математиков. - Издательство "Наука", 1988.

Функции перевода тесно связаны с синтаксически управляемн-ш (СУ) переводами. В п. 3.3 приводятся некоторые определения и 'тверждения из работы , касашиеся СУ-переводов и простых У-первводов, вводится понятие соответствия некоторой функции геревода некоторому переводу, рассматривается несколько приме-юв. Доказывается утверждение о том, что область определения »тношения соответствия функций перевода и СУ-переводов является [©собственным подмножеством функций перевода, а множество зна-гений этого отношение является несобственным подмножеством мно-соства СУ-перевопов.

Это же утверждение доказывается и для простых переводов.

В терминах теории конечных преобразователей (см. ) :репроцессор есть ни что иное, как некий конечный преобразова-ель. Задача препроцессирования полностью укладывается в рамки еории конечных преобразователей. В п. 3.4 приводятся взятые из аботк ^ определения конечных преобразователей, определяемых ми переводов, МП-преобразователеи и определяемых ими перевода, теорема о связи простых СУ-переводов и МП-преобразовате-ей.

Формулируется и доказывается

Утверждение 4.Т. Отношение функций перевод.', с простыми У-переводами эквивалентно отношению функций перевода с МП-пре-бразователями.

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

I) Ахо А., Ульман Дж. Теория синтаксического анализа, пе-

.. .. А. |Я . тппо

сшила VI . — IV!. . 1'11'1 у , ±.у ! .

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

Для решения задачи диалогового препроцессирования в п..3.5 проводится обобщение теории конечных преобразователей. Вводится понятие возвратного конечного преобразователя:

Определение 5.1. Конечный преобразователь М=(0,ХД,<3,40,10 называется возвратным, если существует отображение с1Ь:С)х(-> ОхУ* , т.ч. если с1(ц,а)=(г .г), у=хг, то с1Ь(г ,у,а)=и,х),

Формулируется и доказывается

Утверждение 5.1. (критерий возвратности) Конечный преобразователь М=(0,Х,У,с1 является возвратным тогда и только тогда, когда для любых' 41^2^0, а^Х, убУ* из равенств <1(д1,а)=(г ,21), с1(ц2,а)=(г ,г2), у=хШ=х2г2 следует ц1=ц2, г!=г2.

Для конечных преобразователей, не являющихся возвратными, вводится понятие возвратного расширения:

Определение 5.2. Возвратным расширением конечного преобразователя М=(0,Х,У,с1,д0,Р) называется возвраттШ конечный преобразователь М'^О.ХД'.с!\qO.F), если существует функция р:С1хУ'* -> ОхУ* такая, что для любых д^О, а£Х, выполнено

(Кд.аЬрЫЧч'.а)).

Доказывается

. Тоорема 5.1. Для любого конечного преобразователя М можно построить его возвратное расширение.

В п. 3.6 результаты п. 3.5 расширяются на МП-преобразователи.

Вг-о.сию.я понятие возвратного МП-иреобразователя:

- II -

"Определение 6.1. МП-преобразователь Р=(0,Х,Г,У,(М0,20,Р) называется возвратным, если существует отображение аь:0к(у Г\{е)г)хГ -> ОхУ%Г*, т.ч. если сЗ(п,а,2)=(г,г,у), у=хг, то с!Ь(г ,г ¿у ,а)=(п ,х,2),

Дается определение возвратного расширения МП-преобразователя. .

Определение 6.2. Возвратным расширением МП-преобразователя Р=(0,Х,Г,У,с!,с10,г0,Р) называется возвратный конечный преобразователь Р'-(0,Х-,Г,У ',(3\пОДО,Р), если существует функция р;0хУ -> ОхУ такая, что для любых ч^О, а£Х, Ъ6Т, выполнено сН ц ,а,2)=р(й '(ц ).

Доказывается

■ . Теорема 6.1. Для любого МП-преобразователя Р можно построить его возвратное расширение Р .

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

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

Излагается метод построения редактора-препроцессора на базе этого возвратного расширения.

Приводятся алгоритмы, связывающие препроцессор с редактором для'построения редактора-препроцессора. Описывается стратегии препроцессирования тек~:тз. при ого .

I' I

л —

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

В п. 3.9 исследуется понятие состояния препроцессора кар МП-преобразователя. Состояние рассматривается как совокупное™ состояний некоторых объектов. Эти объекты разбиваются на трь класса: постоянные, транзитные и локальные. Описывается метод, позволяющий использовать это рг .(биение для оптимизации обработки выходной последовательности редактора-препроцессора при изменении редактируемого текста.

В ЧЕТВЕРТОЙ ГЛАВЕ (23 стр.) описывается генератор редакторов-препроцессоров, разработанный автором на основании результатов, полученных в Главах 2 и 3.

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

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

Генератор работает следующим образом. Он переводит паке! во внутреннее представление, представляющее собой текст на базовом языке пакета настройки, подает этот текст на вход пакет-|*ого компилятора и собирает полученный на выходе компилятора

объектный модуль с базовым модулем редактора-препроцессора.

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

Приводится подробное описание разделов пакета настройки, а именно:

1) Описание макроопределений:

а) процедура распознавания макровызова;

б) список имен макрокоманд;

в) описание расширения макровызовов.

2) Формат файлового представления.

3) Сведения об организации макроопределений:

а) абстрактное синтаксическое дерево макровызовов;

б) информация о зависимости текстов макрорасширений;

в) начальные значения транзитных объектов;

г) список постоянных объектов.

4) Прикладные возможности:

а) формат экр£ шого представления;

б) шаблоны;

в) прикладные программы.

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

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

- 14 -

В п. 4.3 рассматриваются некоторые вопросы реализации генератора редакторор-препроцессоров, а именно:

1. Внутреннее представление пакета настройки;

2. Используемые редактором-препроцессором об'ектн;

3. Механизм макрогенерации;

4. Алгоритм определения зоны переразбора при изменениях редактируемого текста.

В ПЯТОЙ ГЛАВЕ (30 стр.) описывается процесс генерации автором конкретных редакторов-препроцессоров для следующих препроцессоров: препроцессор к Фортран-компилятору РАТФОР, пакет макроопределений "Макро-85", тур.бо-верификатор С-программ, препроцессор к Фортран-компилятору "Алгебра-88". Приведено подробное изложение пакетов • настройки вместе с алгоритмами прикладных программ.

В ПРИЛОЖЕНИИ (7 стр.) описываются пакет макроопределений "Макро-85" и препроцессоры "КАТРОЯ" и "Алгебра-88".

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

1. На основании проведенного анализа современных подходов к повышению эффективности разработки' программ на традиционных языках программирования предложен подход к разработке программ на основе совмещения процессов редактирования и препроцессирования. Разработаны типовые структуры данных и алгоритмы их обработки для.задач диалогового препроцессирования.

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

программирования.

3. Сгенерированы конкретные редакторы-препроцессоры для мини-ЭВМ, персональных и школьных ЭВМ.

Разработанное автором программное обеспечение используется

в ряде организаций страны. Получено 10 актов о внедрении.

Основные результаты диссертационной работы опубликованы в

следующих работах:

1. Подольская H.A. Редактор-препроцессор для MAKP0-II. М., 1988, 19 е., Деп. в ВИНИТИ 20.01.88, 487-В88.

2. Подольская H.A. Инструментальные редакторы-препроцессоры на малых ЭВМ. - Материалы IV Всесоюзного семинара "Разработка и применение программных средств'ПЭВМ в учебном процессе". М., 1988, с. 78-80.

3. Подольская H.A. Настраиваемый редактор-препроцессор. - Материалы V Всесоюзного семинара "Разработка и применение программных средств ПЭВМ в учебном процессе". М.,.1989, с. 78.

4. Подольская H.A. Разработка программного обеспечения для УК Ш.//Информатика и образование, 1992, N 2.

5. Подольская H.A. Конечные преобразователи и задача диалогового препроцессирования. М., 1993, 19 е., Деп. в ВИНИТИ 19.01,93, II2-B93.

П'агисано в щчать yjT03-S*

Формат G0X8I/I6. Oijv-тиая печать. Овьем / п л.

3al.J3 Тира* /ОС

!к\'.лтра^ичсское пргдпрпятш rADinr.pi» .Чисто iciail l2;S.iUH. Mmiij, 3 « Сплина-,, ur> , 3'