Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Короткий огляд процесу трансляції
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лекція
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Короткий огляд процесу трансляції.
Основою будь-якої природної або штучної мови є алфавіт − набір допустимих у даній мові елементарних знаків. Для природних мов це букви і знаки пунктуації, для мов програмування − латинські букви, цифри, спеціальні символи. Знаки можуть об'єднуватись у слова − елементарні конструкції мови, які розглядаються у тексті (програмі) як неподільні символи, що мають певний зміст. Словом може бути і окремий знак. Наприклад, у мові програмування словами вважаються ідентифікатори, службові слова, константи, а також односимвольні або двосимвольні позначення операцій, дужки, коми та ін. Словарний склад мови разом з описом способів їх зображення утворюють лексику мови.
Слова у мові об'єднуються у складніші конструкції − речення. У мовах програмування найпростішим реченням є оператор. Взагалі речення будуються із слів та простіших речень згідно з правилами синтаксису. Синтаксис мови − це опис правильних речень. Опис змісту речень, тобто значень слів та їх внутрішніх зв'язків, утворює семантику мови.
Переклад програми з одної мови на іншу, у загальному випадку, полягає у зміні алфавіту, лексики і синтаксису програми із збереженням її семантики. Процес трансляції вхідної програми в об'єктну розбивається на декілька незалежних підпроцесів.
Складові частини компілятора
Транслятор повинен виконати аналіз вхідної програми, а потім синтез об'єктної програми. Спочатку вхідна програма розкладається на її складові частини, а потім з них будуються ( складаються) частини еквівалентної об'єктної програми. Для цього на етапі аналізу будуються декілька таблиць, які використовуються потім як при аналізі, так і при синтезі.
На наступній схемі весь процес показано детальніше. Пунктирні стрілки зображають інформаційні потоки, а суцільні стрілки вказують порядок роботи програм.
Опишемо коротко різні частини компілятора (транслятора).
Інформаційні таблиці.
При аналізі програм з описів, заголовків процедур, заголовків циклів і т.д. вибирається інформація і зберігається для подальшого використання. Ця інформація виявляється в окремих точках програми і організовується так, щоб до неї можна було звернутись з будь-якої частини компілятора. Наприклад, при кожному використанні ідентифікатора необхідно знати, як був описаний цей ідентифікатор і як він використовувався в інших місцях програми. Конкретна інформація, що зберігається, залежить від вхідної мови, об’єктної мови і складності компілятора. Але у кожному компіляторі використовується таблиця символів ( інші назви − таблиця імен або список ідентифікаторів). Це таблиця ідентифікаторів, які зустрічаються у вхідній програмі, разом з їх атрибутами ( тип ідентифікатора, його адреса в об'єктній програмі та інша інформація, яка може бути потрібна для трансляції).
Таблиця констант включає саму константу і відповідна адреса в об'єктній програмі.
Таблиця заголовків циклів відображає структуру вкладень циклів. У ній зберігається інформація про змінні циклів.
При розробці компілятора неможливо визначити вигляд і зміст інформації, яку варто збирати, до того часу, поки не будуть досить ретельно продумані команди об'єктної програми для кожної інструкції вхідної програми і сама об'єктна частина компілятора.
SHAPE \* MERGEFORMAT
КОМПІЛЯТОР
СИНТЕЗ
Вхідна програма
АНАЛІЗ
Лексичний
аналізатор
(сканер)
Синтаксичний
і
семантичний
аналізатори
Підготовка
до генерації
команд
Генерація команд
Об'єктна програма
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Мал.1 Логічні частини компілятора.
Сканер (лексичний аналізатор).
Сканер (лексичний аналізатор) − найпростіша частина компілятора. Сканер проглядає літери вхідної програми зліва направо і будує символи (лексеми, слова, атоми) програми − цілі числа, ідентифікатори, службові слова, дволітерні розділювачі. Символи передаються після цього на обробку фактичному аналізатору (синтаксичному). На цьому етапі можна усунути коментарі. Сканер може заносити ідентифікатори в таблицю символів і виконувати іншу просту роботу, яка не вимагає аналізу структури вхідної програми. Він може виконати більшу частину роботи, яка стосується макрогенерації, коли потрібна тільки текстова підстановка.
Зазвичай сканер передає символи аналізатору у внутрішній формі (деякому коді). Кожен розділювач (службове слово, знак операції або знак пунктуації) можна зобразити цілим числом. Ідентифікатори і константи можна зобразити парою чисел. Це дає змогу в інших частинах компілятора працювати ефективно, оперуючи з символами фіксованої довжини, а не з ланцюжками літер змінної довжини.
Синтаксичний і семантичний аналізатори.
Ці аналізатори виконують складну роботу з розбиття вхідної програми на складові частини, формуванню її внутрішнього зображення і занесення інформації у таблицю символів та інші таблиці. При цьому також виконується повний синтаксичний і семантичний контроль програми.
Звичайний аналізатор є синтаксично керованою програмою. В дійсності намагаються відокремити, наскільки це можливо, синтаксис від семантики. Коли синтакичний аналізатор (розпізнавач) розпізнає конструкцію вхідної мови, він викликає семантичну процедуру або семантичну програму, яка контролює дану конструкцію з точки зору семантики, а потім запам'ятовує відповідну інформацію у таблиці символів або у внутрішньому коді.
Наприклад, коли розпізнається опис змінних, відповідна семантична програма перевіряє ідентифікатори, виявляючи повторні описи, і заносить ідентифікатори разом з їх атрибутами у таблицю символів.
Коли зустрічається оператор присвоєння
<змінна>::=<вираз>,
семантична програма перевіряє змінну і вираз на відповідність типів, а потім заносить оператор присвоєння у програму у внутрішньому зображенні.
Внутрішнє зображення (внутрішня форма) вхідної програми.
Внутрішня форма вхідної програми залежить значною мірою від її подальшого використання. Це може бути дерево, що відображає структуру вхідної програми. Це також може бути польський інверсний запис або інші внутрішні форми. Наприклад, присвоєння А=В+С*D у формі тетрад (операція, операнд, операнд, результат) буде зображено так:
*,C,D,T1
+,B,T1,T2
=,T2, ,A,
де Т1, Т2 − тимчасові змінні, утворені компілятором. Операндами у наведеному прикладі будуть не самі символьні імена, а покажчики на ті елементи( або їх індекси) в таблиці символів, у яких описані ці операнди.
Підготовка до генерації команд.
Перед генерацією команд, як правило, потрібно певним чином обробити і змінити внутрішню програму. Крім того, потрібно розподілити пам'ять під змінні готової програми. Важливим моментом на цьому етапі є оптимізація програми з метою зменшення часу її роботи.
Генерація команд.
На цьому етапі відбувається переклад внутрішнього зображення (внутрішньої форми) вхідної програми на мову асемблера чи машинну мову.
Для наведеного вище прикладу можна згенерувати такі команди на мові асемблера:
mov al, C
mul al, D
add ax, B
mov A,ax
У інтерпретаторі ця частина компілятора заміняється програмою, яка фактично виконує (інтерпретує) внутрішнє зображення вхідної програми. При цьому саме внутрішнього зображення мало чим відрізняється від того, яке отримано при компіляції.
Компілятор в певному сенсі визначається вхідною і вихідною мовами. Але це не означає, що всі компілятори з певної мови для певної серії машин повинні бути однаковими. Великою мірою відмінність компіляторів залежить від того, яка мета ставиться при розробці компіляторів. Для одної і тої самої мови може бути розроблено декілька компіляторів. У наведеній схемі показано логічні зв'язки між окремими частинами компілятора, а не обов'язкова послідовність роботи.
Структура транслятора. Блоки і проходи.
Під структурою транслятора будемо розуміти організацію програми трансляції. Ця структура буде залежати від рівня вхідної і вихідної мов, вимог до об'єктної програми, властивостей машини (зокрема, наявна пам'ять, організація вводу−виводу) і методів трансляції.
Умовно методи трансляції можна поділити на 2 групи.
Прямі методи, орієнтовані на конкретні вхідні мови. Це переважно евристичні методи, у яких на основі деякої загальної ідеї для кожної конструкції вхідної мови розробляється алгоритм трансляції. Етапи синтаксичного і семантичного аналізу чітко не розрізняються.
Синтаксичні методи розроблені пізніше на основі теорії формальних граматик. Вони орієнтовані не на конкретну вхідну мову, а на деякий клас вхідних мов, точніше, на певний спосіб опису синтаксису мови. Наявне певне відокремлення синтаксичного і семантичного аналізу.
Взаємодія між окремими частинами (блоками) компілятора може бути організована різними способами:
послідовне виконання окремих блоків компілятора;
паралельне виконання з певною взаємною синхронізацією.
Розглянемо, наприклад, взаємодію між лексичними і синтаксичними блоками. Ця взаємодія може бути організована такими способами:
кожний раз, коли лексичний блок розпізнає лексему, управління передається синтаксичному блоку для обробки цієї лексеми. Коли виникає необхідність в наступній лексемі, управління передається у лексичний блок;
лексичний блок видає весь ланцюжок лексем до того, як управління передається синтаксичному блоку. У цьому випадку говорять, що робота лексичного блоку утворює окремий прохід.
Прохід − це кожне зчитування вхідного тексту або його версії компілятором. Питання про кількість проходів є дуже важливим при побудові компілятора. При цьому враховуються різні критерії. Такими критеріями можуть бути:
обсяг доступної пам'яті;
мета, яка ставиться при розробці компілятора (отримання ефективного об’єктного коду; мінімізація часу компіляції програми, створення компілятора з широкими можливостями виявлення і виправлення помилок, забезпечення надійності компілятора);
логіка вхідної мови;
кількість розробників компілятора.
На жаль, сформульовані критерії мають певні протиріччя. Компілятор для побудови ефективного коду буде працювати набагато повільніше у порівнянні з іншим компілятором. Для виконання деяких стандартних методів оптимізації може бути потрібно багато часу. Оптимізуючий компілятор є також більшим за обсягом.
Тому часто фірми-розробники пропонують для деяких мов не один компілятор, а декілька.
Однопрохідні компілятори приваблюють своєю простотою. На мал. 2 показано типову схему однопрохідного компілятора.
Вхідна
програма
Звернення
Сканер
(лексичний аналізатор)
Семантичний аналізатор
Розподіл пам'яті
Генератор команд
Синтаксичний
аналізатор
за символом Конструкція
Повернення Повернення
у символу
Формування об'єктної програми і завершення роботи
Об'єктна
програма
Мал. 2. Схема однопрохідного компілятора
У однопрохідному компіляторі синтаксичний аналізатор виступає в ролі основної управляючої програми. Синтаксичний аналізатор викликає сканер, коли потрібен новий символ, і викликає процедуру, коли розпізнано конструкцію мови. Ця процедура викликає семантичну перевірку, розподіл пам'яті і генерує команди перед тим, як повернутись до розпізнавання. Така організація компілятора характеризується високою швидкістю, оскільки програма проглядається тільки один раз, і відсутні операції звертання до файлів. В однопрохідному компіляторі немає потреби у внутрішньому зображенні (внутрішніх формах) програм, у той час як етапи підготовки і генерації суміщаються з семантичними програмами.
Створення багатопрохідних компіляторів зазвичай пов'язане з проектуванням проміжних мов для версій вхідного тексту, що існують між проходами. Будуються також таблиці окремого проходу, які можуть знадобитись для прогляду у наступному проході чи проходах. Тому організація багатопрохідного компілятора видається складнішою і повільнішою у порівнянні з організацією однопрохідного компілятора, хоча окремі проходи можуть бути досить простими. Вони дозволяють поділити завдання між різними виконавцями або групами виконавців і не вимагають складних взаємозв'язків між ними. Зв’язок між проходами здійснюється тільки через файли даних.
Зазвичай багатопрохідні компілятори займають у пам’яті менше місця, ніж однопрохідні, оскільки код кожного проходу може знову використовувати пам'ять, яку займав код попереднього проходу.
Кожен прохід компілятора можна організувати у вигляді одного блоку або декількох блоків. Можлива також організація, коли для реалізації одного блоку потрібно декілька проходів.
Не всі мови допускають однопрохідну трансляцію. Потреба у декількох (принаймні, двох) проходах виникає, коли у певний момент компілятору потрібна інформація з іще не проглянутої частини програми (наприклад, опис змінної з’являється після її використання). Деякі мови, такі, як ФОРТРАН чи ПАСКАЛЬ, можна скомпілювати за один прохід. Транслятори-асемблери зазвичай є двохпрохідними.
Наприкінці відзначимо, що найпростішою для реалізації частиною компілятора є лексичний аналізатор. Для порівняно простих мов розробка синтаксичного аналізатора теж не викликає значних труднощів.
Найбільш важливими і заплутаними частинами компілятора є семантичний аналіз, програми підготовки генерації і програми генерації команд. Ці три частини взаємопов’язані, повинні в значній мірі розроблятись спільно і можуть суттєво (чи навіть докорінно) змінитись при переході з однієї об'єктної мови на іншу або з одної машини на іншу.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора