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

Московский Государственный Университет им. М.В.Ломоносова Факультет Вычислительной математики и кибернетики

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

ЗУЕВ ЕВГЕНИЙ АЛЕКСАНДРОВИЧ

Принципы и методы создания компилятора переднего плана Стандарта Си++

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Диссертация

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

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

Доктор технических наук, профессор Сухомлин Владимир Александрович

Москва 1999

Оглавление

Введение 4

Стандартизация ЯП 4

Процесс стандартизации Ада и Си++ 6

Новый взгляд на задачу компиляции 10

Современные подходы к архитектуре СП 16

Язык Си++ и компилятор переднего плана Си++ 25

Цели и задачи диссертационной работы 28

Результаты, апробация и новизна работы 29

Глава 1. Фазы компиляции и организация лексического разбора 31

1.1. Фазы компиляции. Различные формы реализации фаз 31

1.2. Предварительная обработка исходного текста: фазы 1-2 34

1.3. Особенности препроцессорной обработки: фазы 3-4 37

1.4. Завершение лексического разбора. Концепция непрерывной компиляции 39

1.5. Лексическая структура Си++ 43

1.5.1. Подход к определению базового множества лексем 44

1.5.2. Классификация лексем базового множества 47

1.5.3. Модификация базового множества. Суперлексемы 47

1.5.4. Агрегация 48

1.5.5. Сепарация 52

1.5.6. Динамическое расширение 55 Заключение. Выводы главы 1 55

Глава 2. Синтаксический анализ языка Си++ 58

2.1. Введение. Общая структура компилятора 58

2.2. Интерфейс фазы синтаксического анализа

и требования к его реализации 60

2.3. Основной принцип реализации синтаксического анализатора 62

2.4 Операция динамического расширения и механизм состояний 68

2.5 Разбор выражений языка Си++ 71

Выводы главы 2 76

Глава 3. Управление контекстом компиляции и структура

семантических таблиц 77

3.1. Правила видимости имен в языке Си 77

3.2. Правила видимости в Си++ 78

3.2.1. Единое пространство имен 79

3.2.2. Область действия объявления класса 81

3.2.3. Лексическая вложенность и отношения областей действия 82

3.2.4. Механизм наследования 84

3.2.5. Особенности вложенных и локальных классов 85

3.2.6. Дружественные функции 86

3.2.7. Пространства имен 87

3.3. Проблемы и требования 90

3.4. Традиционная организация семантических таблиц 91

3.5. Модель организации семантических таблиц для Си++ 94

3.6. Обсуждение, замечания и примеры 101

3.7. Модельные операции управления контекстом 107 Заключение. Выводы главы 3 120

Глава 4. Механизм шаблонов и модель компиляции для Си++ 122

4.1. Типовая параметризация структур данных и алгоритмов 122

4.2. Основные требования к реализации шаблонов 125

4.3. Модель семантических таблиц и механизм шаблонов 127

4.4. Представление параметров шаблона 128

4.5. Семантические отношения для механизма шаблонов 132

4.5.1. Отношение настройки 132

4.5.2. Отношение специализации 136

4.6. Модельные операции для механизма шаблонов 139

4.7. Модель программы Си++:

раздельная компиляция или модульность 141

4.8. Раздельная компиляция и механизм шаблонов 143

4.9. Поддержка механизма шаблонов на уровне системы программирования 146

4.10. Семантические таблицы и продвинутая модель компиляции 150

4.11. Концепция непрерывной компиляции 156

4.12. Расширенное множество операций модели семантических таблиц 158

Выводы главы 4 161

Заключение 163

Литература 166

Введение

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

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

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

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

Рассмотрим эти направления подробнее.

Стандартизация ЯП

За последние пять лет в области языков программирования сложилась явная тенденция, которую можно охарактеризовать как процесс приведения распространенных ЯП промышленного назначения к унифицированным и международно признанным формам. Эта тенденция проявилась в активности международной организации (ISO - International Standard Organization) и авторитетных национальных институтов (прежде всего, ANSI - American National Standard Institute), воплотившейся в успешной стандартизации нескольких крупных ЯП. Ряд других ЯП находятся в настоящее время на различных стадиях процесса стандартизации.

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

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

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

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

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

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

Годы, предшествовавшие последнему пятилетию, дали несколько примеров стандартизации, заслуживающих упоминания в контексте позднейшей тенденции. Наряду с выдающимся успехом, связанным с созданием и стандартизацией языка Ада [1], следует отметить

