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

 

 

 

 

 

 

 

 

Курсова робота

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗМІСТ

 

Вступ

 

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

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

 

 

Завдання:

Для програмної організації  компілятора рекомендується використовувати 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. Перший – заноситься в вершину дерева, наступні попадають в дерево за таким алгоритмом:  
   1) вибрати черговий ідентифікатор з потоку, якщо чергового нема, то побудова закінчена
2. зробити поточним вузлом дерева кореневу вершину
3. порівняти ім’я чергового ідентифікатора з іменем ідентифікатора який міститься в поточному вузлі
4. якщо ім’я чергового ідентифікатора менше – перейти до кроку 5, якщо дорівнює – зупинити алгоритм, оскільки однакових ідентифікаторів бути не повинно, інакше – перейти до кроку 7
5. якщо у поточного вузла існує ліва вершина, то зробити її поточним вузлом и повернутися до кроку 3, інакше – до кроку 8
6. створити нову вершину, помістити в неї інформацію про черговий ідентифікатор, зробити цю нову вершину лівою вершиною поточного вузла і перейти до кроку 1
7. якщо у поточного вузла є права вершина, то зробити її поточним вузлом і повернутися до кроку 3, інакше – до кроку 8
8. створити нову вершину, помістити в неї інформацію про черговий ідентифікатор, зробити нову вершину правою вершиною поточного вузла і перейти до кроку 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 поля: тип лексеми, вказівник на інформацію про лексеми. Не слід плутати таблицю лексем з таблицею ідентифікаторів тому, що таблиця лексем фактично містить весь текст початкової програми обробленої лексичним аналізатором.

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

Лексеми обов’язково  розміщені в тому ж порядку, що і в початковій програмі, а в  таблиці ідентифікаторів лексеми  розміщені в порядку зручному для пошуку.

 

Алгоритм роботи лексичного аналізатора:

1. переглядається вхідний потік символів програми на початковій мові до знаходження чергового символу, який обмежує лексеми;
2. для вибраної частини вхідного потоку відбувається розпізнавання лексеми;
3. при успішному розпізнаванні інформація про виділену лексему заноситься в таблицю лексем і алгоритм повертається на перший крок;
4. при неуспішному розпізнаванні видається сповіщення про помилку і наступні дії залежать від реалізації лексичного аналізатора: або його виконання зупиняється або робиться спроба розпізнати наступну лексему тобто крок 1;

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

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

 

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

Синтаксичний аналізатор – частина компілятора, яка відповідає за виявлення і перевірку синтаксичної конструкції вхідної мови. В задачу синтаксичного аналізатора входить:

1. знайти і виділити синтаксичні конструкції в тексті початкової програми;
2. встановити тип і перевірити правильність кожної синтаксичної конструкції;
3. представити синтаксичні конструкції в виді зручному для наступної генерації результуючої програми;

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

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

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

Отже конфігурація МП-автомата визначається 3 параметрами:

1. станом автомату;
2. поточним символом вхідного ланцюжка;
3. вмістом стека;

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

1.4 Генерація  об’єктного коду

 

Генерація об’єктного коду – це переведення компілятором внутрішнього представлення початкової програми в ланцюжок символів вихідної мови. Вихідною мовою компілятора, на відміну від транслятора, може бути або асемблер, або об’єктний код. Генерація об’єктного коду виконується після лексичного, синтаксичного і семантичного аналізу.