додати матеріал

приховати рекламу

Програмно-методичний комплекс для навчання процесу створення компіляторів

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Воткінську ФІЛІЯ ІЖ Г Т У

 

Кафедра Організації обчислювальних процесів і систем управління


До захисту допустити "____"_________ 2003 р

Зав. кафедрою ___________

дипломний проект

Програмно-методичний комплекс для навчання процесу створення компіляторів


ТЕМА:                                                                                                                                   
                                                                                                                                                
                                                                                                                                                

                                                                                                                                                

РОЗРАХУНКОВО - ПОЯСНЮВАЛЬНА ЗАПИСКА


Виконав студент групи Д - 1061 _________ А.І. Кузнєцов

Керівник проекту ст. викладач _________

Консультант з професор, д.т.н. _________
охорони праці
Консультант з еко-доцент, к.т.н. _________
номічного частини
Голова екс-ст. викладач _________
пертной комісії

Воткінськ 2003



Визначення
У цьому дипломному проекті застосовуються такі терміни з відповідними визначеннями.
Асемблер - програма, яка переводить вихідну програму, написану на автокод або мовою асемблера (що, суть, одне і те ж), в об'єктний (виконуваний) код.
БНФ (Бекуса нормальна форма) - граматика, що складається з кінцевого безлічі правил, що визначають в сукупності мову програмування.
Вислів - правила отримання нового значення за допомогою знаків операцій і дужок, приватним випадком виразу може бути просто одиночний елемент, тобто константа або змінна.
Ідентифікатор - ім'я змінної, процедури, функції, програми.
Інструкція - синтаксична структура, що містить ключові, шумові слова та конструкції. Бувають прості та структуровані. Прості інструкції не містять у собі інших вкладених інструкцій (привласнення, GOTO). Структуровані інструкції можуть містити вкладені інструкції (IF <булево вираз> THEN <безумовний оператор> ELSE <оператор>).
Компілятор - системна програма, що виконує перетворення програми, написаної на одному алгоритмічній мові, в програму на мові, близькій до машинного, і в певному сенсі еквівалентну першою.
Лексема - одиниця програми, що виходить в результаті лексичного аналізу, наприклад: for, i, 10, integer, + і т. п.
Лексичний аналіз - виділення у вихідній програмі елементарних складових: ідентифікаторів, обмежувачів, символів операторів, чисел, ключових слів, шумових слів, прогалин, коментарів і т. п.
Літера - будь-який символ, безліч літер складають лексему.
Літерал - чисельне або строкове значення, задане один раз, і не змінюються протягом програми.
Метод операторного передування - висхідний метод граматичного розбору, заснований на аналізі пар послідовно розташованих операторів вихідної програми та вирішенні питання про те, який з них повинен виконуватися першим.
Нетермінальний символ - ім'я конструкції, визначеної всередині граматики.
Рекурсивний спуск - спадний метод граматичного розбору, заснований на тому, що для кожного нетермінального символу, визначеного в граматиці, існує окрема процедура обробки. При цьому в процесі своєї роботи вона може викликати подібні процедури
Семантика мови програмування - це сенс, який закладається в кожну конструкцію мови.
Семантичний аналіз - це перевірка смислової правильності конструкції. Наприклад, якщо ми у вираженні використовуємо змінну, то вона повинна бути визначена раніше по тексту програми, а з цього визначення може бути отримано її тип. Виходячи з типу змінної, можна говорить про допустимість операції з даної змінної.
Семантичний аналіз - у ньому обробляються структури, розпізнані синтаксичним аналізатором, і починає знаходити обриси виконуваний код.
Символьне ім'я - одне з імен, дозволених у мові, яка не є термінальним символом.
Синтаксис мови програмування - це правила складання пропозицій мови з окремих слів. Такими пропозиціями є операції, оператори, визначення функцій та змінних. Особливістю синтаксису є принцип вкладеності (рекурсивность) правил побудови речень. Це значить, що елемент синтаксису мови в своєму визначенні прямо чи опосередковано в одній з його частин містить сам себе. Наприклад, у визначенні оператора циклу тілом циклу є оператор, окремим випадком якого є все той же оператор циклу.
Синтаксичний аналіз (граматичний розбір) - формує синтаксичну одиницю - вираз, інструкцію, виклик підпрограми, декларацію, які далі обробляються семантичним аналізатором. Приклад структури: FOR <вираз> TO int DO <body>.
Синтаксичний розбір - процес отримання дерева синтаксичного розбору на основі заданої граматики.
Сканер (лексичний аналізатор) - програма розпізнавання лексем.
Специфікатор - порядковий номер в таблиці, куди занесена лексема.
Термінальний символ - кінцевий неподільний елемент конструкції мови, є зарезервованим словом (наприклад READ, (, +).
Транслятор - це системна програма, що виконує перетворення програми, написаної на одному алгоритмічній мові, в програму на іншому алгоритмічній мові в певному сенсі еквівалентну першою.

Зміст
"1-3" Вступ ............................................ .................................................. ..... 19
1 Аналіз предметної області .............................................. .................. 20
1.1 Компілятори ................................................ ........................... 20
1.2 Логічна структура компілятора ..................................... 21
1.3 Лексичний аналіз. Сканер ................................................. ... 24
1.4 Синтаксичний і семантичний аналіз .............................. 28
1.5 Граматики ................................................ ............................. 31
1.6 Формування проміжного коду ................................... 34
Метод четвірок ................................................ ..................... 36
1.7 Обгрунтування створення навчального комплексу ............................. 37
1.8 Огляд існуючих розробок .......................................... 38
1.9 Обгрунтування розробки ............................................... ......... 39
2 Створення навчальної розробки .............................................. ............... 42
2.1 Короткий опис навчального компілятора ............................. 42
2.2 Опис навчального мови .............................................. ........... 43
2.3 Лексичний аналізатор LEXAN ............................................ 46
2.3.1 Таблиця термінальних символів .............................. 47
2.3.2 Таблиця символічних імен ..................................... 48
2.3.3 Таблиця літералів ............................................. ......... 49
2.3.4 Робота сканера ............................................. ................ 50
2.3.5 Структура лістингу ............................................. ........ 50
2.3.6 Структура вихідного файлу ...................................... 50
2.3.7 Примірне завдання для студента ............................... 52
2.3.8 Опис роботи лексичного аналізатора ............. 53
2.4 Синтаксичний аналізатор SinAn ........................................ 56
2.4.1 Таблиця переходів ............................................. ......... 56
2.4.2 Правила роботи з таблицею переходів ...................... 60
2.4.3 Правила таблиці переходів для написання програми 62
2.4.4 Формована таблиця переходів. Правила заповнення 65
2.4.5 Правила заповнення формованої таблиці переходів 66
2.4.6 Побудова дерев ............................................. ...... 81
2.4.7 Семантичний аналіз ............................................. .... 83
2.5 Формування проміжного коду ................................... 85
Цикли ................................................. ................................... 85
3 Визначення трудомісткості за стадіями розробки ........................... 89
3.1 Методика розрахунку ............................................... ................... 89
3.2 Визначення витрат на виконання проекту за стадіями розробки 92
3.3 Розрахунок витрат на виконання проекту по етапах .............. 94
4 Рекомендації з охорони праці при роботі з навчальним комплексом. 95
Висновок ................................................. ............................................. 97
Список використаних джерел ............................................... ....... 98
Програми ................................................. ............................................ 99


Введення


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

1 Аналіз предметної області


1.1 Компілятори


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

1.2 Логічна структура компілятора


На малюнку 1 представлена ​​структурна схема компілятора.


Малюнок 1 - Схема компілятора
Вихідна програма - текст програми на мові високого рівня (наприклад Паскаль), який повинен бути переведений в машинний код.
Інформаційні таблиці - самостійні структури, заздалегідь заповнені (таблиця термінальних символів), а також заповнюються в ході лексичного аналізу і доповнюватися під час роботи.
Лексичний аналізатор виконує розпізнавання лексем мови і заміну їх відповідними кодами. Під лексемами розуміються елементарні одиниці, що входять в структуру речення мови, такі як ключові слова, константи, імена і т.п. Правильність завдання структури пропозиції мови на фазі лексичного аналізу не виконується. Результатом є потік лексем (кодів - посилань на таблиці), еквівалентний вихідному тексту.
Синтаксичний аналізатор необхідний для того, щоб з'ясувати, чи задовольняють пропозиції, з яких складається вихідна програма, правилами граматики цієї мови.
Семантичний аналіз. На цьому етапі здійснюється контроль типу та виду всіх ідентифікаторів і інших операндів.
Генерація проміжного коду. Відбувається перетворення вихідної програми в проміжну (наприклад, польську) форму запису.
Оптимізація проміжного коду - виділення загальних подвираженія та обчислення константних подвираженія.
Фаза оптимізації призначена для зменшення надлишковості програми за витратами часу та пам'яті. У залежності від критеріїв проектування транслятора дана фаза обробки програми може виключатися з циклу обробки програми.
Розподіл пам'яті. На цьому етапі виділяються конкретні адреси користувача під змінні, які генеруються компілятором.
Генератор об'єктного (ассемблерного) коду - виконує підстановку кодових зразків на вихідному мовою, відповідних проміжним кодами програми. Генератору коду можуть не турбуватися шаблони, він весь може бути реалізований у процедурному вигляді.
Машинно-залежна компіляція. Залежить від того, які використовуються регістри. Робота цієї процедури залежить від угод, прийнятих для виконуваної частини програми. Наприклад, виділяється базовий регістр для поточної активної запису в стеку.
На всіх цих етапах відбувається робота з різного роду таблицями. Зокрема, для кожного блоку (якщо такі існують у мові) ідентифікатори, описані усередині, запам'ятовуються разом зі своїми атрибутами. Умовно всі ці етапи можна зобразити наступним чином:


Рисунок 2 - Робота з таблицями
Очевидна залежність структури компілятора від структури ЕОМ, точніше, від наявної продуктивності системи. Наприклад, при малій пам'яті збільшується кількість проходів компіляції (т.зв. багатопрохідні компілятори), а при наявності пам'яті великого об'єму можна всі етапи компіляції зробити за один прохід (і тоді ми маємо справу з однопрохідним компілятором).
Необхідно дотримуватися наступні параметри монітора:
- Частота кадрів монітора не повинна бути нижче 75 Гц;
- Повинна бути достатня яскравість і контрастність монітора, щоб була можливість отримання інформації з монітора без напруги для очей;
З ергономічної точки зору необхідно наступне:
- Зручний доступ до дисковода, CD-ROM;
- Зручність роботи з методичною літературою;
- Зручне положення (по висоті) клавіатури, або стілець, регульований по висоті.
Практичні роботи повинні проводитися за комп'ютером на обчислювальному центрі, наприклад аудиторії 205. Загальне освітлення даної аудиторії достатньо для проведення лекцій, але не для роботи за комп'ютером і читанням літератури. Тому потрібне використання додаткового місцевого освітлення.
Для роботи з літературою, наприклад, методичного посібника, потрібний додатковий простір на робочому столі. Його можна звільнити, прибравши зі столу системний блок в стіл і застосувавши спеціальну конструкцію столу, показану на малюнку 7. Стілець має бути обертовим для зручності маневрування, а також з регулюванням по висоті, щоб забезпечити оптимальні умови при роботі з клавіатурою і монітором.
Примірне робоче місце студента показано на малюнку 7.
2
4
5
6
1
3


Малюнок 7 - Робоче місце студента
1 - монітор, 2 - системний блок, 3 - клавіатура, 4 - стілець, 5 - методичний матеріал, 6 - стіл.

Висновок


Результатом виконаної роботи стало створення навчального комплексу складається з двох програм LEXAN і SINAN, відповідно програма лексичного та граматичного розбору. При цьому була розроблена загальна схема компілятора з описом структур та їх взаємодії.
При роботі над проектом були створені алгоритми, що дозволяють виробляти синтаксичний розбір за допомогою таблиць, що дозволяє наочно зрозуміти один із способів формування дерев граматичного розбору.
Розробка включає в себе перші два з чотирьох етапів навчального комплексу по створенню компілятора. Розроблена структура дозволяє реалізувати наступні етапи, тому що визначені подальші напрямки і описані способи взаємодії між етапами. На наступних етапах повинні формуватися проміжний і асемблерний коди.
Даний проект дозволить розібратися студентам з методами аналізу програми і на практиці перевірити знання, отримані при вивченні предмета «Системне програмне забезпечення». Також є основою для подальшої розробки навчального комплексу.
Був виконаний економічний розрахунок, в результаті якого були підраховані загальні витрати на виконання дипломного проекту, вони склали 7000 рублів.

Список використаних джерел


1. Бек Л. Введення в системне програмування.: Пер. з англ. - М.: Світ, 1998.
2. Гріс Д. Конструювання компіляторів для цифрових обчислювальних машин. - М.: Світ, 1975.
3. Карпов В.Е. Класична теорія компіляторів. - Http://itlab.net.ru/ materials / compiler / compiler.html
4. Конспект лекцій з теми "Перекладачі". - Http://www.kulichki.net/ kit / library / transl.zip
5. Креншоу Д. Давайте створимо компілятор! - Http://kit.kulichki.net/ crenshaw / crenshaw.html
6. Лабораторні роботи з курсу Системне ПЗ. - Http://www.fi.ru/ ~ mill / LabFl-97.htm
7. Основи компіляції. http://structur.h1.ru/compil.htm
8. Романов Є.Л. Основи побудови трансляторів. - Http://www.kulichki. net / kit / library / nstu_trans.zip.
9. Пратт Т. Мови програмування. Розробка і реалізація.: Пер. з англ. - М.: Світ, 1979.
10. Типові норми часу на програмування задач для ЕОМ. - М.: Економіка, 1989.
11. Типові норми часу на розробку конструкторської документації. - М.: Економіка, 1991.
12. Фаронов В.В. Турбо Паскаль. Книга1. Основи Турбо Паскаля. - М.: Навчально-інженерний центр «МВТУ-ФЕСТО Дидактика», 1992.
13. Шаньгін В. Ф., Ілюшечкин В. М., Тимофєєв П. А. Програмування мікропроцесорних систем. / Под ред. В. Ф. Шаньгіна. - М.: Вищ. шк., 1990.

Додаток А
Приклад виконання завдання по роботі зі сканером LEXAN
Дана наступна граматика мови:
1. <prog>:: = PROGRAM <prog-name> VAR <dec-list> BEGIN <stmt-list> END.
2. <prog-name>:: = id
3. <dec-list>:: = <dec> | <dec-list>; <dec>
4. <dec>:: = <id-list>: <type>
5. <type>:: = INTEGER
6. <id-list>:: = id | <id-list>, id
7. <stmt-list>:: = <stmt> | <stmt-list>; <stmt>
8. <stmt>:: = <assign> | <for>
9. <assign>:: = id: = <exp>
10. <exp>:: = <term> | <exp> + <term> | <exp> - <term>
11. <term>:: = id | int | (<exp>)
12. <for>:: = FOR <index-exp> DO <body>
13. <index-exp>:: = id: = <exp> TO <exp>
14. <body>:: = <stmt> | BEGIN <begin-list> END
Використовуючи програму LEXAN зробити наступні дії:
1. Вибрати елементи з таблиці термінальних символів, при бажанні можна змінити назви ключових слів (таблиця 1);
2. Написати вихідний текст на навчальному мовою з використанням заданої граматики;
3. Заповнити таблиці: - символьних імен (таблиця 2);
- Літералів (таблиця 3);
- Лексичного аналізу (вихідних символів);
4. Перевірити правильність заповнення таблиць вбудованим аналізатором;
5. При наявності помилок, виправити наявні, і повторно обробити програмою LEXAN;
6. Отримати лістинг отриманих результатів.
7. Зберегти результат у файл.
Спочатку проводиться аналіз, які термінальні символи входять в граматику: "PROGRAM", "VAR", "BEGIN", "END", ".", "INTEGER", ";", ":=", "+", "- "," FOR "," DO "," TO ".
Вихідна програма, написана з використанням термінів вихідної граматики:
program prog1;
var
i, x: integer;
begin
x: = 0;
for i: = 1 to 10 do
x: = x + i;
end.
Далі вибираються термінальні символи, використані в програмі, заповнюється таблиця вибраних термінальних символів. Приблизне уявлення таблиці вибраних термінальних символів показано в таблиці 19.
Таблиця 19
№ стор
Термінальний символ
Коментар (позначення)
Код
1
PROGRAM

1
2
;

27
3
VAR

2
4
,

29

Продовження таблиці 19
№ стор
Термінальний символ
Коментар (позначення)
Код
5
:

31
6
INTEGER

5
7
BEGIN

3
8
: =

28
9
FOR

8
10
TO

9
11
DO

10
12
+

32
13
END

4
14
.

30

Визначаються символічні імена, що зустрічаються в програмі, і заповнюється таблиця 20 в порядку їх появи в тексті
Таблиця 20
Специф
Ідентифікатор
Тип
Розмір, яку він обіймав в пам'яті, байт
Відносний адреса в пам'яті
1
prog1



2
i



3
x




У тексті визначаються літерали і заносяться в таблицю 21 в порядку їх появи.
Таблиця 21
Специф
Літерал
Тип
Розмір, яку він обіймав в пам'яті, байт
1
0
Integer
2
2
1
Integer
2
3
10
Integer
2

Під час заповнення цих трьох таблиць заповнюється четверта - таблиця 22 (таблиця вихідних кодів лексем): у полі «Таблиця» підставляються номери таблиць (таблиця термінальних символів - № 1, таблиця символічних імен - № 2, таблиця літералів - № 3), в полі рядок - код елемента (з таблиці 1), специфікатор (з таблиці 2 і 3). Поле «№ п.п.» заповнюється автоматично.

Таблиця 22
№ п.п.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Таблиця
1
2
1
1
2
1
2
1
1
1
1
2
1
3
1
Рядок
1
1
27
2
2
29
3
31
5
27
3
3
28
1
27

№ п.п.
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Таблиця
1
№ п.п.
Термінальний символ
Коментар (позначення)
1
PROGRAM
Тема програми
2
VAR
Опис змінних
3
BEGIN
Початок тіла програми
4
END
Кінець тіла програми
5
INTEGER
Цілий тип даних
6
FOR
Лічильний оператор циклу (для)
7
TO
Ключове слово рахункового оператора циклу (до)
8
DO
Ключове слово (виконати)

Продовження таблиці 1
№ п.п.
Термінальний символ
Коментар (позначення)
9
WHILE
Оператор циклу з передумовою (поки що)
10
DIV
Розподіл цілочисельне
11
MOD
Залишок від цілочисельного ділення
12
AND
Логічне І
13
OR
Логічне АБО
14
: =
Присвоїти значення

Спочатку заповнюється таблиця лексем (термінальних символів), потім починається зчитування та обробка вхідного тексту програми користувача. При роботі сканера відбувається заповнення таблиць символічних імен та літералів.
Дані таблиці можуть виглядати наступним чином:
Таблиця 2 - Таблиця символічних імен
№ п.п.
Ідентифікатор
Тип
Розмір, яку він обіймав в пам'яті, байт
Відносний адреса в пам'яті
1
I
INTEGER


2
Y
REAL


3
X1
REAL


...





Таблиця 3 - Таблиця літералів
№ п.п.
Літерал
Тип
Розмір, яку він обіймав в пам'яті, байт
Відносний адреса в пам'яті
1
1
INTEGER
2
0
2
100
INTEGER
2
2
...





Результатом роботи сканера є послідовність кодів лексем. Кожен код лексеми зазвичай представляється кодом таблиці і специфікатором (порядковий номер в таблиці, куди занесена лексема). Це дозволяє уникнути додаткового пошуку за таблицями на наступних етапах трансляції. Наприклад в результаті обробки сканером наступного речення мови Паскаль
FOR I: = 1 TO 100 DO Y: = X1
буде отримана рядок:
<1,06> <2,1> <1,14> <3,1> <1,07> <3,2> <1,08> <2,2> <1,14> <2,3> ,
де в кутових дужках пара чисел задає код таблиці і специфікатор. Можна оформити і у вигляді таблиці.
Таблиця 4 - Таблиця вихідних символів
№ п.п.
1
2
3
4
5
6
7
8
9
10
Таблиця
1
2
1
3
1
3
1
2
1
2
Рядок
6
1
14
1
7
2
8
2
14
3

Функціонально в сканері можуть бути виділені наступні модулі [4]:
1) виділення з вхідного рядка чергового слова;
2) пошук в таблицях лексем та визначення коду лексеми;
3) формування та виведення вихідний рядка.
Для модуля виділення слова важлива інформація про те, які символи можуть бути ознаками початку або кінця слова. Наприклад, у мові Паскаль ключові слова відокремлюються від інших елементів пропозиції пробілами. Складніше йде справа з виділенням ідентифікаторів і чисел, оскільки роздільником для них може служити будь-який інший символ, що не входить за визначенням в ідентифікатор або число.
При заповненні таблиць виконується перевірка на наявність в ній елемента, що збігається з виділеним ідентифікатором або константою, і при збігу занесення у таблицю не виконується.
До завдань останнього модуля входить занесення у вихідну рядок кодів лексем.
На додаток до своєї основної функції, розпізнаванню лексем, сканер зазвичай також виконує читання рядків вихідної програми і, можливо, друк лістингу вихідної програми. Коментарі ігноруються сканером, за винятком того випадку, коли вони повинні бути надруковані і, таким чином, ефективно віддаляються з вихідної програми до початку процесу граматичного розбору.
Наступною стадією аналізу є синтаксичний розбір.
Лексичний та синтаксичний аналізатори взаємодіють між собою. Існує два основних способи взаємодії:
1) реалізується на основі прямого лексичного аналізу. Від синтаксичного аналізатора надходить запит «дати лексему» і вказується тип лексеми;
2) непрямий лексичний аналіз. Синтаксичний аналізатор видає запит «дати лексему», тип лексеми не вказується. Ні вирішального блоку, вважаємо, що працює група паралельних автоматів.