относительную неудачу стандартизации языков Pascal [7] и Modula-2 [9]. Так, по общему мнению язык Паскаль был стандартизован до того, как были осознаны требования к этому языку как к инструменту практического программирования. В результате в стандарт не вошли некоторые важные черты (в частности, модульность и гибкие средства работы с массивами), предложенные позднее и зарекомендовавшие себя с положительной стороны. Язык, определенный стандартом, получился недостаточно мощным и развитым и оказался практически непригоден для промышленного использования. Это привело к существенному обесценению принятого стандарта и не послужило преградой появлению многочисленных диалектов и расширений, например Pascal фирмы Borland, объектно-ориентированные версии языка (входной язык системы Delphi, Pascal Plus [89], Pascal++ [90]) и т.п. Этими причинами было вызвано принятие уже через год нового стандарта расширенного Паскаля [13], которое в целом не изменило ситуацию к лучшему.

Следующий этап этого процесса, начало которого можно условно датировать серединой 90-х гг., знаменует собой успешное завершение ряда крупных проектов, среди которых можно упомянуть стандартизацию новой редакции языка Ада [2] (далее - Ада95), языка LISP [10] и языка Си++ [11]. Завершается стандартизация новой редакции языка Си [12], начался процесс стандартизации языка Java [99].

Из упомянутых выше проектов наиболее интересно проследить историю возникновения, развитие и стандартизацию таких мощных и развитых общецелевых языков программирования, как Ада и Си++.

Процесс стандартизации Ада и Си++

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

Что касается Ада95, то это в настоящее время практически единственный универсальный язык программирования, сравнимый с Си++ как по широте возможностей, общецелевому характеру предполагаемого применения, так и по достаточно полному и строгому концептуальному базису. Си++ и Ada95 являются наиболее развитыми современными проектами языков программирования с объектно-ориентированной парадигмой.

Оба этих языка возникли не на пустом месте. Их основой являются, соответственно, язык Си и предыдущая (1983 года) редакция языка Ада (далее - Ада83), хорошо зарекомендовавшие себя в практическим

программировании. Как уже говорилось, оба языка-предшественника были стандартизованы как ANSI, так и ISO [14], [1]; стандарт языка Ада95 принят в 1995 году, стандарт Си++ - в 1998 г.

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

Вместе с тем, характер проектирования и история развития этих языков существенно различны. Язык Си - предшественник Си++ -первоначально был создан как инструмент разработки новой операционной системы UNIX и предназначался для использования коллективом разработчиков в качестве системного языка реализации среднего уровня как альтернатива устаревшим к тому времени языкам типа BCPL [91]. Ничуть не умаляя достоинств Си, можно утверждать, что своим успехам он в значительной степени обязан выдающемуся успеху ОС UNIX. Стандартизация Си в 1989 году, скорее, была призвана зафиксировать сложившийся образ языка и остановить его "расползание" в виде многочисленных диалектов и фирменных расширений.

Язык Ада83, напротив, изначально проектировался как стандартный инструмент реализации широкого класса программных систем, причем конкретный вид языка определялся в ходе систематического процесса проектирования, начиная от выверенной концептуальной базы и совокупности исходных требований [71] до структуры языка и синтаксиса и семантики его конкретных конструкций.

Аналогичная ситуация сложилась с созданием Си++ и Ада95. Си++ возник в той же организации, что и Си и по существу в том же коллективе разработчиков. Первоначально язык представлял собой попытку просто расширить Си понятиями объектно-ориентированного прграммирования, как они сложились к началу 80-х годов. Название языка - "Си с классами" [44] - в точности отражало вполне скромные намерения авторов, что подтверждает и препроцессорная схема его реализации, предложенная в той же статье.

Последующие этапы развития языка [118], которые можно проследить по работам [47], [45], [114], а также начавшийся в 1990 году процесс его стандартизации [16-17], наглядно иллюстрируют хаотический и спонтанный характер превращения "Си с классами" в полноценный объектно-ориентированный язык общего назначения, в котором его создатели сремятся, с одной стороны, преодолеть ряд известных недостатков языка Си [77-79], сохранив в то же время совместимость с ним, с другой стороны, обеспечить приемлемую степень надежности, достаточную для использования Си++ в ответственных проектах, и, наконец, реализовать в языке как можно больше концепций и возможностей, возникших и утвердившихся в программировании к настоящму моменту. В результате типичной

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

Несмотря на то, что процесс стандартизации языка начался еще в 1990 году, срок завершения этого процесса неоднократно переносился. В результате Международный Стандарт был принят только в 1998 году, более чем с четырехлетним опозданием. Чрезмерно затянутая процедура формирования и принятия Стандарта привела к тому, что язык вступил в конфликт со своими реализациями: за это время появилось значительное число компиляторов Си++ промышленного уровня, содержащих собственные интерпретации многочисленных непроясненных Стандартом мест языка. В результате окончательная версия Стандарта содержит большое число компромиссов между решениями различных фирм-производителей компиляторов, а также между рабочей группой WG21 ANSI/ISO и разработчиками компиляторов. Примером может служить использование настроек шаблонов в многомодульных программах (проблема раздельной компиляции шаблонов), описанная в разд. 4.8.

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

В противоположнос