автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Принципы реализации семантики языка Cu++ в системе 3C++

ВВЕДЕНИЕ.

Актуальность работы.

Стандартизация языка Си++.

Проект тройного стандарта.

Компилятор Си++.

Компилятор переднего плана.

Генератор кода.

Цель работы.

Личный вклад автора.

Научная новизна.

Практическая ценность и реализация.

Структура работы.

Апробация работы.

ГЛАВА 1. ОТНОШЕНИЯ МЕЖДУ КЛАССАМИ.

1.1 Введение.

1.2 Отношение наследования.

1.3 Граф подобъектов.

1.4 Правило доминирования.

1.5 Доступность базовых классов и членов класса.

1.6 Использование отношений между классами в компиляторе.

1.7 Структуры данных для хранения информации о классах.

2.2 Объекты классов.50

2.3 Члены класса.53

2.4 Механизмы времени компиляции.54

2.4.1 Обозначения.55

2.4.2 Построение списка всех виртуальных функций.55

2.4.3 Выявление чистых виртуальных функций и абстрактных классов.59

2.4.4 Подбор основного базового класса.60

2.4.5 «Раскладка» класса.:.60

2.4.6 Создание таблицы смещений виртуальных базовых классов.63

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

2.4.8 Создание таблицы виртуальных функций.68

2.4.9 Создание таблиц виртуальных функций для подобъектов базовых классов.69

2.4.10 Пример генерации таблиц виртуальных функций для базовых классов73

2.4.11 Создание объектов класса typejnfo.74

2.4.12 Оптимизация таблиц виртуальных функций.75

2.4.13 Структуры данных, используемые при обработке класса и генерации таблиц.77

2.5 Механизмы времени выполнения.78

2.5.1 Создание и уничтожение объектов классов.79

2.5.2 Преобразования указателей на классы.80

2.5.3 Статические члены класса.82

2.5.4 Доступ к нестатическим членам классов.82

2.5.5 Вызов функций-членов класса.83

2.5.6 Указатели на члены и функции-члены классов.84

2.5.7Преобразования указателей на члены и функции-члены классов.85

2.5.8 Реализация операции typeid.86

2.5.9 Реализация оператора dynamiccast.87

2.5.10 Реализация определения типов исключительных ситуаций.89

2.6 Заключение. Выводы главы 2.90

ГЛАВА 3. ПОИСК ИМЕН.92

3.1 Введение.92

3.2 Особенности поиска имен в языке Си++.94

3.3 Реализация механизма поиска имен в одной области действия.103

3.3.1 Традиционный способ поиска имен и его недостатки.104

3.3.2 Использование общей хеш-таблицы.106

3.3.3 Использование «перевернутой» таблицы.107

3.3.4 Алгоритмы добавления и поиска.109

3.4 Свойства областей действия.111

3.5 Поиск неквалифицированных и квалифицированных имен.115

3.5.1 Поиск неквалифицированного имени.115

3.5.2 Поиск квалифицированного имени. 116

3.6 Заключение. Выводы главы 3.118

ГЛАВА 4. РЕАЛИЗАЦИЯ СИСТЕМЫ ТИПОВ И ПРОВЕРКИ ТИПОВ.119

4.1 Введение.119

4.2 Общие требования к реализации системы типов.120

4.3 Методы реализации типов.122

4.3.1 Реализация типов с помощью типовых цепочек.122

4.3.2 Реализация системы типов при помощи таблицы.124

4.3.3 Реализация типов с помощью структур.128

4.4.4 Квалификаторы const и volatile. 130

4.4 Дополнительные возможности по работе с типами.131

4.5 Реализация системы типов.132

4.6 Преобразования типов.134

4.7 Реализация проверки типов для операторов и выбора наилучшей перегруженной функции.139

4.8 Заключение. Выводы главы 4.146

ЗАКЛЮЧЕНИЕ.147

ЛИТЕРАТУРА.149

Рисунки и диаграммы:

Основные результаты четвертой главы могут быть сформулированы следующим образом:

1. Изучены особенности системы типов языка Си++ и ее отличия от систем типов в родственных языках программирования.

