Пример 38

Схемы трансляции

Пример 37

L-атрибутные определения

Другой класс синтаксически управляемых определений - L-атрибутные определения.

Синтаксически управляемое определение является L-атрибутным, если каждый на­следуемый атрибут символа X_j,1 ≤ j ≤ п, из правой части продукции А → X ₁ X ₂ ...X_n зави­сит только от

1. атрибутов символов X _1, X ₂ ,..., X_j-1, расположенных в продукции слева от X_j-1;

2. наследуемых атрибутов А.

Например, каждое S-атрибутное определение является L-атрибутным, так как ог­раничения (1) и (2) относятся только к наследуемым атрибутам.

Синтаксически управляемое определение на рис. 58 не является L-атрибутным, по­скольку наследуемый атрибут Q.i грамматического символа Q зависит от атрибута R.s грамматического символа справа.

Продукция	Семантические правила
A → L M	L.i:= l(A.i)
	M.i:= m(L.s)
	A.s:= f(M.s)
A → Q R	R.i:= r(A.i)
	Q.i:= q(R.s)
	A.s:= f(Q.s)

Рис. 58. Синтаксически управляемое определение, не являющееся

L-атрибутным

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

Схема трансляции – это контекстно-свободная грамматика, в ко­торой атрибуты, связанные с символами грамматики, и семантические действия за­ключены в фигурные скобки ({ }) и вставлены в правые части продукций. Схемы трансляции являются удобным способом записи определения трансляции, выполняемой в процессе син­таксического анализа.

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

Схема трансляции, преобразующая инфиксные выражения со сложением и вычитанием в соответствующие постфиксные выражения.

E → TR

R → addop T { print (addop. lexeme)} R₁ | λ

T → num { print (num. val)}

На рис. 59 показано дерево разбора для входной строки 9-5+2, на котором семан­тические действия показаны как дочерние узлы по отношению к узлам, представляющим левые части соответствующих продукций. По сути, действия рассматриваются как тер­минальные символы, что удобно для определения момента выполнения этих действий. Вместо лексем num и addop указываются реальные числа и операция сложения. При выполнении действий в порядке обхода в глубину действия на рис. 59 приводят к вы­воду 95-2 +.

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

Рис. 59. Дерево разбора с семантическими действиями

для выражения 9-5+2

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

Т → T ₁ * Fи семантическое правило T ₁ .vа1:= T ₁val × F.val дают следующую продукцию и семантическое действие.

T → T ₁* F { T.vаl:= T₁.val × F.val}

Если имеются и синтезируемые, и наследуемые атрибуты, необходимо соблюдать следующие правила.

1. Наследуемый атрибут для символа из правой части продукции должен вычисляться в действии перед этим символом.

2. Действие не должно обращаться к синтезируемому атрибуту символа справа от действия.

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

Например, следующая схема трансляции не удовлетворяет первому из трех требований.

S → A ₁ А ₂ { А ₁ .iп:= 1; А₂.iп:= 2 }

А → а {print(А. in)}

При попытке вывести его значение в процессе обхода в глубину дерева разбора входной строки аа наследуемый атрибут А.in во второй продукции не определенОбход в глубину начинается в S и проходит поддеревья A ₁ и А₂ до того, как устанавлива­ются значения A ₁ .iп и А₂.in. Если действие, определяющее значения A ₁ .iп и A ₂ .iп, вставить перед символами А в правой части продукции S— > A ₁ А₂, то А.in будет определено при каждом вызове print(А. in).

Начав с L-атрибутного синтаксически управляемого определения, всегда можно по­строить схему трансляции, удовлетворяющую трем приведенным выше требованиям.

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