Лои. Лекция 2025-10-21

Вступление

Цели семантического анализа

Слово - текст компьютерной программы

1. Проверка корректности программы на более глубоком уровне, чем обычный анализ средствами контекстно-свободных грамматик
2. Сбор и систематизация дополнительной информации о программе
3. Атрибутная грамматика - расширение контекстно-свободной грамматики

Основные понятия

Грамматический символ

В грамматике $G=(\Gamma ,\Sigma ,\_,\_)$ грамматическим символом называется элемент из множества $\Sigma \cup \Gamma$

Link to original

Атрибут грамматического символа

Атрибутом грамматического символа $X$ называется параметр, приписанный $X$ и имеющий название (идентификатор)

Всякому грамматическому символу может соответствовать конечное множество его атрибутов (возможно пустое)

Один и тот же атрибут может быть приписан к разным грамматическим символам (важно совпадение его имени)

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

Link to original

Домен атрибута грамматического символа

Область значений атрибута грамматического символа

Link to original

Для терминального символа $t\in \Sigma$ в качестве атрибута используется только его лексическое значение, хранимое в таблице символов. Имя такого атрибута может быть, например lexval. Тогда факт, что терминальный символ $t$ имеет атрибут с именем $lexval$ записывают следующим образом через точку:

$$t.lexval$$

Для нетерминального символа, например $А\in \Gamma$ его атрибут с именем $val$ может быть записан аналогично:

$$A.val$$

Семантическое правило

Семантическим правилом, поставленным в соответствие правилу вывода $A\to {\alpha }_1{\alpha }_2\dots {\alpha }_n$ контекстно-свободной грамматики $G$, ${\alpha }_i\in (\Sigma \cup \Gamma {)}^{\ast },i\in \{0,1,\dots ,n\}$, называется функциональная зависимость

$$b:=f(c_1,\dots ,c_k)$$

$b,c_1,\dots ,c_k$ - атрибуты грамматических символов из множества $\{A\}\cup \{{\alpha }_i{\}}_{i=1}^n$

Для каждого правила грамматики $G$ существует конечное (возможно пустое) множество семантических правил

Link to original

Выделяют 2 класса атрибутов: синтезируемые и наследуемые

flowchart

Атрибут --> Синтезируемый
Атрибут --> Наследуемый

Синтезируемый атрибут

Атрибут $A.s$ символа $А$ называется синтезируемым, если он вычисляется по семантическому правилу*

$$A.s=f(c_1,\dots ,c_k)$$

поставленным в соответствие правилу вывода $A\to \alpha$ в КС-грамматике $G$

$c_1,\dots ,c_k$ - атрибуты символов, принадлежащих символам из цепочки $\alpha$

Link to original

Наследуемый атрибут

Атрибут $A.i$ символа $А$ называется наследуемым, если он вычисляется по семантическому правилу*

$$A.i=f(c_1,\dots ,c_k)$$

поставленному в соответствие правилу вывода $B\to \alpha A\beta$

$c_1,\dots ,c_k$ - атрибуты символов, принадлежащих символам из цепочек $\alpha ,\beta$ и символу $B$

Link to original

Атрибутная грамматика

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

• Контекстно-свободная грамматика $G$
• Множество атрибутов
• Множество семантических правил

Link to original

Замечание: Грамматику $G$ можно преобразовать в атрибутную многими способами

Контекстно-свободная грамматика легко достраивается до атрибутной добавлением в набор пустого множества атрибутов и пустого множества семантических правил

Аннотированное дерево вывода слова

Аннотированным деревом вывода слова $w\in \Sigma$ атрибутной грамматики $G=(G^{\prime },\_,\_)$ называется дерево вывода слова $w$ в грамматике $G^{\prime }$, где каждому узлу $X$ дерева соответствует список значений атрибутов грамматического символа $X$

Link to original

Замечание:

В аннотированном дереве синтезируемый атрибут $A.s$ зависит от значений атрибутов сыновей узла $A$. Следовательно, значения всех синтезируемых атрибутов вычисляются снизу-вверх. Наследуемый атрибут $A.i$ зависит от значений атрибутов отца узла $A$, или от значений атрибутов братьев узла $A$. Следовательно, его значение вычисляется либо «сверху-вниз», либо комбинированным способом обхода дерева.

Пример построения атрибутной грамматики

стр. 186 из учебного пособия А.Ф. Шура и А.П. Замятина

В качестве КС-грамматики возьмем

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

В качестве множества атрибутов:

• $E.val,T.val,F.val$ - значение арифметического выражения
• $x.val$ - лексическое значение $x$

В качестве множества семантических правил (принято записывать в виде таблицы):

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

Пример построения аннотированного дерева по атрибутной грамматике

По атрибутной грамматике $G$, построенной выше, построим аннотированное дерево вывода арифметического выражения $2+5\ast 3$

дерево вывода

Аннотированное дерево вывода слова