Транслятори. Програма, написана на мові високого рівня, перед виконанням повинна бути перетворена в програму на "машинній мові"

Програма, написана на мові високого рівня, перед виконанням повинна бути перетворена в програму на "машинній мові". Такий процес називають трансляцією або компіляцією. По типу вихідних даних розрізняють два основні види трансляторів:

• Компілюють кінцевий код виконання;
• Компілюють код який інтерпретується і для виконання якого потрібно додаткове програмне забезпечення.

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

Мови, які формують кінцевий код виконання, називають компільованими мовами. До них відносяться мови С, C++, FORTRAN, Pascal.

Мови другого типу називають інтерпретованими мовами. До них відносяться Java, LISP, Perl, Prolog.

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

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

Будемо називати формою виконання програми код, який отримується в результаті трансляції програми.

5.2. Процес трансляції

Програму, написану на мові програмування високого рівня, називають (“исходной”) початковою програмою, а кожну самостійну програмну одиницю, яка утворює дану програму, - програмним модулем. Для перетворення початкової програми в її виконувану форму (файл виконання) транслятор виконує певну послідовність дій. Ця послідовність залежить як від мови програмування, так і від конкретної реалізації самого транслятора. В ході трансляції важливо не просто відкомпілювати програму, а і отримати достатньо ефективний код.

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

До переваги однопрохідного компілятора відносять високу швидкість компіляції, а до недоліків – отримання, як правило, не найбільш ефективного коду.

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

На рисунку 5.1 представлені основні етапи, які виконуються в процесі трансляції початкової програми.

Рис. 5.1. Основні етапи трансляції програми.

Фаза аналізу програми складається із:

• лексичного аналізу;
• синтаксичного аналізу;
• семантичного аналізу.

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

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

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

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

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

До найбільш загальних задач, що вирішує семантичний аналізатор, відносяться:

• знаходження помилок часу компіляції;
• заповнення таблиці символів конкретними значеннями, які визначають додаткову інформацію про кожен елемент таблиці;
• заміна макросів їх визначеннями;
• виконання директив часу компіляції.

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

На фазі синтезу програми проходить:

• генерація коду;
• редагування зв’язків.

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

Зауважимо, що на практиці термін "генерація коду" часто застосовують до всіх дій фази синтезу програми, які приводять до отримання форми виконання програми.

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

5.3. Формальні граматики. НБФ-граматика

Граматикою називається формальний опис синтаксису мови програмування.

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

Формальна граматика використовує строгу систему позначень. Існують різні типи граматик. НБФ-граматика (граматика Наура-Бэкуса або граматика Бэкуса-Наура - БНФ-граматика) є контекстно-вільною граматикою. Ця граматика використовує НБФ-нотації, запропоновані Джоном Бэкусом в кінці 50-х років для опису синтаксису мови ALGOL.

Проста НБФ-нотація дозволяє описувати всі достовірні конструкції мови програмування, використовуючи наступні символи:

• символ::= має значення "визначається як " і використовується для визначення всіх допустимих значень, синтаксичної одиниці визначення;
• символ | має значення " або " і використовується для опису альтернативних варіантів;
• пара символів < > обмежує ім’я синтаксичної одиниці, яку називають також не термінальним символом або синтаксичною категорією.

Значення, які стоять поза дужками < >, називаються термінальними символами.

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

Наприклад:

<цифра>::= 0|1|2|3|4|5|6|7|8|9<цілочисельне значення>::= цифра | цифра <цілочисельне значення>

Тут символи 0, 1, 2, 3 и т.д. будуть термінальними символами.

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

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

Можна сказати, що граматика складається із множин термінальних і не термінальних символів, початкового не термінального символу і набору правил. В 1959 році Ноам Хомський запропонував таку класифікацію граматик:

• регулярні граматики, які використовуються для побудови лексичних аналізаторів;
• контекстно-вільні граматики, використовуються для побудови дерева граматичного розбору. До цього типу відносяться і НБФ-граматики;
• контекстно-залежні граматики, задаються набором правил типу x->y, в яких х може бути довільним ланцюжком не термінальних символів, а y – ланцюжком термінальних і не термінальних символів.
• граматики з фразовою структурою задаються набором правил типу x->y, в яких х може бути довільним ланцюжком не термінальних символів, а y – ланцюжком термінальних і не термінальних символів (тут не має ніяких обмежень на довжину отримуваних ланцюжків). Більшість таких граматик не мають практичного застосування.

Розширена НБФ-нотація вводить ряд додаткових елементів, які дозволяють значно покращити наглядність представлення правил НБФ-граматики:

• необов’язкові елементи обмежуються квадратними дужками;
• альтернативні елементи, описані за допомогою символу вертикальної риски, також можуть бути необов’язковими елементами, якщо вони взяті в квадратні дужки;
• послідовність декількох однотипних елементів позначається заключенням їх в фігурні дужки, за якими ставиться символ зірочка або плюс({<ціле>}*). Зірочка позначає одне і більше повторення, а плюс – нуль і більше повторень.

Лекція 6.