Разработка компиляторов

       

Атрибутное дерево разбора


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

На слайде в качестве примера приведено атрибутное дерево разбора, порожденное по следующему оператору исходного языка a := a + b; Отметим, что форма представления дерева, использованная на слайде, является типичной при компиляции, так как позволяет изобразить практически сколь угодно сложные деревья на экране компьютера (попробуйте представить себе традиционное изображение дерева разбора для сколько-нибудь сложной программы!).

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



Содержание раздела