Генерация кода

После того как синтаксис программы проанализирован, последним шагом процесса компиляции является генерация объектного кода. В этом разделе мы обсудим простой метод, кото­рый генерирует объектный код для каждого фрагмента программы, как только распознан синтаксис этого фрагмента.

Для реализации рассматриваемого метода генерации объектного кода необходим набор подпрограмм, соответствующих каждому правилу и каждой альтернативе в правилах грамма­тики. Как только в результате процесса грамматического раз­бора будет распознан фрагмент текста исходной программы, соответствующий некоторому правилу грамматики, вызывается подпрограмма, соответствующая этому правилу. Эти программы часто называют семантическими программами, поскольку выполняемые ими действия связаны со смыслом, который мы связываем с соответствующими конструкциями языка. В рамках нашей простой схемы эти семантические программы непосредственно генерируют объектный код. Поэтому мы будем называть их программами генерации кода. В более сложных компиляторах подобные семантические программы могут генерировать некоторую промежуточную форму представления программы, пригодную для последующего анализа с целью генерации более эффективного объектного кода.

Программы генерации кода, которые мы обсудим в этом разделе, предназначены для использования с грамматикой на рис. 2. Как мы уже видели, ни один из методов грамматического разбора, обсуждавшихся в разд. 3, не распознает в точности те конструкции, которые описаны грамматикой. Метод операторного предшествования игнорирует некоторые нетерминальные символы, а метод рекурсивного спуска вынужден использовать несколько модифицированную грамматику. Существуют, однако, методы грамматического разбора ненамного сложнее описанных, которые могут осуществлять грамматический разбор в строгом соответствии с грамматикой на рис. 5.2. Мы выбрали именно эту грамматику для обсуждения программ генерации кода только для того, чтобы подчеркнуть, что методы генерации кода не связаны непосредственно с каким-либо кон­кретным методом грамматического разбора.

Генерируемый код, очевидно, зависит от того, на каком компьютере будет выполняться компилируемая программа. В этом разделе мы будем рассматривать генерацию объектного кода для машины УУМ/ДС. Для своих рабочих данных наши программы генерации кода будут использовать две структуры: список и стек. Данные, попадающие в список, выбираются в том же порядке, в котором они туда записывались, т. е. В соответствии со стратегией «первым пришел — первым ушел».. Данные, попадающие в стек, выбираются из него в обратном порядке, т. е. в соответствии со стратегией «первым пришел—А последним ушел». Переменная LISTCOUNT используется в качестве счетчика элементов, содержащихся в данный момент в' списке. Программы генерации кода также используют специфи­каторы лексем, описанные в разд. 2 и обозначаемые S (лексема). Для лексемы id выражение S(id) является именем соответствующего идентификатора или указателем на него в таблице символов. Для лексемы int выражение S(int) является зна­чением соответствующего целого числа, например #100.

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

Рис. 12 иллюстрирует процесс генерации объектного кода для предложения READ в строке 9 программы рис. 1. Для удобства дерево грамматического разбора этого предложения повторено на рис. 12а. Это дерево можно получить многими различными методами грамматического разбора. Однако независимо от используемого метода на каждом шаге процесса грамматического разбора распознается самая левая подстрока входного текста, которая может быть интерпретирована в соот­ветствии с каким-либо из правил грамматики. В методе опера­торного предшествования подобное распознавание осуществля­ется, когда подстрока входного текста редуцируется к некото­рому нетерминальному символу <N₁>. В методе рекурсивного спуска распознавание происходит в тот момент, когда соответ­ствующая процедура заканчивает свою работу с признаком ус­пешного завершения. Таким образом, в процессе грамматиче­ского разбора всегда будет сначала распознан идентификатор VALUE в качестве нетерминального символа <id — list>, а уже потом предложение в целом будет распознано в качестве нетер­минального символа <read>.

На рис. 12в символически изображен объектный код, ко­торый должен быть сгенерирован для предложения READ. Этот код представляет собой вызов подпрограммы XREAD, ко­торая должна содержаться в стандартной библиотеке компиля­тора. Эта подпрограмма может быть вызвана также любой программой, желающей выполнить операцию чтения. Подпрограмма XREAD связывается с генерируемой программой связывающим загрузчиком или же редактором связей. (Компилятор должен включить в объектную программу достаточно информации для определения всех необходимых связей, используя, возможно, средства модификации) Подобная техника обычно используется при компиляции предложений, выполняющих относительно сложные функции. Использо­вание подпрограмм в этом случае позволяет избежать повторной генерации больших фрагментов программы, что существенно сокращает генерируемую программу.

