Книга: Системное программное обеспечение. Лабораторный практикум
Пример генерации списка триад
Пример генерации списка триад
Возьмем в качестве примера входную цепочку:
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].
- Пример установочного скрипта
- Пример из практики
- ПРИМЕР ПРОСТОЙ ПРОГРАММЫ НА ЯЗЫКЕ СИ
- Примеры получения статистики
- Пример применения метода «пять почему»
- Пример 12-8. Частота встречаемости отдельных слов
- 1.2.5. Пример программы
- Пример 17-10. Блочный комментарий
- Примеры
- 2. Пример создания базового отношения в записи на псевдокоде
- Пример 9-8. Содержимое $* и $@, когда переменная $IFS -- пуста
- Создание списка