Лои. Лекция 2025-11-04

S-атрибутная грамматика

S-атрибутная грамматика

Атрибутная грамматика, все атрибуты которой являются синтезируемыми

Link to original

Проведение семантического анализа для S-атрибутных грамматик

Замечание: естественный способ вычисления синтезируемых атрибутов “снизу-вверх” совпадает с восстановлением “снизу-вверх” дерева вывода при LR-анализе. Следовательно, синтаксическй анализ можно совместить с семантическим анализом

То есть, если имеем бесконфликтный LR-анализатор для S-атрибутной грамматики, то можем за одну работу анализатора (проведение синтаксического анализа) заодно вычислить значения всех атрибутов с использованием того же анализатора (то есть провести семантический анализ)

Чтобы провести вычисление атрибутов при работе анализатора, рядом с основным стеком заводится второй стек $STACK$, в котором будут храниться дополнительная информация для вычисления значения всех атрибутов всех грамматических символов. В нем будут храниться значения атрибутов, необходимые для вычисления.

Модификация алгоритма работы LR-анализатора

Считаем, что для каждого грамматического символа в рассматриваемой S-атрибутной грамматике задан только один атрибут

Логика работы LR-анализатора (правила, по которым меняются конфигурации) не меняются, добавляются лишь новые правила для работы с семантическими полями в записях стека, а именно:

Действия при переносе

Если во время работы анализатора на очередном такте будет выполняться операция перенос $\leftarrow q$, а на каретке в этот момент находится терминал $x$, имеющий “явно заданный” атрибут $lexval$ (лексическое значение терминала):

• $STACK.push(x.lexval)$

Если же

Действия при свертке

Если во время анализатора на очередном такте

• будет выполняться операция свертки по правилу $P=A\to \alpha$
• $r=|\alpha |$
• $f$ - семантическое правило, соответствующее правилу вывода $P$ для вычисления атрибута, связанного с символом $A$

List<AttributeValues> parameters = new ArrayList(r);
for(int i = 0; i < r; i++) {
	parameters.add(STACK.pop());
}
Collections.reverse(parameters);
STACK.push(f(parameters))

Пример проведения семантического анализа для S-атрибутных грамматик

Распишем подробно, как происходит семантический анализ числового выражения w = (2+4)+5*3, которому соответствует слово $w=(x+x)+x\ast x$ в расширенной грамматике:

$$G=\{E^{\prime }\to E,E\to E+T|T,T\to T\ast F|F,F\to (E)|x\}$$

Для этого пронумеруем ее правила вывода:

Номер	Правило вывода
0	$E^{\prime }\to E$
1	$E\to E+T$
2	$E\to T$
3	$T\to T\ast F$
4	$T\to F$
5	$F\to (E)$
6	$F\to x$

Построим LR-анализатор для этой грамматики (не важно какой именно. Главное, что он бесконфликтный)

	ACTION						GOTO
	$+$	$\ast$	$x$	$($	$)$	$⊣$	$E$	$T$	$F$
$E_1$	$\leftarrow +$					​
$T_1$	$\otimes 2$	$\leftarrow \ast$			$\otimes 2$	$\otimes 2$
$F_1$	$\otimes 4$	$\otimes 4$			$\otimes 4$	$\otimes 4$
$($			$\leftarrow x$	$\leftarrow ($			$E_2$	$T_1$	$F_1$
$x$	$\otimes 6$	$\otimes 6$			$\otimes 6$	$\otimes 6$
$+$			$\leftarrow x$	$\leftarrow ($				$T_2$	$F_1$
$\ast$			$\leftarrow x$	$\leftarrow ($		$\leftarrow$			$F_2$
$E_2$	$\leftarrow +$				$\leftarrow )$
$T_2$	$\otimes 1$	$\leftarrow \ast$			$\otimes 1$	$\otimes 1$
$F_2$	$\otimes 3$	$\otimes 3$			$\otimes 3$	$\otimes 3$
$)$	$\otimes 5$	$\otimes 5$
$\nabla$			$\leftarrow x$	$\leftarrow ($			$E_1$	$T_1$	$F_1$

Зададим атрибуты (синтезируемые) и правила для их вычисления:

Номер правила	Правило вывода	Семантическое правило
1	$E\to E_1+T$	$E.ptr=E_1.ptr+T.ptr$
2	$E\to T$	$E.ptr=T.ptr$
3	$T\to T_1\ast F$	$T.ptr=T_1.ptr\ast F.ptr$
4	$T\to F$	$T.ptr=F.ptr$
5	$F\to (E)$	$F.ptr=E.ptr$
6	$F\to x$	$F.ptr=x.ptr$

$x.ptr\stackrel{def}{=}x.lexval$

В случае слова $w$ атрибут $lexval$ имеет символ $x$ и может принимать значения $2,3,4,5$

Такт	Стек	$STACK$	Обрабатываемое слово	Действие	Действия со $STACK$
1	$\nabla$	$\nabla$	$\diamond (2+4)+5\ast 3$	Перенос $\leftarrow ($	Ничего не кладем в стек, так как символ $($ не имеет атрибут $lexval$
2	$\nabla ($	$\nabla$	$(\diamond 2+4)+5\ast 3$	Перенос $\leftarrow x$	Кладем в $STACK$ 2, так как символ $x$ имеет атрибут $lexval$. Здесь атрибут $x.lexval=2$
3	$\nabla (x$	$\nabla 2$	$(2\diamond +4)+5\ast 3$	Свертка $\otimes 6$	Достаем 1 символ из стека и запоминаем. 1, так как правая часть правила $F\to x$, по которому происходит свертка имеет длину 1. Применяем правило 6. В качестве параметра подставляем взятый элемент стека. Результат вычисления кладем в стек
4	$\nabla F_1$	$\nabla 2$	$(2\diamond +4)+5\ast 3$	Свертка $\otimes 4$	Рассуждения, аналогичные такту 3
5	$\nabla T_1$	$\nabla 2$	$(2\diamond +4)+5\ast 3$	Свертка $\otimes 2$	Рассуждения, аналогичные такту 3
6	$\nabla E_1$	$\nabla 2$	$(2\diamond +4)+5\ast 3$	Перенос $\leftarrow +$	Рассуждения, аналогичные такту 1
7	$\nabla E_1+$	$\nabla 2$	$(2+\diamond 4)+5\ast 3$