Всего за 133 руб. Купить полную версию
Пример генерации списка триад
Возьмем в качестве примера входную цепочку:
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 с – обеспечивает вычисление значений для триад разных типов при свертке объектного кода.
Такое разбиение на модули позволяет использовать те же самые структуры данных для организации нового генератора списка триад при изменении входного языка.
Кроме этих модулей для реализации лабораторной работы № 4 используются следующие программные модули:
• TblElem и FncTree – позволяют работать с комбинированной таблицей идентификаторов (созданы при выполнении лабораторной работы № 1);
• LexType, LexElem, и LexAuto – обеспечивают работу лексического распознавателя (созданы при выполнении лабораторной работы № 2);
• SyntRule и SyntSymb – обеспечивают работу синтаксического распознавателя (созданы при выполнении лабораторной работы № 3).
Кратко опишем содержание программных модулей, используемых для организации генератора списка триад.
Модуль описания допустимых типов триад
Модуль TrdType содержит структуры данных, которые описывают допустимые типы триад.
Он содержит следующие важные типы данных и переменные:
• TTriadType – перечисление всех возможных типов триад;
• TriadStr – массив строковых обозначений для всех типов триад;
• TriaD1ineSet – множество тех триад, которые являются линейными операциями (оно важно для оптимизации и для порождения кода).
Модуль описания структур данных для триад
Модуль Triads содержит структуры данных, которые описывают триады и список триад. Эти структуры зависят от реализации компилятора, но не зависят от входного языка.
Он содержит следующие важные структуры данных:
• TOperand – описывает операнд триады;
• TTriad – описывает триаду и все связанные с нею данные;
• TTriaD1ist – описывает список триад.
Структура TOperand описывает операнд триады. Она содержит следующие данные:
• ОрТуре – тип операнда, который может принимать три значения:
– OPC0NST – константа;
– OPVAR – переменная (идентификатор);
– OPLINK – ссылка на другую триаду;
• и дополнительную информацию по операнду:
– ConstVal – значение (для константы);
– VarLink – ссылка на таблицу идентификаторов (для переменной);
– TriadNum – номер триады (для ссылки на триаду).
Один из вопросов, который необходимо было решить при реализации операндов триад, состоял в следующем: что использовать для описания ссылки на триаду – непосредственно ссылку на тип данных (указатель) или номер триады в списке?
Оба варианта имеют свои преимущества и недостатки:
• при использовании указателя легче осуществлять доступ к триаде (не надо выбирать ее из списка), не надо менять указатели при перемещении триад в списке, но при удалении любой триады из списка нужно корректно менять все указатели на эту триаду, какие только есть;
• при использовании номера триады легче порождать список триад по дереву разбора, но при любом перемещении и удалении триад из списка нужно пересчитывать все номера.
Какой вариант выбрать, решает разработчик компилятора. В данном случае автор выбрал второй вариант (номер триады, а не указатель на нее), поскольку наглядная иллюстрация алгоритмов оптимизации требует удаления триад, а перестановка указателей при каждом удалении намного сложнее, чем изменение номеров (этот недостаток оказался решающим). Но поскольку в реальном компиляторе не нужно иллюстрировать работу алгоритмов оптимизации выводом списка триад (достаточно просто не порождать код для триад с типами С и same), в этом случае указатели, по мнению автора, были бы предпочтительнее.
Структура TTriad описывает триаду и все связанные с ней данные. Она содержит следующие поля данных:
• TriadType – тип триады (один из перечисленных в типе TTriadType в модуле TrdType);
• Operands – массив операндов триады (из двух операндов типа TOperand);
• Info – дополнительная информация о триаде для алгоритмов оптимизации;
• IsLinked – флаг, сигнализирующий о том, что на триаду имеется ссылка из другой триады, обеспечивающей передачу управления (типа IF или JMP).
Для хранения дополнительной информации можно было использовать один из двух подходов: хранить ее непосредственно в самой триаде или хранить внутри триады только ссылку (указатель), а саму дополнительную информацию размещать во внешней структуре данных.
Этот вопрос уже возникал при выборе метода хранения информации при организации таблиц идентификаторов в лабораторной работе № 1. Тогда было отдано предпочтение второму варианту, поскольку характер и размер хранимой информации для каждого идентификатора был неизвестен.
В данном случае известно, что для каждой триады потребуется хранить информацию, обрабатываемую двумя алгоритмами оптимизации – алгоритмом свертки объектного кода и алгоритмом исключения лишних операций. Оба эти алгоритма работают со значениями, которые могут принимать триады – для заданного входного языка это целые десятичные числа. Для их хранения достаточно одного целочисленного поля (два алгоритма никогда не выполняются одновременно, а потому могут использовать одно и то же поле данных). Поэтому тут выбран первый вариант и хранимая информация включена непосредственно в структуру данных триады в виде поля Info.
Флаг наличия ссылки важен для определения границ линейных участков программы при оптимизации: если на какую-то триаду есть ссылка из триад типа IF или JMP, значит, на нее может быть передано управление. Такая триада является возможной точкой входа участка программы, а потому – границей линейного участка.
Кроме перечисленных данных структура TTriad содержит следующие процедуры и функции:
• конструктор Create для создания триады;