1.4 Синтаксичний і семантичний аналіз


Синтаксичний аналіз - це процес, в якому досліджується ланцюжок лексем і встановлюється, чи задовольняє вона структурним умов, явно сформульованим у визначенні синтаксису мови. Це - найскладніша частина компілятора.
Синтаксичний аналізатор розчленовує вихідну програму на складові частини, формує її внутрішнє представлення, заносить інформацію в таблицю символів та інші таблиці. При цьому проводиться повний синтаксичний і, по можливості, семантичний контроль програми. Фактично, це - синтаксично керована програма. При цьому зазвичай прагнуть відокремити синтаксис від семантики наскільки це можливо - коли синтаксичний аналізатор розпізнає конструкцію вихідного мови, він викликає семантичну процедуру, яка контролює цю конструкцію, заносить інформацію куди треба, перевіряє на дублювання опису змінних, перевіряє відповідність типів і т.п.
Процес синтаксичного аналізу може розглядатися як побудова дерева граматичного розбору для трансльованих пропозицій. Граматики можуть використовуватися як для породження так і для розпізнавання речень мови. Породження починається з початкового поняття (або аксіоми граматики). При розпізнаванні з допомогою граматичних правил породжується пропозицію, яка потім порівнюється з вхідними рядком. При цьому застосування правил підстановки для породження чергового символу пропозиції залежить від результатів порівняння попередніх символів з відповідними символами вхідного рядка. Результат аналізу вихідного пропозиції в термінах граматичних конструкцій зручно представляти у вигляді дерева. Такі дерева зазвичай називаються деревами граматичного розбору або синтаксичними деревами. На малюнку 3 зображено дерево граматичного розбору для пропозиції READ (VALUE).
<read>
READ (id)
{VALUE}

