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

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

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

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

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

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

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].

Так же, как и для лабораторных работ № 2 и 3, модули, реализующие генератор списка триад, в лабораторной работе № 4 разделены на две группы:

• модули, программный код которых не зависит от входного языка;

• модули, программный код которых зависит от входного языка.

В первую группу входят модули:

• Triads – описывает структуры данных для представления триад;

• TrdOpt – реализует два алгоритма оптимизации: методом свертки объектного кода и методом исключения лишних операций;

• FormLab4 – описывает интерфейс с пользователем.

Во вторую группу входят модули:

• TrdType – описывает допустимые типы триад и их текстовое представление;

• TrdMake – строит список триад на основе дерева синтаксического разбора;

• TrdCal с – обеспечивает вычисление значений для триад разных типов при свертке объектного кода.

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