Способы внутреннего представления программ

Вопросы

Контрольныевопросыизадачи

1. Дайте определение цепочки, языка. Какие операции можно выполнять над
цепочками символов? Что такое синтаксис и семантика языка?

2. Какие лз перечисленных ниже тождеств являются истинными для двух про­
извольных цепочек символов аир, а какие нет?

|сф| = |а| + |р| - И

ар = р_а

|a^R| = |а|

(a²p²)^R = (p^Ra^R)²

(a²p²)^R - (p^R)²(a^R)²

3. Какие существуют методы задания языков? Почему метод перечисления всех
допустимых цепочек языка не находит практического применения?

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

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

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

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

Известны следующие формы внутреннего представления программ¹:

□ связочные списочные структуры, представляющие синтаксические деревья;

□ многоадресный код с явно именуемым результатом (тетрады);

□ многоадресный код с неявно именуемым результатом (триады);

□ обратная (постфиксная) польская запись операций;
Q ассемблерный код или машинные команды.

В каждом конкретном компиляторе может использоваться одна из этих форм, выбранная разработчиками. Но чаще всего компилятор не ограничивается ис-

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

I ЛсШс! 1Ч-- l

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

Некоторые компиляторы, незначительно оптимизирующие результирующий код, генерируют объектный код по мере разбора исходной программы. В этом случае применяется схема СУ-компиляции, когда фазы синтаксического разбора, семан­тического анализа, подготовки и генерации объектного кода совмещены в одном проходе компилятора. Тогда внутреннее представление программы существует только условно в виде последовательности шагов алгоритма разбора. В любом случае компилятор всегда будет работать с представлением программы в форме машинных команд — иначе он не сможет построить результирующую программу. Далее все перечисленные формы представления рассматриваются более подробно.

Синтаксические деревья

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

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

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

Многоадресный код с явно именуемым результатом (тетрады)

Тетрады представляют собой запись операций в форме из четырех составляю­щих: операция, два операнда и результат операции. Например, тетрады могут выглядеть так: <операция>(<операнд1>,<операнд2>,<результат>). Тетрады представляют собой линейную последовательность команд. При вычис­лении выражения, записанного в форме тетрад, они вычисляются одна за другой последовательно. Каждая тетрада в последовательности вычисляется так: опера­ция, заданная тетрадой, выполняется над операндами и результат ее выполнения помещается в переменную, заданную результатом тетрады. Если какой-то из операндов (или оба операнда) в тетраде отсутствует (например, если тетрада представляет собой унарную операцию), то он может быть опущен или заменен пустым операндом (в зависимости от принятой формы записи и ее реализации).

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

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

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

Например, выражение A:=B*C+D-B*10, записанное в виде тетрад, будет иметь вид:

1. * (В, С, Т1)

2. + (T1,D, T2)

3. * (В, 10,ТЗ)

4. - (Т2.ТЗ.Т4)

5.:= (Т4.0, А)

Здесь все операции обозначены соответствующими знаками (при этом присвое­
ние также является операцией). Идентификаторы Т1............. Т4 обозначают времен­
ные переменные, используемые для хранения результатов вычисления тетрад.
Следует обратить внимание, что в последней тетраде (присвоение), которая тре­
бует только одного операнда, в качестве второго операнда выступает незначащий
операнд «0».

Многоадресный код с неявно именуемым результатом (триады)

Триады представляют собой запись операций в форме из трех составляющих: операция и два операнда. Например, триады могут иметь вид: <операция>(<операнд1>, <операнд2>). Особенностью триад является то, что один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно нумеруют для удобства указания ссылок одних триад на другие (в реализации компилятора в качестве ссылок можно использовать не но­мера триад, а непосредственно ссылки в виде указателей — тогда при изменении нумерации и порядка следования триад менять ссылки не требуется).

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

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

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

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

Например, выражение A:=B*C+D-B*10, записанное в виде триад, будет иметь вид:

Дата добавления: 2015-06-27