Рисунок 3 - Дерево граматичного розбору
Методи граматичного розбору розбиваються на два великих класи висхідні та низхідні - відповідно до порядку побудови дерева граматичного розбору. Спадні (методи зверху-вниз) починаються з аксіоми граматики, з кореня дерева і намагаються так його нарощувати, щоб наступні вузли дерева відповідали синтаксису аналізованого виразу. Висхідні (методи знизу-вверх) починають з елементів пропозиції (з "листя") і відшукують у граматиці якого поняття вони відповідають, тобто визначають батьківську вершину для цих елементів, і т.д. поки не приходять до кореня дерева (аксіомі граматики). У сучасних компіляторах застосовуються як спадні, так і висхідні методи.
Перевагою висхідного методу є його безсумнівна простота, а також висока швидкість виконання (не витрачається час на пошук правила редукції).
Проте всі ці достоїнства геть меркнуть перед головним недоліком даного методу. Справа в тому, що тут практично відсутня яка б то не була діагностика (і тим більше - локалізація) помилок. По-друге, деякі помилки у вихідному виразі не діагностуються зовсім. Наприклад, вирази, в яких зустрічаються йдуть підряд дужки "(" і ")".
Тому при подальшому розгляді буде розглядатися спадний розбір, як найбільш придатний метод при ручному написанні компілятора [4].
Крім цього, алгоритми синтаксичного (граматичного) розбору (контролю) ділять на синтаксично-орієнтовані та синтаксично-неорієнтовані. Синтаксично-орієнтовані алгоритми є універсальними для деякого сімейства мов і перехід до розпізнавання пропозицій іншої мови виконується шляхом зміни граматики, тобто граматика виконує роль якоїсь "програми" розпізнавання речень мови. Головною перевагою цього класу алгоритмів є їх універсальність, а недоліком - наявність надмірності внаслідок орієнтації на сімейство мов.
Синтаксично-неоpіентіpованние алгоритми відрізняються тим, що порядок дій у них визначається правилами граматики даного конкретного мови. Перевагою цього класу алгоритмів є відсутність надмірності, а недоліком - неможливість перенастроювання на розпізнавання пропозицій іншої мови.
Надалі ми будемо працювати з синтаксично-неорієнтованим алгоритмами, тому що будемо працювати лише з однією мовою - навчальний мову на основі мови Паскаль.

1.5 Граматики


Граматика мови програмування є формальним описом його синтаксису або форми, в якій записані окремі пропозиції програми або вся програма. Граматика не описує семантику або значення різних пропозицій. Інформація про семантику міститься у програмах генерації об'єктного коду. В якості ілюстрації різниці між синтаксисом і семантикою розглянемо дві пропозиції:
I: = J + K
і
I: = X + Y
де Х і Y є дійсними змінними, a I, J, К - цілими змінними. Ці дві пропозиції мають однаковий синтаксис. Обидва є операторами присвоювання, в яких привласнюється значення визначається виразом, що складається з двох імен змінних, розділених оператором складання. Однак семантика цих двох пропозицій абсолютно різна. Перше речення говорить про те, що змінні у виразі повинні бути складені з використанням цілих арифметичних операцій, а результат складання повинен бути присвоєний змінній I. Друга пропозиція задає додавання з плаваючою точкою, результат якого має бути перетворений в ціле число перед присвоюванням. Очевидно, ці дві пропозиції будуть скомпільовані в різні послідовності машинних команд, хоча їх граматичне опис однаково. Відмінності між ними виявляться на етапі генерації об'єктного коду.
На малюнку 4 показані БНФ граматики, використовувані в дипломному проекті. Підкреслені хвилястою лінією елементи можуть опускатися (не використовуватися).
1. <prog>:: = PROGRAM <prog-name> VAR <dec-list> BEGIN <stmt-list> END.
2. <prog-name>:: = id   ;
3. <dec-list>:: = <dec> {; <dec>};
4. <dec>:: = <id-list>: <type>
5. <type>:: = INTEGER | REAL | STRING
6. <id-list>:: = id {, id}
7. <stmt-list>:: = <stmt> {; <stmt>};
8. <stmt>:: = <assign> | <for> | <read> | <write> | <while> | <repeat> | <if>
9. <assign>:: = id: = <exp>
10. <exp>:: = - <term> {+ <term> | - <term>}
11. <term>:: = <factor> {* <factor> | DIV <factor> | / <factor>}
12. <factor>:: = id | int | real | <text-val> | (<exp>)
13. <read>:: = READ (<id-list>)
14. <write>:: = WRITE (<value> {, <value>})
15. <for>:: = FOR <index-exp> DO <body>
16. <index-exp>:: = id: = <exp> TO | DOWNTO <exp>
17. <body>:: = <stmt> | BEGIN <stmt-list> END
18. <value>:: = <id-list> | <text-val>
19. <text-val>:: = '<text>'
20. <text>:: = string
21. <if>:: = IF <порівняння>; THEN <body> ELSE <body>
22. <Порівняння>:: = <factor> <умова> <factor>
23. <Умова>:: => | <| = |> = | <= | <>
24. <while>:: = WHILE <порівняння> DO <body>
25. <repeat>:: = REPEAT <body> UNTIL <порівняння>
Рисунок 4 - Спрощена граматика мови Паскаль
Існує кілька різних форм запису граматик, серед яких ми розглянемо форму Бекуса-Наура (БНФ). БНФ не саме потужне з відомих засобів опису синтаксису. Проте ця форма досить проста, широко використовується і надавати відповідні для більшості додатків кошти. На рис.4 зображена одна з можливих граматик БНФ.
Граматика БНФ складається з безлічі правил виведення, кожне з яких визначає синтаксис деякої конструкції мови програмування. Розглянемо, наприклад, правило 13 на рис. 4:
<read>:: = READ (<id-list>)
Це визначення синтаксису пропозиції READ мови Паскаль, що зазначена у граматиці як <read>. Символ:: = можна читати як «є за визначенням». З лівого боку від цього символу знаходиться обумовлена ​​конструкція мови (у нашому випадку-<read>), а з правої-опис синтаксису цієї конструкції. Рядки символів, укладені в кутові дужки <і>, називаються нетермінальним символами (тобто є іменами конструкцій, певними всередині граматики). Те, що не укладено в кутові дужки, називається термінальними символами граматики (лексемами). У цьому правилі виводу нетермінальним символами є <read> і <id-list>. Термінальними символами є лексеми READ, (,). Таким чином, це правило визначає, що конструкція <read> складається з лексеми READ, за якою слідує лексема (, за нею йде конструкція мови, звана <id-list>, за якою слідує лексема). Прогалини при описі граматичних правил не істотні і вставляються лише для наочності.
Для розпізнавання нетермінального символу <read> необхідно щоб було визначення для нетермінального символу <id-list>. Це визначення дається правилом 6 на рис. 4:
<id-list>:: = id {, id}
Ця нотація, означає, що конструкція, укладена у фігурні дужки, може бути або опущена, або повторюватися один або більше число разів. Таким чином, правило 6 визначає нетермінальний символ <id-list> як складається з єдиної лексеми id або ж з довільного числа наступних один за одним лексем id, розділених комою. Відповідно до цього новим визначенням процедура, відповідна нетермінальному символу <id-list>, спочатку шукає лексему id, а потім продовжує сканувати вхідний текст до тих пір, поки наступна пара лексем не співпаде з комою і id. Такий запис усуває проблему лівої рекурсії.

1.6 Формування проміжного коду


Можливі різні форми внутрішнього подання синтаксичних конструкцій вихідної програми в компіляторі. Дерево граматичного розбору виявляється незручним у роботі при роботі при генерації й оптимізації об'єктного коду. Тому перед оптимізацією і безпосередньо генерацією об'єктного коду внутрішнє представлення програми перетвориться в одну з відповідних форм запису.
Прикладами таких форм запису є:
- Зворотна польський запис операцій;
- Тетради операцій;
- Тріади операцій;
- Власне команди асемблера.
Зворотний польський запис - це постфіксній запис операцій. Перевагою її є те, що всі операції записуються безпосередньо в порядку їх виконання. Вона надзвичайно ефективна в тих випадках, коли для обчислень використовується стек.
Тетради представляють собою запис операцій у формі з чотирьох складових:
<Операція> (<операнд1>, <операнд2>, <результат>).
Тетради використовуються рідко, так як вимагають більше пам'яті для свого представлення, ніж тріади, не відображають взаємозв'язку операцій і, крім того, погано відображаються в команди асемблера і машинні коди, тому що в наборах команд більшості сучасних машин не зустрічаються операції з трьома операндами.
Тріади представляють собою запис операцій у формі з трьох складових: <операція> (<операнд1>, <операнд2>), при цьому один або обидва операнди можуть бути посиланнями на іншу тріаду в тому випадку, якщо в якості операнда даної тріади виступає результат виконання іншою тріади. Тому тріади при записі послідовно номеруют для зручності вказівки посилань одних тріад на інші. Наприклад, вираз A: = B * C + D - B * 10, записане у вигляді тріад буде мати вигляд:
1) * (B, C)
2) + (^ 1, D)
3) * (B, 10)
4) - (^ 2, ^ 3)
5): = (A, ^ 4)
Тут операції позначені відповідним знаком (при цьому присвоєння також є операцією), а знак ^ означає посилання операнда однієї тріади на результат інший.
Команди асемблера зручні тим, що при їх використанні внутрішнє представлення програми повністю відповідає об'єктного коду і складні перетворення не потрібні. Проте використання команд асемблера вимагає додаткових структур для відображення їх взаємозв'язку. Крім того, внутрішнє представлення програми виходить залежним від результуючого коду, а це значить, що при орієнтації компілятора на інший результуючий код потрібно перебудовувати як саме внутрішнє представлення програми, так і методи його обробки в алгоритмах оптимізації (при використанні тріад або тетрад цього не потрібно) .
Для побудови внутрішнього подання об'єктного коду (надалі - просто коду) по дереву висновку може використовуватися найпростіша рекурсивна процедура. Ця процедура перш за все повинна визначити тип вузла дерева - він відповідає типу операції, символ якої знаходиться в листі дерева для поточного вузла. Цей лист є середнім листом вузла дерева для бінарних операцій і крайнім лівим листом - для унарних операцій. Після визначення типу процедура будує код для вузла дерева відповідно до типу операції. Якщо всі вузли наступного рівня для поточного вузла є листя дерева, то в код включаються операнди, що відповідають цим листю, і код, стає результатом виконання процедури. Інакше процедура повинна рекурсивно викликати сама себе для генерації коду нижележащих вузлів дерева і результат виконання включити в свій породжений код.
Тому для побудови внутрішнього подання об'єктного коду по дереву виведення в першу чергу необхідно розробити форми подання об'єктного коду для чотирьох випадків, відповідних видів поточного вузла дерева виведення:
обидва нижележащих вузла дерева - листя (термінальні символи граматики);
тільки лівий нижележащий вузол є листом дерева;
тільки правий нижележащий вузол є листом дерева:
обидва нижележащих вузла не є листям дерева.

Метод четвірок


Кожна четвірка записується у вигляді:
операція, op1, op2, результат,
де операція - це виконувана об'єктним кодом функція
op1, op2 - операнди цієї операції
Наприклад,
(-A + b) * (c + d)
буде відповідати такій послідовності четвірок
- A, T1
+ T1, b T2
+ C, d T3
* T2, T3, T4
З сформованих четвірок неважко згенерувати машинний код.

1.7 Обгрунтування створення навчального комплексу


Створення навчального комплексу обгрунтовано складністю предметної області створення компіляторів і відсутністю подібного наочного матеріалу, що дозволяє поетапно відстежити процеси, що відбуваються в компіляторі (робота аналізаторів, заповнення таблиць).
З описаного вище матеріалу видно, що компілятори мають дуже багато варіантів побудови, це визначає додаткову складність при виборі оптимальної структури компілятора. Процес компіляції досить складний і важкий для сприйняття в цілому. Він містить у собі безліч понять, підходів обробки, методів розбору, таблиць, формальні граматики. Тому доцільно розбиття комплексу на ряд лабораторних робіт, в яких будуть описані практичні методики вивчення різних етапів компіляції на основі спеціальних навчальних програм.

1.8 Огляд існуючих розробок


На поточний момент існує безліч розробок, пов'язаних зі створенням компіляторів. В основному це методичні, навчальні посібники з проектування компіляторів, де розглядаються основні принципи аналізу тексту програми і синтезу об'єктного коду. В основному в цих матеріалах наводяться приклади як написати оптимальну програму компіляції за швидкістю, використовуючи стеки, таблиці передування і т.п. структури, що не дозволяють або ускладнюють передавати дані між етапами як потрібно в навчальному комплексі.
Робота з методичним (теоретичним) матеріалом увазі виконання завдання з подальшою перевіркою викладачем, що витрачає його час і сили. Програмна реалізація дає можливість самому проконтролювати себе на правильність проведеного аналізу або коректність синтезованого коду.
Керівництво з написання компіляторів Креншоу [5] дозволяє створити свій компілятор, але його особливістю є прямий переклад зчитаного тексту у вихідний код, що не дає наочності внутрішнього подання компілятора. Цей компілятор є однопрохідним, він не зберігає і створює в пам'яті таблиць, вся обробка описується в процедурах.
Існуючі компілятори не дають наочне уявлення внутрішніх структур, а зазвичай мають один виконуваний файл, який реалізує переклад тексту програми в об'єктний або виконуваний файл. Ставка зазвичай робиться або на швидкість компіляції, або на мінімальний розмір генерованого файлу.
Компілятори компіляторів в основній своїй масі створюють лише лексичні аналізатори, залишаючи допрацьовувати синтаксичну частину самому програмісту. При огляді не було знайдено російських розробок компіляторів компіляторів, що так само говорить про те, що при роботі з існуючими розробками додасться ще одна проблема - проблема мови.

