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

ВВЕДЕНИЕ.

1. СЕМАНТИЧЕСКИЕ АСПЕКТЫ РЕАЛИЗАЦИИ ТРАНСЛЯТОРОВ

ФОРМАЛЬНЫХ ЯЗЫКОВ.

1.1. Методы и средства создания трансляторов.

1.2. Формализация семантических описаний.

1.3'. Структура семантического процессора.

1.4. Метасемантический язык.

2. ИССЛЕДОВАНИЕ ВНЕШНЕЙ СРЕДЫ ТРАНСЛЯТОРА.

2.1. Общая характеристика входного языка

2.2. Стандартные средства объектного уровня

2.3. Уровень виртуальной исполнительной среды.

3. ФОРМАЛЬНАЯ СЕМАНТИКА ОБЩЕАЛГОРИТШЧЕСКИХ СРЕДСТВ.

3.1. Структуры данных.

3.2. Основные управляющие структуры

3.3. Метапрограммирование общеалгоритмических средств

4. ФОРМАЛЬНАЯ СЕМАНТИКА СРЕДСТВ ВЗАИМОДЕЙСТШЯ

С ОПЕРАЦИОННОЙ СРЕДОЙ.IOI

4.1. Супервизорное управление в реальном масштабе времени

4.2. Средства обмена.

4.3. Метапрограммирование средств взаимодействия с операционной средой

5. ИССЛЕДОВАНИЕ РЕАЛИЗАЦИИ СЕМАНТИЧЕСКИХ ПРОЦЕДУР

5.1. Архитектура комплекса семантических процедур.

5.2. Технология генерации транслятора.

5.3. Количественные оценки и вопросы оптимизации

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

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

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

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

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

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

Входным языком реализации является алгоритмический язык высокого уровня PB-2.I.2 [l2.3] , в качестве выходного служит язык ассемблера ДОС АСПО [э.з] .

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

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

ЗАКЛЮЧЕНИЕ

К основным результатам проведенных исследований следует отнести следующие:

1. Проведен анализ конструктивных методов формализации семантики и предложен расширенный атрибутивный метод задания семантики.

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

3. Предложенный метод формализован в виде разработанного мета-семантического языка.

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

5. Разработаны и исследованы методы и метапрограммы отобра-кения основных структур данных и общеалгоритмических управляющих структур входного языка PB-2.I.2.

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

7. Разработана общая архитектура семантического процессора и зхема генерации его программ для исполнительного вида.

8. Получены оценки затрат на разработку семантики языка высо-soro уровня для практической реализации канала трансляции языка РВ з кроссовой системе подготовки программ для управляющих ЭВМ -Ж-2.1.2.

9. Разработанное программное обеспечение семантического процессора в составе системы СМИ принято междуведомственной комиссией и сдано в ГосФАП.

1. Материалы съездов, конференций, симпозиумов.

2. П Всесоюзное совещание "Автоматизация проектирования и конструирования (Ленинград): тезисы докл./ Ананьевский С.А., Бед-ненко В.В., Бею Т.В. и др. Кроссовая система автоматизации проектирования программного обеспечения АСУ ТП. М.: 1983, с. 59-60.

3. Ш Всесоюзная научно-техническая конференция молодых ученых и специалистов (Северодонецк): тезисы докл./ Ананьевский С.А., Бедненко В.В., Бею Т.В. и др. Синтаксически ориентированный транслятор для управляющих ЦВМ. М.: 1973, с. 18-19.

4. Ш Всесоюзная межвузовская конференция: тезисы докл./ Ананьевский С.А., Самофалов К.Г., Бею Т.В. и др. Реализация параметрического транслятора. К.: 1975, с. 97-98.

5. Труды всесоюзной конференции по программированию (3-6 февраля 1970 г.): международная дискуссия. Новосибирск: ВЦ АН СССР, 1970, - 70 с.

6. Труды Всесоюзного симпозиума по методам реализации новых алгоритмических языков (Новосибирск, 1985). Новосибирск: ВЦ АН СССР, 1975, - 90 с.

7. Шестая межреспубликанская школа-семинар "Интерактивные системы" (Батуми): тезисы докл./ Бею Т.В., Механикова М.П., Сархан С.И.

