Опис та введення граматики

ТЕОРІЯ МОВ ПРОГРАМУВАННЯ ТА МЕТОДИ ТРАСЛЯЦІЇ

АТРИБУТНІ ТРАНСЛЮЮЧІ ГРАМАТИКИ

Методичні вказівки

До виконання лабораторної роботи №2

Для студентів очної форми навчання спеціальності 230105 «Програмне забезпечення обчислювальної техніки

І автоматизованих систем»

Брянськ 2010

Теорії мов програмування та методи трансляції. Атрибутні транслюючі граматики: методичні вказівки до виконання лабораторної роботи №2 для студентів очної форми навчання спеціальності 230105 «Програмне забезпечення обчислювальної техніки та автоматизованих систем». - Брянськ: БДТУ, 2010. - 16 с.

доцент, канд. техн. наук,

МЕТА РОБОТИ

Метою роботи є отримання практичних навичок щодо складання правил атрибутної транслюючої граматики та перевірка їх правильності шляхом моделювання.

Тривалість роботи – 6 годин.

Основні поняття та терміни

Транслюючі граматики дозволяють задавати відповідності між ланцюжками вхідної та вихідної мов, які називають перекладом. Ці відповідності відображають структурні або синтаксичні властивості вхідних та вихідних ланцюжків, проте при спробах їх використання для опису контекстно-залежних умов чи сенсу конструкцій – семантики мов програмування виникають значні труднощі. Тому для завдання семантики застосовуються різні прийоми: W-граматики, віденська метамова, аксіоматичний та денотаційний методи, а також атрибутні транслюючі граматики.

Існує два види запису для пов'язаних із продукціями семантичних правил - синтаксично керовані визначення та схеми трансляції. Синтаксично керовані визначення євисокорівневі специфікації трансляції, що приховують безліч деталей реалізації та звільняють користувача від явної вказівки порядку виконання трансляції. Схеми трансляції вказують порядок, у якому виконуються семантичні правила; отже, ці схеми показують певну частину деталей реалізації. Виконання семантичних правил може генерувати код, зберігати інформацію в таблиці символів, виводити повідомлення про помилки або виконувати інші дії.

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

Семантичні правила визначають залежності між атрибутами, які представляються графом залежності, що визначає порядок виконання семантичних правил, що у свою чергу дає значення атрибутів у вузлах дерева розбору вхідного рядка. Семантичні правила можуть мати і побічні дії, наприклад, виведення значення або зміна глобальної змінної. Дерево розбору, що показує значення атрибутів у кожному вузлі, називаєтьсяанотованим,а процес обчислення значень атрибутів у вузлах дерева -анотуванням дерева розбору.

2.1 Синтезовані атрибути.

У синтаксично керованому визначенні кожна продукція граматикиА→амає пов'язане з нею безліч семантичних правил видуb := f (c1, c2, …, ск),деf- функція,с1, с2,.ск- атрибути граматичних символів продукції, аb— атрибут, що синтезується,Аабо успадкований атрибут одного з граматичних символів правої частини продукції.

У будь-якому разі атрибутb залежитьвід атрибутівс1 с2, . ск.Таким чином,атрибутна граматика є синтаксично керованим визначенням, в якому функції в семантичних правилах не мають побічних ефектів. Функції у семантичних правилах часто записуються як вирази. Можливо, єдина мета семантичного правила в синтаксично керованому визначенні полягає саме у створенні побічного ефекту. Такі семантичні правила записуються як виклики процедур чи фрагменти програм. Їх можна розглядати як правила, що визначають значення фіктивних синтезованих атрибутів нетерміналу у лівій частині пов'язаної продукції; фіктивний атрибут і знак присвоєння = при цьому не вказуються.

Як приклад розглянемо синтаксично кероване визначення програми простого калькулятора. Це визначення пов'язує з кожним з нетерміналівЕ, ТіFцілочисленний синтезований атрибутval.Для кожноїЕ-, Т-таF-продукції семантичне правило обчислює значення атрибутуvalнетерміналу з лівої частини продукції за значеннями атрибутів нетерміналів правої частини.

Продукція Семантичні правила

F→digitF.val := digit.lexval

Лексемаdigit має синтезований атрибутlexval,значення якого надається лексичним аналізатором. Правило, пов'язане з продукцієюL→Еnдля стартового нетерміналуL,є процедурою виведення значення арифметичного виразу, що породжуєтьсяE(це правило можна розглядати як визначальне фіктивний атрибут для нетерміналуL).