1.9 Обгрунтування розробки


Розробка є навчальним комплексом, що включає в себе лабораторні роботи з вивчення процесу компіляції. Це програма, що дозволяє без керівника виконувати і перевіряти видані завдання (перевіряти виконані завдання). Теоретичний матеріал для проведення лабораторної роботи сформований у методичній (описової) частини.
Особливість даної розробки в тому, що спроектований компілятор побудований поетапно (модульно). Результат роботи кожного з етапів може бути зафіксований (збережено) у вигляді файлу з певною структурою. Це файл з проміжним кодом, що отримується від сканера, файл з формованої таблицею переходів (зберігає структуру дерева), файл з проміжним кодом (тетради), асемблерний код. На кожному з етапів є можливість генерації файлу звіту зі структурами, з описом і зазначенням помилок, а також додаткової службовою інформацією.
Даний комплекс служить для ознайомлення з принципами компіляції, отримання практичних навичок лексичного аналізу та граматичного розбору (синтаксичний аналіз), формування проміжного коду. Комплекс побудований таким чином, щоб по можливості охопити всі етапи компіляції, наочно представляючи формовані таблиці.
При проектуванні (розробці, плануванні) комплексу ставка робилася на наочність, що відбуваються і доступність для розуміння правил формування і заповнення безлічі таблиць. При роботі з програмним продуктом не показано роботу зі стеком, тому що вся реалізація, весь аналіз відбувається тільки з таблицями і тільки в таблицях, виняток становить хіба що вхідний текст програми і вихідний код.
Навчальний посібник складається з:
- Вступної частини (теоретичні відомості):
1) опис компіляторів, їх суть, призначення;
2) лексичний аналізатор (сканер);
3) синтаксичний аналізатор, дерево граматичного розбору;
4) отримання проміжного коду;
- Практичній (робота з програмами):
1) огляд компіляторів (Паскаль, C, Delphi);
2) робота з програмою LexAn;
3) робота з програмою SinAn;
4) робота з програмою SinAn;
- Перевірка отриманих знань за допомогою контрольних запитань і завдань.
Навчальний комплекс служить для полегшення роботи викладача, можливості самостійно вивчення матеріалу, отримання практичних навичок з дисципліни, що вивчається, можливості більш наочного подання інформації тощо
Навчальний комплекс включає в себе кілька взаємопов'язаних лабораторних робіт, що охоплюють всю предметну область або основну її частину, наприклад навчання процесу компіляції. При цьому при виконанні кожної лабораторної роботи відбувається поетапне вивчення предметної області.
Лабораторні роботи зазвичай включає в себе:
- Теоретичні відомості;
- Порядок виконання роботи;
- Контрольні запитання та завдання.
Теоретичні відомості дають уявлення про досліджуваної області, ознайомлення з її основними принципами, структурами і характерними особливостями. При цьому часто проводиться розбір якого-небудь наочного прикладу.
Для проведення лабораторних робіт можуть використовуватися різні технічні засоби. Це можуть бути різного роду стенди, що імітують роботу реальних пристроїв, самі пристрої, які виступають в ролі досліджуваного об'єкта, комп'ютер, з набором необхідних для роботи програм, а також інші пристрої й устаткування, що підходять для цієї мети.
Використання в лабораторних роботах обладнання дозволяє отримувати додаткові практичні навички, коли студент може впливати на роботу досліджуваного об'єкта, змінюючи різні вхідні і керуючі параметри. При цьому учень краще розуміє всю картину того, що відбувається, досліджувані процеси.
Під час виконання лабораторних робіт часто доводиться знімати показання з приладів, отримувати різні дані від датчиків, програм тощо, заносити їх в таблиці і обробляти відповідним чином. При цьому проводяться розрахунки, пов'язані з роботою, оформляється звіт, який і здається викладачу на перевірку.
Контрольні питання формують виходячи з мети проведення лабораторної роботи й того, що повинен винести навчається в результаті її виконання: визначення терміни, поняття, пов'язані з досліджуваним об'єктом, принципи його роботи, будову.

2 Створення навчальної розробки


2.1 Короткий опис навчального компілятора


Навчальний компілятор складається з чотирьох окремих модулів, це:
1) лексичний аналізатор (сканер) LEXAN;
2) синтаксичний аналізатор (парсер) SYNAN;
3) генератор проміжного коду PROMKOD;
4) генератор ассемблерного коду ASMKOD.
На даному етапі реалізовані перші два. Ці модулі (етапи) взаємодіють між собою за допомогою проміжних файлів.
Середа LEXAN генерує файл з розширенням LEX, в якому зберігаються таблиці, отримані в результаті розбору тексту програми: таблиця вибраних термінальних символів, таблиця символічних імен, таблиця лексем і таблиця вихідних кодів лексем, яка і являє собою програму у вигляді посилань на три попередні таблиці. Даний файл є вхідним на етапі синтаксичного аналізу.
Середа SINAN генерує файл з розширенням SYN, що зберігає в собі формовану таблицю переходів, що представляє собою граматичне дерево в табличному вигляді. У цьому ж файлі зберігаються таблиці вибраних термінальних символів, символічних імен і лексем. Даний файл є вхідним на етапі генерації проміжного коду.
Середа PROMKOD генерує файл PRK, що зберігає в собі спрощене дерево граматичного розбору, представлене у вигляді таблиці тріад.
Середа ASMKOD генерує файл ASK, що представляє собою програму на асемблері.
У результаті проведеного аналізу було обрано багатопрохідних схема перегляду компілятора. На кожному етапі (лексичний аналіз, синтаксичний аналіз, формування проміжного коду, формування ассемблерного коду) відбувається новий перегляд (прохід) за програмою, представленої в різному вигляді. На першому етапі (сканер) - у вигляді тексту програми, на другому (парсер) - у вигляді кодів лексем, на третьому - дерево граматичного розбору, на четвертому - таблиця проміжного коду. Це зроблено для поетапного навчання процесу компіляції і можливості роботи з внутрішнім поданням програми.
Всі дані, крім вхідного тексту програми поміщаються в таблиці. Це зроблено для того, щоб не використовувати стек і всі дані представляти по можливості в одному місці.
При виборі мови високого рівня, як вхідна мова для аналізу був прийнятий навчальний мову, заснований на спрощеному варіанті мови Паскаль. Мова Паскаль є досить поширеним, досить зрозумілим і простим для сприйняття, до того ж його структури досить зручні для розбору. Опис навчального мови наведено нижче.

2.2 Опис навчального мови


Навчальний мова побудована на основі мови Паскаль.
Алфавіт навчальному мови включає літери, цифри, спеціальні символи і зареєстровані слова.
Букви - це букви латинського алфавіту від а до я, від А до Я, від a до z, і від A до Z. У даній мові нема різниці між великими та малими буквами алфавіту, якщо тільки вони не входять в символьні і рядкові вирази.
Цифри - арабські цифри від 0 до 9.
Спеціальні знаки навчального мови - це символи:
+ - * / =,. :; <> {} [] ()
До спеціальних знаків також належать такі пари символів:
<> <=> =: =
в програмі ці символи не можна розділяти пробілами, якщо вони використовуються як знаки операцій відносини.
Особливе місце в алфавіті мови посідають прогалини. Ці символи розглядаються як обмежувачі ідентифікаторів, констант, чисел, зарезервованих слів. Кілька наступних один за одним прогалин вважаються одним пропуском.
У навчальному мові є такі зарезервовані слова:

and
begin
div
do
downto
else
end
for
function
if
integer
procedure
program
real
repeat
string
then
to
until
var
while
write
read


Їх можна змінювати при побудові компілятора у відповідній програмному середовищі LEXAN.
Ідентифікатори - імена змінних, процедур, функцій, програм. Довжина ідентифікатора обмежена 255 символами. Ідентифікатор завжди починається буквою або знаком підкреслення, за яким можуть слідувати літери, цифри і знак підкреслення. Прогалини і спеціальні символи не можуть входити в ідентифікатор.
Константи.
Послідовність, що складається з однієї або більше цифр 0, 1, ..., 9, є цілою (INTEGER) константою. Даний тип займає в пам'яті 2 байта. Послідовність цифр, розділених крапкою, є речовинної (REAL) константою, даний тип займає в пам'яті 4 байта. Послідовність будь-яких символів (крім знака одинарних лапок), укладених в одинарні лапки, є строковою (STRING) константою, довжина даного типу варіюється від 1 до 255 байт, в залежності від кількості символів в послідовності.
Вирази.
Операції у вираженні виконуються зліва направо; як звичайно, враховується наявність дужок і пріоритети операторів. Пріоритети операторів наведені в таблиці 5 (оператор в першому рядку має найвищий пріоритет):
Таблиця 5 - Таблиця пріоритетів
- (Унарний)
* / Div
+ - (Бінарний)
= <> <> <=> =

Ключові слова, ідентифікатори, лексеми відокремлюються один від одного пробілами, від спеціальних символів поділ не обов'язково.
Можливі для використання символи:
літери: а .. я, А.. Я, a.. z, A.. Z;
символ, дозволений при написанні імен: _
елементи поділу:,;: пробіл
роздільник цілої та дробової частин в дійсних числах:.
виділення тексту: '
знаки операторів: + - * /
коментарі: {}
розстановка пріоритетів: ()
знаки порівняння:> <=> = <= <>
ознака закінчення програми:.

2.3 Лексичний аналізатор LEXAN


Мета створення програми LEXAN полягає в тому, щоб навчити студента виробляти розбір тексту програми на складові її лексеми, відповідно до вказаної БНФ, при цьому правильно заповнивши таблиці вибраних термінальних символів, символічних імен, літералів і вихідних кодів лексем.
Дане середовище дозволяє порівняти дані, внесені студентом з даними, отриманими програмою і згенерувати повідомлення про помилки, на основі яких студент буде мати можливість внести відповідні виправлення.
При виконанні дипломного проекту був проведений аналіз способів побудови лексичного аналізатора. За основу був прийнятий прямий синтаксичний аналізатор, так як зчитує лексему, що знаходиться праворуч від покажчика і лише потім визначає тип лексеми [3]. Крім того, частково використовується непрямий аналіз при відділенні спеціальних символів від ідентифікаторів, ключових слів і літералів, коли розділовий пробіл не обов'язковий.
Лексичний аналізатор дозволяє працювати з наступними таблицями:
1) таблиця вибраних термінальних символів (формується з таблиці термінальних символів);
2) таблиця символічних імен (ідентифікаторів);
3) таблиця літералів (констант);
4) таблиця вихідних кодів лексем.
Далі описуються структури таблиць.

2.3.1 Таблиця термінальних символів


Всередині програми зберігається таблиця термінальних символів. Вона зберігає в собі всі термінальні символи, які можуть використовуватися у навчальному мовою (ключові слова і спеціальні символи). Вони мають свої назви, опис і кожному ключовому слову відповідає свій унікальний код, за яким відбувається ідентифікація елемента на наступних стадіях компіляції. На даному етапі відбувається робота з таблицею вибраних термінальних символів, приклад якої показано в таблиці 6.
Таблиця 6 - Таблиця вибраних термінальних символів
№ стор
Термінальний символ
Коментар
Код
1
PROGRAM
Оголошення змінних
1

