Вивчення складових частин, основних принципів побудови і функціонування компіляторів. Поняття хешування, сутність алгоритму роботи лексичного аналізатора. Практичне освоєння методів побудови простих компіляторів для заданої вхідної мови - Borland Delphi.
Краткое сожержание материала:

Размещено на

3

Размещено на

КУРСОВА РОБОТА

з дисципліни: “Системне програмне забезпечення”

На тему: “Створення компілятора”

ЗМІСТ

• Вступ 3
• 1. Короткі теоретичні відомості 4
• 1.1 Таблиці ідентифікаторів 4
• 1.1.1 Метод бінарного дерева 5
• 1.1.2 Хешування 6
• 1.2 Лексичний аналізатор 7
• 1.3 Синтаксичний аналізатор 9
• 1.4 Генерація об'єктного коду 11
• 2. Таблиця передування 13
• 3. Лістинг програм 15
• 4. Результати роботи 144
• Висновки 147
• Перелік використаної літератури 148

Вступ

Тема: Створення компілятора

Мета роботи: вивчення складових частин, основних принципів побудови і функціонування компіляторів. Практичне освоєння методів побудови простих компіляторів для заданої вхідної мови.

Завдання

Для програмної організації компілятора рекомендується використовувати Borland Delphi:

Компілятор повинен складатися:

1) лексичний аналізатор

2) синтаксичний аналізатор

3) оптимізатор

4) генератор результуючого кода

Для побудови компілятора бажано використовувати методи застосовані при виконанні лабораторної роботи.

Варіант - 5

1) Тип констант: вісімкові

2) Додаткові операції: >><<

3) Оператори цикла: repeat <оператор> until <вираз>

4) Оптимізація: виключення зайвих операцій

5) Тип даних: integer

6) Тип коментарів: {коментарій}

1. Короткі теоретичні відомості

1.1 Таблиці ідентифікаторів

Способи організації таблиць ідентифікаторів:

1) прості і впорядковані списки

2) бінарне дерево

3) хеш-адресація з ре хешуванням

4) хеш-адресація за методом ланцюжків

5) комбінація хеш-адресації зі списком або бінарним деревом

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

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

1.1.1 Метод бінарного дерева

В цьому методі кожний вузол дерева є елементом таблиці, кореневим вузлом стає перший елемент, який компілятор зустрів при заповненні таблиці. Дерево є бінарним, бо кожна вершина має не більше 2 гілок.

Компілятор працює з потоком вхідних даних, що містить ідентифікатори.

Алгоритм роботи бінарного дерева:

1) Перший - заноситься в вершину дерева, наступні попадають в дерево за таким алгоритмом:

2) 1) вибрати черговий ідентифікатор з потоку, якщо чергового нема, то побудова закінчена

3) зробити поточним вузлом дерева кореневу вершину

4) порівняти ім'я чергового ідентифікатора з іменем ідентифікатора який міститься в поточному вузлі

5) якщо ім'я чергового ідентифікатора менше - перейти до кроку 5, якщо дорівнює - зупинити алгоритм, оскільки однакових ідентифікаторів бути не повинно, інакше - перейти до кроку 7

6) якщо у поточного вузла існує ліва вершина, то зробити її поточним вузлом и повернутися до кроку 3, інакше - до кроку 8

7) створити нову вершину, помістити в неї інформацію про черговий ідентифікатор, зробити цю нову вершину лівою вершиною поточного вузла і перейти до кроку 1

8) якщо у поточного вузла є права вершина, то зробити її поточним вузлом і повернутися до кроку 3, інакше - до кроку 8

9) створити нову вершину, помістити в неї інформацію про черговий ідентифікатор, зробити нову вершину правою вершиною поточного вузла і перейти до кроку 1

Пошук називається бінарним тому, що на кожному кроці об'єм розгляданої інформації скорочується в 2 рази, тобто шуканий символ порівнюється з (n+1)/2 елементами в середині таблиці, якщо співпадінь немає, то переглядається блок елементів пронумерованих від 1 до (n+1)/2-1 або від (n+1)/2 до n в залежності від того менше чи більше шуканий елемент порівнюваного, далі процес повторюється над блоком вдвічі меншого розміру.

Число порівнянь і форма дерева залежить від порядку надходження ідентифікаторів.

Недоліком також є необхідність зберігати 2 додаткові посилання на ліву и праву гілки в кожному елементі дерева і робота з динамічним виділенням пам'яті для побудови дерева.

1.1.2 Хешування

Для хешування використовується поняття хеш-функції і хеш-адресації. Хеш-функція F відображає множини вхідних елементів R на множину цілих невід'ємних чисел Z

R->Z:F(r) = n, r є R, n є Z

Множина допустимих вхідних елементів називається областю визначення функції F.

Множина значень хеш-функції - M є Z

Процес відображення області визначення хеш-функції на множину значень - хешування, тобто відображення імен ідентифікаторів на множину цілих невід'ємних чисел. Хеш-адресація полягає у використанні значення, яке видає хеш-функція в якості комірки з деякого масиву даних.

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

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

Недоліки:

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

- необхідність прийнятного вибору хеш-функції

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

Лексичний аналізатор - це частина компілятора, яка читає літери програми на вхідній мові і будує з них слова (лексеми) початкової мови. На вхід лексичного аналізатора надходить текст початкової програми, а інформація на виході передається синтаксичному аналізатору.

Лексема - структурна одиниця мови, яка складається з символів мови і не містить в своєму складі інших структурних одиниць мови. Лексемами є ідентифікатори, константи, ключові слова, знаки операції.

Етап лексичного аналізу програми введено за таких причин:

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

- для виділення і розбору лексем можливо застосовувати легку і ефективну техніку аналізу

- лексичний аналізатор відділяє конструктивно складний синтаксичний аналіз від роботи з текстом початкової програми, це дає змогу при переході від однієї версії мови до іншої внести незначні зміни в простий лексичний аналізатор

Таблиця лексем

Результатом роботи лексичного аналізатора є перелік всіх знайдених в початковій програмі лексем і додаткової службової інформації. Таблиця лексем в кожному рядку містить інформацію про вид лексеми, її тип і значення. Як правило в цій таблиці є 2 поля: тип лексеми, вказівник на інформацію про лексеми. Не слід плутати таблицю лексем з таблицею ідентифікаторів тому, що таблиця лексем фактично містить весь текст початкової програми обробленої лексичним аналізатором.

В таблиці лексем будь-яка лексема може зустрічатися будь-яке число раз, тоді як в таблиці ідентифікаторів кожна лексема зустрічається лише один раз. До того ж таблиця ідентифікаторів містить лише ідентифік...