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

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

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

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

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

Схемы СУ-перевода для полного и неполного условных операторов представлены на рис. 4.1.

Рис. 4.1. Схемы СУ-перевода для условных операторов.

Для того чтобы реализовать эти схемы, необходимы два типа триад: триада условного перехода и триада безусловного перехода.

Эти два типа триад реализуются следующим образом:

• IF(<операнд1>,<операнд2>) – триада условного перехода;

• JMP(1,<операнд2>) – триада безусловного перехода.

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

У триады JMP первый операнд не имеет значения (для определенности он всегда будет равен 1), второй операнд – всегда ссылка на другую триаду. Триада JMP всегда передает управление на триаду, указанную вторым операндом.

СУ-перевод для семантически ненагруженных конструкций

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

Тем не менее функция генерации списка триад должна обрабатывать и эти операции.

Они должны обрабатываться следующим образом:

• для вершины, у которой первая нижележащая вершина – открывающая скобка, вторая нижележащая вершина – узел дерева (не концевая вершина) и третья нижележащая вершина – закрывающая скобка, должна рекурсивно вызываться функция порождения кода для второй нижележащей вершины;

• для вершины, у которой первая нижележащая вершина – узел дерева (не концевая вершина) и вторая нижележащая вершина – точка с запятой, должна рекурсивно вызываться функция порождения кода для первой нижележащей вершины.

Пример генерации списка триад

Возьмем в качестве примера входную цепочку:

if a and b or a and b and 345 then a:= 5 or 4 and 7;

В результате лексического и синтаксического разбора этой входной цепочки будет построено дерево синтаксического разбора, приведенное на рис. 4.2.

Этому дереву будет соответствовать следующая последовательность триад:

1: and (a, b)

2: and (a, b)

3: and (^2, 345)

4: or (^1, ^3)

5: if (^4, ^9)

6: and (4, 7)

7: or (5, ^6)

8::= (a, ^7)

9:…

В этой последовательности два линейных участка: от триады 1 до триады 5 и от триады 6 до триады 9.

После оптимизации методом свертки объектного кода получим последовательность триад:

1: and (a, b)

2: and (a, b)

3: and (^2, 345)

4: or (^1, ^3)

5: if (^4, ^9)

6: C (4, 0)

7: C (5, 0)

8::= (a, 5)

9:…

Если удалить триады типа С, то эта последовательность примет следующий вид:

1: and (a, b)

2: and (a, b)

3: and (^2, 345)

4: or (^1, ^3)

5: if (^4, ^7)

6::= (a, 5)

7:…

Рис. 4.2. Дерево синтаксического разбора цепочки «if a and b or a and b and 345 then a:= 5 or 4 and 7;».

После оптимизации методом исключения лишних операций получим последовательность триад:

1: and (a, b)

2: same (^1, 0)

3: and (^1, 345)

4: or (^1, ^3)

5: if (^4, ^7)

6::= (a, 5)

7:…

Если удалить триады типа same, то эта последовательность примет следующий вид:

1: and (a, b)

2: and (^1, 345)

3: or (^1, ^2)

4: if (^3, ^6)

5::= (a, 5)

6:…

После применения оптимизации получаем последовательность из пяти триад. Это на 37,5 % меньше, чем в исходной без применения оптимизации последовательности, состоявшей из восьми триад. Следовательно, объем результирующего кода и время его выполнения в данном случае сократятся примерно на 37,5 % (слово «примерно» указано здесь потому, что разные триады могут порождать различное количество команд в результирующем коде, а потому соотношения между количеством триад и между количеством команд объектного кода могут немного различаться).

Можно еще обратить внимание на то, что алгоритм оптимизации методом исключения лишних операций не учитывает особенности выполнения логических и арифметических операций. Методами булевой алгебры последовательность операций «a and b or a and b and 345» можно преобразовать в «a and b» точно так же, как последовательность операций «a-b + a-b-345» – в «a-b-346», что было бы эффективней, чем варианты, которые строит алгоритм оптимизации методом исключения лишних операций. Но для таких преобразований нужны алгоритмы, ориентированные на особенности выполнения логических и арифметических операций [1, 2, 7].

Реализация генератора списка триад