8. Реализация режима диалога в кроссовых СПТ при настройке на семантику входных языков. Тбилиси: 1984, с. 350-360.4. Книги41. Ахо А., Ульман Дж.

9. Методы построения компиляторов, /в сб.: Языки программирования. М.: Мир, 1972. - 40 с.44. Ван-Вейнгаартен Ф.

10. Трансляция языков программирования, /пер. с англ. Л.В.Ухова под ред. В.В.Мартынюка. М.: Мир, 1977. - 192 с.45. Вельбицкий И.В.

11. Методы для формального деления семантики языков программирования. К.: ИК АН УССР, 1975. - 26 с.

12. Вельбицкий А.В., Ходаковский В.М., Шолмов А.И. Технологический комплекс производства программ на машинах ЭС ЭВМ, БЭСМ-6. М.: Статистика, 1980. - 263 с.47. Глушков В.М. и др.

13. Алгебра, языки, программирование. К.: Наукова душа, 1974.328 с.48. Гонца М.Г.

14. Многоязыковые транслирующие системы.Синтаксис, семантика, проектирование./ под ред. В.Д.Рынгача. Кишинев: ШТШНЦАД978.139 с.49. Гонца М.Г. и др.

15. Параметрические транс .пирующие системы, ч. I. Основные принципы и методы построения. Кишинев: НГШИНЦА» 1974. - 116 с.410. Грис Д.

16. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. 544 с.

17. Дал У., Дейкстра Э., Хоор К.

18. Структурное программирование./ пер.с англ. С.Д.Зеленецкого под ред. Э.З.Лгобимского. М.: Мир, 1975. - 247 с.412. Донаху Д.

19. Взаимодействующие определения семантики языков программирования. / в кн.: Семантика языков программирования. М.: Мир, 1980. - с. 222-387.413. Донован Дж.

20. Системное программирование. / пер. с англ. Л.Д.Райкова и С.Н.Флоренцова под ред. Л.Д.Райкова. М.: Мир, 1975, - 540 с.414. Ершов А.П.

21. Введение в теоретическое программирование. М.: Наука, 1977. - 286 с.

22. Зелковиц Д., Шоу А., Гэннон Дж.

23. Принципы разработки программного обеспечения. М.: Мир, . 1982. - 366 с.416. Ингерман П.

24. Синтаксически ориентированный транслятор, /пер. с англ. Ф.Ф. Шиллер под ред. А.И.Китова. М.: Мир, 1969, - 175 с.417. Квиттнер П.

25. Задачи, программы,, вычисления, результаты./пер. с англ. М.М,Горбунова-Посадова,.Д.А.Корягина и В.В.Красотченко под ред. В.В.Мартынюка. М.: Мир, 1980.-422 с.418. Кнут Д.

26. Семантика контекстно-свободных языков./ в кн.: Семантика языков программирования. М.: Мир, 1980. - с. I37-I6I.

27. Льюис П., Розенкрац Д., Стирнз Р.

28. Атрибутные трансляции./ в кн.: Семантика языков программирования. М.: Мир, 1980. - с. 162-195.420. Майерс Г.

29. Надежность программного обеспечения. М.: Мир, 1980.-353 с.421. Мак-Кракен Р., Дорн У.

30. Численные методы программирование на Фортране. М.: Мир, 1977. - 380 с.

31. Маккиман У., ХорнингД., Уортман Д.

32. Генератор компиляторов. М.: Статистика, 1980. - 521 с.

33. Маркоти М., Ледгард X., Бохман Г.

34. Формальные описания языков программирования. -/В кн.: Семантика языков программирования. М.: Мир, 1980. - с. 9-136.424. Мейер Б., Бодуэн К.

35. Методы програмщювания. М.: Мир, 1982. - 724 с.

36. Мини-ЭВМ: Сборник статей под ред. Э.Опперля./ пер. с англ. -М.: Мир, 1975. 115 с.426. Пратт Т.

37. Языки программирования, разработка и реализация. М.: Мир, 1979. - 575 с.427. РенделлБ., РасселЛ.

