Автоматическая реализация семантики проблемно-ориентированных языков тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

§ I. ВВЕДЕНИЕ

1.1. Цели исследований . Ц

1.2. Обзор смежных работ

§ 2. АТРИБУТНЫЕ ГРАММАТИКИ. ИЪ

§ 3. СТРУКТУРНЫЙ СИНТЕЗ ПРОГРАММ .2.

3.1. Планирование .2.

3.2. Извлечение программы.2.

§ 4. ДИНАМИЧЕСКАЯ РЕАЛИЗАЦИЯ АТРИБУТНОЙ СЕМАНТИКИ.2-8>

4.1. Динамическая корректность атрибутной схемы.X Ъ

4.2. Вычисление семантики программы.3 2.

§ 5. СТРАТЕГИЯ ВЫЧИСЛЕНИЯ АТРИБУТОВ

5.1. Входные и выходные атрибуты.3?

5.2. Понятие стратегии вычисления атрибутов.42.

5.3. Стратегии визитов.

§ б. КЛАССИФИКАЦИЯ АТРИБУТНЫХ СХЕМ.

6.1. Традиционная классификация атрибутных схем

6.2. Расширенные классы атрибутных схем.5"

6.3. Метод визитов и абсолютно ациклические атрибутные схемы.5" G

§ 7. РЕАЛИЗАЦИЯ МЕТОДА ВИЗИТОВ.5"

7.1. Общая характеристика проблемы.

7.2. Построение вычислительной модели языка.

7.3. Доказательство вычислимости семантики .£>

7.4. Синтез семантического процессора.

§ 8. ЭКСПЕРИМЕНТЫ ПО ПЛАНИРОВАНИЮ ВЫЧИСЛЕНИЯ АТРИБУТОВ.

8.1. Программирование атрибутной грамматики.

8.2. Динамическая реализация.g/j

8.3. Статическая реализация. $5"

8.4. Динамическая реализация языка МИЛАН.

8.5. Статическая реализация языка .32.

8.6. Анализ результатов экспериментов .g J.

1.1. Цели исследований

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

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

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

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

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

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

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

Содержание работы распределено по параграфам следующим образом.

- б

Во введении приведен краткий обзор отечественных и зарубежных работ по данной тематике.

Во втором параграфе введены основные понятия и обозначения. ся процесс вычисления семантики программы.

В третьем параграфе дано краткое описание структурного синтеза программ.

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

В пятом параграфе описана стратегия визитов для вычисления атрибутов. Задан алгоритм определения входных и выходных атрибутов.

В шестом параграфе исследуется вопрос корректности атрибутных грамматик. На основе введенного в этом параграфе нетрадиционного понятия корректности предлагается новая классификация атрибутных грамматик.

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

Алгоритмы структурного синтеза црограмм, описанные в [26] , реализованы в системе ПРИЗ-ЕС [9 ] . Разработанные в данной работе методы динамической и статической реализации экспериментально реализованы в этой же системе.

Реализация языков МИЛАН и dip описана в восьмом параграфе.

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

Приводится оцределение атрибутной грамматики зуемых в данной работе. Цифра, следующая за символом обозначает номер страницы, на которой объясняется смысл этого символа.

ЗАКЛЮЧЕНИЕ

При выполнении данной диссертационной работы были получены следующие результаты:

1. Доказана возможность описания семантики языков программирования вычислительной моделью в виде формул в интуиционистском исчислении высказываний.

2. Разработаны новые методы динамического и статического синтеза семантического процессора по атрибутной грамматике.

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

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

- отладка атрибутной грамматики методом динамической реализации;

- статическая реализация языка.

5. Автоматически построены трансляторы для языка программирования МИЛАН (методом динамической реализации) и проблемно-ориентированного языка (методом статической реализации).

1. Ахо А., Ульман Дне. Теория синтаксического анализа, перевода и компиляции, т.1. - М.: Мир, 1978. - 612 с.

2. Ахо А., Хопкрофт Дж., Ульман Дне. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 535 с.

3. Волож Б.Б., Мацкин М.Б., Минц Г.Е., Тцугу Э.Х. Система ПРИЗ и исчисление высказываний. Кибернетика, 1982, № б, с. 63-70.

4. Вооглайд А.О., Меристе М.Б. Абстрактные атрибутные грамматики. Программирование, 1982, № 5, с. 17-26.

5. Гейтинг А. Инуиционизм. М., 1965, - 200 с.

6. Диковский А.Я. Оценки эффективности алгоритмов, связанных с вычислительными моделями. В кн.: Ш конференция "Применение методов математической логики": Тезисы докл. - Таллин, 1983. - с.42-51.

