2.13 Общие принципы генерации кода

Генерация объектного кода – это перевод компилятором внутреннего представления исходной программы в цепочку символов выходного языка. Генерация объектного кода порождает результирующую объектную программу на языке машинных команд. Внутреннее представление программы может иметь любую структуру в зависимости от реализации компилятора, в то время как результирующая программа всегда представляет собой линейную последовательность команд. Поэтому генерация объектного кода (объектной программы) в любом случае должна выполнять действия, связанные с преобразованием сложных синтаксических структур в линейные цепочки.

Генерация объектного кода выполняется после того, как выполнен синтаксический анализ программы и все необходимые действия по подготовке к генерации кода: распределено адресное пространство под функции и переменные, проверено соответствие имен и типов переменных, констант.

В идеале компилятор должен выполнить синтаксический разбор всей входной программы, затем выполнить семантический анализ, после чего приступить к подготовке генерации и непосредственно к генерации кода. Однако такая схема работы компилятора практически почти никогда не применяется. В общем случае ни один семантический анализатор и ни один компилятор не способны проанализировать и оценить смысл всей входной программы в целом. Формальные методы анализа семантики применимы только к очень незначительной части возможных программ. Поэтому у компилятора нет практической возможности порождать эквивалентную выходную программу на основании всей входной программы.

Как правило, компилятор выполняет генерацию результирующего кода поэтапно, на основе законченных синтаксических конструкций входной программы:

1) компилятор выделяет законченную синтаксическую конструкцию из текста входной программы,

2) порождает для нее фрагмент результирующего кода и помещает его в текст выходной программы.

3) Затем он переходит к следующей синтаксической конструкции.

Так продолжается до тех пор, пока не будет разобрана вся входная программа. В качестве анализируемых законченных синтаксических конструкций выступают операторы, блоки операторов, описания процедур и функций. Их конкретный состав зависит от входного языка и реализации компилятора.

2.14 Синтаксически управляемый перевод (су-схемы).

Работает на базе грамматик V+ α β → ∈ λ Ɐ

Чтобы компилятор мог построить код результирующей программы для синтаксической конструкции входного языка, часто используется метод, называемый синтаксически управляемым переводом – СУ-переводом.

СУ-перевода заключается в том, что каждому правилу входного языка компилятора сопоставляется одно или несколько (или ни одного) правил выходного языка в соответствии с семантикой входных и выходных правил. То есть при сопоставлении надо выбирать правила выходного языка, которые несут тот же смысл, что и правила входного языка.

T( VN, VT₁, VT₂, R, S) – схема СУ-перевода

S ∈ VN

G₁ (VT₁, VN, P_1, S) – входная грамматика

P: A → α

A ∈ VN, α ∈ (VN∪VT₁)*

G₂ (VT₂, VN, P₂, S) – выходная грамматика

P: A → B, B∈ (VN∪VT₂)*

С помощью СУ-перевода можно одновременно с кусочком входной цепочки получать кусочек выходной цепочки.

Пример.

T = {( x, y)}

X ∈ VT₁*, y ∈ VT₂*

T={0ⁿ,1ⁿ, a²ⁿ, b^n-1, n>0}

R: S→ 0S1, aaSb

S→ 01, aa

Таким образом, одновременно с формированием цепочки, состоящей из 0 и 1, будет формироваться выходная цепочка, представляющая собой перевод.

T ({S}, {0,1}, {a,b}, R, S) – схема СУ-перевода

Нетерминалы должны использоваться одни и те и в одинаковом количестве в правилах вывода (слева) и в элементов перевода (справа)