Всего за 133 руб. Купить полную версию
2. Изучить алгоритм генерации объектного кода по дереву синтаксического разбора.
3. Разработать схемы СУ-перевода для операций исходного языка в соответствии с заданной грамматикой.
4. Выполнить генерацию последовательности триад вручную для выбранного простейшего примера. Проверить корректность результата.
5. Изучить и реализовать (если требуется) для заданного входного языка алгоритмы оптимизации результирующего кода методом свертки и методом исключения лишних операций.
6. Разработать алгоритм преобразования последовательности триад в заданный объектный код (по согласованию с преподавателем).
7. Подготовить и защитить отчет.
8. Написать и отладить программу на ЭВМ.
9. Сдать работающую программу преподавателю.
Требования к оформлению отчета
Отчет должен содержать следующие разделы:
• Задание по лабораторной работе.
• Краткое изложение цели работы.
• Запись заданной грамматики входного языка в форме Бэкуса-Наура.
• Описание схем СУ-перевода для операций исходного языка в соответствии с заданной грамматикой.
• Пример генерации и оптимизации последовательности триад на основе простейшей исходной программы.
• Текст программы (оформляется после выполнения программы на ЭВМ).
Основные контрольные вопросы
• Что такое транслятор, компилятор и интерпретатор? Расскажите об общей структуре компилятора.
• Как строится дерево вывода (синтаксического разбора)? Какие исходные данные необходимы для его построения?
• Какую роль выполняет генерация объектного кода? Какие данные необходимы компилятору для генерации объектного кода? Какие действия выполняет компилятор перед генерацией?
• Объясните, почему генерация объектного кода выполняется компилятором по отдельным синтаксическим конструкциям, а не для всей исходной программы в целом.
• Расскажите, что такое синтаксически управляемый перевод.
• Объясните работу алгоритма генерации последовательности триад по дереву синтаксического разбора на своем примере.
• За счет чего обеспечивается возможность генерации кода на разных объектных языках по одному и тому же дереву?
• Дайте определение понятию оптимизации программы. Для чего используется оптимизация? Каким условиям должна удовлетворять оптимизация?
• Объясните, почему генерацию программы приходится проводить в два этапа: генерация и оптимизация.
• Какие существуют методы оптимизации объектного кода?
• Что такое триады и для чего они используются? Какие еще существуют методы для представления объектных команд?
• Объясните работу алгоритма свертки. Приведите пример выполнения свертки объектного кода.
• Что такое лишняя операция? Что такое число зависимости?
• Объясните работу алгоритма исключения лишних операций. Приведите пример исключения лишних операций.
Варианты заданий
Варианты заданий соответствуют вариантам заданий для лабораторной работы № 3. Для выполнения работы рекомендуется использовать результаты, полученные в ходе выполнения лабораторных работ № 2 и 3.
Пример выполнения работы
Задание для примера
В качестве задания для примера возьмем язык, заданный КС-грамматикой G({if,then,else,a,=,or,xor,and,(,),},{S,F,_£,£), C},P,S) с правилами Р:
S → F;
F → if-then T else F | if E then F | a:= E
T → if-then T else T | a:= E
E → E or D | E xor D | D
D → D and С | С
С → a | (E)
Жирным шрифтом в грамматике и в правилах выделены терминальные символы.
Этот язык уже был использован для иллюстрации выполнения лабораторных работ № 2 и № 3.
Результатом примера выполнения лабораторной работы № 4 будет генератор списка триад. Преобразование списка триад в ассемблерный код рассмотрено далее в примере выполнения курсовой работы (см. главу "Курсовая работа").
Построение схем СУ-перевода
Все операции, которые могут присутствовать во входной программе на языке, заданном грамматикой G, по смыслу (семантике) можно разделить на следующие группы:
• логические операции (or, xor и and);
• оператор присваивания;
• полный условный оператор (if…then… else…) и неполный условный оператор (if… then…);
• операции, не несущие смысловой нагрузки, а служащие только для создания синтаксических конструкций исходной программы (в данном языке таких операций две: круглые скобки и точка с запятой).
Рассмотрим схемы СУ-перевода для всех перечисленных групп операций.
СУ-перевод для линейных операций
Линейной операцией будем называть такую операцию, для которой порождается код, представляющий собой линейный участок результирующей программы. Например, рассмотренные ранее бинарные арифметические операции (см. раздел "Краткие теоретические сведения") являются линейными.
В заданном входном языке логические операции выполняются над целыми десятичными числами как побитовые операции, то есть они также являются бинарными линейными операциями. Поэтому для них могут быть использованы те же самые схемы СУ-перевода, что были рассмотрены ранее.
Примечание.
На самом деле возможен другой вариант вычисления логических операций в том случае, когда они являются операциями булевой логики и их операндами могут быть только значения "Истина" (1) и "Ложь" (0). Здесь этот вариант не рассматривается. Более подробно о нем сказано в разделе "Курсовая работа", когда строятся схемы СУ-перевода для логических операций, а также можно обратиться к литературе [2].
СУ-перевод для оператора присваивания
Оператор присваивания также является бинарной логической операцией, поэтому для него может быть использована соответствующая схема СУ-перевода.
Отличие оператора присваивания от прочих бинарных линейных операций заключается в том, что первым операндом у него всегда должна быть переменная. Поэтому функция, строящая код для оператора присваивания, должна проверять тип первого операнда. Эта проверка представляет собой реализацию простейшего семантического анализа и в данном случае необходима, так как присваивание значений константам не отслеживается на этапе синтаксического анализа (об этом было сказано в лабораторной работе № 3).
СУ-перевод для условных операторов
Для условных операторов генерация кода должна выполняться в следующем порядке:
1. Порождается блок кода№ 1, вычисляющий логическое выражение, находящееся между лексемами if (первая нижележащая вершина) и then (третья нижележащая вершина), – для этого должна быть рекурсивно вызвана функция порождения кода для второй нижележащей вершины.
2. Порождается команда условного перехода, которая передает управление в зависимости от результата вычисления логического выражения:
• в начало блока кода № 2, если логическое выражение имеет ненулевое значение;
• в начало блока кода № 3 (для полного условного оператора) или в конец оператора (для неполного условного оператора), если логическое выражение имеет нулевое значение.
3. Порождается блок кода № 2, соответствующий операциям после лексемы then (третья нижележащая вершина), – для этого должна быть рекурсивно вызвана функция порождения кода для четвертой нижележащей вершины.
4. Для полного условного оператора порождается команда безусловного перехода в конец оператора.
5. Для полного условного оператора порождается блок кода № 3, соответствующий операциям после лексемы else (пятая нижележащая вершина), – для этого должна быть рекурсивно вызвана функция порождения кода для шестой нижележащей вершины.
Схемы СУ-перевода для полного и неполного условных операторов представлены на рис. 4.1.
Рис. 4.1. Схемы СУ-перевода для условных операторов.
Для того чтобы реализовать эти схемы, необходимы два типа триад: триада условного перехода и триада безусловного перехода.
Эти два типа триад реализуются следующим образом:
• IF(<операнд1>,<операнд2>) – триада условного перехода;
• JMP(1,<операнд2>) – триада безусловного перехода.
У триады IF первый операнд может быть переменной, константой или ссылкой на другую триаду, второй операнд – всегда ссылка на другую триаду. Триада IF передает управление на триаду, указанную вторым операндом, если первый операнд равен нулю, иначе управление передается на следующую триаду.
У триады JMP первый операнд не имеет значения (для определенности он всегда будет равен 1), второй операнд – всегда ссылка на другую триаду. Триада JMP всегда передает управление на триаду, указанную вторым операндом.
СУ-перевод для семантически ненагруженных конструкций
Операции, которые не несут никакой смысловой нагрузки, не требуют построения результирующего кода. Для них не требуется строить схемы СУ-перевода.
Тем не менее функция генерации списка триад должна обрабатывать и эти операции.
Они должны обрабатываться следующим образом:
• для вершины, у которой первая нижележащая вершина – открывающая скобка, вторая нижележащая вершина – узел дерева (не концевая вершина) и третья нижележащая вершина – закрывающая скобка, должна рекурсивно вызываться функция порождения кода для второй нижележащей вершины;
• для вершины, у которой первая нижележащая вершина – узел дерева (не концевая вершина) и вторая нижележащая вершина – точка с запятой, должна рекурсивно вызываться функция порождения кода для первой нижележащей вершины.