2. Сформулированы требования к реализации системы типов в компиляторе Си++.

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

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

5. Исследованы особенности проверки типов в языке Си++ и требования к реализации проверки типов в компиляторе.

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

Заключение

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

1. Дано формальное определение графа наследования, на основе которого проведенео систематическое исследование семантических свойств механизма наследования классов в языке Си++. Построена и изучена формальная модель (граф подобъектов) строения объектов классов, учитывающая особенности языка. На основании формальной модели предложен способ эффективного вычисления числа подобъектов базового класса и дано формальное определение однозначности базового класса. Дано определение доминирующего класса, основанное на формальной модели, и предложен способ эффективного определения доминирующего класса. Предложен способ определения доступности базового класса и члена базового класса на основании графа наследования.

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

3. Разработаны алгоритмы генерации машинно-независимого низкоуровневого промежуточного кода и структур данных (таблиц) периода выполнения, реализующие семантику механизмов классов. В частноси, предложены следующие решнения: способ реализации множественного и виртуального наследования; метод реализации виртуального наследования, основанный на генерации таблиц смещений виртуальных базовых классов; алгоритмы генерации таких таблиц; метод генерации кода для доступа к членам классов и членам базовых классов; способ реализации преобразований указателей и ссылок на классы, учитывающий особенности множественного и виртуального наследования; метод реализации виртуальных функций, основанный на генерации таблиц. Дано определение доминирования для виртуальных функций и предложен способ его выявления. Описаны методы определения абстрактности классов и неявной виртуальности функций. Предложен метод реализации и преобразования указателей на члены классов. Описаны методы реализации операторов typeid и dynamiccast с использованием объектов расширенного класса typeinfo. Предложен метод реализации динамического определения типов для исключительных ситуаций.

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

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

6. Исследованы особенности поиска имен в Си++ и отличия правил поиска имен в этом языке от правил поиска имен в других языках программирования. Сформулированы требования к реализации поиска имен в компиляторе.

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

8. Исследованы особенности системы типов языка Си++ и ее отличия от систем типов в родственных языках программирования. Сформулированы требования к реализации системы типов в компиляторе Си++.

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

10. Исследованы особенности проверки типов в языке Си++ и требования, к реализации проверки типов в компиляторе.

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

1. 1.O/l ЕС 14882:1998 Programming languages - С++.

2. ISO/I EC DIS 9899 Programming languages C.

3. I SO/I EC 9899:1990 Programming languages -- C.

4. ISO/IEC 8652:1995 Information Technology-Programming Languages—Ada.

5. ISO/IEC 15291:1999, Information Technology-Programming Languages-Ada Semantic Interface Specification (ASIS).

6. ISO/I EC 18009:1999, Conformity Assessment of an Ada Language Processor.

7. ISO/IEC 13816:1997 Programming Language ISLISP.

8. ISO/IEC TR 9547:1988 Test methods for programming language processors -guidelines for their development and procedures for their approval. 1993.

9. ISO/I EC TR 10034:1990 Guidelines for the preparation of conformity clauses in programming language standards. 1995.

10. NCITS technical committees, J20 Programming Language Smalltalk, working papers, http://www.ncits.org/tc home/i20sd4.htm.

11. Bancilhon F., Ferran G. ODMG-93: the object database standard. Data Engineering Bulletin, December 1994, vol. 17., N 4 .

12. R. G. Cattel The Object Database standard: ODMG 2.0 The Morgan-Kaufmann series in Database Management systems, 1997.

13. D.E.Knuth The Art of Computer Programming, Second edition. Volume 3: Sorting and Searching. Addison-Wesley, 1998. Имеется русский перевод:

14. Д.Э. Кнут. Искусство программирования, Второе издание. Том 3. Сортировка и поиск. "Вильяме", 2000.

15. A.V. Aho, R. Sethi, J.D. Ullman Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1985. Имеется русский перевод:

16. A. Ахо, P.Сети, Дж. Ульман. Компиляторы: принципы, технологии, инструменты. "Вильяме", 2001.

