Память для типов данных (rtti-информация)
Современные компиляторы с объектно-ориентированных языков программирования предусматривают, что результирующая программа может обрабатывать не только переменные, константы и другие структуры данных, но и информацию о типах данных, описанных в исходной программе. Эта информация получила название RTTI — Run Time Type Information — «информация о типах во время выполнения».
Состав RTTI-информации определяется семантикой входного языка и реализацией компилятора. Как правило, для каждого типа данных в объектно-ориентированном языке программирования создается уникальный идентификатор типа данных, который используется для сопоставления типов. Для него может храниться наименование типа, а также другая служебная информация, которая используется компилятором в коде результирующей программы. Вся эта информация может быть в той или иной мере доступна пользователю. Еще одна цель хранения RTTI-информации — обеспечить корректный механизм вызова виртуальных процедур и функций (так называемое «позднее связывание»), предусмотренный во всех объектно-ориентированных языках программирования [8, 34, 35, 76,71].
RTTI-информация хранится в результирующей программе в виде RTTI-таблицы. RTTI-таблица представляет собой глобальную статическую структуру данных, которая создается и заполняется в момент начала выполнения результирующей программы. Компилятор с объектно-ориентированного входного языка отвечает за порождение в результирующей программе кода, ответственного за заполнение RTTI-таблицы.
Каждому типу данных в RTTI-таблице соответствует своя область данных, в которой хранится вся необходимая информация об этом типе данных, его взаимосвязи с другими типами данных в общей иерархии типов данных программы, а также все указатели на код виртуальных процедур и функций, связанных с этим типом. Всю эту информацию и указатели размещает для каждого типа данных в RTTI-таблице код, автоматически порождаемый компилятором.
B принципе всю эту информацию можно было бы разместить непосредственно в памяти, статически или динамически отводимой для каждого экземпляра объекта (класса) того или иного типа. Ho поскольку данная информация для всех объектов одного и того же типа совпадает, то это привело бы к нерациональному использованию оперативной памяти. Поэтому компилятор размещает всю информацию по типу данных в одном месте, а каждому экземпляру объекта (класса) при выделении памяти для него добавляет только небольшой объем служебной информации, связывающей этот объект с соответствующим ему типом данных (как правило, эта служебная информация является указателем на нужную область данных в RTTI-таблице). При статическом распределении памяти под экземпляры объектов (классов) компилятор сам помещает в нее необходимую служебную информацию, при динамическом распределении — порождает код, который заполнит эту информацию во время выполнения программы (поскольку RTTI-таблица является статической областью данных, адрес ее известен и фиксирован).
Ha рис. 14.3 приведена схема, иллюстрирующая построение RTTI-таблицы и ее связь с экземплярами объектов в результирующей программе.
Компилятор всегда сам автоматически строит код, ответственный в результирующей программе за создание и заполнение RTTI-таблицы и за ее взаимосвязь с экземплярами объектов (классов) различных типов. Разработчику не надо заботиться об этом, тем более что он, как правило, не может воздействовать на служебную информацию, помещаемую компилятором в RTTI-таблицу.
Проблемы могут появиться в том случае, когда некоторая программа взаимодействует с динамически загружаемой библиотекой. При этом могут возникнуть ситуации, вызванные несоответствием типов данных в программе и библиотеке, хотя и та и другая могут быть построены на одном и том же входном языке с помощью одного и того же компилятора. Дело в том, что код инициализации программы, порождаемый компилятором, ответственен за создание и заполнение своей RTTI-таблицы, а код инициализации библиотеки, порождаемый тем же компилятором, — своей RTTI-таблицы. Если программа и динамически загружаемая библиотека работают с одними и теми же типами данных, то эти RTTI-таблицы будут полностью совпадать, но при этом они не будут одной и той же таблицей. Это уже должен учитывать разработчик программы при проверке соответствия типов данных.
Еще большие сложности могут возникнуть, если программа, построенная на основе входного объектно-ориентированного языка программирования, будет взаимодействовать с библиотекой или программой, построенной на основе другого объектно-ориентированного языка (или даже построенной на том же языке, но с помощью другого компилятора). Поскольку формат RTTI-таблиц и состав хранимой в них служебной информации не специфицированы для всех языков программирования, то они полностью зависят от используемой версии компилятора. Соответствующим образом различается и порождаемый компилятором код результирующей программы. B общем случае организовать такого рода взаимодействие между двумя фрагментами кода, порожденного двумя различными компиляторами, напрямую практически невозможно (о других возможностях такого рода взаимодействия см. в разделе «Примеры современных систем программирования», глава 15).
Генерация кода. Методы генерации кода
Общие принципы генерации кода. Синтаксически управляемый перевод
Генерация объектного кода — это перевод компилятором внутреннего представления исходной программы в цепочку символов выходного языка. Генерация объектного кода порождает результирующую объектную программу на языке ассемблера или непосредственно на машинном языке (в машинных кодах). Внутреннее представление программы может иметь любую структуру в зависимости от реализации компилятора, в то время как результирующая программа всегда представляет собой линейную последовательность команд. Поэтому генерация объектного кода (объектной программы) в любом случае должна выполнять действия, связанные с преобразованием сложных синтаксических структур в линейные цепочки.
Генерацию кода можно считать функцией, определенной на синтаксическом дереве и на информации, содержащейся в таблице идентификаторов. Поэтому генерация объектного кода выполняется после того, как выполнен синтаксический анализ программы и все необходимые действия по подготовке к генерации кода: распределено адресное пространство под функции и переменные, проверено соответствие имен и типов переменных, констант и функций в синтаксических конструкциях исходной программы и т. д. Характер отображения входной программы в последовательность команд, выполняемого генерацией, зависит от входного языка, архитектуры вычислительной системы, на которую ориентирована результирующая программа, а также от качества желаемого объектного кода.
B идеале компилятор должен выполнить синтаксический разбор всей входной программы, затем провести ее семантический анализ, после чего приступить к подготовке генерации и непосредственно генерации кода. Однако такая схема работы компилятора практически почти никогда не применяется. Дело в том, что в общем случае ни один семантический анализатор и ни один компилятор не способны проанализировать и оценить смысл всей входной программы в целом. Формальные методы анализа семантики применимы только к очень незначительной части возможных входных программ. Поэтому у компилятора нет практической возможности порождать эквивалентную выходную программу на основе всей входной программы.
Как правило, компилятор выполняет генерацию результирующего кода поэтапно, на основе законченных синтаксических конструкций входной программы. Компилятор выделяет законченную синтаксическую конструкцию из текста входной программы, порождает для нее фрагмент результирующего кода и помещает его в текст выходной программы. Затем он переходит к следующей синтаксической конструкции. Так продолжается до тех пор, пока не будет разобрана вся входная программа. B качестве анализируемых законченных синтаксических конструкций выступают операторы, блоки операторов, описания процедур и функций. Их конкретный состав зависит от входного языка и реализации компилятора.
Смысл (семантику) каждой такой синтаксической конструкции входного языка можно определить, исходя из ее типа, а тип определяется синтаксическим анализатором на основании грамматики входного языка. Примерами типов синтаксических конструкций могут служить операторы цикла, условные операторы, операторы выбора и т. д. Одни и те же типы синтаксических конструкций характерны для различных языков программирования, при этом они различаются синтаксисом (который задается грамматикой языка), но имеют схожий смысл (который определяется семантикой). B зависимости от типа синтаксической конструкции выполняется генерация кода результирующей программы, соответствующего данной синтаксической конструкции. Для семантически схожих конструкций различных входных языков программирования может порождаться типовой результирующий код.
Чтобы компилятор мог построить код результирующей программы для синтаксической конструкции входного языка, часто используется метод, называемый синтаксически управляемым переводом — СУ-переводом. СУ-перевод — это основной метод порождения кода результирующей программы на основании результатов синтаксического разбора. Для удобства понимания сути метода можно считать, что результат синтаксического разбора представлен в виде дерева синтаксического разбора (либо же дерева операций), хотя в реальных компиляторах это не всегда так.
Суть принципа СУ-перевода заключается в следующем: с каждой вершиной дерева синтаксического разбора N связывается цепочка некоторого промежуточного кода C(N). Код для вершины N строится путем сцепления (конкатенации) в фиксированном порядке последовательности кода C(N) и последовательностей кодов, связанных со всеми вершинами, являющимися прямыми потомками N. B свою очередь, для построения последовательностей кода прямых потомков вершины N потребуется найти последовательности кода для их потомков — потомков второго уровня вершины N — и т. д. Процесс перевода идет, таким образом, снизу вверх в строго установленном порядке, определяемом структурой дерева.
Для того чтобы построить СУ-перевод по заданному дереву синтаксического разбора, необходимо найти последовательность кода для корня дерева. Поэтому для каждой вершины дерева порождаемую цепочку кода надо выбирать таким образом, чтобы код, приписываемый корню дерева, оказался искомым кодом для всего оператора, представленного этим деревом. B общем случае необходимо иметь единообразную интерпретацию кода C(N), которая бы встречалась во всех ситуациях, где присутствует вершина N. B принципе эта задача может оказаться нетривиальной, так как требует оценки смысла (семантики) каждой вершины дерева. При применении СУ-перевода задача интерпретации кода для каждой вершины дерева решается только разработчиком компилятора.
Возможна модель компилятора, в которой синтаксический анализ входной программы и генерация кода результирующей программы объединены в одну фазу. Такую модель можно представить в виде компилятора, у которого операции генерации кода совмещены с операциями выполнения синтаксического разбора. Для описания компиляторов такого типа часто используется термин «СУ-ком-пиляция» (синтаксически управляемая компиляция).
Схему СУ-компиляции можно реализовать не для всякого входного языка программирования. Если принцип СУ-перевода применим ко всем входным КС-языкам, то применить СУ-компиляцию оказывается не всегда возможным. Однако известно, что схемы перевода на основе СУ-компиляции можно построить для многих из широко распространенных классов КС-языков, в частности для LR- и LL-языков [6, 15].
B процессе СУ-перевода и СУ-компиляции не только вырабатываются цепочки текста выходного языка, но и совершаются некоторые дополнительные действия, выполняемые самим компилятором. B общем случае схемы СУ-перевода могут предусматривать выполнение следующих действий:
--- помещение в выходной поток данных машинных кодов или команд ассемблера, представляющих собой результат работы (выход) компилятора;
--- выдача пользователю сообщений об обнаруженных ошибках и предупреждениях (которые должны помещаться в выходной поток, отличный от потока, используемого для команд результирующей программы);
--- порождение и выполнение команд, указывающих, что некоторые действия должны быть произведены самим компилятором (например, операции, выполняемые над данными, размещенными в таблице идентификаторов).
Ниже рассмотрены основные технические вопросы, позволяющие реализовать схемы СУ-перевода и СУ-компиляции. Ho прежде чем рассматривать их, необходимо разобраться со способами внутреннего представления программы в компиляторе. От того, как исходная программа представляется внутри компилятора, во многом зависят методы, используемые для обработки команд этой программы.