Поскольку подпрограмма XREAD может быть использована для любых операций чтения, она должна иметь параметры, определяющие детали этой операции. В нашем случае список параметров подпрограммы XREAD помещается непосредственно за инструкцией JSUB, которая ее вызывает. Первое слово в этом списке параметров содержит величину, определяющую ко­личество переменных, которым должно быть присвоено значение в результате осуществления операции чтения. В последующих словах содержатся адреса этих переменных. Таким обра­зом, вторая строка на рис. 12в определяет, что должно быть прочитано значение одной переменной, а третья строка содер­жит ее адрес. Адрес первого слова списка параметров будет автоматически помещен в регистр L при выполнении инструк­ции JSUB. Подпрограмма XREAD может использовать этот адрес для определения своих параметров и, сложив содержимое регистра L с длиной списка параметров, определить значение адреса возврата.

На рис. 12б представлен набор программ, которые могут использоваться для генерации объектного кода. Первые две программы соответствуют двум альтернативам для нетер­минального символа <id—list> в грамматическом правиле 6 на рис. 2. В любом случае спецификатор лексемы S(id) для очередного идентификатора, являющегося элементом <id — list>, включается в список, используемый программами генерации кода. Соответствующая переменная LISTCOUNT увеличивается на единицу, чтобы отразить включение в список нового иденти­фикатора. После того как нетерминальный символ <id — list> будет разобран, список будет содержать спецификаторы лексем для всех идентификаторов, содержащихся в <id — list>. Когда будет распознано предложение <read>, эти спецификаторы лексем будут удалены из списка н использованы для генерации объектного кода, соответствующего операции чтения READ.

Обратите внимание, что в процессе генерации дерева грам­матического разбора, изображенного на рис. 5.12а, вначале рас­познается <id — list>, а уже потом <read>. На каждом шаге грамматического разбора вызывается соответствующая програм­ма генерации объектного кода. Вы должны внимательно про­анализировать этот пример, чтобы убедиться в правильном по­нимании процесса генерации объектного кода, символически представленного на рис. 12в с помощью программ генерации на рис. 126.

На рис. 13 изображен процесс генерации объектного кода для предложения присваивания в строке 14 на рис. 1. На рис. 13а приведено дерево грамматического разбора этого предложения. Основная работа при грамматическом разборе этого предложения состоит в анализе нетерминального символа <ехр> в правой части оператора присваивания. Как мы видим, в процессе грамматического разбора идентификатор SUMSQ распознается сначала как <factor>, потом как <term>. Далее распознается целое число 100 как <factor>; затем фрагмент SUMSQ DIV 100 распознается как <term> и т. д. Эта цепочка шагов примерно совпадает с изображенной на рис. 86. Поря­док распознавания фрагментов этого предложения совпадает с порядком, в котором должны выполняться соответствующие вычисления; сначала вычисляются подвыражения SUMSQ DIV 100 и MEAN * MEAN, а затем второй результат вычитается из первого.

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

<term>₁ ::== <term>₂*<factor>

Индексы использованы здесь для различения двух вхождений нетерминального символа <term>. Наши программы генерации кода выполняют все арифметические операции с использовани­ем регистра А, и мы заведомо должны сгенерировать в объект­ном коде операцию MUL. Результат этого умножения <term>₁ — .после операции MUL сохранится в регистре А. Если либо <term>₂, либо <factor> уже находятся на регистре А (после выполнения предыдущих вычислений), генерация инструкции .MUL—это все, что нам нужно. Иначе мы должны сгенериро­вать также инструкцию LDA, предшествующую инструкции MUL. В этом случае нам также надо предварительно сохра­нить значение регистра А, если оно понадобится в будущем.

Очевидно, необходимо отслеживать значение, помещенное в регистр А, после каждого фрагмента генерируемого объектного кода. Это можно осуществить за счет расширения понятия спецификатора лексемы на нетерминальные узлы дерева грам­матического разбора. В только что рассмотренном примере спецификатору узла S(<term>₁) будет присвоено значение rА, указывающее па то, что результат этих вычислений содержится в регистре А. Переменная REGA используется для указания на самый высокий уровень узла дерева грамматического разбора, значение которого помещено в регистр А в сгенерированном до данного момента объектном коде (т. е. указатель па узел, спе­цификатор которого равен rА). Очевидно, в каждый момент процесса генерации объектного кода существует ровно один такой узел. Если же в регистре А нет значения, соответствую­щего некоторому узлу, то спецификатор этого узла аналогичен спецификатору лексемы: это либо указатель на переменную (в таблице символов), содержащую соответствующее значение, либо указатель на целую константу.

