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

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

Совет.

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

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

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

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

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

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

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

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

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

Текст полученного программного модуля TrdMake приведен в листинге П3.12, приложение 3.

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

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

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

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

Например, последовательности операторов:

d:= a + b + c;

с:= d *(a + b);

a:= d *(a + b) + 1;

будет соответствовать последовательность триад:

1: + (a, b)

2: + (^1, c)

3::= (d, ^2)

4: * (d, ^1)

5::= (с, ^4)

6: + (^4, 1)

7::= (a, ^6)

Область действия для каждой триады в этой последовательности показана на рис. 5.3.