Таблиця вибраних термінальних символів містить наступні поля:
№ стр - номер рядка в таблиці вибраних термінальних символів;
Термінальний символ - назва термінального символу;
Коментар - опис термінального символу;
Код - код термінального символу, визначений у таблиці термінальних символів.
Дана таблиця формується з таблиці термінальних символів, певної усередині програми (описана в додатку А) шляхом вибору необхідних термінальних символів у відповідному вікні програми. Вона служить (необхідна) для перевірки, чи є отримана лексема термінальним символом або ідентифікатором, тобто проводиться порівняння з усіма термінальними символами таблиці. Якщо лексема знайдена в таблиці, то в таблицю вихідних кодів лексем заноситься номер таблиці (у програмі № 1) та код термінального символу.
Деякі термінальні символи можна змінювати - це ключові слова. Зміна можливо в момент заповнення таблиці вибраних термінальних символів.

2.3.2 Таблиця символічних імен


Для збереження значень ідентифікаторів служить таблиця символічних імен, приклад якої наведено в таблиці 7.
Таблиця 7 - Таблиця символічних імен
Специф
Ідентифікатор
Тип
Розмір в пам'яті
Відносний адреса в пам'яті
1
а




Таблиця символічних імен містить наступні поля:
Специф - специфікатор (номер рядка) визначає положення ідентифікатора в таблиці;
Ідентифікатор - ім'я ідентифікатора, знайденого в тексті програми;
Тип - тип розпізнаного ідентифікатора (заповнюється у програмі LEXAN), поле залишається не заповненим;
Розмір в пам'яті - розмір ідентифікатора, яку він обіймав в пам'яті, визначається в залежності від типу (заповнюється у програмі LEXAN), поле залишається не заповненим;
Відносний адреса в пам'яті - адресу щодо початку оголошення змінних, формується в залежності від розміру пам'яті попередніх ідентифікаторів (заповнюється у програмі LEXAN), поле залишається не заповненим.
Таблиця служить для зберігання ідентифікаторів, знайдених в тексті програми. Після внесення ідентифікатора або виявлення вже наявного в таблиці, в таблицю вихідних кодів лексем заноситься номер таблиці (№ 2) і специфікатор знайденого елемента.

2.3.3 Таблиця літералів


Для збереження значень констант використовується таблиця літералів, приклад її заповнення показано у таблиці 8.
Таблиця 8 - Таблиця літералів
Специф
Літерал
Тип
Розмір в пам'яті
1
10
INTEGER
2

Таблиця містить наступні поля:
Специф - специфікатор, визначає положення ідентифікатора в таблиці;
Літерал - значення літерала, знайденого в тексті програми;
Тип - тип розпізнаного літерала;
Розмір в пам'яті - розмір літерала, яку він обіймав в пам'яті, визначається в залежності від типу;
Відносний адреса в пам'яті - адресу щодо початку оголошення змінних, формується в залежності від розміру пам'яті займаної літералами і ідентифікаторами.
Таблиця служить для зберігання літералів, знайдених в тексті програми. Після внесення літерала в таблицю, в таблицю вихідних кодів лексем заноситься номер таблиці (№ 3) і специфікатор знайденого елемента.

2.3.4 Робота сканера


Робота сканера LEXAN відбувається наступним чином. Студент у відповідне поле пише (або завантажує з файлу через меню) текст програми. Далі вибираються термінальні символи, необхідні для розбору тексту програми і на основі правил розбору заповнюються таблиці символічних імен, літералів і вихідних кодів лексем. Після цього проводиться перевірка правильності заповнення. При цьому програма робить аналіз тексту і заповнює свої внутрішні відповідні таблиці і порівнює з даними, отриманими від студента і, при наявності помилки, генерує повідомлення в полі повідомлень. При необхідності можна отримати лістинг. Також можна зберегти результати у файл для передачі даних на наступний етап - синтаксичний аналіз.

2.3.5 Структура лістингу


Лістинг включає в себе текст програми, всі таблиці з заповненими студентом даними і всі повідомлення про помилки.

2.3.6 Структура вихідного файлу


Вихідний файл зберігає в собі всі 4 таблиці, підрядник зберігаючи кожну клітинку. Це дозволяє не обмежувати довжину ідентифікаторів і ключових слів. Спочатку файлу також порядково вказуються розміри таблиць, спочатку вибраних термінальних символів (число стовпців, число рядків), потім символічних імен, літералів і, нарешті, вихідних кодів лексем (тільки число стовпців). Структура проміжного файлу показана в таблиці 9.
Таблиця 9 - Приклад проміжного файлу
№ рядка
Вміст-майо
Опис вмісту
1
5
4 шпальти + 1 (четвертий) зарезервовано
2
7
1 рядок - заголовок таблиці, наступні 6 - рядки з даними
3
5
5 стовпців
4
4
1 рядок - заголовок таблиці, наступні 3 - рядки з даними
5
5
5 стовпців
6
3
1 рядок - заголовок таблиці, наступні 2 - рядки з даними
7
16
1 стовпець - описи, інші 15 - з цими
(У таблиці три рядки)
8

дані з таблиці 1 по осередках, слідують зліва направо (підрядник), зверху вниз.
...

7 +5 * 7 = 42

43

дані з таблиці 2 по осередках, слідують зліва направо (підрядник), зверху вниз.
...

42 +5 * 4 = 62

63

дані з таблиці 3 по осередках, слідують зліва направо (підрядник), зверху вниз.
...

62 +5 * 3 = 77

78

дані з таблиці 4 по осередках, слідують зверху вниз (по стовпцях), зліва направо.
...

77 +16 * 3 = 125


Як приклад наводиться приклад розбору завдання, описаного в додатку А.

2.3.7 Примірне завдання для студента


Дана деяка граматика мови:
1. <prog>:: = PROGRAM <prog-name> VAR <dec-list> BEGIN <stmt-list> END.
2. <prog-name>:: = id
3. <dec-list>:: = <dec> | <dec-list>; <dec>
4. <dec>:: = <id-list>: <type>
5. <type>:: = INTEGER
6. <id-list>:: = id | <id-list>, id
7. <stmt-list>:: = <stmt> | <stmt-list>; <stmt>
8. <stmt>:: = <assign> | <for>
9. <assign>:: = id: = <exp>
10. <exp>:: = <term> | <exp> + <term> | <exp> - <term>
11. <term>:: = id | int | (<exp>)
12. <for>:: = FOR <index-exp> DO <body>
13. <index-exp>:: = id: = <exp> TO <exp>
14. <body>:: = <stmt> | BEGIN <begin-list> END
Використовуючи програму LEXAN зробити наступні дії:
1. Заповнити таблицю термінальних символів (таблиця 1);
2. Написати вихідний текст на навчальному мовою з використанням заданої граматики;
3. Заповнити таблиці: - символьних імен (таблиця 2);
- Літералів (таблиця 3);
- Лексичного аналізу (вихідних символів);
4. Перевірити правильність заповнення таблиць вбудованим аналізатором;
5. При наявності помилок виправити наявні, і повторно обробити програмою LEXAN;
6. Отримати лістинг отриманих результатів;
7. Зберегти результат у файл.
Приклад виконання наведено у додатку А.

2.3.8 Опис роботи лексичного аналізатора


Після того як студент написав програму або завантажив її з файлу, також заповнив всі таблиці і запустив програму на перевірку, програма починає виконувати наступне.
Програма проводить читання першого символу, далі проводяться перевірки.
- Якщо лічений символ є буквою або знаком підкреслення "_", якщо так, то це або ключове слово, або ідентифікатор. Далі зчитується наступний символ (літера) та проводиться його перевірка, чи входить цей символ у безліч букв російського і латинського алфавітів, цифр, чи є він символом підкреслення, якщо так, то отриманий символ додається до строкової змінної, формує лексему. Подальше зчитування та обробка відбувається до тих пір, поки не зустрінеться який або інший символ.
- Якщо лічений символ є цифрою, то далі відбувається перевірка, чи є наступний символ цифрою або крапкою. Якщо отримана літера складається з одних цифр, то отримане число цілого (INTEGER) типу, якщо в літері є точка, то число речового (REAL) типу.
- Якщо лічений символ - одинарна лапка, то текст, наступний за нею до наступної одинарної лапки, буде строковою константою, а знаки лапок будуть визначені як спеціальні символи.
- Якщо лічений символ є знаком «{», то сам знак і наступні за ним символи до знака «}» включно ігноруються, так як є коментарем.
- Якщо лічений символ є спеціальним символом, відбувається перевірка, чи є даний символ здвоєним і перевіряється другий символ. Якщо другий символ не утворює пару або перший з двох знайдених є одинарним, то відбувається обробка даного термінального символу, пошук його коду.
Після розпізнавання лексеми відбувається заповнення таблиць, відповідають типу лексеми. Якщо передбачається, що отримана лексема є термінальним символом, то відбувається перебір всіх значень таблиці термінальних символів. У випадку, коли лексема знайдена, необхідно отримати її код і заповнити відповідним чином таблицю вихідних кодів лексем. У випадку, коли лексема не знайдена передбачається, що лексема є ідентифікатором. Відбувається пошук по таблиці символьних імен. У випадку, коли в таблиці така лексема вже є, відбувається заповнення таблиці вихідних кодів лексем, інакше лексема включається в таблицю і також заповнюється таблиця кодів лексем.
При виявленні літерала, знайдена лексема заноситься в таблицю, у відповідному полі заноситься її тип, далі вказується його розмір у байтах. Потім заповнюється таблиця вихідних кодів лексем.
У порядку розпізнавання лексем відбувається заповнення таблиці вихідних кодів лексем. Якщо Незрозумілий лексема є термінальним символом, то в клітинку, що відповідає номеру таблиці, заноситься номер 1, якщо є ідентифікатором - номер 2, якщо літералом - 3. Специфікатор («код» для термінального символу) заноситься в поле «Рядок».
Далі відбувається покрокове порівняння значень, отриманих програмою, зі значеннями внесеними студентом. Порівняння відбувається за таблицею вихідних кодів лексем. При кожному невідповідність генерується повідомлення у вікні повідомлень, що в такий-то позиції не вірно заповнено значення номера таблиці, коду елемента, специфікатора.
Є можливість отримання лістингу в окремий файл з розширенням LOG.
Крім того, необхідно зберегти файл для роботи на наступному етапі синтаксичного аналізу.

2.4 Синтаксичний аналізатор SinAn


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

2.4.1 Таблиця переходів


Існує два шляхи аналізу: висхідний і спадний, даний проект реалізований за допомогою спадного, він називається рекурсивний спуск. У проекті граматичний розбір реалізований за допомогою правил БНФ граматики, заданих в таблиці переходів.
У таблиці переходів за допомогою спеціальних кодів реалізовані посилання, переходи, позначення термінальних символів, ідентифікаторів і літералів, див. таблицю 10. Нетермінальні символи являють собою посилання на конструкції, термінальні - покажчики на код елемента відповідної таблиці, ідентифікатори та літерали представляють собою відповідні позначення. Для вирішення проблеми вибору одного з декількох варіантів запроваджено елемент АБО, що дозволяє реалізувати всі можливі варіанти розгалуження. Для реалізації стека в кожному рядку передбачена осередок повернення, в якій вказується адреса, куди слід перейти після відпрацювання відповідної конструкції.
На основі даної таблиці проводиться аналіз кодів лексем і створюється нова сформована таблиця переходів, по якій надалі будується синтаксичне дерево.
Таблиця переходів повністю заснована на БНФ граматиці, показаної на рис. 4. Ця таблиця призначена для реалізації синтаксичного розбору за допомогою методу рекурсивного спуску. За допомогою неї можна визначити закінченість виразів, відстежити граматику навчального мови. Вона є основною базою при написанні програми, хоча її можна використовувати і для побудови формованої таблиці переходів вручну.
На основі цієї таблиці формується інша (яку за потреби легко можна перетворити в дерево граматичного розбору), кінцева таблиця являє собою програму, розібрану по граматика (на граматики), представлену переходами (посиланнями) та адресами таблиць і специфікатором (№-в рядків) на що зберігаються в них дані.
Робота з даною таблицею не оптимальна за швидкістю, тому що при роботі не використовується стек, зате дане подання більш наочно.

Таблиця 10 - Таблиця переходів


1
2
3
4
5
6
7
8
9
1
<prog>

PROGRAM | 1,4
$ 1 | @ 1,4
<prog-name>
~ 2
VAR | 1,6
$ 2 | @ 1,6
<dec-list>
~ 3
BEGIN
$ 3
<stmt-list>
~ 7
END
$ 4
.
$ 30
2
<prog-name>


+ Id
;
$ 27






3
<dec-list>

<dec>
~ 4
;
$ 27
<dec> |
~ 4 | @ 3,1
;
$ 27

