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

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

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

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

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

Оглавление книги