У синтаксично керованому визначенні передбачається, що термінали можуть мати тільки атрибути, що синтезуються, оскільки визначення не дає ніяких семантичних правил для терміналів (зазвичай значення атрибутів терміналів надаються лексичним аналізатором). Крім того, якщо інше не зазначено особливо, стартовий символ не має спадкових атрибутів.

Синтаксично кероване визначення, що використовує тільки синтезовані атрибути, називаєтьсяS-атрибутним визначенням.S-атрибутне визначення в прикладі описує калькулятор, що зчитує арифметичний вираз з цифр, дужок , операторів + і *, за яким слідує символ нового рядка n, і виводить значення виразу. Наприклад, отримавши вираз 3*5+4, за яким слідує символ нового рядка, програма виводить значення 19. На рис. 2.1 показано анотоване дерево аналізу для вхідного рядка 3*5+4n. Вихід програми, що друкується в корені дерева, є значенняE.valв першому дочірньому вузлі кореня дерева.

L

n

E.val=19

E.val:=15 T.val=4

T.val = 15 F.val = 4

* digit./ewa/ = 4

T.val = 3 F.val=5

F.val=3 digit.lexval=5

digit.lexval= 3

Мал. 2.1.Анотоване дерево розбору для 3*5+4n.

Розглянемо вузол продукціїT→T*F.Значення атрибутуT.valу цьому вузлі визначається так:

Продукція Семантичне правило

При використанні цього семантичного правила в даному вузліT1.valмає значення 3, отримане від лівого спадкоємця, aF.valзначення 5 отримане від правого спадкоємця. Отже, у цьому вузліT.valстановить 15.

Правило, пов'язане з продукцією для стартового нетерміналуL → Еn, виводить значення виразу, породженогоЕ.

2.2. Успадковані атрибути.

Продукція Семантичні правила

D → TL L.in:= Т.type

T → intТ.type:= integer

T →reaIT.type:=real

addtype(id. entry, L.in)

L→idaddtype(id.entry, L.in)

На рис. 2.2 наведено анотоване дерево розбору для пропозиціїreal id1, id2, id3.

D

T.type = real L.in = real

L.in = real ,id2

Мал. 2.2Дерево розбору з успадкованими атрибутамиinу кожному вузлі, позначеномуL.

Опис та введення граматики

введення

Граматика описується за допомогою нотації Бакус-Наура. Термінальні символи полягають у лапки. Термінальні та нетермінальні символи можуть складатися з кількох літер. Усередині багатолітерних символів не повинні траплятися спеціальні символи, у тому числі пробіли. Правила граматики записуються у вигляді

Кожне визначення нетермінального символу має закінчуватися знаком крапки з комою (;).

У термінальних символах можна використовувати такі позначення:

\r – переклад каретки (символ із кодом 10);

\n - повернення каретки (символ з кодом 13);

\t - Знак табуляції;

\ - знак зворотного слішу;

Атрибутні правила записуються всередині фігурних дужок та поділяються точками зкомою (;). Усередині атрибутних правил звернення до атрибутів записуються як

нетермінальний_символ. назва_атрибута

Самі атрибутні правила мають виглядати так:

У виразах можна використовувати математичні операції «+», «–» , «*» , «/» та операцію об'єднання рядків «&». Крім того, до всіх успішно розібраних нетермінальних символів відразу після їх розбору аналізатор додає атрибутtext, який поміщає ту частину вихідного ланцюжка, яка відповідає нетермінальному символу. Цей атрибут у дереві аналізу прихований (яка частина ланцюжка відповідає нетермінальному символу легко дізнатися, виконавши клацання лівою кнопкою миші по вузлу дерева).

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

Порожні ланцюжки слід задавати нетермінальним символом_EMPTY. Для спрощення завдання непустих буквено-цифрових послідовностей можна використовувати вбудований символ_TEXT.

Листинг 1. Приклад граматики.

[1] VarBlock = VarRule VarBlock;

[2] VarBlock = _EMPTY;

[3] VarRule = Type < Var.type = Type.text; VarList.type = Type.text > '' Var VarList';' SPACE;

[4] VarList = < Var.type = VarList.type; VarList2.type = VarList.type > ',' SPACE Var VarList2;

[5] VarList = _EMPTY;

[8] Number = _TEXT;

[11] SPACE = _EMPTY;

Після того, як граматика набрана, вона повинна бути збережена. Ім'я файлу вибираєтьсядовільно, розширення має бути lat.