Всего за 133 руб. Купить полную версию
Процедура генерации триад по синтаксическому дереву прежде всего должна определить тип узла дерева. Для бинарных арифметических операций каждый узел дерева имеет три нижележащие вершины (левая вершина – первый операнд, средняя вершина – операция и правая вершина – второй операнд). При этом тип узла дерева соответствует типу операции, символом которой помечена средняя из нижележащих вершин. После определения типа узла процедура строит триады для узла дерева в соответствии с типом операции.
Фактически процедура генерации триад должна для каждого узла дерева выполнить конкатенацию триады, связанной с текущим узлом, и цепочек триад, связанных с нижележащими узлами. Конкатенация цепочек триад должна выполняться таким образом, чтобы триады, связанные с нижележащими узлами, выполнялись до выполнения операции, связанной с текущим узлом. Причем для арифметических операций важно, чтобы триады, связанные с первым операндом, выполнялись раньше, чем триады, связанные со вторым операндом (так как все арифметические операции при отсутствии скобок и приоритетов выполняются в порядке слева направо).
При этом возможны четыре ситуации:
• левая и правая вершины указывают на непосредственный операнд (это можно определить, если у каждой из них есть только один нижележащий узел, помеченный символом какой-то лексемы – константы или идентификатора);
• левая вершина является непосредственным операндом, а правая указывает на другую операцию;
• левая вершина указывает на другую операцию, а правая является непосредственным операндом;
• обе вершины указывают на другую операцию.
Считаем, что на вход процедуры порождения триад по синтаксическому дереву подается список, в который нужно добавлять триады, и ссылка на узел дерева, который надо обработать. Тогда процедура порождения триад для узла синтаксического дерева, связанного с бинарной арифметической операцией, может выполняться по следующему алгоритму:
1. Проверяется тип левой вершины узла. Если она – простой операнд, запоминается имя первого операнда, иначе для этой вершины рекурсивно вызывается процедура порождения триад, построенные ею триады добавляются в конец общего списка и запоминается номер последней триады из этого списка как первый операнд.
2. Проверяется тип правой вершины узла. Если она – простой операнд, запоминается имя второго операнда, иначе для этой вершины рекурсивно вызывается процедура порождения триад, построенные ею триады добавляются в конец общего списка и запоминается номер последней триады как второй операнд.
3. В соответствии с типом средней вершины в конец общего списка добавляется триада, соответствующая арифметической операции. Ее первым операндом становится операнд, запомненный на шаге 1, а вторым операндом – операнд, запомненный на шаге 2.
4. Процедура закончена.
Процедуры такого рода должен создавать разработчик компилятора, так как только он может сопоставить по смыслу узлы синтаксического дерева и соответствующие им последовательности триад. Для разных типов узлов синтаксического дерева могут быть построены разные варианты процедур, которые будут вызывать друг друга в зависимости от принятого порядка обхода синтаксического дерева (в описанном выше варианте – рекурсивно).
В рассмотренном примере при порождении кода преднамеренно не были приняты во внимание многие вопросы, возникающие при построении реальных компиляторов. Это было сделано для упрощения примера. Например, фрагменты кода, соответствующие различным узлам дерева, принимают во внимание тип операции, но никак не учитывают тип операндов. Все эти требования ведут к тому, что в реальном компиляторе при генерации кода надо принимать во внимание очень многие особенности, зависящие от семантики входного языка и от используемой формы внутреннего представления программы. В данной лабораторной работе эти вопросы не рассматриваются.
Кроме того, в случае арифметических операций код, порождаемый для узлов синтаксического дерева, зависит только от типа операции, то есть только от текущего узла дерева. Такие схемы можно построить для многих операций, но не для всех. Иногда код, порождаемый для узла дерева, может зависеть от типа вышестоящего узла: например, код, порождаемый для операторов типа Break и Continue (которые есть в языках C, C++ и Object Pascal), зависит от того, внутри какого цикла они находятся. Тогда при рекурсивном построении кода по дереву вышестоящий узел, вызывая функцию для нижестоящего узла, должен передать ей необходимые параметры. Но код, порождаемый для вышестоящего узла, никогда не должен зависеть от нижестоящих узлов, в противном случае принцип СУ-перевода неприменим.
Далее в примере выполнения работы даются варианты схем СУ-перевода для различных конструкций входного языка, которые могут служить хорошей иллюстрацией механизма применения этого метода.
Общие принципы оптимизации кода
Как уже говорилось, в подавляющем большинстве случаев генерация кода выполняется компилятором не для всей исходной программы в целом, а последовательно для отдельных ее конструкций. Для построения результирующего кода различных синтаксических конструкций входного языка используется метод СУ-перевода. Он объединяет цепочки построенного кода по структуре дерева без учета их взаимосвязей.
Построенный таким образом код результирующей программы может содержать лишние команды и данные. Это снижает эффективность выполнения результирующей программы. В принципе, компилятор может завершить на этом генерацию кода, поскольку результирующая программа построена и является эквивалентной по смыслу (семантике) программе на входном языке. Однако эффективность результирующей программы важна для ее разработчика, поэтому большинство современных компиляторов выполняют еще один этап компиляции – оптимизацию результирующей программы (или просто "оптимизацию"), чтобы повысить ее эффективность, насколько это возможно.
Важно отметить два момента: во-первых, выделение оптимизации в отдельный этап генерации кода – это вынужденный шаг. Компилятор вынужден производить оптимизацию построенного кода, поскольку он не может выполнить семантический анализ всей входной программы в целом, оценить ее смысл и исходя из него построить результирующую программу. Во-вторых, оптимизация – это необязательный этап компиляции. Компилятор может вообще не выполнять оптимизацию, и при этом результирующая программа будет правильной, а сам компилятор будет полностью выполнять свои функции. Однако практически все современные компиляторы так или иначе выполняют оптимизацию, поскольку их разработчики стремятся завоевать хорошие позиции на рынке средств разработки программного обеспечения.
Теперь дадим определение понятию "оптимизация".
Оптимизация программы – это обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эффективной результирующей объектной программы. Оптимизация выполняется на этапах подготовки к генерации и непосредственно при генерации объектного кода.
В качестве показателей эффективности результирующей программы можно использовать два критерия: объем памяти, необходимый для выполнения результирующей программы, и скорость выполнения (быстродействие) программы. Далеко не всегда удается выполнить оптимизацию так, чтобы она удовлетворяла обоим этим критериям. Зачастую сокращение необходимого программе объема данных ведет к уменьшению ее быстродействия, и наоборот. Поэтому для оптимизации обычно выбирается один из упомянутых критериев. Выбор критерия оптимизации обычно выполняется в настройках компилятора.
Но даже выбрав критерий оптимизации, в общем случае практически невозможно построить код результирующей программы, который бы являлся самым коротким или самым быстрым кодом, соответствующим входной программе. Дело в том, что нет алгоритмического способа нахождения самой короткой или самой быстрой результирующей программы, эквивалентной заданной исходной программе. Эта задача в принципе неразрешима. Существуют алгоритмы, которые можно ускорять сколь угодно много раз для большого числа возможных входных данных, и при этом для других наборов входных данных они окажутся неоптимальными [1, 2]. К тому же компилятор обладает весьма ограниченными средствами анализа семантики всей входной программы в целом. Все, что можно сделать на этапе оптимизации, – это выполнить над заданной программой последовательность преобразований в надежде сделать ее более эффективной.
Чтобы оценить эффективность результирующей программы, полученной с помощью того или иного компилятора, часто прибегают к сравнению ее с эквивалентной программой (программой, реализующей тот же алгоритм), полученной из исходной программы, написанной на языке ассемблера. Лучшие оптимизирующие компиляторы могут получать результирующие объектные программы из сложных исходных программ, написанных на языках высокого уровня, почти не уступающие по качеству программам на языке ассемблера. Обычно соотношение эффективности программ, построенных с помощью компиляторов с языков высокого уровня, и программ, построенных с помощью ассемблера, составляет 1,1–1,3. То есть объектная программа, построенная с помощью компилятора с языка высокого уровня, обычно содержит на 10–30 % больше команд, чем эквивалентная ей объектная программа, построенная с помощью ассемблера, а также выполняется на 10–30 % медленнее.