17. В.А. Серебряков, М.П. Галочкин Основы конструирования компиляторов. Москва, УУРС, 2000.

18. S. Rybin, A. Strohmeier, Е. Zueff ASIS for GNAT: Goals, Problems and Implementation Strategy, Ada-Europe'95 Conference, Frankfurt, Germany, October 1995.

19. S. Rybin, A. Strohmeier, E. Zueff ASIS Implementation for the GNAT Compiler, First Workshop on Free Software, Universidad Carlos III, Madrid, Spain, September 1995.

20. B.W. Kernighan, R.Pike The Practice of Programming. Addison-Wesley, 1999. Имеется русский перевод:

21. Б.Кернинган, Р. Пайк Практика программирования. СПб: Невский диалект, 2001.

22. B.W. Kernighan, R.Pike The UNIX Programming Environment. Prentice-Hall, 1984. Имеется русский перевод:

23. Б.Кернинган, Р. Пайк UNIX-универсальная среда программирования. Москва: Финансы и Статистика, 1992.

24. B.W. Kernighan, D.M. Ritchie The С Programming Language. Prentice-Hall, 1978. Имеется русский перевод:

25. Б.Кернинган, Д. Ритчи Язык программирования Си. Москва: Финансы и Статистика, 1992.

26. В. Stroustrup Adding Classes to the С Language: An Exercise in Language Evolution Software Practice and Experience, pp 139-161. February 1983.

27. Ellis M. A., Stroustrup В., The Annotated С++ Reference Manual (ARM), Reading, MA: Addison-Wesley, 1990. Имеется русский перевод: Эялис М., Строуструп Б. Справочное руководство по языку программирования С++ с комментариями: Пер. с англ.- М.: Мир, 1992.

28. В. Stroustrup What is "Object-Oriented Programming"? (1991 revised version), AT&T Bell Laboratories, Murray Hill, New Jersey 07974.http.V/www. resea rch. att. com/- bs/whatis. pdf

29. B. Stroustrup Why С++ is not just an Object-Oriented Programming Language, AT&T Bell Laboratories, Murray Hill, New Jersey 07974. Invited talk given at OOPSLA'95 in Austin Texas. http://www.research.att.com/-bs/oopsla.pdf

30. B. Stroustrup The С++ Programming Language. The third edition. Addison-Wesley, 1997. Имеется русский перевод:

31. Б. Страуструп Язык программирования Си++, М; СПб: Невский диалект, Бином, 1999.

32. В. Stroustrup The Design and Evolution of С++. Addison-Wesley, 1994. Имеется русский перевод:

33. Б. Страуструп Дизайн и эволюция языка С++. М: ДМК, 2000.

34. G. Booch Object-Oriented Design with Applications, Benjamin Cummings, 1991. Имеется русский перевод:

35. Г.Буч, Объектно-ориентированное проектирование с примерами применения М., "Конкорд", 1992.

36. G. Booch Object-Oriented Analysis and Design with Applications, Second edition, Addison-Wesley, 1994. Имеется русский перевод:

37. Г. Буч Объектно ориентированный анализ и проектирование с примерами приложений на С++, М: Бином, Невский диалект, 1998.

38. I. Pohl Object-Oriented Programming Using С++. Second edition. Имеется русский перевод:

39. А. Пол Объектно-ориентированное программирование на Си++. Второе издание М: Бином,2001.

40. G. Booch, J. Rumbaugh, I. Jacobson The Unified Modelling Language User Guide. Addison-Wesley, 1999. Имеется русский перевод:

41. Г. Буч, Д. Рамбо, А. Джекобсон UML: руководство пользователя, ДМК, 2000.

42. G. Booch, J. Rumbaugh, I. Jacobson The Unified Modelling Language Reference Manual, Addison-Wesley, 1999.

43. D. C. Schmidt, S. Huston С++ Network Programming: Mastering Complexity with ACE and Patterns, Addison-Wesley Longman, 2002.

44. D. C. Schmidt, M. Stal, H. Rohert, F. Buschmann Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, John Wiley and Sons, 2000.34.