497
правок
Изменения
Нет описания правки
|definition =
'''Атрибут''' {{---}} дополнительное поле с данными у терминалов и нетерминалов. (Более строгое определение требует ввести систему типов).
}}
{{Определение
|definition =
Дерево разбора, имеющее вычисленные атрибуты в каждом узле, называется '''аннотированным''', а процесс вычисления этих атрибутов - '''аннотированием''' дерева разбора.
}}
$
E \to E + T + E \mid T \\T \to F T \times T F \mid F \\
F \to n \mid (E)
$
{{Определение
|definition =
Грамматика называется '''S-атрибутной''', если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню.
}}
Хотя всегда можно переписать синтаксически управляемое определение таким образом, чтобы использовать только синтезируемые атрибуты, зачастую более удобно и естественно воспользоваться также и наследуемыми атрибутами. При реализаци реализации методом рекурсивного спуска, каждому нетерминалу соответствует некая рекурсивная функция, которая ранее возвращала дерево разбора соответствующего узла. Теперь же функция, соответствующая некоторому нетерминалу $A$, будет принимать в качестве аргументов его наследуемые атрибуты, а возвращать его синтезируемые атрибуты.
T(): '''int'''
T_1.val=T()
consume('*')
F.val=F()
MUL.res = MUL(op1=T1.val, op2=F.val)
'''return''' MUL.res
Заметим, что в рассматриваемой грамматике присутствует левая рекурсия, в связи с чем некоторые наши примеры имеют искусственный характер, хотя и являются наглядными. Левую рекурсию устраним позже.
Распишем все правила, добавив транслирующие символы и ассоциировав с каждым правилом список присваиваний(присваивания помечены троеточием и отступом):
$
val\ E \to E + T\ \{ADD\ res = op_1 + op_2\} \\
{{...}}\ \ \ ADD.op_1=E_1.val \\
{{...}}\ \ \ ADD.op_2=T.val \\
{{...}}\ \ \ E_0.val=ADD.res \\
E \to T \\
{{...}}\ \ \ E.val=T.val \\
val\ T \to T \times F \ \{MUL\ res = op_1 + op_2\} \\
{{...}}\ \ \ MUL.op_1=T.val \\
{{...}}\ \ \ MUL.op_2=F.val \\
{{...}}\ \ \ T_0.val=MUL.res \\
T \to F \\
{{...}}\ \ \ T.val=F.val \\
F \to n \\
{{...}}\ \ \ F.val=n.val \\
F \to (E) \\
{{...}}\ \ \ F.val=E.val \\
$
Рассмотрим, что происходит с атрибутами при [[Устранение_левой_рекурсии| устранения левой рекурсии]] из грамматики.
Пусть есть правила:
$
x\ A \to A \alpha \Leftrightarrow x=g(A_1, \alpha) \\
x\ A \to \beta \Leftrightarrow x=f(\beta)
$
<картинка>
После устранения левой рекурсии:
$
x\ A \to \beta A' \\
x\ A' \to \alpha A' \\
x\ A \to \varepsilon
$
</wikitex>
