Дерево разбора. Преобразование дерева разбора

В дерево операций

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

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

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

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

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

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

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

Алгоритм преобразования дерева семантического разбора в дерево операций мож­но представить следующим образом.

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

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

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

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

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

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

Этот алгоритм всегда работает с узлом дерева, который считает текущим, и стре­мится исключить из дерева все узлы, помеченные нетерминальными символами. То, какие из символов считать семантически незначащими, а какие считать зна­ками операций, решает разработчик компилятора. Если семантика языка задана корректно, то в результате работы алгоритма из дерева будут исключены все нетерминальные символы.

Возьмем в качестве примера синтаксическое дерево, построенное для цепочки (а+а)*b, языка, задающего грамматику арифметиче­ских выражений. Это дерево приведено на рис. 5.

Грамматика для арифметиче­ских выражений над символами a и b имеет вид:

G ({+,-,/,*,a,b},{S,R,T,F,E},P,S)

Р:

S  TR | T

R  +T | -T | +TR | -TR

Т  EF | E

F  *E | /E | *EF | /EF

E  (S) | a | b

Семантически незначащими символами в этой грамматике являются скобки (они задают порядок операций и влияют на синтаксический разбор, но результирующего кода не порождают) и пустые строки. Знаки операций заданы символами +, -, / и *, остальные символы (а и b) являются операндами.

В результате применения алгоритма преобразования дерева синтаксического разбора в дерево операций к дереву, представленному на рис. 8, получим дерево операций, представленное на рис. 9.

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