Стр. 66 - Информационные структуры и их преобразование

64 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Рассмотрим входную цепочку: a*a
(q, 1, $, e) | (q, 2, $a, S) | (q, 2, $F, 5S) | (q, 2, $T, 45S) | (q, 2, $E, 245S)|
(q, 3, $E*, S245S) | (q, 4, $E*a, SS245S) | (q, 4, $E*F, 5SS245S) |
(q, 4, $E*T, 45SS245S) | (q, 4, $E*E, 245SS245S) | (b, 4, $E*a, SS245S) |
(b, 3, $E*, S245S) | (b, 2, $E, 245S) | (b, 2, $T, 45S) | (q, 3, $T*, S45S) |
(q, 4, $T*a, SS45S) | (q, 4, $T*F, 5SS45S) | (q, 4, $T, 35SS45S) | (q, 4, $E,
235SS45S) |
(t, 4, $E, 235SS45S).
Получили дерево:
T
a
E
T
F
F
a
5
4 5
3
2
*
Рис. 3. Дерево
4.2. Польская запись, тетрады, триады, деревья
Атрибутное дерево разбора
Атрибутное дерево разбора является, наверное, самой
распространенной формой организации внутреннего представления
программы. При таком подходе каждая исходная конструкция языка
представляется в виде узла дерева, содержащего ссылки на все возможные
элементы этой конструкции (естественно, каждый отдельный элемент тоже
может иметь сложную структуру и, таким образом, также может быть
поддеревом). Кроме того, каждый узел дерева может нагружаться
дополнительными атрибутами, такими как ссылки в таблицы представлений
или таблицы идентификаторов. В итоге, вся программа представляется в виде
единого дерева разбора.
Деревья разбора привлекательны прежде всего своей гибкостью и
возможностью использования в самых разных этапах компиляции. Их можно
спроектировать таким образом, чтобы они мало зависели от исходного языка
и целевой платформы. Деревья разбора легко строить во время анализа