38. Реализация АЛГ0Л-60. / пер. с англ. Д.Б.Подшивалова под ред. . , В.М.Курочкина. М.: Мир, 1967. - 476 с.128. Хигман Б.

39. Сравнительное изучение языков программирования. / пер. с англ. Л.В.Ухова под ред. В.В.Мартынюка. М.: Мир, 1974. -204 с.429. Щуксман А.Л. и др.

40. Основы разработки трансляторов. Ростов-на-Дону: 1974. -170 с.

41. Ed. 6.W. Potlack), K.Y., Шг.р.р.

42. McCarthy 3-. A Basis for a Mathematical Theoryof Computation, Brafforfc P. fHerscfiberj D (eds.), Computed Programming and format Systems,

43. North HoCeand ,{963, p. 53-69.5. Статьи.51. Агафонов В.Н.

44. О семантике переменных в паскалеобразных языках. В сб.: Теоретические основы компиляции. - Новосибирск: изд. НГУ, 1980, с. 17-23.

45. Ананьевский С.А., Стеблянко В.Г., Бедненко В.В., Бею Т.В. и ДР.

46. Параметрический транслятор в системе автоматизированного проектирования математического омеспечения. Механизация и автоматизация управления, 1975, № 4, с. 19-25.

47. Арефьева Н.А., Пушкина И.П., Родионов С.Т.

48. ЖРО -технология метод разработки и сквозного документирования программ по принципу "сверху-вниз". - Управляющие системы и машины, 1978, В 3, с. 35-39. >.4. Ананьевский С.А.

49. Язык описания вычислительного процесса в АСУ ТП. Механизация и автоматизация управления, 1976, № I, с. 43-46. i.5. Белявский Б.И., Михлин Г.З., Фрункин В.А.

50. О построении интерпретаторов специализированных ЦВМ. Управ. ляющие машины и системы, 1975, № 5, с. 96-99. • .б.Бэкус Дж. и др.

51. Сообщение об алгоритмическом языке АЛГ0Л-60./ под ред. П.Наура Журнал вычислительной математики и математической физики, 1961, В I, с. 32-56. .7. Вельбицкий И.В.

52. Метаязык R/-грамматик. Кибернетика, 1973, № 3, с. 47-63.8. Вельбицкий И.В.

53. Технология производства программ на базе ft-метаязыка. -/В кн.: Системное и теоретическое.программирование. Кишинев: Кишиневский госуниверситет. 1974, т.1, с. 260-271.

54. Глушков В.М.Вельбицкий И.В., Стогний М.А.

55. Об одном подходе к построению системного математического обеспечения современных вычислительных машин. Кибернетика, 1972, В 3, с. 25-35.

56. Глушков В.М., Вельбицкий И.В.

57. Технология программирования и проблемы ее автоматизации. -Управляющие системы и машины, 1976, № 6, с. 75-93.

58. Грушецкий В.В., Ершов А.П., Покровский С.В. Метапроцессоры для универсального программирующего процессора./ в кн.: Некоторые проблемы вычислительной и прикладной математики. Новосибирск: Наука,сибирское отделение, 1975, с. 226-250.512. Ершов А.П.

59. Технология разработки систем программирования, /в кн.: Системное и теоретическое программирование. Новосибирск: ВЦ СО АН СССР, 1972, с. 136-184.513. Ершов А.П.

60. Трансформационный метод в технологии программирования. -/ докл. на 1-й Всесоюзной конференции "Технология программирования" (Киев) . К.: ИК АН УССР, 1979, с. 12-26.514. Кауфман В.Ш. '

61. О технологии создания трансляторов. Программирование, 1978, J6 3, с. 36-44.

62. Кахро М.И., Мяннисалу М.А., Саан Ю.П., Тыугу Э.Х. Система программирования ПРИЗ. Программирование, 1976, № I, с. 38-76.

63. Красник Л.И., Неменман М.Е.

64. COM,CO P = 'ADA ' i С О M,P A R = ' = D 2'J call WRA;

65. COM.COPs'STA'JCALL GPR('tZ+',NC) Jcall w r a ;

66. CALu GL3{'.L'»NL) !COM.COP='lSZ'i CALL KPR ( '.Z+',NC) ! CALL WRA» CQ?J, COP= 'JMP ' i COM . ?AR= '* + 2 ' ! CALL WRA;com.cop='jmp';com.par='*+';

67. ЗАВЕРШЕНИЕ ЭЛЕМЕНТА СПИСКА ЦИКЛА */ip sc1 = k them call gen i ' i sz ' > else do ; call gen( pl3a ') ; com.cop='ad a';call gpr( 7 1+ ' ,ns) ; call wra 5 call gen('sta'); end i1. s с 1-0 THEN DO; COM.COP=fJMP ' i

68. Некоторые аспекты технологии программирования. Управляющие системы и машины, 1975, f 6, с. 12-16.518. Лавров С.С.

69. Методы задания семантики языков программирования. Программирование, 1978, Я 6, с. 3-10.

70. Липаев В.В., Серебровский АД,, Филиппович В.В.

71. Система автоматизации программирования и отладки комплексов программ управления ЯУЗА-6. Программирование, 1977, № 3, с. 87-94.520. Марков А.С.

72. К вопросу об унификации языков программирования. Кибернетика, 1975, № 2, с. 95-106. 5.20. Прууден Ю.И., Тамм Б.Г.

73. Метасистема для создания информационно-связанных специализированных систем программирования. Кибернетика, 1974, № 6, с. 69-73.522. Орешкин Н.П.

74. О средствах реализации проблемно-ориентированных языков. -Программирование, 1977,т № 6. с. 39-43.523. Редько В.Н.

75. Основания композиционного программирования. Программирование, 1979, № 3, с. 37-40.524. Редько В.Н.

76. Семантические стуктуры программ. Программирование, 1981, № I, с. 3-19.

77. Самофалов К.Г., Колинько Р.Ф., Бею Т.В.

78. Вопросы метапрограммирования в параметрических системах трансляции. Вестник КОИ, автоматика и электроприборострое-. . ние, 1983, № 20, с. 80-82.

79. Стеблянко В.Г., Бею Т.В. и др.- 142

80. Вопросы кроссовой реализации языков программирования для микропроцессоров и микро-ЭВМ. Методы и средства системного программирования, сборник научных трудов. -К.: 1984, с. 90-96. 5.27.Фелдман Дж. Грис Д.

81. Система построения трансляторов, /в сб.: Алгоритмы и алгоритмические языки. М.: ВЦ АН СССР, 1971, вып.5, е. 37-56.5.2,8. baker Е.Т. Chie-f Programmer Team Managment of Products ProgrammCnq.- "(6M System V\ WZ, p. «9-Ш.

82. MoC&ure C.U Top-down , bottom-ар and structured Programming. ~ in :Proc, of the Math Conf of Software Enyeneering. Wochington D.C. ,Ш6,р.89-9к. 5,30. Stay ?.£. Hopo and integrated cfestgn,-"(6M System J", /976, p.R3454.6. Диссертации

83. Деогирикар Арвинд Девендрарао.

84. Вопросы параметрической реализации языка Паскаль. Дисс.на соискание уч. степени канд. техн. наук. - К.: 1981. - 135 с.62. Колинько Р.Ф.

85. Система построения трансляторов. Дисс. на соискание уч. степени канд. техн. наук. - К.: 1982. - 133 с.63. Стеблянко В.Г.

86. Разработка параметрического транслятора для автоматизации проектирования математического обеспечения управляющих ЦВМ.-Дисс. на соискание уч. степени канд. техн. наук. К.: 1976.140 с.

87. Нормативно-технические документы

88. Агрегатная система программного обеспечения М-7000 и СМ ЭВМ. Дисковые операционные системы. Краткое описание и руководство по пользованию.

89. Единая система электронных вычислительных машин ЕС ЭВМ. Операционная система. Техническое описание.

90. Система М-6000/М-7000 АСВТ-М. Мнемокод М-7000. Руководство по программированию.

91. Система автоматизации.проектирования математического обеспечения (САП МО) АСУ ТП. Межотраслевого применения. К.: 1978, 577 с. /Рукопись представлена Киевским политехническим институтом. Деп в СО ФАП 21 февраля.1978 г. Инв. № 2060-К.