@ 3,4



4
<dec>

<id-list>
~ 6
:
$ 31
<type>
~ 5





5
<type>

INTEGER | REAL | STRING
$ 5 | $ 6 | $ 7







6
<+ Id-list>


+ Id
, |
$ 29 | @ 6,1

+ Id

@ 6,3




7
<stmt-list>

<stmt> |
~ 8 | @ 7,1
; |
$ 27 | @ 7,1

@ 7,2






8
<stmt>

<assign> | <for> | <read> | <write> | <for> | <while> | <repeat> | <if>
~ 9 | ~ 15 | ~ 13 | ~ 14 | ~ 15 | ~ 24 | ~ 25 | ~ 21




9
<assign>


+ Id
: =
$ 28
<exp>
~ 10





10
<exp>

- | + |
$ 33 | $ 32 | @ 10,3
<term>
~ 11
+ | - |
$ 32 | $ 33 | @ 10,1
<term>
~ 11

@ 10,4



11
<term>

<factor>
~ 12
* | DIV | / |
$ 34 | $ 17 | $ 37 | 11,1
<factor>
~ 12

11,3




12
<factor>


+ Id | ^ int | ^ real | ^ string | @ 12,4

(
$ 35 | @ 12,1
<exp>
~ 10
)
$ 36



13
<read>

READ
$ 19
(
$ 35
<id-list>
~ 6
)
$ 36




14
<write>

WRITE
$ 18
(
$ 35
<VALUE>
~ 18
, | 14,9
$ 29 | @ 14,9
<VALUE>
~ 18

@ 14,5

)
$ 36
15
<for>

FOR
$ 8
<index-exp>
~ 16
DO
$ 10
<body>
~ 17




16
<index-exp>


+ Id
: =
$ 28
<exp>
~ 10
TO | DOWNTO
$ 9 | $ 20
<exp>
~ 10



17
<body>

<stmt> | 17,4
~ 8 | @ 17,4

BEGIN
$ 3
<stmt-list>
END
$ 4
; |
$ 27 | @ 17,1


18
<value>

<id-list> | <text-val>
~ 6 | ~ 19







Продовження таблиці 10
19
<text-val>

'
$ 38
<text>
~ 20
'
$ 38





20
<text>


^ String







21
<if>

IF
$ 14
<Порівняння>
~ 22
THEN
$ 15
<body>
~ 17
ELSE |
$ 16 | @ 21,1
<body>
~ 17


22
<Порівняння>

<factor>
~ 12
<Умова>
~ 23
<factor>
~ 12





23
<Умова>

<|> | = |> = | <= | <>
$ 39 | $ 40 | $ 41 | $ 42 | $ 43 | $ 44







24
<while>

WHILE
~ 13
<Порівняння>
~ 22
DO
$ 10
<body>
~ 17




25
<repeat>

REPEAT
$ 11
<body>
~ 17
UNTIL
$ 12
<Порівняння>
~ 22





2.4.2 Правила роботи з таблицею переходів


Осередком повернення є перша клітинка кожного рядка, її опис: X, 1, де Х - рядок, 1 - стовпець.
~ X - перехід на рядок з номером х, стовпець № 2, формування адреси повернення в першій клітинці, якщо перехід був здійснений від одного з параметрів умов АБО, то формування адреси повернення та адреси переходу при помилку (негативному результаті).
| - Елемент АБО, перевага віддається більш лівому елементу. Перебором порівнюється кожен елемент, і якщо ні один не підійшов, то помилка.
$ X - у таблиці переходів - номер рядка в таблиці термінальних символів
$ X, y - у формованої таблиці переходів - одна з трьох таблиць (x = 1 - термінальних символів, x = 2-ідентифікаторів, x = 3 - літер);
+ Id - таблиця ідентифікаторів (№ 2) в таблиці переходів.
Елементи, що починаються зі знака ^ (int, real, string) у таблиці переходів є елементами таблиці літералів (№ 3).
@ X, y, z - перехід до рядка x, стовпець y, параметр z
@ X, y, z% a, b, c - перехід до рядка x, стовпець y, параметр z (при наявності елемента АБО), при наявності помилки в a, b, c (вказується тільки в осередках повернення, формується тільки за присутності елемента АБО)
Перехід помилково (значення після знаку% у клітинці повернення) діє тільки для комірок стовпчика № 2.
Алгоритми:
Використовуються таблиці Table_Perehod [i, j], Table_Perehod1 [i1, j1]
Table_Perehod-основна таблиця переходу
Table_Perehod1 - формована таблиця переходу
[I, j] - адреси комірок всередині Table_Perehod, i - стовпці, j - рядки
[I1, j1] - адреси комірок всередині Table_Perehod1, i1 - стовпці, j1 - рядки
count_vs - лічильник переміщення, що показує поточний стан в таблиці вихідних символів (Tabl_vs);
pos - номер позиції у клітинці (при наявності елемента АБО).
Таблиця № 1 - таблиця термінальних символів.
Таблиця № 2 - таблиця символічних імен (ідентифікаторів).
Таблиця № 3 - таблиця літералів.
Перегляд здійснюється зліва направо, і по зверненнях. Кожного разу відбувається порівняння з поточним елементом з таблиці вихідних символів.
При позитивному результаті порівняння (термінальних символів, ідентифікаторів, літер), здійснюється перехід на більш праву клітинку.
При негативному результаті (err = 1), обробка відбувається в наступній послідовності:
1) якщо в комірці повернення поточного рядка немає знака%, то err: = 0;
2) якщо параметр єдиний (немає АБО елемента) чи це останній елемент послідовності АБО, і в комірці повернення поточного рядка немає знака%, то генерувати помилку «Повинен бути елемент% в позиції%%», де% або термінальний символ (або його код ), або "ідентифікатор", або "літера";%% - позиція в таблиці вихідних символів;
3) за наявності декількох параметрів (розділених елементом АБО) і якщо поточний не останній з них, то перейти на наступний параметр, більш правий, значення змінної err присвоїти значення 0;
4) якщо номер стовпця поточної комірки - 2, то якщо у клітинці повернення є знак%, то перейти за адресою, вказаною за знаком% і:
- У таблиці переходів очистити комірку повернення,
- У формованої таблиці переходів видалити останній рядок.

2.4.3 Правила таблиці переходів для написання програми


Якщо чарунка порожня, то здійснюється перехід на першу клітинку поточного рядка, i: = 1.
Якщо значення в комірці типу x, y або x, y, z, то необхідно перейти на рядок х, осередок y, позицію z. При цьому: після переходу в зазначену комірку на зазначену позицію осередок з адресою переходу, якщо вона є осередком повернення, очищається (Table_Perehod [i, j ]:=''; i: = y; j: = x; pos: = z) , в формованої таблиці переходів відбувається перехід в клітинку, зазначену в першій клітинці рядка без очищення її значення (i1: = y; j1: = x).
Якщо значення в комірці типу x, y% a, b, c, при цьому err = 1 і номер стовпця дорівнює 2 (i = 2), то слід перейти за посиланням a, b, c, очистити комірку повернення таблиці переходів (Table_Perehod [ i, j ]:=''; i: = b; j: = a; pos: = c), в формованої таблиці переходів перейти за адресою повернення і видалити останній рядок (i1: = y; j1: = x).
Якщо значення в комірці типу x, y% a, b, c, і err = 0, то перейти по посиланню x, y, в формованої таблиці переходів перейти за адресою, вказаною в поточній комірці.
Якщо номер стовпця поточної комірки = 3 і err <> 0, то в комірці повернення видалити за наявності знак% і значення за ним.
Якщо перший символ ^ - значення у клітинці є літерою (таблиця літералів - № 3). Здійснювана при цьому перевірка: якщо в таблиці вихідних символів № поточної таблиці дорівнює 3 (if Tabl_vs [count_vs, 2] = '3 '), то занести в поточну клітинку формованої таблиці № таблиці (3) і № рядка в ній (Table_Perehod1 [i1 , j1]: = $ 3, № рядка), перейти на наступну комірку (i: = i +1; i1: = i1 +1; count_vs: = count_vs +1). У разі негативного результату порівняння змінної err присвоюється значення 1.
Якщо перший символ $ - значення у клітинці є термінальним символом (таблиця термінальних символів - № 1). Здійснювана перевірка: якщо в таблиці вихідних символів № поточної таблиці дорівнює 1 (if Tabl_vs [count_vs, 2] = "1"), то занести в поточну клітинку формованої таблиці № таблиці (1) та № рядка в ній (Table_Perehod1 [i1, j1 ]: = $ 1, код), перейти на наступну комірку (i: = i +1; i1: = i1 +1; count_vs: = count_vs +1). У разі негативного результату порівняння змінної err присвоюється значення 1.
Якщо перший символ ~ - це перехід на другий осередок рядка з номером, зазначеним за символом ~, в формованої таблиці переходів додається новий рядок і перехід здійснюється на неї. При цьому здійснюється наступне: в першу клітинку (осередок повернення) зазначеного рядка заноситься адреса повернення: якщо перехід здійснюється за однією з позицій з елементом АБО і не є останнім у списку, то в комірці повернення формується код повернення типу x, y, z, де x - номер рядка, y - номер стовпця, z - номер позиції звідки був зроблений перехід (x: = j; y: = i; z: = pos; j: = a; i: = 2, де а номер рядка в адресі переходу - ~ a), теж відбувається і в формованої таблицею переходів (x: = j1; y: = i1; j1: = № останнього рядка; i1: = 2).
Коди термінальних символів показані в таблиці 11.

Таблиця 11 - Таблиця кодів термінальних символів
Код
Термінальний символ
Коментар


1
PROGRAM
оголошення програму


2
VAR
оголошення змінних


3
BEGIN
початок тіла


4
END
кінець тіла


5
INTEGER
тип ціле


6
REAL
дійсний тип


7
STRING
рядковий тип


8
FOR
цикл з параметром - ДЛЯ


9
TO
цикл з параметром - ДО


10
DO
ВИКОНАТИ


11
REPEAT
цикл з постусловіем - ПОВТОРЮВАТИ


12
UNTIL
цикл з постусловіем - ПОКИ НЕ


13
WHILE
цикл з передумовою - ПОКИ


14
IF
умовний оператор - ЯКЩО


15
THEN
умовний оператор - ТО


16
ELSE
умовний оператор - ІНАКШЕ


17
DIV
ділити на ціле


18
WRITE
вивести на консоль


19
READ
рахувати з консолі


20
DOWNTO
цикл з параметром - ДО


21
FUNCTION
функція


22
PROCEDURE
процедура


23
{
початок коментаря


24
}
кінець коментаря


25
[
відкриття квадратних дужок


26
]
закриття квадратних дужок


27
;
кінець операції


28
: =
присвоїти значення


29
,
роздільник


30
.
кінець програми / відділення дробової частини


31
:
поділ ідентифікатора від його типу


32
+
оператор складання


33
-
оператор віднімання


34
*
оператор множення


35
(
відкривається дужка


36
)
закривається дужка


37
/
оператор ділення


38

лапки


39
<
менше


40
>
більше


41
=
одно


42
> =
більше або дорівнює


43
<=
менше або дорівнює


44
<>
не дорівнює




2.4.4 Формована таблиця переходів. Правила заповнення


