Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

2. Порождается блок кода № 2 для второго операнда. Для этого рекурсивно вызывается функция порождения кода для третьей нижележащей вершины, в качестве первого аргумента ей передается адрес А 1, а в качестве второго аргумента – адрес А 2.

Схема СУ-перевода для операции NOT будет выглядеть следующим образом:

Порождается блок кода для единственного операнда. Для этого рекурсивно вызывается функция порождения кода, в качестве первого аргумента ей передается адрес А 2, а в качестве второго аргумента – адрес А 1(аргументы меняются местами).

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

Такой подход потребует изменить схемы СУ-перевода для условных операторов и для оператора цикла.

Для условных операторов генерация кода может выполняться в следующем порядке:

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

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

3. Для полного условного оператора порождается команда безусловного перехода в конец оператора.

4. Для полного условного оператора порождается блок кода № 3, соответствующий операциям после лексемы else (пятая нижележащая вершина) – для этого должна быть рекурсивно вызвана функция порождения кода для шестой нижележащей вершины (оба аргумента нулевые).

Генерация кода для цикла с предусловием выполняется в следующем порядке:

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

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

3. Порождается команда безусловного перехода в начало блока кода № 1.

Современные компиляторы порождают различный код для логических операций:

• для побитовых операций порождается код как для линейных операций;

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

Например, в языке Object Pascal код, порождаемый для операций and, or, xor и not, зависит от типов операндов (являются ли они логическими или целочисленными), а в языках C и C++ логические и побитовые операции даже обозначаются разными знаками операций. При этом в современных компиляторах существует команда, позволяющая разработчику отключить порождение «сокращенного» кода (обычно она называется «Complete Boolean evaluations») – тогда для всех логических выражений порождается полный линейный код.

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

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

Совет.

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

Генерация кода для сокращенного вычисления логических выражений подробно рассмотрена в [2].

Все возможные типы триад перечислены в модуле TrdType (листинг П3.8, приложение 3).

Структуры данных, использованные в лабораторной работе № 4, не зависят от входного языка. Поэтому имеет смысл использовать их для генерации триад в курсовой работе. Эти структуры данных описаны в модуле Triads (листинг П3.10, приложение 3).

Генератор триад также реализован на базе модуля, который был использован для генерации триад в лабораторной работе № 4. В данный модуль были внесены изменения в соответствии с изменившимся синтаксисом входного языка, добавлены новые линейные операции (арифметические операции и операции сравнения), а также добавлена реализация схемы СУ-перевода для оператора цикла (которая была представлена на рис. 5.2).

Для проверки заданных семантических ограничений в генератор триад добавлены следующие проверки:

• при определении имени операнда любой линейной операции проверяется, что имя не совпадает с недопустимым именем «Result»;

• при определении имени операнда операции присваивания проверяется, что имя не совпадает с недопустимыми именами «InpVar» и «Result».

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