7. Калья А.П. Система управления базой данных DABU-2 / ИК АН ЭССР, Институт планирования ЭССР. Таллин, 1982. - 56 с. (Препринт).

8. Кахро М.И., Калья А.П., Тцугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). М.¡Финансы и статистика, 1981. - 157 с.

9. Кнут Д. Семантика контекстно-свободных языков. В кн.: Семантика языков программирования. М.: Мир, 1980, с.132--161.

10. Котов В.Е. Введение в теорию схем программ. Новосибирск, 1978. - 256 с.

11. Курочкин В.М. Алгоритм вычисления семантических атрибутов* В сб.: Автоматизация производства пакетов прикладных программ (Автоматизация производства трансляторов): Тезисы докл. Таллин, 1980, с. 64-66.

12. Лоро Б. Метод семантических атрибутов в системе DELTA . -В кн.: Труды Всесоюзного симпозиума по методам реализации новых алгоритмических языков. Часть I. Новосибирск, 1975, с. 29-46.

13. Меристе М.Б. Методы реализации атрибутных схем в системах построения трансляторов (обзор). Программирование, 1980, № 5, с.52-61.

14. Минц Г.Е., Пеньям Я.Э., Тцугу Э.Х., Харф М.Я. Структурный синтез рекурсивных программ. В сб.: Автоматический синтез программ. Таллин, 1983, с. 58-72.

15. Минц Г.Е., Тыугу Э.Х. Обоснование структурного синтеза программ. В кн.: Автоматический синтез программ. Таллин, 1983, с. 5-40.

16. Минц Г.Е., Тыугу Э.Х. Полнота правил структурного синтеза. ДАН СССР, 1982, т.263, № 2, с. 291-295.

17. Минц Г.Е., Тыугу Э.Х. Структурный синтез и неклассические логики* В кн.: Ш конференция "Применение методов математической логики": Тезисы докл. - Таллин, 1983, с.52-60.

18. Пеньям Я.Э. Метод автоматической реализации семантики н трансляторах. Технология программирования: Тезисы докл.

19. Всеслюзной конференции. Секция: Метода и средства написания программ. Киев, 1979, с. 46-47.

20. Пеньям Я.Э. Реализация атрибутной семантики. Кибернетика, 1980, № 2, с. 36-41.

21. Пеньям Я.Э. Реализация семантики языков программированияв системе ПРИЗ. Автоматизация производства пакетов прикладных программ (Автоматизация производства трансляторов): Тезисы докл. Таллин, 1980, с. 78-80.

22. Пеньям Я.Э. Синтез семантического процессора по атрибутной грамматике. Программирование, 1983, № I, с. 50-60.

23. Пеньям Я.Э. Эксперименты синтеза семантического процессора по атрибутной грамматике. II Всесоюзная конференция автоматизации производства пакетов прикладных программ и трансляторов: Тезисы докл. Таллин, 1983, с. 41-43.

24. Серебряков В.А. Основные особенности входного языка и реализации СПТ СУПЕР. Программирование, 1982, № I, с.78-83.

25. Томбак М.О. Об использовании метода предшествования в синтаксическом анализе. Дисс. канд.физ.-мат.наук. - Тарту, 1978. - 82 с.

26. Тыугу Э.Х., Харф М.Я. Алгоритмы структурного синтеза программ. Программирование, 1980, № 4, с. 3-13.

27. Чеботарь К.С. Порядок вычисления семантических атрибутов. Программирование, 1979, № 2, с. 50-55.

28. Bochmann, G-.V. Semantic evaluation from left to right. -Commun. ACM, 1976, v. 19, n. 2, pp. 55-62.29« Courcelle, B. Attribute grammars: theory and applications. ■ beet. Notes Comput. Sei., 1981, v. 107, pp. 75-95.

29. Courcelle, В., Franchi-Zannetacci, P. Attribute grammars and recursive program schemes. I. Theor. Comput. Sei., 1982, v. 17, pp. 163-191.

30. Dembinski, P., Maluszynski, J. Attribute grammars and two-level grammars: an unifying approach. Lect. Notes Comput. Sei., 1979, v. 72, pp. 172-178.

31. Deransart, P. Logical attribute grammars. In: Information Processing 83 (IFIP, 1983), 1983, pp. 463-469.

32. Deransart, P. Proof by semantic attributes of a LISP compiler. Comput. J., 1978, v. 22, n. 3, pp. 240-245.

33. Deransart, P., Jourdan, M., Lorho, B. Speeding up circularity tests for attribute grammars. Report n. 211, INRIA, Rocquencourt, 1983« - 27 pp.