Таблиця являє собою набір осередків. Стовпці та рядки нумеруються. Стовпці визначають номер розпізнаної лексеми (елементу конструкції), рядки визначають номер отриманої конструкції.
У таблиці можуть існувати тільки два види даних: покажчики на таблиці та переходи.
Покажчики на таблиці складаються з символу ознаки посилання на таблицю «$», номера таблиці і, через кому, коду (для термінального символу) або специфікатора. Номери таблиць: 1 - таблиця термінальних символів, 2 - таблиця символічних імен, 3 - таблиця літералів.
Покажчики на клітинки складаються з символу «@» і наступних за ним через кому адрес стовпця і рядка, куди слід перейти, опинившись в цій комірці.
Всі осередки першого стовпця зарезервовані для значень посилань зворотного переходу на клітинку, наступну за викликала перехід у даний рядок і називаються осередками повернення.
Щоб заповнити формовану таблицю переходів необхідно знати наступні правила.
Таблиця заповнюється в точності за БНФ, показаної на малюнку 4, при цьому рядки таблиці є елементами конструкцій даної граматики. Розбір робиться за даними, отриманими з таблиць термінальних символів, символічних імен, літералів, вихідних кодів лексем.
1) Заповнення таблиці починається з лівого верхнього осередку, кожного разу зміщуючись на наступну, більш праву.
2) При наявності вкладеності конструкції (знайдений нетермінальний символ) створюється (заповнюється) новий рядок, де в першій клітинці вказується адреса повернення: покажчик переходу «@», номер рядка, номер стовпця, звідки здійснено перехід плюс один (тобто перехід на наступну комірку за тією, з якої був зроблений виклик).
3) За наявності декількох елементів, розділених знаком «|», здійснюється перебір варіантів, які підходять значенням, вказаним у таблиці вихідних кодів.
4) За відповідності значення клітинки або одного з елементів АБО терміналу символу вказується ознака посилання на таблицю «$», потім номер таблиці - 1 і код елемента в таблиці термінальних символів (номер таблиці і код береться з таблиці кодів лексем).
5) За відповідності значення клітинки або одного з елементів АБО ідентифікатору вказується ознака посилання на таблицю «$», потім номер таблиці - 2 і специфікатор (номер таблиці і специфікатор береться з таблиці кодів лексем).
6) За відповідності значення клітинки або одного з елементів АБО літерали вказується ознака посилання на таблицю «$», потім номер таблиці - 3 і специфікатор (номер таблиці і специфікатор також береться з таблиці кодів лексем).
7) Підкреслені елементи в БНФ граматиці не обов'язкові (вони можуть бути відсутніми).

2.4.5 Правила заповнення формованої таблиці переходів


Розбір робиться за даними, отриманими від БНФ граматик, з таблиць термінальних символів, вихідних кодів лексем.
Заповнення формованої таблиці переходів починається з другої осередку першого рядка.
Для термінальних символів алгоритм може виглядати таким чином.
Припустимо, робиться аналіз першого елемента таблиці кодів лексем.
1) Номер позиції у таблиці кодів лексем дорівнює 1. Проводиться читання даних з першого стовпця таблиці кодів лексем. Отримане значення номера таблиці - 1 (таблиця термінальних символів), код дорівнює 1 (за таблицею кодів - «оголошення програми»).
2) Розглядається перший елемент БНФ граматики, їм є ключове слово PROGRAM, воно належить таблиці термінальних символів - 1, за таблицею кодів визначається код, він дорівнює 1.
3) Проводиться порівняння номерів таблиць, отриманих на етапі 1 та етапі 2. Значення збіглися.
4) Проводиться порівняння кодів таблиць. Значення збіглися.
5) У другу клітинку першого рядка формованої таблиці переходів заноситься покажчик на таблицю 1, код 1 - «$ 1,1».
6) Номер позиції у таблиці кодів лексем збільшується на 1 (стає рівним 2).
7) У граматиці БНФ починає розглядатися наступний елемент конструкції - нетермінальний символ <prog-name>.
8) Нове значення у формовану таблицю переходів буде заноситися в праву осередок від поточної (номер стовпця збільшився на 1).
При розбіжності значень на етапах 3 і 4 відбувається припинення розбору, якщо тільки термінальний символ не є елементів масиву АБО - «|» (наприклад <type>:: = INTEGER | REAL | STRING) або не є необов'язковим елементом конструкції (наприклад, PROGRAM < prog - name>), тоді здійснюється перехід на наступний елемент масиву АБО або перехід до наступного елементу конструкції не входить до цієї групи необов'язкових елементів (підкреслюються однією загальною лінією).
Для нетермінальних символів алгоритм приблизно такий.
Припустимо, робиться аналіз другого елементу таблиці кодів лексем. Поточна розбирається лексема у граматиці БНФ є нетермінальним символом. У формованої таблиці переходів дані заносяться в третю клітинку першого рядка.
1) Номер позиції у таблиці кодів лексем дорівнює 2. Проводиться читання даних з другого стовпця таблиці кодів лексем. Отримане значення номера таблиці - 2 (таблиця символічних імен), специфікатор дорівнює 1.
2) Конструкція, що визначає структуру нетермінального символу <prog-name>, у граматиці БНФ має номер 2.
3) У формованої таблиці переходів додається новий рядок, де в першу клітинку заноситься адреса повернення на клітинку, що викликала перехід, зміщену на 1 вправо (у даному випадку вказується перехід на четверту клітинку першого рядка - «@ 1,4»).
4) Номер позиції у таблиці кодів лексем не змінюється (залишається рівним 2).
5) У граматиці БНФ починає розглядатися наступний елемент конструкції - id (ідентифікатор).
6) Нове значення у формовану таблицю переходів буде заноситися в праву осередок від поточної (в даному прикладі рядок 2, стовпець 2).
Для ідентифікаторів алгоритм приблизно такий.
Припустимо, робиться аналіз другого елементу таблиці кодів лексем. Поточна розбирається лексема у граматиці БНФ знаходиться в конструкції <prog-name> є першим її елементом. У формованої таблиці переходів дані заносяться в другий осередок другого рядка.
1) Номер позиції у таблиці кодів лексем дорівнює 2. Проводиться читання даних з другого стовпця таблиці кодів лексем. Отримане значення номера таблиці - 2 (таблиця символічних імен), специфікатор дорівнює 1.
2) Розглядається перший елемент БНФ граматики конструкції <prog-name>, цей елемент є ідентифікатором, отже є елементом таблиці символічних імен - таблиці 2.
3) Проводиться порівняння номерів таблиць. Значення збіглися.
4) У другий осередок другого рядка заноситься покажчик на таблицю 2, специфікатор 1 (його значення береться з таблиці кодів лексем) - «$ 2,1»
5) Номер позиції у таблиці кодів лексем збільшується на 1 (стає рівним 3).
6) У граматиці БНФ починає розглядатися наступний елемент конструкції <prog-name> - термінальний символ «;».
7) Нове значення у формовану таблицю переходів буде заноситися в праву осередок від поточної (номер стовпця збільшився на 1) - другий рядок, третя клітинка.
При розбіжності значень на етапі 3, відбувається припинення розбору, якщо тільки поточний елемент не є елементів масиву АБО - «|» (наприклад <factor>:: = id | int | real | <text-val> | (<exp>)) або не є необов'язковим елементом конструкції (наприклад, PROGRAM <prog - name>), тоді здійснюється перехід на наступний елемент масиву АБО або перехід до наступного елементу конструкції не входить до цієї групи необов'язкових елементів (підкреслюються однією загальною лінією).
Якщо конструкція закінчилася, то здійснюється перехід на першу клітинку (осередок повернення) поточного рядка в формованої таблиці переходу. За значенням адреси, що міститься у клітинці повернення активної (готової для внесення даних) стає осередок із зазначеним номером рядка та номером стовпця. У граматиці БНФ здійснюється перехід до елемента, наступного за елементом конструкції, який був визначений в поточній конструкції. Наприклад, після визначення останнього елемента конструкції <prog-name> «;» здійснюється повернення до елемента, наступного за елементом, що викликав цю конструкцію. Повернення здійснене на рядок 1 граматики БНФ, до елементу VAR, наступного за нетермінальним символом <prog-name>.
Для літералів алгоритм приблизно такий.
Припустимо, робиться аналіз шістнадцятого елемента таблиці кодів лексем. Поточна розбирається лексема у граматиці БНФ знаходиться в конструкції <factor> є другим елементом конструкції АБО. У формованої таблиці переходів дані заносяться в другий осередок десятого рядка.
1) Номер позиції у таблиці кодів лексем дорівнює 16. Проводиться читання даних з шістнадцятого стовпця таблиці кодів лексем. Отримане значення номера таблиці - 3 (таблиця літералів), специфікатор дорівнює 1.
2) Розглядається другий елемент безлічі АБО БНФ граматики конструкції <factor>, цей елемент є літералом цілого типу, отже є елементом таблиці літералів - таблиці 3.
3) Проводиться порівняння номерів таблиць. Значення збіглися.
4) У другу клітинку десятого рядка заноситься покажчик на таблицю 3, специфікатор 1 (його значення береться з таблиці кодів лексем) - «$ 3,1»
5) Номер позиції у таблиці кодів лексем збільшується на 1 (стає рівним 17).
6) У граматиці БНФ починає розглядатися наступний елемент конструкції <factor>, тому що він відсутній це говорить про те, що кінець конструкції.
7) Викликається обробка кінця конструкції.
При розбіжності значень на етапі 3, відбувається припинення розбору, якщо тільки поточний елемент не є елементів масиву АБО - «|» (наприклад <factor>:: = id | int | real | <text-val> | (<exp>)) або не є необов'язковим елементом конструкції (наприклад, PROGRAM <prog - name>), тоді здійснюється перехід на наступний елемент масиву АБО або перехід до наступного елементу конструкції не входить до цієї групи необов'язкових елементів (підкреслюються однією загальною лінією).
Опис роботи з елементами масиву АБО БНФ граматики.
Якщо в БНФ граматиці зустрічається масив АБО, перебір значень здійснюється з лівого.
При виникненні помилки при роботі з одним з елементів масиву АБО здійснюється перехід до наступного, що знаходиться правіше.
У разі, коли останній (крайній правий) елемент масиву АБО або значення у клітинці не задовільно, відбувається припинення розбору програми.
У разі позитивного результату (порівняння одного з елементів вдало або порівняння з кінцевим результатом переходів вдало) відбувається перехід на наступну лексему граматики БНФ, на наступний елемент таблиці кодів лексем, на наступну комірку (на 1 правіше) формованої таблиці переходів.
Нижче розглядається приклад програми.
Program prog1;
var a, b, c: integer;
begin
a: = 1 + b * (a-c);
end.
Отримана послідовність символів від програми LEXAN представлена ​​в таблиці 12.
Таблиця 12 - Таблиця вихідних символів
№ п.п.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Таблиця
1
2
1
1
2
1
2
1
2
1
1
1
1
2
1
Рядок
1
1
27
2
2
29
3
29
4
31
5
27
3
2
28

№ п.п.
16
17
18
19
20
21
22
23
24
25
26
27
Таблиця
3
1
2
1
1
2
1
2
1
1
1
1
Рядок
1
32
3
34
35
2
33
4
36
27
4
30

