Прийняття звіту про мову ALGOL 58

Публікацію в грудні 1958 року звіту про мову ALGOL 58 (Perlis and Samelson) зустріли з великим ентузіазмом. У Сполучених Штатах нову мову уявляли скоріше набором ідей в області структури мови програмування, ніж універсальною мовою програмування. Дійсно, звіт про мову ALGOL створював враження не закінченого продукту, а чорнового документа, виставленого на міжнародне обговорення. Тим не менш, цей звіт став підґрунтям трьох основних робіт з розробки і реалізації мов програмування. В Університеті штату Мічиган була створена мова MAD (Arden et al., 1961). Американською військово-морською електронною групою (U. S. Naval Electronics Group) була створена мова NELIAC (Huskey et al., 1963). Корпорація з розробки систем System Development Corporation розробила і реалізувала мову JOVIAL (Shaw, 1963). Назва останньої мови — абревіатура від "Jules' Own Version of the International Algebraic Language" (Власна версія інтернаціональної алгебраїчної мови, розроблена Жулем), а сама вона єдиною версією мови, основою якої стала мова ALGOL 58 і яка була широко розповсюджена (Жулем був Жуль Шварц (Jules I. Schwartz), один з розробників мови JOVIAL). Мова JOVIAL стала широко використовуватись, оскільки чверть сторіччя вона була офіційною мовою наукових розробок ВВС США.

Інша частина обчислювального співтовариства Сполучених Штатів не була так прихильна до нової мови. Спочатку корпорація IBM і її головна наукова група SHARE, схоже, прийняли мову ALGOL 58. Корпорація IBM почала її реалізацію незабаром після публікації звіту, і група SHARE сформувала підкомітет SHARE IAL для вивчення цієї мови. Пізніше підкомітет запропонував асоціації АСМ стандартизувати мову ALGOL 58, і в такий спосіб корпорація IBM реалізувала його на всіх комп'ютерах 700-й серії. Проте, ентузіазм незабаром спав. Навесні 1959 року і корпорація IBM, і група SHARE, що мали вже досвід роботи з мовою FORTRAN, вирішили, що з них досить проблем і витрат, щоб починати роботу над новою мовою. У середині 1959 року і корпорація IBM, і група SHARE, що вклали чималі засоби в мову FORTRAN, вирішили підтримати саме цей проект і зробити його мовою наукових розробок для 700-й серії машин корпорації IBM, відмовившись, таким чином, від мови ALGOL 58.

Процес розробки мови ALGOL 60

Протягом 1959 року мова ALGOL 58 гаряче обговорювався як у Європі, так і Сполучених Штатах. У європейському виданні ALGOL Bulletin і в Communications of the АСМ була опублікована велика кількість пропозицій, що стосувались змін і доповнень до цієї мови. У 1959 році на Інтернаціональній конференції з обробки інформації (International Conference on Information Processing) була представлена робота Цюріхского комітету, у якій Бекус запропонував нову форму для опису синтаксису мов програмування, пізніше названу формою Бекуса-Наура (BNF — Backus-Naur form). Докладно вона описана в главі 3.

У січні 1960 року відбулися другі збори комітету з розробки мови ALGOL, цього разу в Парижі. На цих зборах мали обговорити 80 пропозицій, офіційно представлених на розгляд. При цьому розробкою мови ALGOL глибоко займався Питер Наур (Peter Naur) з Данії, незважаючи на те, що він не був членом Цюріхской групи. Саме Наур створив і видавав ALGOL Bulletin. Наур довгий час вивчав роботу Бекуса, що вводила поняття форми BNF, і прийшов до висновку, що цю форму можна використовувати для формального опису результатів зборів 1960 року. Після внесення у форму BNF декількох відносно невеликих змін Наур створив за її допомогою опис знову запропонованої мови і передав його комітету 1960 року на початку наради.

Огляд мови ALGOL 60

Хоча збори 1960 року тривали лише шість днів, зміни, внесені в мову ALGOL 58, були значними. Серед найважливіших нових розробок були наступні.

• Була введена концепція блокової структури. Це дозволило програмістам локалізувати частини програм, вводячи нові середовища даних, чи області видимості.

• З'явилася можливість передавати параметри підпрограмам двома новими способами: передача за значенням і передача за ім’ям.

• З'явилася можливість створення рекурсивних процедур. В описі мови ALGOL 58 це питання було висвітлене не зовсім ясно. Відмітимо, що, хоча для імперативних мов подібна рекурсія і була новою, мова LISP у 1959 році вже містила рекурсивні функції.

