Генерация промежуточного представления

Промежуточная форма (тетрады, триады, постфиксная запись и др.)

СУ-трансляция

Синтез

Анализ и

локализация

ошибок

Оптимизация

Промежуточная форма

(ориентированный граф)

+

таблицы символов

Потоковый анализ

Генерация кода

Таблицы решений,

динамическое

программирование

Объектный модуль

Рис. 1.1. Структурная схема компилятора

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

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

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

Фазы функционирования компиляторов тесно связаны с такими понятиями, как семантика, синтаксис и лексика языка, поэтому представляется необходимым коротко остановиться на этих понятиях.

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

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

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

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

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

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

Рассмотрим кратко сущность, назначение и взаимосвязь основных фаз процесса компиляции.

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

Синтаксический анализ (синтаксический разбор) – это главная фаза этапа анализа. Основная задача синтаксического анализа – синтаксический разбор структуры программы. На этой фазе происходит выделение синтаксических конструкций в тексте исходной программы, обработанном лексическим анализатором; устанавливается тип и проверяется правильность каждой выделенной конструкции; кроме того, синтаксические конструкции представляются в виде, удобном для дальнейшей генерации объектного кода. Результатом синтаксического анализа является синтаксическое дерево (дерево разбора) со ссылками на таблицы символов. Основой для построения синтаксических анализаторов является формализм контекстно-свободных грамматик (КС-грамматик).

Семантический (контекстный) анализ – это такая фаза работы компилятора, на которой проверяется семантическая правильность исходной программы. Это в основном связи «описание-использование», в частности, анализ типов объектов, анализ областей видимости, соответствие типов и количества формальных и фактических параметров подпрограмм, правильность использования меток и прочее. В процессе синтаксического анализа таблицы лексем и идентификаторов пополняются информацией об описаниях (свойствах) объектов. На фазе семантического анализа могут быть выявлены ошибки, связанные с неправильным использованием объектов (лексем). Кроме этого, на данной фазе осуществляются некоторые преобразования текста программы, обусловленные семантикой входного языка (например, добавление функций неявного преобразования типов). Основным формализмом, использующимся при семантическом анализе, является аппарат атрибутных грамматик. Результатом семантического анализа является атрибутированное дерево программы. В зависимости от реализации, семантический анализ может представлять собой как самостоятельную фазу процесса компиляции, так и частично осуществляться на предыдущей и последующей фазах.

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

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

Наконец, генерация кода – последняя фаза компиляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различные синтаксические методы.

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

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

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

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

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

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

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

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