Атрибутний метод визначення семантики програм. Синтезовані та успадковані атрибути. Порядок та правила обчислення атрибутів

Синтаксично кероване визначення — узагальнення контекстно-вільної граматики, в якій кожен граматичний символ має зв`язану множину атрибутів, розділену на дві підмножини, – синтезовані і успадковані атрибути цього граматичного символа.

Атрибут може бути чим завгодно, – строкою, числом, типом, адресою пам`яті і т.д. Значення атрибуту у вузлі дерева розбору визначається семантичними правилами, зв`язаними з використованою в даному вузлі продукцією. Значення синтезованого атрибута у вузлі обчислюється по значеннях атрибутів в нащадках даного вузла; значення успадкованих атрибутів визначається значеннями атрибутів сусдніх (тобто вузлів, що є нащадками по відношенню до батьківського вузла даного) і батьківського вузлів.

Атрибутний метод визначення семантики програм був запропонований Кнутом.

Ідея: з довільною граматикою пов`язана певна множина атрибутів. Значення одного атрибута обчислюється через значення інших атрибутів. Є правила, в котрих для певних атрибутів вводяться константи або певні значення з таблиць.

Для розрахунку атрибутів фіксується процедура (на синт. дереві), наприклад лівосторонній обхід дерева. Якщо атрибутна схема вимагає декілька переглядів дерева, то неефективно.

Проблема: Коректність атрибутної схеми — чи можна для довільного правила побудувати синтаксичне дерево обчислення довільних атрибутів?

Відповідь: Для довільного КВ-граматики не існує алгоритму перевірки коректності атрибутної схеми. Як вихід із положення, Кнут запропонував конкретизацію атрибутів, а саме поділення атрибутів на

1) успадковані (int i,j,k – типи “j” та “k” такі ж, як і у “i”),

2) синтезовані (напр. a+b, синтезовані з “а” та “b” за допомогою “+”).

Обмеження до конкретизації: Доведення атрибуту для даного правила може розраховуватись лише через атрибут, що пов`язаний з цим правилом, а також через атрибути нащадків для правої частини правила.

Висновок:

1) Атрибутну схему з конкретизацією легко перевірити на коректність

2) Атрибутну схему можна розрахувати за 1 перегляд.