• З'явилися автоматичні (stack-dynamic) масиви. Автоматичним масивом називається такий масив, для якого діапазон чи діапазони зміни індексів визначаються значеннями змінних. Розмір масиву встановлюється під час його розміщення в пам'яті. Це відбувається в процесі виконання програми при оголошенні масиву. Автоматичні масиви докладно описані в главі 5.

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

Звіт про мову ALGOL 60 був опублікований у травні 1960 року (Naur, 1960). В описі мови усе ще залишалося багато невизначеностей, і на квітень 1962 року в Римі були призначені треті збори комітету, на розгляд якого і передавалися всі питання. На цих зборах група займалися тільки вирішенням ускладнень, ніяких нових доповнень у мову не вносилося. Результати зборів були опубліковані за назвою "Revised Report on the Algorithmic Language ALGOL 60" ("Перероблений звіт про алгоритмічну мову ALGOL 60") (Backus at al., 1962).

Оцінка мови ALGOL 60

Якщо судити з одних показників, то мова ALGOL 60 мала приголомшливий успіх, якщо з інших — була найбільшим провалом. Успіхом, що проявився практично одразу ж, було те, що вона стала єдиним офіційним засобом представлення алгоритмів у науковій літературі і понад 20 років залишалася ним. Кожна імперативна мова програмування, створена після 1960 року, щось запозичила у мови ALGOL 60. Більшість з них прямо чи опосередковано є нащадками мови ALGOL 60; як приклади можна назвати мови PL/I, SIMULA 67, ALGOL 67, ALGOL 68, З, Pascal, Ada, C++ і Java.

У процесі створення мов ALGOL 58/ALGOL 60 багато чого було зроблено вперше. Вперше інтернаціональна група спробувала розробити мову програмування. Мова ALGOL була першою машинно-незалежною мовою. Вона також була першою мовою з формально описаним синтаксисом. Це успішне використання форми BNF поклало початок декільком важливим галузям теорії обчислювальних систем: формальним мовам, теорії синтаксичного аналізу і теорії розробки компіляторів. У підсумку, структура мови ALGOL 60 вплинула на машинну архітектуру. Одним з найвидатніших прикладів цього є той факт, що розширена версія цієї мови використовувалася як системна мова в серії універсальних обчислювальних машин компанії Burrough: B5000, B6000 і В7000, що були сконструйовані з апаратно-реалізованим стеком для ефективної реалізації блокової структури і рекурсивних процедур мови.

Розглянемо зворотну сторону медалі: у Сполучених Штатах мова ALGOL 60 ніколи не набула широкого поширення чи хоча б значного використання. Навіть у Європі вона так і не стала домінуючою мовою. Можна навести безліч причин, що призвели до цього. По-перше, деякі властивості мови ALGOL 60 сталі занадто гнучкими; вони ускладнювали розуміння і робили реалізацію мови неефективною. Кращим прикладом цього є метод передачі підпрограмам параметрів за ім’ям, докладно описаний у главі 8. Складності реалізації мови ALGOL 60 сформулював Рутішаузер (Rutishauser, 1967), який зазначив, що далеко не всі (якщо такі взагалі є) реалізації містять мова ALGOL 60 повністю.

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

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

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

Робота над мовою ALGOL 60 у дійсності ніколи не закінчувалась в тому розумінні, що неясності і невизначеності завжди були частиною опису цієї мови (Knuth, 1967).

Нижче неведений приклад програми мовою ALGOL 60.

comment Приклад програми мовою ALGOL 60

Введення: Ціле число listlen, менше 100, за яким іде набір цілих чисел у кількості listlen

Виведення: Кількість введених величин, що більше їх середнього арифметичного;

Begin

integer array intlist [1:99];

integer listlen, counter, sum, average, result;

sum:= 0;

result:= 0;

readint (listlen);

if (listlen > 0) ^ (listlen < 100) then

Begin

comment Зчитування вхідних величин у масив і обчислення суми;

for counter:= 1 step 1 until listlen do

Begin

readint (intlist[counter]);

sum:= sum + intlist[counter]

end;

comment Обчислення середнього арифметичних;

average:= sum / listlen;

comment Обчислення кількості вхідних величин, що більше їх середнього;

for counter:= 1 step 1 until listlen do

if intlist[counter] > average

then result:= result + 1;

comment Виведення результатів;

printstring("Число величин, що більше їх середнього:);

printint (result)

End

Else

printstring ("Помилка — уведена невірна довжина списку");

End

 

Лекція 5.

on_load_lecture() Трансляція і формальні граматики

Транслятори

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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