Технологія обробки тексту програми

Трансляція програм

Програма, написана на алгоритмічній мові програмування не може бути безпосередньо виконана на ЕҐОМ – вона містить тільки текст, що описує послідовність дій. Щоб одержати працюючу програму, треба цей текст перевести на машинну мову.

Процес перекладу вихідного тексту програми, написаного на мові високого рівня, в машинну мову називається трансляцією (від англ. translation — переклад). Трансляція - це чисто технічна робота і її доручають ПК.

Існує два способи трансляції:

- інтерпретація (від англ. interpretation) – пооператорний переклад і виконання команд програми. Кожна інструкція програми перекладається в машинний код та виконується, і тільки після цього процесор переходить до обробки наступної інструкції. Процес продовжується до першої помилки або, якщо помилок немає, - до кінця програми. Це гнучка система перекладу, яка реалізовується нескладно;

- компіляція (від англ. compile — збирати) - автоматичний переклад усього тексту програми в машинний код і формування об'єктного модуля, який згодом може бути виконаний самостійно. При цьому паралельно здійснюється синтаксичний контроль програми в цілому. Відтрансльована програма не виконується негайно, а зберігається в пам'яті комп'ютера. При перегляді програми компілятор виділяє місце в пам’яті для кожної змінної.

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

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

Однак, інтерпретатор корисний як при налагодженні, так і при трансляції програм, схильних до частих змін: виправлену програму можна відразу запустити на виконання, щоб перевірити її працездатність. При використанні ж компілятора виправлену програму доводиться перекомпільовувати. Інтерпретатор використовується в тих випадках, коли потрібна простота трансляції (Basic), або там, де інший спосіб перекладу дуже складний або навіть неможливий (Lisp).

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

Мовами інтерпретуючого типу є BASІC, LISP, Perl, Prolog, Java; компілюючого типу – FORTRAN, Pascal, С, C++.

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

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

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

Наприклад, рядок програми на мові С/С++

len = 3.14*r;

складається з наступних лексем: len, “=”, 3.14, “*”, r, “;”.

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

Більшість сформованих сканером лексем мають точно визначений правилами мови зміст: ключові слова (наприклад, if, for, while) вказують на дії, які задаються синтаксисом мови програмування; операції (типу “+”, “*”) вказують на певні дії (арифметичні, логічні тощо) або на пересилку даних; числа задають реальні числові значення (скажімо 5 або 7); знаки пунктуації допомагають транслятору розібратися в структурі програми. Інший різновид лексем - ідентифікатори - не мають точно визначеного правилами мови змісту, наприклад, ім'я програми, імена змінних або констант.

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

Токен	Приклади лексем	Опис	Примітка
if	if	оператор	одна лексема
relation	>, <=	операції відношення	< або <= або = або <> або >= або >
id	count, Name1	ідентифікатор	багато лексем
num		числова стала	багато лексем
string	"Мова C++"	рядкова стала	багато лексем

Тут шаблон для символу if - це єдиний рядок if, що повторює ключове слово. Шаблоном для символу relation є множина усіх відношень мови програмування (наприклад, < або <= або = або <> або >= або >). Для точного опису шаблонів більш складних токенів, таких як id чи num, використовується нотація регулярних виразів.

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

Синтаксичний аналіз (від англ. parsing). Це процес аналізу отриманих на попередньому етапі токенів з метою розбору граматичної структури тексту програми у відповідності із заданою формальною граматикою.

Синтаксичний аналізатор отримує від сканера токени і розташовує їх у вигляді синтаксичного дерева - структури, яка дозволяє транслятору розібратися в логіці програми. Токен може бути або «батьком», або «сином», або тим і іншим одночасно. Синтаксичний аналізатор розміщує токен в дереві, аналізуючи його зміст, зміст токена, що передує даному, а інколи і наступного токена. Групи токенів об'єднуються в оператори - основні структурні одиниці програми.

Приклад синтаксичного дерева розбору для виразу:

Побудовою дерева управляє набір явно записаних правил: кожній послідовності токенів відповідає один-єдиний спосіб розміщення їх у дереві.

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

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

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

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

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

Якщо типи синів одного батька не збігаються, то транслятор використовує правило, що дозволяє йому продовжити роботу. Наприклад, якщо один із синів має цілий, а інший - дійсний тип, то таке правило може вказувати, що батько повинен мати дійсний тип. Проте можливі недопустимі поєднання типів. На малюнку показаний випадок, коли один син має цілий (I) тип, а другий - літерний (C). Для такої комбінації типів не існує правила дозволу, і тому транслятор видає програмістові повідомлення про помилку.

Контроль типів грає ще одну дуже важливу роль: дає транслятору додаткову інформацію про лексему, яка потрібна при генерації коду. Наприклад, операція «+» діє по-різному, а значить, вимагає різного машинного коду - залежно від типів її доданків.

Генерація коду. Цепроцесрозбору синтаксичного дерева для отримання машинних команд. Генератор коду вирішує основну задачу транслятора: перетворює лексеми в послідовності машинних команд, керуючих комп'ютером. Він виконує це в процесі обходу синтаксичного дерева. З вузлів дерева в певному порядку витягуються лексеми. Коли набирається кількість, достатня для визначення потрібної операції, відбувається генерація відповідних машинних команд і обхід дерева поновлюється.

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

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