Пример 33

Графы зависимости

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

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

Предположим, что продукция А → XY имеет связанное с ней семантическое правило А.а:=f(Х.х, У.у). Это правило определяет синтезируемый атрибут А.а, который зависит от атри­бутов Х.х и Y.у. Если эта продукция используется в дереве разбора, то в графе зависимо­сти будет три узла А.а, Х.х и Y.у с дугами от Х.х к А.а, поскольку А.а зависит от Х.х, и от Y.у к А.а, поскольку А.а зависит от Y.у.

Если продукция А → ХY имеет семантическое правило Х.і:=g(А.а, Y.у), связанное с ней, то в графе зависимости будут дуги от А.а к Х.і и Y.у к Х.і, поскольку Х.і зависит как от А. а, так и Y.у.

Когда в дереве разбора используется следующая продукция, мы добавляем показан­ные на рис. 53 дуги в граф зависимости.

Продукция Семантическое правило

E → E ₁ * E₂ E.val:=E _1. val+ E₂.val

Три узла, помеченные в графе зависимости символом •, представляют синтезируемые атри­буты Е.vаl, Е ₁ .vаl и Е ₂ .vаl в соответствующих узлах дерева разбора. Дуги, направленные от Е₁.vаl, Е₂.vаl к Е.vаl, показывают, что Е.vаl зависит от Е₁.vаl, Е₂.vаl. Пунктирные линии на рисунке представляют дерево разбора и не являются частью графа зависимости.

Рис. 53. Атрибут Е.val синтезирован из Е₁.val и Е₂.val

id₃

Рис. 54. Граф зависимости для дерева разбора на рис. 43

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