Синтаксически управляемый перевод

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

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

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

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

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

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

Суть принципа СУ-перевода заключается в следующем: с каждой вершиной де­рева синтаксического разбора N связывается цепочка некоторого промежуточного кода С(N). Код для вершины N строится путем сцепления (конкатенации) в фик­сированном порядке последовательности кода С(N) и последовательностей кодов, связанных со всеми вершинами, являющимися прямыми потомками N. В свою очередь, для построения последовательностей кода прямых потомков вершины N потребуется найти последовательности кода для их потомков – потомков вто­рого уровня вершины N – и т. д. Процесс перевода идет, таким образом, снизу вверх в строго установленном порядке, определяемом структурой дерева.

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

Возможна модель компилятора, в которой синтаксический анализ входной про­граммы и генерация кода результирующей программы объединены в одну фазу. Такую модель можно представить в виде компилятора, у которого операции ге­нерации кода совмещены с операциями выполнения синтаксического разбора. Для описания компиляторов такого типа часто используется термин “СУ-ком­пиляция” (синтаксически управляемая компиляция).

Схему СУ-компиляции можно реализовать не для всякого входного языка программирования. Если принцип СУ-перевода применим ко всем входным КС-языкам, то применить СУ-компиляцию оказывается не всегда возможным. Од­нако известно, что схемы перевода на основе СУ-компиляции можно построить для многих из широко распространенных классов КС-языков, в частности для LR- и LL-языков.

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

· помещение в выходной поток данных машинных кодов или команд ассембле­ра, представляющих собой результат работы (выход) компилятора;

· выдача пользователю сообщений об обнаруженных ошибках и предупрежде­ниях (которые должны помещаться в выходной поток, отличный от потока, используемого для команд результирующей программы);

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