Пример 35

Порядок выполнения

Пример 34

На рис. 54 показан граф зависимости для дерева разбора на рис. 52. Узлы в графе зависимости помечены числами. Имеется дуга узла 4 для T.type в узел 5 L.in, поскольку наследуемый атрибут L.in зависит от атрибута T.type согласно семантическому правилу L.in:= T.type для продукции D → TL. Две нисходящие дуги в узлы 7 и 9 появляются в силу зависимости L₁.in от L.in в соответствии с семантическим правилом L₁.in:= L.in для продукции L → L ₁, id. Каждое из семантических правил addtype( id .entiy,L.in), связанных с L-продукциями, приводит к созданию фиктивного атрибута. Узлы 6, 8 и 10 построены для таких фиктивных атрибутов.

Топологическая сортировка направленного ациклического графа является упорядочением узлов графа т₁ , т₂,… т_k, таким, что дуги направлены от узлов, расположенных в упорядоченной последовательности раньше, к узлам, расположенным поэтапно т.е. если т_i, → т_j — дуга от т_i, к т_j то т_i, встречается в упорядоченной последовательности раньше т_j.

Любая топологическая сортировка графа зависимости дает правильный порядок пополнения семантических правил, связанных с узлами дерева разбора, т.е. к моменту пополнения семантического правила b:=f(с₁, с₂, …,с_k) атрибуты с₁,с₂,…, с_к доступны для вычисления f.

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

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

а₄:= real;

а₅:= а₄ ;

addtype ( id₃. entry, a₅);

a₇:= a₅;

addtype ( id₂. en try, a₇,);

a₉: = a₇',

addtype ( id₁. entry, a₉);

Выполнение этих семантических правил вносит тип real в записи таблицы символов для каждого из идентификаторов.

Для выполнения семантических правил существует ряд методов.

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

2. Методы, основанные на правилах. В процессе создания компилятора анализируются семантическиеправила, связанные с продукциями, либо вручную, с помощью специализированного инструментария. Порядок вычисления атрибутов, связанных с каждой продукцией, предопределяется в процессе разработки компилятора.

3. Игнорирующие методы. Выбор порядка выполнения происходит без рассмотрения семантических правил. Например, если трансляция происходит в процессе синтак­сического анализа, то порядок выполнения задается методом синтаксического ана­лиза, независимо от семантических правил. Игнорирующие методы ограничивают класс реализуемых синтаксически управляемых определений.

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

Дата добавления: 2014-12-27