Синтезируемые атрибуты. Их обработка в алгоритме сдвиг — свертка

Являются расширением контекстно-свободными грамматик. С грамматическими символами связывают множество атрибутов. Дерево будет в вершинах иметь набор переменных. Это дерево называется аннотированным деревом разбора. Значения атрибутов определяется семантическими правилами, связанными с продукциями грамматики в зависимости от вида семантических правил атрибуты м.б. синтезируемыми и наследуемыми.

Синтезируемые — вычисляют свои значения не используя атрибуты своих «детей».

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

Построение абстрактного синтаксического дерева

Транслятор на основе текста программы формирует некоторый промежуточный код. Этот код м.б. абстрактным синтаксическим деревом (АСД).

АСД — это абстрактное представление конструкций языка, полученное из дерева разбора. Обычно в АСД ключевые слова и операторы не показываются, а объединяются в один родительский узел.

Продукция S > if B then S₁ else S₂ порождает сл. фрагмент дерева разбора:

Этому фрагменту соответствует конструкция языка — условный оператор, состоящий из условия и двух операторов:

Самый простой способ вычислить это выражение — это использование постфиксной записи. П.з. — это линеаризированное, т. е. представленное последовательно, представление синтаксического дерева. В ней узлы следуют сразу после своих детей: а в с uminus * в с uminus * + assign.

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

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

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

Полученное дерево можно представить в виде массива:

Из этого представления в форме массива можно получить трехадресный код, где каждая команда представляется следующим образом: х:=y op z. x, y, zимена, константы или генерируемые компилятором временные ячейки. ор — оператор.

С помощью трехадресных команд можно представить и АСД и НАГ.

АСД:

t1:=-c, t2:=b*t1, t3:=-c, t4:=b*t3, t5;=t2+t4, a:=t5.

Для НАГ программа будет проще:

t1:=-c, t2:=b*t1, t5:=t2+t2, a:=t5.

Имена переменных можно рассматривать как указатели на записи в таблице символов.