За вихідними даними, також використовуючи таблицю кодів термінальних символів, заповнюється таблиця побудов.
Для кращого розуміння заповнення формованої таблиці переходів заповнюється таблиця побудов. Обробка даних і заповнення таблиці процес досить трудомісткий, однак, треба розуміти, що і для машини даний розбір є самою трудомісткою завданням. Тут же процес розбору програми максимально уніфікований. Дається можливість відстежити всі можливі (вихідні) параметри (значення). Перервати заповнення таблиці побудов можна в будь-який момент часу, а потім продовжити, не втрачаючи логіку переходів (побудови).
Таблиця побудов складається з декількох розділів, вони називаються: кроки, таблиця кодів лексем, ім'я в програмі, елемент граматики БНФ, результат порівняння, формована таблиця переходів, виконану дію.
У розділі «Кроки» перераховуються номери вироблених кроків. Розділ «Таблиця кодів лексем» служить для відстеження позиції у таблиці кодів лексем і зберігає значення таблиці та коду (або специфікатора) з якими надалі відбувається порівняння поточного елемента граматики БНФ. Розділ «Елемент граматики БНФ» містить ім'я елемента, ім'я конструкції, в яку він входить, тип поточного елемента граматики, номер таблиці, відповідної йому, а також код (для термінальних символів), визначений за таблицею кодів термінальних символів. У розділі «Формована таблиця переходів» відстежується поточна комірка формованої таблиці переходів, куди заноситься сформоване значення, а також позиція наступної комірки, з якої буде проводитися робота на наступному кроці. У розділі «Виконана дія» вказується виконану дію.
Таблиця побудови пропонується як допоміжний засіб для заповнення формованої таблиці переходів. Заповнювати всі кроки і осередки в ній не обов'язково, головне зрозуміти логіку заповнення формованої таблиці переходів. Набувши досвіду, в подальшому, можна обходитися без таблиці побудов, заповнюючи формовану таблицю переходів по БНФ граматиці, тексту програми, таблиці кодів термінальних символів, таблиці кодів лексем.
З даних, отриманих в розділі «Формована таблиця переходів, поточна позиція» таблиці побудови, заповнюється формована таблиця переходів. У результаті повинна вийти таблиця 14.
Прийняті скорочення в таблиці побудов.
НС - нетермінальний символ
ТЗ - термінальний символ
ВД - ідентифікатор
Лх - літерал, де х: Ц - цілий тип, В - дійсний тип, З - рядковий тип.
Л - літерал будь-якого типу.
Наявність знаку «-» попереду типу в елемента граматики БНФ показує, що даний елемент у розборі може не брати участь.
При заповненні таблиці побудов особливу складність представляє робота з переходами. Нижче описується робота з ними.
При виявленні термінального символу у граматиці БНФ, необхідно здійснити перехід на перший елемент конструкції з тим же ім'ям. У таблиці побудов визначається номер останньої не зайнятою рядка в формованої таблиці переходів. Номером наступній позиції вказується номер цього рядка, номер стовпця - 1. Значення внесеного значення має вказувати на другий осередок останньої порожнього рядка. Наступним кроком заповнюється значення поточний позиції, адреса повернення і адреса наступної позиції. Наприклад. Після знаходження термінального символу <prog-name> починає розглядатися перший елемент конструкції <prog-name> - id. У формованої таблиці переходів останньої вільної рядком є ​​рядок 2, на неї і здійснюється перехід, наступна позиція вказує на рядок 2, стовпець 1 (крок 2). На третьому кроці в клітинку повернення 2,1 (де 2 - номер рядка, 1 - номер стовпця) буде внесена значення, яке вказує на клітинку 1,4, тому що перехід здійснено з комірки 1,3. Поточна позиція - 2,1, наступна позиція - 2,2.
При поверненні виникають інші труднощі. Наприклад, при закінченні конструкції відбувається перехід на порожню клітинку, потім здійснюється перехід на клітинку повернення. Значення, заповнене у клітинці повернення шукається по таблиці. За отриманого значення здійснюється перехід. Наприклад, при закінченні конструкції <id-list> (крок 20), поточної осередком виявляється осередок 5,7. Потім здійснюється перехід в клітинку 5,1 (крок 21). За таблицею визначаємо, що адреса повернення @ 4,3 (значення з кроку 14), тобто перейти на четвертий рядок, третій стовпець.
Далі відшукується становище в граматиці БНФ на ім'я попередньої позиції. Наприклад, після переходу в клітинку 4,3 (крок 22) відшукуємо у таблиці ім'я елемента граматики осередку 4,2 (значення з кроку 13), їм надається нетермінальний символ <id-list> конструкції <dec>. За граматиці БНФ визначається, що наступний елемент конструкції <dec> є «:».

Таблиця 13 - Таблиця побудов
Кроки
Таблиця кодів лексем
Ім'я в програмі
Елемент граматики БНФ
Результат порівняння
Формована таблиця переходів
Виконане дію
поточна позиція
наступна позиція
позиція
табл
код, специф
тип
ім'я
поточна конструкція
тип
табл
код
(Для ТЗ)
рядок
стовпець
вноситься значення
рядок
стовпець
1
1
1
1
ТЗ
PROGRAM
PROGRAM
<prog>
-ТС
1
1
+
1
2
$ 1,1
1
3

2
2
2
1
ВД
Prog1
<prog-name>
<prog>
НС



1
3
@ 2,2
2
1

3
2
2
1
ВД
Prog1






2
1
@ 1,4
2
2

4
2
2
1
ВД
Prog1
id
<prog-name>
ВД
2

+
2
2
$ 2,1
2
3

5
3
1
27
ТЗ
;
;
<prog-name>
-ТС
1
27
+
2
3
$ 1,27
2
4

6
4
1
2
ТЗ
VAR

<prog-name>




2
4

2
1
кінець конструкції
7
4
1
2
ТЗ
VAR






2
1

1
4
перехід
8
4
1
2
ТЗ
VAR
VAR
<prog>
-ТС
1
2
+
1
4
$ 1,2
1
5

9
5
2
2
ВД
a
<dec-list>
<prog>
НС



1
5
@ 3,2
3
1

10
5
2
2
ВД
a






3
1
@ 1,6
3
2

11
5
2
2
ВД
а
<dec>
<dec-list>
НС



3
2
@ 4,2
4
1

12
5
2
2
ВД
а






4
1
@ 3,3
4
2

13
5
2
2
ВД
а
<id-list>
<dec>
НС



4
2
@ 5,2
5
1

14
5
2
2
ВД
а






5
1
@ 4,3
5
2

15
5
2
2
ВД
а
id
<id-list>
ВД
2

+
5
2
$ 2,2
5
3

16
6
1
29
ТЗ
,
,
<id-list>
ТЗ
1
29
+
5
3
$ 1,29
5
4

17
7
2
3
ВД
b
id
<id-list>
ВД
2

+
5
4
$ 2,3
5
5

18
8
1
29
ТЗ
,
,
<id-list>
ТЗ
1
29
+
5
5
$ 1,29
5
6

19
9
2
4
ВД
c
id
<id-list>
ВД
2

+
5
6
$ 2,4
5
7

20
10
1
31
ТЗ
:

<id-list>




5
7

5
1
кінець конструкції
21
10
1
31
ТЗ
:






5
1

4
3
перехід
22
10
1
31
ТЗ
:
:
<dec>
ТЗ
1
31
+
4
3
:
4
4

23
11
1
5
ТЗ
INTEGER
<type>
<dec>
НС



4
4
@ 6,1
6
1

24
11
1
5
ТЗ
INTEGER






6
1
@ 4,5
6
2

25
11
1
5
ТЗ
INTEGER
INTEGER
<type>
ТЗ
1
5
+
6
2
$ 1,5
6
3

26
12
1
27
ТЗ
;

<type>




6
3

6
1
кінець конструкції
27
12
1
27
ТЗ
;






6
1

4
5
перехід
28
12
1
27
ТЗ
;

<dec>




4
5

4
1
кінець конструкції
29
12
1
27
ТЗ
;






4
1

3
3
перехід
30
12
1
27
ТЗ
;
;
<dec-list>
-ТС
1
27
+
3
3
$ 1,27
3
4

31
13
1
3
ТЗ
BEGIN

<dec-list>




3
4

3
1
кінець конструкції
32
13
1
3
ТЗ
BEGIN






3
1

1
6
перехід
33
13
1
3
ТЗ
BEGIN
BEGIN
<prog>
ТЗ
1
3
+
1
6
$ 1,3
1
7

34
14
2
2
ВД
а
<stmt-list>
<prog>
-НС



1
7
@ 7,2
7
1

35
14
2
2
ВД
а






7
1
@ 1,8
7
2

36
14
2
2
ВД
а
<stmt>
<stmt-list>
НС



7
2
@ 8,2
8
1

37
14
2
2
ВД
a






8
1
@ 7,3
8
2

38
14
2
2
ВД
a
<assign>
<stmt>
НС



8
2
@ 9,2
9
1

39
14
2
2
ВД
a






9
1
@ 8,3
9
2

Продовження таблиці 13
Кроки
Таблиця кодів лексем
Ім'я в програмі
Елемент граматики БНФ
Результат порівняння
Формована таблиця переходів
Виконане дію
поточна позиція
наступна позиція
позиція
табл
код, специф
тип
ім'я
поточна конструкція
тип
табл
код
(Для ТЗ)
рядок
стовпець
вноситься значення
рядок
стовпець
40
14
2
2
ВД
a
id
<assign>
ВД
2

+
9
2
$ 2,2
9
3

41
15
1
28
ТЗ
: =
: =
<assign>
ТЗ
1
28
+
9
3
$ 1,28
9
4

42
16
3
1
ЛЦ
1
<exp>
<assign>
НС



9
4
@ 10,2
10
1

43
16
3
1
ЛЦ
1






10
1
@ 9,5
10
2

44
16
3
1
ЛЦ
1
-
<exp>
-ТС
1
33
-
10
2




45
16
3
1
ЛЦ
1
<term>
<exp>
НС



10
2
@ 11,2
11
1

46
16
3
1
ЛЦ
1






11
1
@ 10,3
11
2

47
16
3
1
ЛЦ
1
<factor>
<term>
НС



11
2
@ 12,2
12
1

48
16
3
1
ЛЦ
1






12
1
@ 11,3
12
2

49
16
3
1
ЛЦ
1
id
<factor>
ВД
2

-
12
2




50
16
3
1
ЛЦ
1
int
<factor>
ЛЦ
3

+
12
2
$ 3,1
12
3

51
17
1
32
ТЗ
+

<factor>




12
3

12
1
кінець конструкції
52
17
1
32
ТЗ
+






12
1

11
3
перехід
53
17
1
32
ТЗ
+
*
<term>
ТЗ
1
34
-
11
3




54
17
1
32
ТЗ
+
DIV
<term>
ТЗ
1
17
-
11
3




55
17
1
32
ТЗ
+
/
<term>
ТЗ
1
37
-
11
3




56
17
1
32
ТЗ
+

<term>




11
3

11
1
кінець конструкції
57
17
1
32
ТЗ
+






11
1

10
3
перехід
58
17
1
32
ТЗ
+
+
<exp>
ТЗ
1
32
+
10
3
$ 1,32
10
4

59
18
2
3
ВД
b
<term>
<exp>
НС



10
4
@ 13,2
13
1

60
18
2
3
ВД
b






13
1
@ 10,5
13
2

61
18
2
3
ВД
b
<factor>
<term>
НС



13
2
@ 14,2
14
1

62
18
2
3
ВД
b






14
1
@ 13,3
14
2

63
18
2
3
ВД
b
id
<factor>
ВД
2

+
14
2
$ 2,3
14
3

64
19
1
34
ТЗ
*

<factor>




14
3

14
1
кінець конструкції
65
19
1
34
ТЗ
*






14
1

13
3
перехід
66
19
1
34
ТЗ
*
*
<term>
ТЗ
1
34
+
13
3
$ 1,34
13
4

67
20
1
35
ТЗ
(
<factor>
<term>




13
4
@ 15,2
15
1

68
20
1
35
ТЗ
(

<term>




15
1
@ 13,5
15
2

69
20
1
35
ТЗ
(
id
<factor>
ВД
2

-
15
2




70
20
1
35
ТЗ
(
int
<factor>
ЛЦ
3

-
15
2




71
20
1
35
ТЗ
(
real
<factor>
ЛВ
3

-
15
2




72
20
1
35
ТЗ
(
(
<factor>
ТЗ
1
35
+
15
2
$ 1,35
15
3

73
21
2
2
ВД
а
<exp>
<factor>
НС



15
3
@ 16,2
16
1

74
21
2
2
ВД
а






16
1
@ 15,4
16
2

75
21
2
2
ВД
а
-
<exp>
-ТС
1
33
-
16
2




76
21
2
2
ВД
а
<term>
<exp>
НС



16
2
@ 17,2
17
1

77
21
2
2
ВД
а






17
1
@ 16,3
17
2

78
21
2
2
ВД
а
<factor>
<term>
НС



17
2
@ 18,2
18
1

Продовження таблиці 13
Кроки
Таблиця кодів лексем
Ім'я в програмі
Елемент граматики БНФ
Результат порівняння
Формована таблиця переходів
Виконане дію
поточна позиція
наступна позиція
позиція
табл
код, специф
тип
ім'я
поточна конструкція
тип
табл
код
(Для ТЗ)
рядок
стовпець
вноситься значення
рядок
стовпець
79











18
1
@ 17,3
18
2

80
21
2
2
ВД
а
id
<factor>
ВД
2

+
18
2
$ 2,2
18
3

81
22
1
33
ТЗ
-






18
3

18
1
кінець конструкції
82
22
1
33
ТЗ
-






18
1

17
3
перехід
83
22
1
33
ТЗ
-
*
<term>
ТЗ
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Диплом | 949.7кб. | скачати

Схожі роботи:
Програмно-апаратний комплекс для тестування інтегральних мікросхем 155 серії
Стародавній Схід Стародавня Греція Стародавній Рим Навчально-методичний комплекс для студентів I курсу заочного
Створення програми для автоматизації процесу нарахування заробітної плати
Створення математичної моделі процесу обробки кінцевими фрезами для прогнозування параметрів
Науково-методичний супровід створення систем фізичного захисту об`єктів
Навчально методичний посібник для адаптаційної практики
Навчально-методичний посібник для адаптаційної практики
Навчально-методичний посібник для самостійної роботи
© Усі права захищені
написати до нас
Рейтинг@Mail.ru