М.Ю. Харламов, ВНУ им. В.Даля, 2010

Генерация объектного кода это перевод компилятором внутреннего представ­ления исходной программы в цепочку символов выходного языка выполняется после того, как выполнены синтаксический анализ программы и все необходимые действия по подготовке к генерации кода (распределено адресное пространство под функции и переменные, проверено соответствие имен и типов переменных, констант и функций в синтаксических конструкциях исходной про­граммы) компилятор выделяет законченную синтаксическую конструкцию из текста исходной программы, порождает для нее фрагмент результирующего кода и помещает его в текст результирующей программы. Затем он переходит к следующей синтаксической конструкции Тема 8. Генерация кода 2

Идея синтаксис и семантика языка взаимосвязаны смысл предложения языка зависит от синтаксической структуры этого предложения каждому правилу вход­ного языка компилятора сопоставляется одно или несколько (или ни одного) правил выходного языка Суть с каждой вершиной дерева синтаксического разбора N связывается цепочка некоторого промежуточного кода C(N). Код для вершины N строится путем сцепления (конкатенации) в фиксированном порядке последовательности кода C(N) и последовательностей кодов, связанных со всеми вершинами, являющимися прямыми потомками N СУ-компиляция - модель компилятора, в которой синтаксический анализ исходной про­граммы и генерация кода объединены в одну фазу Тема 8. Генерация кода 3

Дерево вывода содержит массу избыточной информации, которая для дальнейшей работы компилятора не требуется Возможно использование последовательности примененных правил грамматики Известны следующие формы внутреннего представления программ: связные списочные структуры, представляющие синтаксические деревья многоадресный код с явно именуемым результатом (тетрады); многоадресный код с неявно именуемым результатом (триады); обратная (постфиксная) польская запись операций ассемблерный код или машинные команды Тема 8. Генерация кода 4

Дерево операций можно построить из дерева вывода. Для этого исключаются из дерева вывода цепочки нетерминальных символов, а также узлы, не несущие семанти­ческой (смысловой) нагрузки при генерации кода Если текущий узел (крайний левый узел дерева) имеет только один нижележащий узел, то текущий узел необходимо удалить из дерева, а связанный с ним узел присоединить к узлу вышележащего уровня (исключить из дерева цепочку) Если текущий узел имеет нижележащий узел, помеченный терминальным символом, который не несет семантической нагрузки, тогда этот лист нужно удалить из дерева Если текущий узел имеет один нижележащий узел (лист дерева), поме­ченный терминальным символом, обозначающим знак операции, а остальные узлы помечены как операнды, то лист, помеченный знаком операции, надо уда­лить из дерева, а текущий узел пометить этим знаком операции Тема 8. Генерация кода 5

6 S S T T R R e e E E ( ( S S ) ) T T R R E E F F a a e e + + T T R R E E F F e e a a e e F F * * E E b b F F e e * * b b + + a a a a Дерево вывода в LL(1)- грамматике для цепочки (а+а)*b Дерево операций Дерево операций является формой внутреннего представления программы, ко­ торой удобно пользоваться на этапах синтаксического и семантического анализа, а также подготовки к генерации кода, когда еще нет необходимости работать не­ посредственно с кодами команд результирующей программы

Тетрады Тетрады представляют собой линейную последовательность команд в форме Тема 8. Генерация кода 7 (,, ) Для тетрад (ввиду их лин. последовательности ) несложно написать тривиальный алгоритм, который будет преобразовывать последовательность тетрад в последовательность команд результирующей программы А := В * С + D - В * * (В, С, Т1) 2. + (T1, D, T2) 3. * (В, 10, ТЗ) 4. – (T2, ТЗ, Т4) 5. := (Т4, 0, А) 1. * (В, С, Т1) 2. + (T1, D, T2) 3. * (В, 10, ТЗ) 4. – (T2, ТЗ, Т4) 5. := (Т4, 0, А)

Тема 8. Генерация кода 8 Триады Триады представляют собой запись операций из трех составляющих: (, ) Для триад также можно записать тривиальный алгоритм, который будет преобразовывать по­следовательность триад в последовательность команд результирующей програм­мы (например, в код ассемблера) А := В * С + D - В * * (В, С) 2. + (^1, D) 3. * (В, 10) 4. – (^2, ^3) 5. := (А, ^4) 1. * (В, С) 2. + (^1, D) 3. * (В, 10) 4. – (^2, ^3) 5. := (А, ^4)

