Синтаксическое дерево.

Способы внутреннего представления программ Виды внутреннего представления программы.

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

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

Известны следующие формы внутреннего представления программ:

· связные списочные структуры, представляющие синтаксические деревья;

· многоадресный код с явно именуемым, результатом (тетрады);

· многоадресный код с неявно именуемым результатом (триады);

· обратная (постфиксная) польская запись операций;

· ассемблерный код или машинные команды.

Дерево вывода. Методы построения дерева вывода

Деревом вывода грамматики G(VT,VN,P,S) называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

· каждая вершина дерева обозначается символом грамматики ;

· корнем дерева является вершина, обозначенная целевым символом грамма­тики — S;

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

· если некоторый узел дерева обозначен нетерминальным символом , а связанные с ним узлы - символами b₁b₂…b_n; n > 0, то в грамматике G(VT,VN,P,S) существует правило .

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

Примеры деревьев приведены на рисунке.

Для того чтобы построить дерево вывода, достаточно иметь только цепочку вы­вода. Дерево вывода можно построить двумя способами: сверху вниз и снизу вверх. Для строго формализованного построения дерева вывода всегда удобнее пользоваться строго определенным выводом: либо левосторонним, либо право­сторонним.

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

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

Синтаксические деревья. Преобразование дерева разбора в дерево операций.

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

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

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

То, какой узел в дереве является операцией, а какой — операндом, никак невоз­можно определить из грамматики, описывающей синтаксис входного языка. Также ниоткуда не следует, каким операциям должен соответствовать объектный код в результирующей программе, а каким — нет. Все это определяется только исходя из семантики — «смысла» — языка входной программы. Поэтому только разработчик компилятора может четко определить, как при построении дерева опера­ций должны различаться операнды и сами операции, а также то,, какие операции являются семантически незначащими для порождения объектного кода. Алгоритм преобразования дерева семантического разбора в дерево операций можно представить следующим образом:

Шаг 1. Если в дереве больше не содержится узлов, помеченных нетерминальны­ми символами, то выполнение алгоритма завершено; иначе перейти к шагу 2.

Шаг 2. Выбрать крайний левый узел дерева, помеченный нетерминальным сим­волом грамматики, и сделать его текущим. Перейти к шагу 3.

Шаг 3. Если текущий узел имеет только один нижележащий узел, то текущий узел необходимо удалить из дерева, а связанный с ним узел присоединить к узлу вышележащего уровня (исключить из дерева цепочку) и вернуться к шагу 1; иначе перейти к шагу 4.

Шаг 4. Если текущий узел имеет нижележащий узел (лист дерева), помеченный терминальным символом, который не несет семантической нагрузки, тогда этот лист нужно удалить из дерева и вернуться к шагу 3; иначе перейти к шагу 5.

Шаг 5. Если текущий узел имеет один нижележащий узел (лист дерева), поме­ченный терминальным символом, обозначающим знак операции, а остальные узлы помечены как операнды, то лист, помеченный знаком операции, надо уда­ лить из дерева, текущий узел пометить этим знаком операции и перейти к шагу 1; иначе перейти к шагу 6.

Шаг 6. Если среди нижележащих узлов для текущего узла есть узлы, помечен­ные нетерминальными символами грамматики, то необходимо выбрать крайний левый среди этих узлов, сделать его текущим узлом и перейти к шагу 3; иначе выполнение алгоритма завершено.

Если семантика языка задана корректно, то в результате работы алгоритма из де­рева будут исключены все нетерминальные символы.