34. Engelfriet, J., File, G. Passes, sweeps and visits. -Lect. Notes Comput. Sei., 1981, v. 195, pp. 193-207.

35. Engelfriet, J., File, G. Simple multi-visit attribute grammars. J. Comput. and Syst. Sei., 1982, v. 24, pp. 283-314.

36. Farrow, R. Attribute grammars and data-flow languages. -SIGPLAN Notic., 1983, v. 18, n. 6, pp. 28-40.

37. Farrow, R. LINGUIST-86 Yet another translator writing system based on attribute grammars. SIGPLAN Notic., 1982, v. 17, n. 6, pp. 160-171.

38. File, G. Interpretation and reduction of attribute grammars. Acta Inf., 1983, v. 19, n. 2, pp. 115-150.

39. Ganzinger, M., Giegerich, R., Möncke, U., Wilhelm, R.

40. A truly generative semantics-directed compiler generator. -SIGPLAN Notic., 1982, v. 17, n. 6, pp. 172-184.

41. Ganzinger, H., Ripken, K., Wilhelm, R. Automatic generation of optimizing multipass compilers. In: Information Processing-77, Proc. of IFIP-1977. - Amsterdam etc.: North-Holland Pub1. Co., 1977, pp. 535-540.

42. Jazayeri, M. A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars. J. Assoc. Comput. Mach., 1981,v. 28, n. 4, pp. 715-721.

43. Jazayeri, M., Ogden, W.F., Rounds, W.C. The intrinsically exponential complexity of the circularity problem for attribute grammars. Commun. ACM, 1975, v. 18, n. 2,pp. 697-706.

44. Jazayeri, M., Walter, K.G. Alternating semantic evaluator. Proc. of the ACM 1975 Annu. Conf., 1975, pp. 230-234.

45. Kastens, U. Ordered attributed grammars. Acta Inf., 1970, v. 13, PP. 229-256.

46. Kastens, M., Hutt, B., Zimmermann, E. GAG: a practical compiler generator. Lect. Notes Comput. Sci., 1982, v. 141. - 156 pp.

47. Katayama, T. Treatment of big values in an applicative language HFP. Lect. Notes Comput. Sci., 1983, v. 147, pp. 36-50.

48. Katayama, T. HFP: A hierarchical and functional programming based on attribute grammar. Proc. 5th Int. Conf. on Software Eng., San Diego, California, 1981, pp. 9-12.

49. Kennedy, K., Warren, S.K. Automatic generation of efficient evaluators for attribute grammars. Proc. 3th ACM Conf. on Principles of Program. Lang., Atlanta, Georgia, 1976, pp. 32-49.

50. Koskimies, K., Juutinen, L., Paalli, J. An attribute grammar for C-Euclid, Computer Listing. Technical Report, Department of Gomput. Sci., University of Helsinki, 1982.

51. Koskimies, K., Raiha, K.-J., Sarjakoski, M. Compiler construction using attribute grammars. SIGPLAN Notic. v. 17, n. 6, 1982, pp. 153-159.

52. Plath, W.J. REQUEST: a natural language question-answering system. IBM J. Res. and Dev., 1976, v. 20, n. pp. 326-335.55« Riis, H., Skyum, S. K-visit attribute grammars. -Math. Syst. Theory, 1981, v. 15, PP. 17-28.

53. Raiha, K.-J., Saarinen, M. Testing attribute grammars for circularity. Acta Inf., 1982, v. 17, pp. 185-192.59« Raiha, K.-J., Saarinen, M., Soisalon-Soininen, E.,

54. Tienari, M. The compiler writing system HLP (Helsinki Language Processor). Report A-1978-2, Department of Comput. Sci., Helsinki University, 1978. - 115 PP«

55. Tienari, M. On the definition of attribute grammar. -Lect. Notes Comput. Sci., 1980, v. 94, pp. 408-414.

56. Tyugu, E. Using a problem solver in CAD. In:

57. J. C. Latombe (ed.), Artificial Intelligence and Patterns Recognition in CAD. North-Holland, Amsterdam, 1978, pp. 197-210.

58. Mt, 29 вычислительная модель семантики дереваразбора t

59. Мц, 62 вычислительная модель семантики языка, соответствующего атрибутной схеме tJ out(ct), 14 множество результатов семантического правила <* Р, 13 - множество продукций

60. Р, 64 конъюнкция переменных, выражающих вычислимостьпараметров атрибутной схемы Рх , 62 множество продукций с левой частью Xсинтаксическое правило (продукция) Q, 20 - условия задачи