Чтобы проиллюстрировать приведенные соображения рассмотрим программу генерации объектного кода на рис. 13б, соответствующую правилу

<term>₁ ::== <term>₂ * <factor>

Если спецификатор узла какого-либо из операндов равен rА, то соответствующее значение уже содержится в регистре А и программа генерирует только одну инструкцию MUL. Адрес операнда для инструкции MUL содержится в спецификаторе узла другого операнда (значение которого не находится на регистре А). В противном случае вызывается процедура GETA. Эта процедура, изображенная на рис. 13в, генерирует инструкцию LDA для загрузки значения, связанного со значением <term>₂, в регистр А. Дополнительно перед инструкцией LDA процедура генерирует инструкцию STA для сохранения текущего значения регистра А, если только REGA не нуль (равенство REGA нулю означает, что это значение больше не понадобится). Это значение запоминается в некоторой рабочей переменной. Рабочие переменные образуются в процессе генерации объектного кода (с именами Т1, Т2, ...) по мере необходимости. Для используемых компилятором рабочих переменных будет отведено место в конце объектной программы. На узел; дерева грамматического разбора, связанный со значением, содержащимся в регистре А, указывает переменная REGA. Спецификатор этого узла модифицируется, чтобы указывать на рабочую переменную, используемую для хранения этого значения.

После того как все необходимые инструкции сгенерированы, программа генерации кода устанавливает спецификатор S(<term>i) и переменную REGA таким образом, чтобы было вид'; по, что значение, соответствующее <term₁>, находится в настоя­щее время в регистре А. На этом процедура генерации кода для операции * завершается.

Программа генерации кода, соответствующая операции + практически совпадает с только что рассмотренной програм­мой для операции *. Программы для DIV и — также аналогичны, за исключением того, что для этих операций необходимо, чтобы на регистре А был установлен именно первый операнд. Программа генерации кода для операции присваивания (assign) состоит в загрузке присваиваемой величины на регистр А (с использованием GETA) и генерации инструкции STA. Обратите внимание, что переменная REGA потом обнуляется, поскольку код, соответствующий предложению присваивания, полностью сгенерирован и все промежуточные результаты больше не нужны.

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

На рис. 13б представлено символическое изображение объектного кода, сгенерированного для предложения присваивания. Вы должны внимательно проследить генерацию этого кода, чтобы понять механизм работы программ на рис. 13б и 13в. Нам надо также проверить, что эти коды действительно выполняют те вычисления, которые записаны в предложении исходной программы.

На рис. 14 изображены другие программы генерации кода для грамматики рис. 2. Программа для <prog—name> генери­рует заголовок объектной программы, аналогичной результату работы директив ассемблера START и EXTREF. Она также генерирует инструкции для сохранения адреса возврата и пе­рехода на первую выполняемую инструкцию компилируемой программы. После того как вся программа распознана, резер­вируется память для рабочих переменных (Ti). Затем все ссыл­ки на эти переменные фиксируются в объектном коде с исполь­зованием процедуры обработки ссылок вперед, осуществляемой однопросмотровым ассемблером. Компилятор генерирует так же модифицирующие записи, необходимые для описания внешних ссылок на библиотечные подпрограммы.

Генерация кода для предложения <for> состоит из не­скольких шагов. После того как распознан нетерминальный символ <index—exp>, генерируется код для инициализации ин­дексной переменной цикла и инструкции проверки конца цикла. Часть информации также записывается в стек для дальнейше­го использования. Далее независимо генерируются коды для каждого предложения, составляющего тело цикла. После того как вся конструкция (for) распознана, генерируется код, увеличивающий индексную переменную и осуществляющий возврат на начало цикла для проверки условий его завершения. Здесь программы генерации кода используют информацию, за­писанную в стек программой, соответствующей <index—exp>. •Использование стека для запоминания этой информации позво­ляет обрабатывать вложенные циклы <for>.

Вы можете проследить весь процесс генерации кода для этой программы, используя дерево грамматического разбора рис. 4 в качестве управляющей информации. Результат дол­жен совпасть с изображенным на рис. 15. Еще раз повторим, что это всего лишь символическое изображение сгенерирован­ного кода. Большинство компиляторов генерирует коды непо­средственно на машинном языке.

Предлагаю ознакомиться с аналогичными статьями: