ВСТУП
Перші програми, які створювалися ще для ЕОМ першого покоління, писалися безпосередньо на мові машинних код.
Написання програм в машинних кодах стало практично неможливим у міру зростання складності алгоритмів, а, власне, і кількості команд в програмі. Розвиток апаратури обчислювальних систем також ускладнював ситуацію: написані в машинних кодах програми були абсолютно непереносні, оскільки містили не просто алгоритмічні інструкції, а безпосередньо команди конкретного процесора. З цього виходив вивід, що людина не може і не повина говорити на мові машинних команд, навіть якщо вона фахівець з обчислювальної техніки. Проте всі спроби навчити ЕОМ говорити на мовах людей не увінчалися успіхом. У зв'язку з цим весь подальший розвиток програмного забезпечення комп'ютерів нерозривно пов'язаний з виникненням і розвитком компіляторів.
Першими компіляторами були компілятори з мов асемблера або, як вони називалися, мнемокодів. Мнемокоди значно спростили процес написання програм, замінивши шістнадцятькові коди команд процесора на більш менш доступну мову мнемонічних позначень цих команд. Така інструкція була вже змістовнішою і, крім того, не була так жорстко прив'язана до типу процесора. Проте виконувати сам мнемокод (мова асемблера) жоден комп'ютер не здатний, тому виникла необхідність в створенні компілятора, що перекладає текст програми, написаний на мові асемблера, в машинні коди. Ці компілятори достатньо прості, оскільки командами асемблера є примітивні синтаксичні конструкції, кожній з яких ставиться у відповідність, як правило, одна машинна команда.
Завдання компіляції асемблерних програм ускладнилося з появою макрокоманд, які в загальному випадку повинні були бути приведені в довільне число машинних інструкцій.
Наступним етапом стало створення мов високого рівня, що є деякою проміжною ланкою між чисто формальними мовами і мовами природного спілкування людей. Від перших їм дісталася строга формалізація синтаксичних структур (пропозицій) мови, від других – значна частина словарного запасу, семантика основних конструкцій і виразів (з елементами математичних операцій, що прийшли з алгебри).
Поява мов високого рівня істотно спростила процес програмування, дозволяючи програмістові концентруватися на алгоритмі вирішуваного завдання. Покращала і ситуація з переносимістю програм. Тепер в завдання компілятора входило правильно транслювати алгоритмічні інструкції в машинні команди конкретної архітектури процесора.
Як тільки виникла масова потреба, почала розвиватися теорія формальних мов і граматик, а також були розроблені алгоритми генерації машинних кодів, оптимізації і розподілу пам'яті. В даний час ця область доповнюється новими теоремами, алгоритмами, технічними рішеннями. Багато хто з них знайшов практичну реалізацію в комерційних компіляторах провідних фірм миру: Intel, Sun, Microsoft. З часом компілятори, як автономні транслюючі програми, були доповнені текстовими редакторами, системами відладки, засобами покрокового виконання програм, засобами візуального програмування і так далі Такі системи отримали назву «Системи програмування». Найбільш відомі системи програмування - Microsoft Visual Studio, Borland Delphi, KDevelop.
В даний час компілятори є невід'ємною частиною будь-якої обчислювальної системи. Без їх існування програмування будь-якого прикладного завдання було б утруднене. Програмування безпосередньо на мовах машинних кодів відбувається виключно рідко і лише для вирішення дуже вузького круга завдань.
1.Огляд методів та способів проектування трансляторів
Транслятор - обслуговуюча програма, що перетворює початкову програму, надану на вхідній мові програмування, в робочу програму, представлену на об'єктній мові.
Приведене визначення відноситься до всіх різновидів транслюючих програм. Проте у кожної з таких програм можуть бути свої особливості по організації процесу трансляції. В даний час транслятори розділяються на три основні групи: асемблери, компілятори і інтерпретатори.
Асемблер - системна обслуговуюча програма, яка перетворить символічні конструкції в команди машинної мови. Специфічною межею асемблерів є те, що вони здійснюють дослівну трансляцію однієї символічної команди в одну машинну. Таким чином, мова асемблера (ще називається автокодом) призначена для полегшення сприйняття системи команд комп'ютера і прискорення програмування в цій системі команд. Програмістові набагато легко запам'ятати мнемонічне позначення машинних команд, чим їх двійковий код. Тому, основний виграш досягається не за рахунок збільшення потужності окремих команд, а за рахунок підвищення ефективності їх сприйняття.
Разом з тим, мова асемблера, окрім аналогів машинних команд, містить безліч додаткових директив, що полегшують, зокрема, управління ресурсами комп'ютера, написання фрагментів, що повторюються, побудову багатомодульних програм. Тому виразність мови набагато багатша, ніж просто мови символічного кодування, що значно підвищує ефективність програмування.
Компілятор - це обслуговуюча програма, що виконує трансляцію на машинну мову програми, записаної на початковій мові програмування. Також як і асемблер, компілятор забезпечує перетворення програми з однієї мови на іншій (найчастіше, в мову конкретного комп'ютера). Разом з тим, команди початкової мови значно відрізняються по організації і потужності від команд машинної мови. Існують мови, в яких одна команда початкової мови транслюється в 7-10 машинних команд. Проте є і такі мови, в яких кожній команді може відповідати 100 і більш машинних команд (наприклад, Пролог). Крім того, в початкових мовах достатньо часто використовується строга типізація даних, здійснювана через їх попередній опис. Програмування може спиратися не на кодування алгоритму, а на ретельне обдумування структур даних або класів. Процес трансляції з таких мов зазвичай називається компіляцією, а початкові мови зазвичай відносяться до мов програмування високого рівня (або високорівневим мовам). Абстрагування мови програмування від системи команд комп'ютера привело до незалежного створення найрізноманітніших мов, орієнтованих на вирішення конкретних завдань. З'явилися мови для наукових розрахунків, економічних розрахунків, доступу до баз даних та інші.
Інтерпретатор - програма або пристрій, що здійснює пооператорную трансляцію і виконання початкової програми. На відміну від компілятора, інтерпретатор не породжує на виході програму на машинній мові. Розпізнавши команду початкової мови, він тут же виконує її. Як у компіляторах, так і в інтерпретаторах використовуються однакові методи аналізу початкового тексту програми. Але інтерпретатор дозволяє почати обробку даних після написання навіть однієї команди. Це робить процес розробки і відладки програм гнучкішим. Крім того, відсутність вихідної машинної коди дозволяє не "захаращувати" зовнішні пристрої додатковими файлами, а сам інтерпретатор можна достатньо легко адаптувати до будь-якої машинної архітектури, розробивши його тільки один раз на широко поширеній мові програмування. Тому, мови, що інтерпретуються, типу Java Script, VB Script, набули широкого поширення. Недоліком інтерпретаторів є низька швидкість виконання програм. Програми, що зазвичай інтерпретуються, виконуються в 50-100 разів повільніше за програми, написані в машинних кодах.
2.Формальний опис вхідної мови прогамування Паскаль
2.1.У процесі створення нових мов програмування та в зв'язку з розробкою трансляторів виникає проблема формалізації опису синтаксису мов програмування. Мови, що використовуються для формалізації синтаксису інших мов, називаються метамовами. Зараз найбільш уживаною для опису синтаксису мов програмування є метамова форм Бекуса-Наура (скорочено БНФ). Ідея цієї метамови полягає в структуруванні понять вихідної мови програмування і визначення більш складних понять через більш прості.
Алфавіт - це довільна множина символів. Поняття символу не визначається. Ланцюжок символів (слово) - це довільна послідовність символів, що записані рядом. Множина усіх ланцюжків, що складаються з елементів множини X позначають через X*. Мова - це підмножина X*. Приклади мов: Паскаль, C, С++, {0n1n | n >= 0 }.
Мову можна задати так:
- перелічити всі ланцюжки (слова);
- за допомогою механізму породження слів - граматики;
- написати програму, що одержує на вхід ланцюжок символів і видає відповідь "так", якщо ланцюжок належить мові і "ні" у супротивному випадку.
Щоб задати граматику G=<N,T,P,S>, потрібно вказати:
- множину символів алфавіту (чи термінальних символів) T. Найчастіше позначають їх малими символами алфавіту та цифрами;
- множину N нетермінальних символів (чи метасимволів), що не перетинається з T зі спеціально виділеним початковим символом S (аксіомою). Будемо позначати їх великими буквами;
- множину P правил виводу, що визначають правила підстановки для ланцюжків.
Кожне правило складається з двох ланцюжків (наприклад, p та q), причому ланцюжок p повинен містити принаймні один нетермінал. Правило виводу означає, що ланцюжок p у процесі виводу можна замінити на q. Вивід ланцюжків мови починається з нетермінала S (аксіоми). Правила граматики записують у вигляді
p ® q.
Більш строго поняття виведеного ланцюжка подамо так:
- аксіома S - виведений ланцюжок;
- якщо apb - виведений ланцюжок і в граматиці є правило p ® q, то aqb - виведений ланцюжок;
- означена граматикою мова складається з виведених ланцюжків, що містять тільки термінальні символи.
Приклади:
а) S ® e
S ® 0S1
б) S ® e
S ® (S)
S ® SS
Тут e означає порожній ланцюжок (довжини 0). Для скорочення запису прийнято використовувати символ "|" (читають "або") . Коротка форма запису попередніх прикладів:а) S ® e | 0S1 б) S ® e | (S) | SS
Граматики є метамовами. Вище була описана "академічна" форма запису метамови. На практиці застосовується також інша форма запису, яку за традицією називають нормальними формами Бекуса-Наура (БНФ).
У метамові БНФ прийняті певні угоди.
Будь-яке поняття мови програмування зображується своїм найменуванням, укладеним у кутові дужки: <...> . Наприклад, речення БНФ, що подає одне визначення деякого поняття Паскаля через інші, має такий вигляд:
поняття Паскаля знак "::=" визначення цього поняття.
У складі визначення можуть використовуватися інші поняття мови програмування, символи алфавіту (термінальні символи) і ключові слова мови програмування, а також спеціальні символи мови БНФ (метасимволи), що мають визначене значення. У якості таких символи використовуються вертикальна риса, квадратні і фігурні дужки. У перші роки використання БНФ множина метасимволів обмежувалась знаком "::=" та вертикальною рисою, квадратні і фігурні дужки (а і потім і круглі) додались у розширених версіях БНФ.
2.2 Побудова конструкцій БНФ підкоряється наступним правилам:
запис <поняття1> ::= <поняття2> <поняття3> і т.д. означає, що перше поняття в Паскалі являє собою послідовний запис інших понять;
запис <поняття1> ::= <поняття2> | <поняття3> | і т.д. означає, що перше поняття збігається з одним з інших понять;
круглі дужки використовуються для угруповання складних конструкцій БНФ усередині простих;
частина визначення, укладена в квадратні дужки, не обов'язкова;
частина визначення, укладена у фігурні дужки, може бути повторена довільне число раз (у тому числі жодного разу);
у якості неозначуваних елементів у правій частині БНФ можуть бути термінальні символи (символи основного алфавіту та ключові слова означуваної мови); для того, щоб відрізняти їх від метасимволів БНФ (наприклад, дужок) у друкованих текстах практикують виділення символів означуваної мови програмування і ключових слів (напр., жирним шрифтом, курсивом, підкресленням або ж, як це прийнято в окремих описах мови C, укладення термінальних символів в одинарні лапки).
Термінали в БНФ записуються як звичайні символи алфавіту, а нетермінали - як імена в кутових дужках < та >.
Наприклад, граматику для множини цілих чисел без знаку можна записати у вигляді:
<число> ::= <цифра> | <цифра> <число>
<цифра> : := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |9
Якщо розглянути мову найпростіших арифметичних формул:
<формула> ::= (<формула>) |<число> | <формула><знак><формула>
<знак> : := + | *
Наведу послідовність перетворень ланцюжків (так званий quot;розбір" або "вивід") для ланцюжка 3+5*2. Необхідно зобразити виконувані заміни ланцюжків у вигляді дерева розбору (або дерева виводу). За традицією дерево зображується "догори ногами":
Як і кожне дерево, дерево виводу для виразу з прикладу має ребра і вузли (позначені терміналами та нетерміналами), з яких ростуть гілки. Кінцеві вузли (термінали) називаються листами. Одне й те ж дерево розбору може описувати різні виводи (у дереві не фіксується порядок застосування правил). Якщо для одного й того ж ланцюжка можна побудувати два різних дерева розбору (або, що то ж саме, побудувати, два різних правих виводи), граматика називається неоднозначною. Описана вище граматика є неоднозначною. Ту ж мову можна описати й однозначною граматикою:
<формула> ::= <терм> | <терм><знак> <формула>
<терм> ::= (<формула>) | <число>
<знак> : := + | *
Наведемо кілька прикладів. Непорожній список, що складається з довільної кількості елементів, розділених комою, описується так:
<список> ::= <елемент списку> {, <елемент списку>}
Якщо ж список може бути порожнім, то його опис буде виглядати так:
<список> ::= | <елемент списку> {, <елемент списку>}
Інший приклад. Ідентифікатором є послідовність букв і цифр, що починається з букви:
<ідентифікатор>::=<буква>{<буква>|<цифра>}
Той факт, що параметри в процедурі можуть бути відсутніми, відбивається за рахунок укладання списку параметрів у квадратні дужки:
<заголовок процедури> ::= procedure <ім'я процедури> [(<параметри>)];
Використання круглих дужок ілюструється на прикладі опису процедури або функції, що є або описом процедури, або описом функції, після чого іде крапка з комою:
< процедура чи функція>::=(<процедура>|<функція>);
Далі наведемо кілька фрагментів опису синтаксису мови Паскаль . Так подається загальна структура програми на Паскалі в термінах мови БНФ:
<опис програми> ::=
<заголовок програми>
<блок оголошень>
<блок процедур і функцій>
<операторна частина> .
<заголовок програми> ::=
program <ім'я програми> [ (<список параметрів>) ];
<блок оголошень> ::={<розділ оголошень>; }
<розділ оголошень> ::= <розділ констант> | <розділ типів> |
<розділ змінних> | <розділ міток> | <розділ модулів>
<розділ констант> ::=
const <опис константи> {; <опис константи>}
<опис константи> ::= <ім'я константи> [ : <тип> ] = <вираз>
<розділ типів> ::= type <опис типу> {; <опис типу>}
<опис типу> ::= <ім'я типу> = <тип>
<розділ змінних> ::=
var <оголошення змінних> {; <оголошення змінних>}
<оголошення змінних> ::=
<ім'я змінної> {, <ім'я змінної> }: <тип>
<розділ міток> ::= label <мітка> {, <мітка>}
<мітка> ::= <ціле без знака> | <ідентифікатор>
<розділ модулів> ::= uses <ім'я модуля> {, <ім'я модуля>}
<блок процедур і функцій> ::= {<опис процедури чи функції> }
<опис процедури чи функції>::= (<опис процедури> | <опис функції>) ;
<опис процедури> ::=
<заголовок процедури>
<блок оголошень>
<заголовок процедури> ::=
procedure <ім'я процедури> [(<список формальних параметрів>)];
<список формальних параметрів> ::=
<формальний параметр> { ; <формальний параметр> }
<формальний параметр> ::=
[var] <ім'я параметра> {, <ім'я параметра> }: <ім'я типу>
<опис функції> ::=
<заголовок функції>
<блок оголошень>
<операторна частина>
<заголовок функції> ::= function <ім'я функції>
[ (<список формальних параметрів>) ] : <ім'я типу>;
<операторна частина> ::=
begin ( | <оператор>{; <оператор> }) end
Зазначимо, що імена констант, типів, змінних, модулів, функцій і процедур є ідентифікаторами
Як інший приклад фрагмента синтаксису Паскаля наведемо опис специфікації типу:
<тип> ::= <ім'я стандартного типу> | <ім'я користувацького типу> |
<перелічимий тип> | <діапазон> | <тип масиву> | <тип запису> |
<тип множини> | <тип файлу>
<перелічимий тип> ::= ( <ідентифікатор> {, <ідентифікатор> } )
<діапазон> ::= <значення> .. <значення>
<тип масиву> ::= array [<ім'я типу> | <діапазон>] of <тип>
<тип запису> ::= record <поле запису> {; <поле запису> } end
<поле запису> ::= <ім'я поля> : <тип>
<тип множини> ::= set of ( <ім'я типу> | <діапазон> )
<тип файлу> ::= file of <тип>