Ассемблерный код и машинные команды + внутреннее представ­ление программы полностью соответствует объектному коду сложные преоб­разования не требуются - требует дополнительных структур для отображения взаимосвязи операций - зависит от архитектуры ВС Обратная польская запись постфиксная запись операций (знаки операций записываются непосредственно за операндами) + эффективна, когда для вычислений используется стек - затруднена оп­тимизация выражений Тема 8. Генерация кода *+ 6+7*(10+4)=104

Тема 8. Генерация кода 10 act oper1 oper2 i) act (oper1, oper2) act тип триады oper1, oper2 операнды (листья дерева вывода) Узел 2, Узел 3 - нижележащие узлы дерева вывода Code (Узел 2, i) - последовательность триад, порождаемая для Узла 2, начиная с триады с номером i j количество триад, порождаемых для Узла 2 k количество триад, порождаемых для Узла 3 act тип триады oper1, oper2 операнды (листья дерева вывода) Узел 2, Узел 3 - нижележащие узлы дерева вывода Code (Узел 2, i) - последовательность триад, порождаемая для Узла 2, начиная с триады с номером i j количество триад, порождаемых для Узла 2 k количество триад, порождаемых для Узла 3 i) Code (Узел 2, i) i+j) act (oper1, ^i+j-1) i) Code (Узел 2, i) i+j) act (^i+j-1, oper2) i) Code (Узел 2, i) i+j) Code (Узел 3, 1+j) i+j+k) act (^i+j-l, ^i+j+k-l) act oper1 Узел 2 act Узел 2 oper2 act Узел 2 Узел 3

Тема 8. Генерация кода 11 := A - +* D* BC B10 А := В * С + D - В * 10 Шаг 1: 1) Code (U2, 1) i) := (А, ^i-1) Шаг 2: 1) Code (U3, 1) j) Code (U5, j) i-l) - (^j-l, ^i-2) i) := (А, ^i-1) Шаг 3: 1) Code (U4, 1) k) + (^k-1, D) j) Code (U5, j) i-l) -(^j-1, ^i-2) i) := (A, ^i-1) Шаг 4: 1) * (В, С) 2) + (^1, D) 3) Code (U5, 3) i-1) – (^j-1, ^i-2) i) := (A, ^i-1) Шаг 5: 1) * (В, С) 2) + (*1, D) 3) * (В, 10) 4) - (^2, ^3) 5) := (A, ^4)

Тема 8. Генерация кода 12 act oper1 oper2 mov ax, oper1 act ax, oper2 act команда соответствующей операции oper1, oper2 операнды (листья дерева вывода) Узел 2, Узел 3 - нижележащие узлы дерева Code (Узел 2) -код, порождаемый процедурой для нижележащего узла push и pop команды сохранения результатов в стеке и извлечения результатов из стека act команда соответствующей операции oper1, oper2 операнды (листья дерева вывода) Узел 2, Узел 3 - нижележащие узлы дерева Code (Узел 2) -код, порождаемый процедурой для нижележащего узла push и pop команды сохранения результатов в стеке и извлечения результатов из стека Code (Узел 2) mov dx, ax mov ax, oper1 act ax, dx Code (Узел 2) act ax, oper2 Code (Узел 2) push ax Code (Узел 3) mov dx, ax pop ax act ax, dx act oper1 Узел 2 act Узел 2 oper2 act Узел 2 Узел 3

Тема 8. Генерация кода 13 := oper1 oper2 mov ax, oper2 mov oper1, ax oper1, oper2 операнды (листья дерева вывода) Узел 2 - нижележащий узел дерева Code (Узел 2) -код, порождаемый процедурой для нижележащего узла oper1, oper2 операнды (листья дерева вывода) Узел 2 - нижележащий узел дерева Code (Узел 2) -код, порождаемый процедурой для нижележащего узла Code (Узел 2) mov oper1, ax := oper1 Узел 2

Тема 8. Генерация кода 14 := A - +* D* BC B10 А := В * С + D - В * 10 Шаг 1: Code(U2) mov A, ax Шаг 2: Code(U3) push ax Code(U5) mov dx, ax pop ax sub ax, dx mov A, ax Шаг 3: Code(U4) add ax, D push ax Code(U5) mov dx, ax pop ax sub ax, dx mov A, ax Шаг 4: movах, B mul С add ax,D push ax Code(U5) mov dx, ax pop ax sub ax,dx movA, ax Шаг 5: mov ax, B mulС addax, D push ax mov ax, B mul 10 mov dx, ax pop ax sub ax, dx mov A, ax