• Адресний. Функціональний пристрій, що перетворює віртуальну адресу (англ. Virtual address) на реальну адресу.
• Діалоговий. Забезпечує використання мови програмування в режимі розподілу часу.
• Багатопрохідний. Формує об'єктний модуль за декілька переглядів вихідної програми.
• Зворотній. Те саме, що детранслятор. також: декомпілятор, дизассемблер.
• Однопрохідний. Формує об'єктний модуль за послідовний перегляд вихідної програми.
• Оптимізуючий. Виконує оптимізацію коду в об'єктному модулі, що створюється.
• Синтаксично-орієнтований (синтаксично-керований).Отримує на вхід опис синтаксису та семантики мови та текст описаною мовою, який і транслюється відповідно до заданого опису.
• Тестовий. Набір макрокоманд мови асемблера, що дозволяють задавати різні процедури налагодження в програмах, складених мовою асемблера.

Мета трансляції- перетворити текст з однієї мови на іншу, яка зрозуміла адресату тексту. У випадку програм-трансляторів адресатом є технічний пристрій (процесор) або програма-інтерпретатор.

Мова процесорів (машинний код) зазвичай є низькорівневим. Існують платформи, які використовують як машинну мову високого рівня(наприклад, iAPX-432), але вони є винятком із правила через складність і дорожнечу. Транслятор, який перетворює програми на машинну мову, який приймається і виконується безпосередньо процесором, називається компілятором.

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

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

Інший метод реалізації – коли програма виконується за допомогою інтерпретаторавзагалі без трансляції. Інтерпретатор програмно моделює машину, цикл вибірки виконання якої працює з командами мовами високого рівня, а не з машинними командами. Таке програмне моделюваннястворює віртуальну машину, що реалізує мову. Цей підхід називається чистою інтерпретацією. Чиста інтерпретація застосовується зазвичай для мов із простою структурою (наприклад, АПЛ чи Лисп). Інтерпретатори командного рядкаобробляють команди в скриптах UNIX або пакетних файлах (.bat) в MS-DOS також зазвичай у режимі чистої інтерпретації.

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

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

Трансляціяі інтерпретація - різні процеси: трансляція займається перекладом програм з однієї мови на іншу, а інтерпретація відповідає за виконання програм. Однак, оскільки метою трансляції зазвичай є підготовка програми до інтерпретації, ці процеси зазвичай розглядаються разом. Наприклад, мови програмування часто характеризуються як "компілювані" або "інтерпретовані", залежно від того, переважає при використанні мови компіляція або інтерпретація. Причому практично всі мови програмування низького рівня і третього покоління, на зразок асемблера, Сі або Модули-2, є компілюваними, а більш високорівневі мови, як Python або SQL, - інтерпретовані.

З іншого боку, існує взаємопроникнення процесів трансляції та інтерпретації: інтерпретатори можуть бути компілюючими (у тому числі з динамічною компіляцією), а в трансляторах може бути потрібна інтерпретація для конструкцій метапрограмування (наприклад, для макросів у мові асемблера, умовної компіляції у Сі або для шаблонів C ++).

Більше того, та сама мова програмування може і транслюватися, і інтерпретуватися, і в обох випадках повинні бути присутніми загальні етапи аналізу та розпізнавання конструкцій та директив вихідної мови. Це стосується і програмних реалізацій, і апаратних - так, процесори сімейства x86 перед виконанням інструкцій машинної мови виконують їх декодування, виділяючи в опкодах поля операндів (регістрів, адрес пам'яті, безпосередніх значень), розрядності тощо, а в процесорах Pentiumз архітектурою NetBurst машинний код перед збереженням у внутрішньому кеші взагалі транслюється у послідовність мікрооперацій.

РОЗДІЛ 7. Трансляція, компіляція та інтерпретація

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

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

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

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

Транслятор зазвичай виконує також діагностику помилок, формує словники ідентифікаторів, видає тексти програми для друку і т.д.

Трансляція програми -перетворення програми, представленої однією з мов програмування, на програму іншою мовою і, у певному сенсі, рівносильну першої.

Мова, на якій представлена ​​вхідна програма, називається вихідною мовою, а сама програма - вихідним кодом. Вихідна мова називається цільовою мовоюабо об'єктним кодом.

Види трансляторів

Транслятори поділяють:

· Адресний. Функціональний пристрій, що перетворює віртуальну адресу (англ. Virtual address) на реальну адресу (англ. Memory address).

· Діалоговий. Забезпечує використання мови програмування в режимі розподілу часу.

· Багатопрохідний. Формує об'єктний модуль за декілька переглядів вихідної програми.

· Зворотній. Те саме, що детранслятор. також: декомпілятор, дизассемблер.

· Однопрохідний. Формує об'єктний модуль за послідовний перегляд вихідної програми.

· Оптимізуючий. Виконує оптимізацію коду в об'єктному модулі, що створюється.

· Синтаксично-орієнтований (синтаксично-керований). Отримує на вхід опис синтаксису та семантики мови та текст описаною мовою, який і транслюється відповідно до заданого опису.

· Тестовий. Набір макрокоманд мови асемблера, що дозволяють задавати різні процедури налагодження в програмах, складених мовою асемблера.

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

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

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

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

Компілювати -проводити трансляцію машинної програми з проблемно-орієнтованої мови машинно-орієнтованою мовою.

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

Інтерпретатор(англ. interpreter- тлумач, усний перекладач) перекладає та виконує програму рядок за рядком. Інтерпретатор бере черговий оператор мови з тексту програми, аналізує його структуру і потім одразу виконує (зазвичай після аналізу оператор транслюється в деяке проміжне уявлення або навіть машинний код для більш ефективного виконання). Тільки після того, як поточний оператор успішно виконано, інтерпретатор перейде до наступного. При цьому якщо один і той же оператор виконуватиметься в програмі багаторазово, інтерпретатор виконуватиме його так, начебто зустрів уперше. Внаслідок цього програми, в яких потрібно здійснити великий обсяг обчислень, виконуватимуться повільно. Крім того, для виконання програми на іншому комп'ютері там теж має стояти інтерпретатор - адже без нього текст є просто набір символів.

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

Відмінностіміж компіляцією та інтерпретацією.

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

2. Відкомпіловані програми працюють швидше, але простіше виправляти і змінювати інтерпретовані.

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

З іншого боку, Бейсікстворювався як мова для програмістів-початківців, для яких строкове виконання програми має незаперечні переваги.

Практично всі мови програмування низького рівня і третього покоління, на кшталт асемблера, Сі або Модули-2, є компилируемыми, а більш високорівневі мови, на кшталт Python чи SQL, - інтерпретованими.

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

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

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

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

Процес компіляції поділяється на кілька етапів:

1. Препроцесор.Вихідна програма обробляється шляхом підстановки наявних макросів та заголовних файлів.

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

3. Світова оптимізація.Внутрішнє уявлення програми неодноразово перетворюється з метою скорочення розміру та часу виконання програми.

4. генерація коду.Внутрішнє уявлення перетворюється на блоки команд процесора, які перетворюються на асемблерівський текст чи об'єктний код.

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

6. Складання.Складальник з'єднує кілька об'єктних файлів у виконуваний файл або бібліотеку.

На фазі лексичного аналізу (ЛА) вхідна програма, що є потік символів, розбивається на лексеми - слова відповідно до визначення мови. Основним формалізмом, що лежить в основі реалізації лексичних аналізаторів, є кінцеві автомати та регулярні вирази. Лексичний аналізатор може працювати двох основних режимах: або як підпрограма, викликана синтаксичним аналізатором за черговий лексемою, або як повний прохід, результатом якого є файл лексем. У процесі виділення лексем ЛА може самостійно будувати таблиці імен і констант, і видавати значення кожної лексеми при черговому зверненні щодо нього. І тут таблиця імен будується у наступних фазах (наприклад, у процесі синтаксичного аналізу).

На етапі ЛА виявляються деякі (найпростіші) помилки (неприпустимі символи, неправильний запис чисел, ідентифікаторів та ін.).

Розглянемо докладніше стадію лексичного аналізу.

Основне завдання лексичного аналізу - Розбити вхідний текст, Який складається з послідовності одиночних символів, на послідовність слів, чи лексем, тобто. виділити ці слова із безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору поділяються на символи, що належать будь-яким лексем, і символи, що розділяють лексеми (розділювачі). У деяких випадках між лексемами може і не бути розподільником. З іншого боку, деякі мови лексеми можуть містити незначні символи (наприклад, символ пробілу в Фортрані). У Сі роздільне значення символів-розділювачів може блокуватися («\» в кінці рядка всередині «...»).

Зазвичай усі лексеми поділяються на класи. Прикладами таких класів є числа (цілі, вісімкові, шістнадцяткові, дійсні тощо), ідентифікатори, рядки. Окремо виділяються ключові слова та символи пунктуації (іноді їх називають символи-обмежувачі). Як правило, ключові слова – це деяке кінцеве підмножина ідентифікаторів. У деяких мовах (наприклад, ПЛ/1) зміст лексеми може залежати від її контексту і неможливо провести лексичний аналіз у відриві від синтаксичного.

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

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

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

Лексичний аналізатор може бути як самостійною фазою трансляції, так і підпрограмою, що працює за принципом дай лексему. У першому випадку (рис. 3.1 а) виходом аналізатора є файл лексем, у другому (рис. 3.1 б) лексема видається при кожному зверненні до аналізатора (при цьому, як правило, ознака класу лексеми повертається як результат функції «лексичний аналізатор») , А значення лексеми передається через глобальну змінну). З погляду обробки значень лексем, аналізатор може або просто видавати значення кожної лексеми, й у разі побудова таблиць об'єктів (ідентифікаторів, рядків, чисел тощо.) переноситься більш пізні фази, або може самостійно будувати таблиці об'єктів. У цьому випадку значення лексеми видається покажчик на вхід у відповідну таблицю.

Мал. 3.1:

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

Основне завдання синтаксичного аналізу - Розбір структури програми. Як правило, під структурою розуміється дерево, що відповідає розбору в контекстно-вільній граматиці мови. В даний час найчастіше використовується або LL(1) - аналіз (і його варіант - рекурсивний спуск), або LR(1)-аналіз та його варіанти (LR(0), SLR(1), LALR(1) та інші) . Рекурсивний спуск найчастіше використовується при ручному програмуванні синтаксичного аналізатора, LR(1) - під час використання систем автоматизації побудови синтаксичних аналізаторів.

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

На етапі контекстного аналізу виявляються залежності між частинами програми, які можуть бути описані контекстно- вільним синтаксисом. Це переважно зв'язок «опис- використання», зокрема аналіз типів об'єктів, аналіз областей видимості, відповідність параметрів, мітки та інші. У процесі контекстного аналізу будується таблиця символів, яку можна як таблицю імен, поповнену інформацією про описи (властивості) об'єктів.

Основним формалізмом, що використовується при контекстному аналізі, є атрибутні граматики.Результатом роботи фази контекстного аналізу є атрибутоване дерево програми. Інформація про об'єкти може бути розосереджена в самому дереві, так і зосереджена в окремих таблицях символів. У процесі контекстного аналізу можуть бути виявлені помилки, пов'язані з неправильним використанням об'єктів.

Потім програма може бути переведена у внутрішнє уявлення . Це робиться з метою оптимізації та/або зручності генерації коду. Ще однією метою перетворення програми у внутрішнє уявлення є бажання мати компілятор, що переноситься. Тоді лише остання фаза (генерація коду) є машинно-залежною. Як внутрішній подання може використовуватися префіксний або постфіксний запис, орієнтований граф, трійки, четвірки та інші.

Фаз оптимізації може бути дещо . Оптимізаціїзазвичай ділять на машинно-залежні та машинно-незалежні, локальні та глобальні. Частина машинно-залежної оптимізації виконується фазі генерації коду. Глобальна оптимізаціянамагається взяти до уваги структуру всієї програми, локальна – лише невеликих її фрагментів. Глобальна оптимізація ґрунтується на глобальному потоковому аналізі, який виконується на графі програми та представляє по суті перетворення цього графа. При цьому можуть враховуватися такі властивості програми, як міжпроцедурний аналіз, міжмодульний аналіз, аналіз сфер життя змінних і т.д.

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

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

Надіслати свою гарну роботу до бази знань просто. Використовуйте форму нижче

гарну роботуна сайт">

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

Розміщено на http://www.allbest.ru

Вступ

1.1 Розбір зверху-вниз

1.2 Розбір знизу вгору

1.2.1 LR(k) – граматики

1.2.1.1 LR(0) – граматики

1.2.2 LALR(1) – граматики

2. Розробка транслятора

2.1 Аналіз вимог

2.2 Проектування

2.2.1 Проектування лексичного аналізатора

2.2.4 Програмна реалізація синтаксичного аналізатора

2.3 Кодування

2.4 Тестування

Висновок

Список використаних джерел

Додаток А. Лістинг програмного тексту транслятора

Додаток Б. Результати тестування

Додаток В. Схема програми транслятора

Вступ

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

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

Мови програмування є інструментами на вирішення завдань у різних предметних галузях, що визначає специфіку їх організації та відмінності за призначенням. Як приклад можна навести такі мови як Фортран, орієнтований на наукові розрахунки, C, призначений для системного програмування, Пролог, що ефективно описує завдання логічного висновку, Лісп, що використовується для рекурсивної обробки списків. Ці приклади можна продовжити. p align="justify"> Кожна з предметних областей пред'являє свої вимоги до організації самої мови. Тому можна відзначити різноманітність форм подання операторів і виразів, відмінність у наборі базових операцій, зниження ефективності програмування під час вирішення завдань, які пов'язані з предметної областю. Мовні відмінності відбиваються у структурі трансляторів. Лісп і Пролог найчастіше виконуються як інтерпретації через те, що використовують динамічне формування типів даних під час обчислень. Для трансляторів з мови Фортран характерна агресивна оптимізація результуючого машинного коду, яка стає можливою завдяки відносно простій семантиці конструкцій мови - зокрема, через відсутність механізмів альтернативного іменування змінних через покажчики або посилання. Наявність вказівників у мові C пред'являє специфічні вимогидо динамічного розподілупам'яті.

Структура мови характеризує ієрархічні відносини між його поняттями, що описуються синтаксичними правилами. Мови програмування можуть відрізнятися друг від друга з організації окремих понять і з відносинам з-поміж них. Мова програмування PL/1 допускає довільне вкладення процедур та функцій, тоді як у C всі функції повинні знаходитись на зовнішньому рівні вкладеності. Мова C++ допускає опис змінних у будь-якій точці програми перед першим її використанням, а Паскале змінні мають бути визначені у спеціальній області описи. Ще далі у цьому питанні йде PL/1, який допускає опис змінної після її використання. Або опис можна взагалі опустити та керуватися правилами, прийнятими за умовчанням. Залежно від прийнятого рішення, транслятор може аналізувати програму за один чи кілька проходів, що впливає швидкість трансляції.

Семантика мов програмування змінюється у дуже широких межах. Вони відрізняються як по особливостям реалізації окремих операцій, а й у парадигмам програмування, визначальним важливі розбіжності у методах розробки програм. Специфіка реалізації операцій може стосуватися як структури даних, що обробляються, так і правил обробки одних і тих же типів даних. Такі мови, як PL/1 та APL підтримують виконання матричних та векторних операцій. Більшість мов працюють в основному зі скалярами, надаючи для обробки масивів процедури та функції, написані програмістами. Але навіть при виконанні операції додавання двох цілих чисел такі мови, як C і Паскаль можуть поводитися по-різному.

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

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

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

Мови програмування призначені для полегшення програмування. Тому їхні оператори та структури даних потужніші, ніж у машинних мовах.

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

Для будь-якої мови визначається:

- безліч символів, які можна використовувати для запису правильних програм (алфавіт), основні елементи,

- безліч правильних програм (синтаксис),

- "Сенс" кожної правильної програми (семантика).

Незалежно від специфіки мови будь-який транслятор можна вважати функціональним перетворювачем F, що забезпечує однозначне відображення X в Y, де X - програма вихідною мовою, Y - програма вихідною мовою. Тому процес трансляції формально можна уявити досить легко і зрозуміло: Y = F(X).

Формально кожна правильна програма X - це ланцюжок символів з деякого алфавіту A, що перетворюється на відповідний їй ланцюжок Y, складений із символів алфавіту B.

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

У зв'язку з цим для всіх мов та їх програм можна додатково виділити такі загальні риси: кожна мова повинна містити правила, що дозволяють породжувати програми, що відповідають цій мові або розпізнавати відповідність між написаними програмами та заданою мовою.

Інший характерною рисою всіх мов є їхня семантика. Вона визначає зміст операцій мови, коректність операндів. Ланцюжки, що мають однакову синтаксичну структуру в різних мовах програмування, можуть відрізнятися за семантикою (що, наприклад, спостерігається у C++, Pascal, Basic). Знання семантики мови дозволяє відокремити її від його синтаксису та використовувати для перетворення на іншу мову (здійснити генерацію коду).

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

1. Методи граматичного аналізу

Розглянемо основні методи граматичного аналізу.

1.1 Розбір зверху-вниз

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

1.1.1 LL(k) - мови та граматики

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

-S--

/ \

/-А-x-\

/ | \

-w---u----

Малюнок 1

Для продовження аналізу потрібно замінити нетермінал A за одним із правил виду A:y. Якщо потрібно, щоб розбір був детермінованим (без повернень), це правило потрібно вибирати спеціальним способом. Кажуть, що граматика має властивість LL(k), якщо вибору правила виявляється досить розглянути лише wAx і перші k символів непроглянутої ланцюжка u. Перша літера L (Left, лівий) відноситься до перегляду вхідного ланцюжка зліва направо, друга - до лівого висновку, що використовується.

Визначимо дві множини ланцюжків:

а) FIRST(x) - множина термінальних ланцюжків, що виводяться з x, укорочених до k символів.

б) FOLLOW(A)- безліч укорочених до k символів термінальних ланцюжків, які можуть йти безпосередньо за A у ланцюжках, що виводяться.

Граматика має властивість LL(k), якщо із існування двох ланцюжків лівих висновків:

S:: wAx: wzx:: wu

S:: wAx: wtx:: wv

з умови FIRST (u) = FIRST (v) слід z = t.

У випадку k=1 для вибору правила для А достатньо знати тільки нетермінал A і а - перший символ ланцюжка u:

- слід вибрати правило A:x, якщо входить у FIRST(x),

- слід вибрати правило A:е, якщо входить у FOLLOW(A).

LL(к)-властивість накладає досить сильні обмеження на граматику. Наприклад, LL(2) граматика S: aS | a не має властивості LL(1), т.к. FIRST(aS)=FIRST(a)=a. В даному випадку можна знизити величину k за допомогою "факторизації" (винесення множника за дужку):

S: aA

A: S | e

Будь-яка LL(k)-граматика однозначна. Леворекурсивна граматика не належить класу LL(k) для якого k. Іноді вдається перетворити не LL(1)-граматику на еквівалентну їй LL(1)-граматику за допомогою усунення лівої рекурсії та факторизації. Однак проблема існування еквівалентної LL(k)-граматики для довільної не LL(k)-граматики не вирішена.

1.1.2 Метод рекурсивного спуску

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

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

Рекурсивний спуск можна використовувати для будь-якої LL(1)-граматики. кожному нетерміналу граматики відповідає процедура, яка починається з переходу на мітку, що обчислюється, і містить код, відповідний кожному правилу для даного нетерміналу. Для тих вхідних символів, які належать множині вибору цього правила, обчислюваний перехід передає управління коду, що відповідає цьому правилу. Для решти вхідних символів керування передається процедурі обробки помилок.

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

Застосування рекурсивного спуску мовою високого рівня полегшує програмування і налагодження.

1.2 Розбір знизу вгору

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

-S--

/ \

/-x- \

/ | \

--w--b--u-

Малюнок 2

Проміжний висновок має вигляд xbu, де x - ланцюжок терміналів і нетерміналів, з якого виводиться переглянута частина термінального ланцюжка w, bu - непереглянута частина термінального ланцюжка, b - черговий символ. Щоб продовжити розбір, можна або додати символ b до переглянутої частини ланцюжка (виконати так званий "зсув"), або виділити в кінці x такий ланцюжок z (x=yz), що z можна застосувати одне з правил граматики B:z і замінити x на ланцюжок yB (виконати так звану "згортку"):

-S-- -S--

/ \ / \

/-x-b- \ /yB- \

/ | \ / | \

--w--b--u- --w--b--u-

Малюнок 3 - Після зсуву Малюнок 4 - Після згортки

Якщо згортку застосовувати тільки до останнім символам x, то ми отримуватимемо праві висновки ланцюжка. Такий розбір отримав назву LR, де символ L (Left, лівий) відноситься до перегляду ланцюжка зліва направо, а R (Right, правий) відноситься до одержуваних висновків.

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

1.2.1 LR(k) – граматики

Якщо в процесі LR-розбору прийняти детерміноване рішення про зсув/згортку вдається, розглядаючи тільки ланцюжок x і перші k символів непроглянутої частини вхідного ланцюжка u (ці k символів називають аванцепочкою), кажуть, що граматика має LR(k)-властивість.

-S--

/ \

/-x- \

--w----u--

Малюнок 5

Відмінність між LL(k)- та LR(k)-граматиками в термінах дерева виводу:

-S-

/ | \

/A\

/ / \ \

-w---v---u-

Малюнок 6

У разі LL(k)-граматик однозначно визначити правило, застосоване до A, можна w і першим k символам vu, а у випадку LR(k)-граматик - w,v і першим k символам u. Ця нестрога міркування показує, що LL(k)-мови< LR(k)-языки (при k > 0).

1.2.1.1 LR(0) – граматики

Розглянемо спочатку найпростіші граматики цього - LR(0). При розборі рядка LR(0)-мови можна взагалі використовувати аванцепочку - вибір між зсувом і згорткою робиться виходячи з ланцюжка x. Так як у процесі розбирання вона змінюється лише з правого кінця, її називають стеком. Вважатимемо, що в граматиці немає марних символіві початковий символ немає у правих частинах правил - тоді згортка до початкового символу сигналізує про успішне завершення разбора. Спробуємо описати безліч ланцюжків з терміналів і нетерміналів, що з'являються в стеку в процесі всіх LR-розборів (тобто - правих висновків з граматики).

Визначимо такі множини:

L(A:v) - лівий контекст правила A:v - безліч станів стека, безпосередньо перед згорткою v A в ході всіх успішних LR-розборів. Очевидно, кожен ланцюжок з L(A:v) закінчується на v. Якщо у всіх таких ланцюжків відрізати хвіст v, то вийде безліч ланцюжків, що зустрічаються ліворуч від A у всіх успішних правих висновків. Позначимо цю множину L(A) - лівий контекст нетерміналу A.

Побудуємо граматику для множини L(A). Терміналами нової граматики будуть термінали та нетермінали вихідної граматики, нетермінали нової граматики позначимо ,... - їх значеннями будуть ліві контексти нетерміналів вихідної граматики. Якщо S - початковий символ вихідної граматики, то граматика лівих контекстів міститиме правило : e - лівий контекст S містить порожній ланцюжок Для кожного правила вихідної граматики, наприклад, A: B C d E

і додамо до нової граматики правила:

: - L(B) включає L(A)

: B - L(C) включає L(A) B

: B C d - L(E) включає L(A) B C d

Отримана граматика має спеціальний вигляд (такі граматики називаються леволінійними), отже, безлічі лівих контекстів

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

Назвемо LR(0)-ситуацією правило граматики з однією зазначеною позицією між символами правої частини правила. Наприклад, для граматики S:A; A:aAA; A:b існують такі LR(0)-ситуації: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (позиція позначена символом підкреслення).

Будемо говорити, що ланцюжок x узгоджений із ситуацією А:b_c, якщо x=ab і a належить L(A). (Іншими словами, LR-висновок може бути продовжений x_... = ab_...:: abc_...:: aA_...:: S_.) У цих термінах L(A:b) - безліч ланцюжків, узгоджених із ситуацією A:b_, L(A)

- ланцюжки, узгоджені із ситуацією A:_b, для будь-якого правила A:b.

Нехай V(u) - безліч ситуацій, узгоджених з u. Покажемо, що функція V – індуктивна.

Якщо безліч V(u) входить ситуація A:b_cd, то ситуація A:bc_d належить V(uc). (c - термінал або нетермінал; b, d - послідовності (може бути порожні) терміналів та нетерміналів). Інших ситуацій виду A:b_d, з непустим b V(uc) немає. Залишилося додати в V(uc) ситуації виду C:_..., кожного нетермінала C, лівий контекст якого містить uc. Якщо ситуація A:..._C... (C-нетермінал) належить множині V(uc), то uc належить L(C) і V(uc) включає ситуації вигляду C:_... для всіх C- правил граматики

V(e) містить ситуації S:_... (S-початковий символ), а також ситуації A:_..., якщо нетермінал A зустрічається безпосередньо після _ у ситуаціях, вже включених до V(e).

Нарешті ми готові дати визначення LR(0)-граматики. Нехай u - вміст стека в процесі LR-розбору, V(u)-множина LR(0) ситуацій, узгоджених з u. Якщо V(u) містить ситуацію виду А:x_ (x-послідовність терміналів і нетерміналів), то u належить L(A:x) і допустима згортка x A. Якщо V(u) містить ситуацію A:..._a. .. (а-термінал), то допустимо зрушення. Говорять про конфлікт зсув-згортка, якщо для одного ланцюжка u допустимі і зсув, і згортка. Говорять про конфлікт згортка-згортка, якщо допустимі згортки за різними правилами.

Граматика називається LR(0), якщо для всіх станів стека в процесі LR-виведення немає конфліктів зсув-згортка або згортка-згортка.

1.2.1.2 LR(k) – граматики

Для вибору між зсувом або згорткою в LR(0) аналізі використовується тільки стан стека. У LR(k) аналізі враховується також k-перших символів непроглянутої частини вхідного ланцюжка (так звана аванцепочка). Для обґрунтування методу слід акуратно повторити міркування попереднього параграфа, внісши зміни до визначення.

Включатимемо в лівий контекст правила також аванцепочку. Якщо правому висновку застосовується висновок wAu: wvu, пара wv,FIRSTk(u) належить Lk(A:v), а пара w,FIRSTk(u) - Lk(A). Безліч лівих контекстів, як і у випадку LR(0), можна обчислювати за допомогою індукції по лівому ланцюжку. Назвемо LR(k)-ситуацією пару: правило граматики із зазначеною позицією та аванцепочку довжини не більше k. Відокремлювати правило від аванцепочки будемо вертикальною межею.

Будемо говорити, що ланцюжок x узгоджений із ситуацією А:b_c|t якщо існує LR-висновок: x_yz = ab_yz:: abc_z:: aA_z:: S_, і FIRSTk(z)=t. Правила індуктивного обчислення множини станів Vk наступні:

Vk(e) містить ситуації S:_a|e всім правил S:a, де S-початковий символ. Для кожної ситуації А:_Ba|u з Vk(e), кожного правила B:b і ланцюжка x, що належить FIRSTk(au), треба додати Vk(e) ситуацію B:_b|x.

Якщо Vк(w) входить ситуація A:b_cd|u, то ситуація A:bc_d|u належатиме Vk(wc). Для кожної ситуації А:b_Cd|u з Vk(wc), кожного правила C:f і ланцюжка x, що належить FIRSTk(du), треба додати у Vk(wc) ситуацію C:_f|x.

Використовуємо побудовані множини LR(k)-станів для вирішення питання зсув-згортка. Нехай u – вміст стеку, а x – аванцепочка. Очевидно, що згортка за правилом A:b може бути проведена, якщо Vk(u) містить ситуацію A:b_|x. Вирішення питання про допустимість зсуву вимагає акуратності, якщо в граматиці є e-правила. У ситуації A:b_c|t (c не порожньо) зрушення можливе, якщо c починається з терміналу і x належить FIRSTk(ct). Неформально кажучи, можна занести в стек найлівіший символ правої частини правила, готуючи наступну згортку. Якщо c починається з нетерміналу (ситуація має вигляд A:b_Cd|t), то занести в стек символ, готуючи згортку в C, можна тільки у випадку, якщо C не породжує порожній ланцюжок. Наприклад, може V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a немає допустимих зрушень, т.к. при виведенні з термінальних ланцюжків A на деякому кроці потрібно застосувати правило A:e до нетерміналу A, що знаходиться на лівому кінці ланцюжка.

Визначимо безліч EFFk(x), що складається з усіх елементів множини FIRSTk(x), при виведенні яких нетермінал на лівому кінці x (якщо він є) не замінюється порожнім ланцюжком. У цих термінах зрушення допустимо, якщо в множині Vk(u) є ситуація А:b_c|t, c не порожньо і x належить EFFk(ct).

Граматика називається LR(k)-граматикою, якщо жоден LR(k) стан не містить двох ситуацій A:b_|u та B:c_d|v, таких що u належить EFFk(dv). Така пара відповідає конфлікту згортка-згортка, якщо d порожньо, і конфлікту зсув-згортка, якщо d не порожньо.

Насправді LR(k)-грамматики при k>1 не застосовуються. На це є дві причини. Перша: дуже велике число LR(k) станів. Друга: для будь-якої мови, що визначається LR(k)-граматикою, існує LR(1)-граматика; більше того, для будь-якої детермінованої КС мови існує LR(1)-граматика.

Число LR(1)-станів для практично цікавих граматиктакож дуже велике. LR(0) властивістю такі граматики мають рідко. Насправді частіше використовується проміжний між LR(0) і LR(1) метод, відомий під назвами і LALR(1).

1.2.2 LALR(1) – граматики

В основі цих двох методів лежить та сама ідея. Побудуємо безліч канонічних LR(0)-станів граматики. Якщо це безліч не містить конфліктів, можна застосувати LR(0)-парсер. Інакше спробуємо вирішити конфлікти, розглядаючи односимвольну аванцепочку. Іншими словами, спробуємо побудувати LR(1) парсер із безліччю LR(0)-станів.

LALR(1)-метод (Look Ahead – заглядання вперед) полягає в наступному. Введемо на безлічі LR(1)-ситуацій відношення еквівалентності: вважатимемо дві ситуації еквівалентними, якщо вони відрізняються лише аванцепочками. Наприклад, ситуації A:Aa_Ab|e та A:Aa_Ab|a еквівалентні. Побудуємо канонічну множину LR(1)-станів і об'єднаємо стани, що складаються з безлічі еквівалентних ситуацій.

Якщо отримана безліч станів не містить LR(1) конфліктів, і, отже, дозволяє побудувати LR(1)-парсер, то кажуть, що граматика має властивість LALR(1).

2. Розробка транслятора

2.1 Аналіз вимог

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

Проектування лексичного аналізатора;

Проектування магазинного автомата;

Програмна реалізація синтаксичного аналізатора;

Розробка модуля інтерпретації.

Розробку буде проведено з використанням операційної системи Windows XP на персональному комп'ютері IBM PC з процесором Intel Pentium IV.

Виходячи з тенденцій розвитку програмного забезпечення для реалізації навчального транслятора, обрана мова програмування С# в середовищі Visual Studio 2010.

2.2 Проектування

2.1.1 Проектування лексичного аналізатора

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

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

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

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

Перегляд таблиці ідентифікаторів виконує дві основні функції:

а) запис нового імені до таблиці при обробці опису змінних;

б) пошук імені, раніше записаного у таблицю.

Це дозволяє виявляти такі помилкові ситуації, як множинний опис змінної та наявність неописаної змінної.

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

Запускаючи лексичний аналізатор, ми розбиваємо нашу програму на лексеми, після чого кожна лексема проходить перевірку довжини (лексема може бути більше 11 символів). Пройшовши успішно цей етап, ми перевіряємо правильність розташування лексем (ключових слів var, begin, end, for, to, do, end_for). Потім аналізуємо лексеми змінні - вони повинні містити цифр у своєму описі і повторюватися. На останньому етапі перевіряємо правильність написання лексем (ключові слова, невідомі ідентифікатори). Якщо хоча одна з перевірок видає помилку, лексичний аналізатор виводить помилку.

Схема програми роботи лексичного аналізатора наведено у додатку B малюнку В.1.

2.2.2 Проектування магазинного автомата

Задамо наступну граматику:

Г: (Vt, Va, I, R),

де Vt - це безліч термінальних символів, Va - безліч нетермінальних символів, I - початковий стан граматики, R - безліч правил граматики.

Для даної граматики поставимо безліч термінальних і нетермінальних символів:

Складемо правила нашої граматики Р і наведемо їх у таблиці 1.

Таблиця 1 – Правила граматики

№ правила	Ліва частина правила	Права частина правила
		f ID = EX t EX d LE n;
Продовження таблиці 1.
№ правила	Ліва частина правила	Права частина правила

Позначення лексем, переклад лексем у коди та список позначень граматики наведемо у таблицях 2, 3, 4 відповідно.

Таблиця 2 - Позначення лексем

	Позначення лексеми
	ключове слово «begin» (початок опису дій)
	ключове слово "end" (закінчення опису дій)
	ключове слово "var" (опис змінних)
	ключове слово "read" (оператор введення даних)
	ключове слово "write" (оператор виведення даних)
	ключове слово "for" (оператор циклу)
	ключове слово "to"
	ключове слово «do»
	ключове слово "end_case" (закінчення оператора циклу)
	тип змінних «цілий»
	операція додавання
	операція віднімання
	операція множення
	розділовий символ ":"
	розділовий символ ";"
	розділовий символ «(»)
	розділовий символ ")"
	розділовий символ ","
	Позначення лексеми
	розділовий символ "="

Таблиця 3 - Переклад лексем у коди

<цифра>
<буква>

Таблиця 4 - Список позначень граматики

Позначення	Пояснення
	Програма
	Опис обчислень
	Опис змінних
	Список змінних
	Оператор
	Привласнення
	Вираз
	Підвираження
	Бінарні операції
	Унарні операції
	Список присвоювань
	Ідентифікатор
	Константа

Побудуємо детерменований висхідний розпізнавач.

Розглянемо такі відносини, щоб побудувати детермінований висхідний розпізнаватель:

а) Якщо є символ групи В такий, що в деяке правило граматики входить ланцюжок АВ і існує символ хПЕРВ "(В), то вважатимемо, що між символами х і А визначаються відносини х ПІСЛЯ А

б) Якщо в заданій граматиці маючи правило В-> бАб А, ВV a, то між А і х визначається відношення А СВЕРТ х.

Вся наша граматика залишається незмінною, тобто:

Г: (Vt, Va, I, R),

а правила граматики Р наведено у таблиці 5.

Таблиця 5 – Правила граматики

№ правила	Ліва частина правила	Права частина правила
		f ID = EX t EX d LE n;?
Продовження таблиці 5.
№ правила	Ліва частина правила	Права частина правила

Де? - Маркер кінця ланцюжка.

Визначимо деякі випадки:

а) Ідентифікатор ID складається з безлічі букв латинського алфавітутобто будемо вважати, що u = (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z)

б) Константа СО складається з цифр, тобто вважатимемо, що k = (0,1,2,3,4,5,6,7,8,9)

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

а) Відсутність е - правил

б) Є правила за яких, х ПІСЛЯ А? А СВЕРТ х = ?

в) А -> бYг

і необхідно, щоб У ПІСЛЯ х? У СВЕРТ х = ?

тобто в граматиці будуть виконуватися У ПІСЛЯ х або А ПІСЛЯ х, де х - символ-предикат ланцюжка б.

а) ПЕРВ" (PG) = (PG?)

ПЕРВ"(RG) = ПЕРВ(DE) = (RG, v,:, i,;)

ПЕРВ" (AL) = ПЕРВ (b LE e) = (AL, b, e)

ПЕРВ" (DE) = ПЕРВ (v LV: i;) = (DE, v,:, i,;)

ПЕРВ" (LV) = ПЕРВ (ID, LV) = ( LV, ID )

ПЕРВ" (OP) = (OP, ID, CO)

ПЕРВ" (EQ) = ПЕРВ(ID = EX;) = (EQ, =,;)

ПЕРВ" (EX) = (EX, SB, -)

ПЕРВ" (BO) = (B0, +, *,-)

ПЕРВ" (SB) = ПЕРВ ((EX) SB) ? ПЕРВ (OP) ? ПЕРВ (ВО) = (SB, (,), OP, BO);

ПЕРВ" (LE) = ПЕРВ(EQ) = (LE, (,), =,;, f, t, d, n, w, r)

ПЕРВ" (UO) = (UO,-)

ПЕРВ" (ID) = ПЕРВ" (u) = (u)

ПЕРВ" (CO) = ПЕРВ" (k) = (k) ПЕРВ" (e) = (e)

ПЕРВ" (b) = (b)

ПЕРВ" (e) = (e)

ПЕРВ" (v) = (v)

ПЕРВ" (w) = (w)

ПЕРВ" (r) = (r)

ПЕРВ" (i) = (i)

ПЕРВ" (f) = (f)

ПЕРВ" (d) = (d)

ПЕРВ" (n) = (n)

ПЕРВ" (c) = (c)

ПЕРВ" (+) =(+)

ПЕРВ" (*) = (*)

ПЕРВ" (-) =( -)

ПЕРВ" (,) =(,)

ПЕРВ" (;) =(;)

ПЕРВ" (:) =(:)

ПЕРВ" (=) = ( = )

ПЕРВ" (() =( ()

ПЕРВ" ()) =() )

ПЕРВ" (u) = (u)

ПЕРВ" (k) = (k)

б) СЛІД `(AL) = (?)? СЛІД "(PG) = (?, b, e)

СЛІД `(DE) = (?)?ПЕРВ" (AL) = (?, b, e)

СЛІД `(LV) = (?)?ПЕРВ"(:)= (?,:)

СЛІД `(OP) = (?)?ПЕРВ" (SB) = (?,;,), d, t, +, -, *)

СЛІД `(EQ) = (?)?ПЕРВ"(LE) = (?, (,),;

СЛІД `(EX) = (?)? ПЕРВ" (t)? ПЕРВ" (d)? ПЕРВ" (;)?

СЛІД `(BO) = (?)?ПЕРВ" (SB) = (?, (,), OP, BO)

СЛІД `(UO) = (?)?ПЕРВ" (SB) = (?, (,), OP, BO)

СЛІД `(SB) = (?)? СЛІД" (EX) = (?, t, d,;,), +, *, -)

СЛІД `(LE) = (?) ?ПЕРВ"(e) ?ПЕРВ"(n) = (?, e, n)

СЛІД `(ID) = (?)? СЛІД" (OP) ? ПЕРВ" (=) =(?,;,), d, t, +, -, *, =)

СЛІД `(CO) = (?)? СЛІД" (OP) = (?,;,), d, t, +, -, *, =)

СЛІД `(b) = (?)? ПЕРВ "(LE) = (?, u, =,;)

СЛІД `(e) = (?)? СЛІД "(AL) = (?, b)

СЛІД `(v) = (?)? ПЕРВ "(LV) = (?, u)

СЛІД `(w) =(?)?ПЕРВ"(()= (?, ()

СЛІД `(r) =(?)?ПЕРВ"(() = (?, ()

СЛІД `(i) =(?)?ПЕРВ"(;)= (?,; )

СЛІД `(f) =(?)?ПЕРВ"(ID) = (?, u)

СЛІД `(d) = (?)? ПЕРВ "(LE) = (?, u, =,;)

СЛІД `(n) =(?)?ПЕРВ"(i) = (?, i)

СЛІД `(+) = (?)? СЛІД "(ВО) = (?, +, *,-)

СЛІД `(-) = (?)? СЛІД "(ВО) = (?, +, *,-)

СЛІД `(*) = (?)? СЛІД "(ВО) = (?, +, *,-)

СЛІД `(;) =(?)?СЛЕД" (DE)?СЛЕД`(LE1)?СЛЕД" (EQ) = (?, b, e, l, u)

СЛІД `(:) =(?)?ПЕРВ"(i)=(?, i)

СЛІД `(=) = (?)?ПЕРВ"(EX) = (? (,), u, k, +, -, *)

СЛІД `(() =(?)?ПЕРВ"(DE)= (?, v,:, i,;)

СЛІД `()) = (?)? ПЕРВ"(;) = (?,; )

СЛІД `(,) = (?)? ПЕРВ" (LV) = (?, u)

СЛІД `(u) =(?)? ПЕРВ" (ID) = (u,?)

СЛІД `(k) = (?)? ПЕРВ (CO) = (?, k)

в) PG -> DE AL

AL ПІСЛЯ DE = (b,e) ПІСЛЯ DE = ((b DE), (e DE) )

e ПІСЛЯ LE = ((e LE))

LE ПІСЛЯ b = ((,), =,;, f, t, d, n, w, r) ПІСЛЯ b = (((b), ()b), (=b), (;b), ( f b), (t b), (d b), (n b), (w b), (r b))

;ПІСЛЯ i = ((; i))

i ПІСЛЯ: = ((i:) )

: ПІСЛЯ LV = ( (: LV) )

LV ПІСЛЯ v = ( (ID, v) )

LV ПІСЛЯ, = ((ID,))

ПІСЛЯ ID = ((,u))

LE ПІСЛЯ EQ = ((,), =,;, f, t, d, n, w, r) ПІСЛЯ EQ = (((EQ), () EQ), (= EQ), (; EQ), ( f EQ), (t EQ), (d EQ), (n EQ), (w EQ), (r EQ))

LE -> r(DE);

; ПІСЛЯ) = ((;)))

) ПІСЛЯ DE = (((DE))

DE ПІСЛЯ (= (= ((v)), (:)), (i)), (;)), (e)))

(ПІСЛЯ r = (((r))

LE -> w(DE);

; ПІСЛЯ) = ((;)))

) ПОСЛ DE = (((DE))

DE ПІСЛЯ (= ((v)), (:)), (i)), (;)), (e)))

(ПІСЛЯ w = (((w))

LE -> f ID = EX t EX d LE n;

; ПІСЛЯ n = ((; n))

n ПІСЛЯ LE = ((n, LE))

LE ПІСЛЯ d = (((,), =,;, f, t, d, n, w, r)) ? ПІСЛЯ d = (((d), ()d), (;d), (f d), (t d), (d d), (n d), (w d), (r d))

d ПІСЛЯ EX = ((d, EX))

EX ПІСЛЯ t = (BO, -) ? ПІСЛЯ t = ((BO t), (- t))

t ПІСЛЯ EX = (t EX)

EX ПІСЛЯ = = ((BO, -) ? ПІСЛЯ = = ((BO =), (- =))

ПІСЛЯ ID = ((= ID))

ID ПІСЛЯ f = ((ID f))

EQ -> ID = EX;

; ПІСЛЯ EX = ((; EX )

EX ПІСЛЯ = = (BO, -) ? ПІСЛЯ = = ((BO =), (- =))

ПІСЛЯ u = ((=u))

SB ПІСЛЯ UO = ((,), OP, BO ) ПІСЛЯ UO = (((UO), (OP UO), (BO UO) )

) ПІСЛЯ EX = (()EX) )

EX ПІСЛЯ (= (BO, -) ? ПІСЛЯ (= ((BO (), (- ())

SB-> SB BO SB

SB ПІСЛЯ BO = ((,), OP, BO) ПІСЛЯ BO = (((BO), ()BO), (OP BO), (BO BO))

BO ПІСЛЯ SB = (+,*,-) ПІСЛЯ SB = ((+SB), (*SB), (-SB))

ID ПІСЛЯ u = ((u, u))

г) PG ->DE AL

AL СВЕРТ PG = AL СВЕРТ СЛІД" (PG) = ((AL ?))

e ЗВЕРТ AL = e ЗВЕРТ СЛІД"(AL)= ((eb), (e?))

=; СВЕРТ СЛЕД"(DE) = ((; b), (;?))

LV СВЕРТ LV = LV СВЕРТ СЛЕД" (LV) = ((LV:), (LV?))

ID СВЕРТ LV = ID СВЕРТ СЛЕД" (LV) = ((ID:), (ID ?))

; ЗВЕРТ LE =; СВЕРТ СЛЕД" (LE) = ((; e), (;?), (; n))

LE -> f ID = EX t EX d LE n;

; ЗВЕРТ LE =; СВЕРТ СЛЕД" (LE) = ((; e), (;?), (; n))

EQ СВЕРТ LE = EQ СВЕРТ СЛЕД" (LE) = ((EQ e), (EQ?), (EQ n))

EQ -> ID = EX;

; СВЕРТ EQ =; СВЕРТ СЛЕД" (EQ) = ((; (), (;)), (;;), (; f), (;?), (; =), (; t), (; d), (; n), (; w), (; r))

SB СВЕРТ EX = SB СВЕРТ СЛІД" (EX) = ((SB t), (SB?), (SB d), (SB)), (SB;), (SB(), (SB=), (SBf ), (SBn), (SBw), (SBr) )

) ЗВЕРТ SB = SB ЗВЕРТ СЛІД" (SB) = (() t), ()?), () d), ())), ();))

OP СВЕРТ SB = OP СВЕРТ СЛЕД" (SB) = ((OP t), (OP ?), (OP d), (OP)), (OP;))

SB-> SB BO SB

SB СВЕРТ SB = SB СВЕРТ СЛЕД" (SB) = ((SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB? ) }

ЗВЕРТ UO = - ЗВЕРТ СЛІД" (UO) = ((-?), (--))

ЗВЕРТ BO = + ЗВЕРТ СЛІД" (BO) = ((++), (+?), (+*), (+-))

* ЗВЕРТ BO = * ЗВЕРТ СЛІД" (BO) = ((*+), (*?), (**), (*-))

ЗВЕРТ BO = - ЗВЕРТ СЛІД" (BO) = ((-+), (-?), (-*), (--))

ID СВЕРТ OP = ID СВЕРТ СЛЕД" (OP) = ((ID+), (ID?), (ID*), (ID-))

CO СВЕРТ OP = CO СВЕРТ СЛЕД" (OP) = ((CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

ID ЗВЕРТ ID = ID ЗВЕРТ СЛІД" (ID) = ((ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt) , (IDd)))

u ЗВЕРТ ID = l ЗВЕРТ СЛІД" (ID) = ((u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (ud)))

CO СВЕРТ CO = CO СВЕРТ СЛЕД" (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

k ЗВЕРТ CO = k ЗВЕРТ СЛІД" (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k)))

Виявлено одну конфліктну ситуацію при згортанні правил

OP -> ID та ID -> u ID

Вводимо ID1 -> ID, отже переписуємо правило ID1 -> u ID

Отже, проведемо операції згортка.

ID1 ЗВЕРТ ID = ID1 ЗВЕРТ СЛІД" (ID) = ((ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t) , (ID1d)))

Для кожної пари (x, A)? х ПІСЛЯ А будуємо функцію переходу, що визначає дію перенесення? (S 0 , x, A) = (S 0 , A)

? (S0, b, DE) = (S0, DEb)

? (S0, e, DE) = (S0, DEe)

? (S0, e, LE) = (S0, LEe)

? (S0,), b) = (S0, b))

? (S0,;, b) = (S0, b;)

? (S0, (, b) = (S0, b()

? (S0, =, b) = (S0, b=)

? (S0, f, b) = (S0, bf)

? (S0, t, b) = (S0, bt)

? (S0, d, b) = (S0, bd)

? (S0, n, b) = (S0, bn)

? (S0, w, b) = (S0, bw)

? (S0, r, b) = (S0, br)

? (S0,;, i) = (S0, i;)

? (S0, i,:) = (S0, i:)

? (S0,: LV) = (S0, LV:)

? (S0, ID, v) = (S0, vID)

? (S0, ID,) = (S0, ID)

? (S0, u) = (S0, u,)

? (S0, (, EQ) = (S0, EQ ()

? (S0,), EQ) = (S0, EQ))

? (S0, =, EQ) = (S0, EQ =)

? (S0,;, EQ) = (S0, EQ;)

? (S0, f, EQ) = (S0, EQf)

? (S0, t, EQ) = (S0, EQt)

? (S0, d, EQ) = (S0, EQd)

? (S0, n, EQ) = (S0, EQn)

? (S0, w, EQ) = (S0, EQw)

? (S0, r, EQ) = (S0, EQr)

? (S0,;,)) = (S0,);)

? (S0, (, DE) = (S0, DE()

? (S0, v,)) = (S0,)v)

? (S0,;,)) = (S0,);)

? (S0, i,)) = (S0,) i)

? (S0,:,)) = (S0,):)

? (S0, e,)) = (S0,) e)

? (S0, (, r) = (S0, r()

? (S0, (, w) = (S0, w()

? (S0,;, n) = (S0, n;)

? (S0, n, LE) = (S0, LEn)

? (S0, (, d) = (S0, d()

? (S0,), d) = (S0, d))

? (S0,;, d) = (S0, d;)

? (S0, f, d) = (S0, df)

? (S0, t, d) = (S0, dt)

? (S0, d, d) = (S0, dd)

? (S0, n, d) = (S0, dn)

? (S0, w, d) = (S0, dw)

? (S0, r, d) = (S0, dr)

? (S0, d, EX) = (S0, EXd)

? (S0, BO, t) = (S0, tBO)

? (S0, -, t) = (S0, t-)

? (S0, t, EX) = (S0, EXt)

? (S0, BO, =) = (S0, = BO)

? (S0, -, =) = (S0, =-)

? (S0, =, ID) = (S0, ID=)

? (S0, ID, f) = (S0, fID)

? (S0,;, EX) = (S0, EX;)

? (S0, =, u) = (S0, u=)

? (S0, (, UO) = (S0, UO()

? (S0, OP, UO) = (S0, UO OP)

? (S0, BO, UO) = (S0, UO BO)

? (S0,), EX) = (S0, EX))

? (S0, BO, () = (S0, (BO)

? (S0, BO, -) = (S0, -BO)

? (S0, (, BO) = (S0, BO()

? (S0,), BO) = (S0,)BO)

? (S0, OP, BO) = (S0, BOOP)

? (S0, +, SB) = (S0, SB+)

? (S0, *, SB) = (S0, SB *)

? (S0, -, SB) = (S0, SB-)

? (S0, u, u) = (S0, uu)

Для кожної пари (х, А)? А СВЕРТ х будуємо функцію переходу, що визначає дію згортка? * (S 0 , x, бA) = (S 0 , В), де В-> бA

? * (S 0 , AL, ?) = (S 0 , PG)

? * (S 0 , e, b) = (S 0 , AL)

? * (S 0 , n, ?) = (S 0 , AL)

? * (S 0,;, b) = (S 0, DE)

? * (S 0 ,;, ?) = (S 0 , DE)

? * (S 0 ,;, e) = (S 0 , DE)

? * (S 0 , LV,:) = (S 0 , LV)

? * (S 0 , LV, ?) = (S 0 , LV)

? * (S 0 ID, ?) = (S 0 LV)

? * (S 0 ID, e) = (S 0 LV)

? * (S 0 ,;, e) = (S 0 , LE)

? * (S 0 ,;, ?) = (S 0 , LE)

? * (S 0 ,;, n) = (S 0 , LE)

? * (S 0 , EQ, n) = (S 0 , LE)

? * (S 0 , EQ, e) = (S 0 , LE)

? * (S 0 , EQ, ?) = (S 0 , LE)

? * (S 0 ,;, e) = (S 0 , LE)

? * (S 0 ,;, ?) = (S 0 , LE)

? * (S 0 ,;, () = (S 0 , EQ)

? * (S 0 ,;,)) = (S 0 , EQ)

? * (S 0,;, f) = (S 0, EQ)

? * (S 0 ,;, =) = (S 0 , EQ)

? * (S 0,;, t) = (S 0, EQ)

? * (S 0,;, d) = (S 0, EQ)

? * (S 0,;, n) = (S 0, EQ)

? * (S 0,;, w) = (S 0, EQ)

? * (S 0,;, r) = (S 0, EQ)

? * (S 0 , SB, ?) = (S 0 , EX)

? * (S 0 , SB, d) = (S 0 , EX)

? * (S 0 , SB,)) = (S 0 , EX)

? * (S 0 , SB,;) = (S 0 , EX)

? * (S 0 , SB, w) = (S 0 , EX)

? * (S 0 , SB, r) = (S 0 , EX)

? * (S 0 , SB, f) = (S 0 , EX)

? * (S 0 , SB, =) = (S 0 , EX)

? * (S 0 , SB, t) = (S 0 , EX)

? * (S 0 , SB, ?) = (S 0 , SB)

? * (S 0 , SB, () = (S 0 , SB)

? * (S 0 , SB,)) = (S 0 , SB)

? * (S 0 , SB, u) = (S 0 , SB)

? * (S 0 , SB, k) = (S 0 , SB)

? * (S 0 , SB, +) = (S 0 , SB)

? * (S 0 , SB, -) = (S 0 , SB)

? * (S 0 , SB, *) = (S 0 , SB)

? * (S 0 , SB, e) = (S 0 , SB)

? * (S 0 ,), t) = (S 0 , SB)

? * (S 0 ,), ?) = (S 0 , SB)

? * (S 0 ,), t) = (S 0 , SB)

(S 0 ,),)) = (S 0 , SB)

? * (S 0 ,),;) = (S 0 , SB)

? * (S 0 , -, ?) = (S 0 , UO)

? * (S 0 , -, -) = (S 0 , UO)

? * (S 0 , +, +) = (S 0 , BO)

? * (S 0 , +, ?) = (S 0 , BO)

? * (S 0 , +, *) = (S 0 , BO)

? * (S 0 , -, +) = (S 0 , BO)

? * (S 0 , -, ?) = (S 0 , BO)

? * (S 0 , -, *) = (S 0 , BO)

? * (S 0 , -, -)) = (S 0 , BO)

? * (S 0 , *, +) = (S 0 , BO)

? * (S 0 , *, ?) = (S 0 , BO)

? * (S 0 , *, *) = (S 0 , BO)

? * (S 0 , *, -)) = (S 0 , BO)

? * (S 0 , u, +) = (S 0 , BO)

? * (S 0 , u, ?) = (S 0 , BO)

? * (S 0 , u, *) = (S 0 , BO)

? * (S 0 , u, -)) = (S 0 , BO)

? * (S 0 , k, +) = (S 0 , BO)

? * (S 0 , k, ?) = (S 0 , BO)

? * (S 0 , k, *) = (S 0 , BO)

? * (S 0 , k, -)) = (S 0 , BO)

? * (S 0 , CO, ?) = (S 0 , OP)

? * (S 0 , CO, +) = (S 0 , OP)

? * (S 0 , CO, *) = (S 0 , OP)

? * (S 0 , CO, -) = (S 0 , OP)

? * (S 0, CO,;) = (S 0, OP)

? * (S 0, CO, d) = (S 0, OP)

? * (S 0, CO, t) = (S 0, OP)

? * (S 0 , ID, -) = (S 0 , OP)

? * (S 0 , ID, *) = (S 0 , OP)

? * (S 0 , ID, ?) = (S 0 , OP)

? * (S 0 , ID, () = (S 0 , OP)

? * (S 0 , ID,)) = (S 0 , OP)

? * (S 0 , ID, u) = (S 0 , OP)

? * (S 0 ID, k) = (S 0 OP)

? * (S 0 , ID, -) = (S 0 , OP)

? * (S 0 , ID, +) = (S 0 , OP)

? * (S 0 , u,)) = (S 0 , I OP)

? * (S 0 ID1, *) = (S 0 ID)

? * (S 0 ID1, ?) = (S 0 ID)

? * (S 0 , ID1, () = (S 0 , ID)

? * (S 0 , ID1,)) = (S 0 , ID)

? * (S 0 ID1, u) = (S 0 ID)

? * (S 0 ID1, k) = (S 0 ID)

? * (S 0 ID1, -) = (S 0 ID)

? * (S 0 , ID1, +) = (S 0 , ID)

? * (S 0 , u,)) = (S 0 , ID)

? * (S 0 , u, ?) = (S 0 , BO)

? * (S 0 , u, k) = (S 0 , ID)

? * (S 0 , u, *)) = (S 0 , ID)

? * (S 0 , u, -)) = (S 0 , ID)

? * (S 0 , u, +)) = (S 0 , ID)

? * (S 0 , u, d)) = (S 0 , ID)

? * (S 0 , u, t)) = (S 0 , ID)

? * (S 0 , u, =)) = (S 0 , ID)

? * (S 0 , CO, ?) = (S 0 , CO)

? * (S 0, CO, +) = (S 0, CO)

? * (S 0 , CO, -) = (S 0 , CO)

? * (S 0 , CO, *) = (S 0 , CO)

? * (S 0, CO,;) = (S 0, CO)

? * (S 0, CO, d) = (S 0, CO)

? * (S 0, CO, t) = (S 0, CO)

? * (S 0, CO,)) = (S 0, CO)

? * (S 0, k, +) = (S 0, CO)

? * (S 0 , k, -) = (S 0 , CO)

? * (S 0, k, *) = (S 0, CO)

? * (S 0, k,;) = (S 0, CO)

?? * (S 0, k, d) = (S 0, CO)

? * (S 0, k, t) = (S 0, CO)

? * (S 0, k,)) = (S 0, CO)

? * (S 0 , k, () = (S 0 , CO)

2.2.3 Програмна реалізація синтаксичного аналізатора

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

Для висхідного граматичного розбору для детермінованого висхідного розпізнавача після приведення її до потрібного виглядупотрібно з використанням функцій ПІСЛЯ та СВЕРТ спроектувати магазинний автомат з докладним описом всіх переходів у рамках функції переходів.

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

такт роботи магазинного автомата без читання вхідного символу (порожній такт);

Такт роботи магазину з читанням вхідного символу.

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

Схема програми роботи синтаксичного аналізатора наведено у додатку B малюнку В.2.

2.2.4 Розробка модуля інтерпретації

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

Розглянемо основні засади формування та виконання постфіксної форми запису виразів.

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

Лічені операнди додаються до постфіксного запису, операції записуються в стек.

Якщо операція у вершині стека має більший (або рівний) пріоритет, ніж поточна лічена операція, то операція зі стека додається до запису, а поточна операція заноситься в стек. В іншому випадку (при нижчому пріоритеті) відбувається лише занесення поточної операції у стек.

Лічена дужка, що відкриває, заноситься в стек.

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

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

Постфіксний запис виразу дозволяє проводити його обчислення в такий спосіб.

Якщо лексема є операндом, вона записується в стек. Якщо лексема є операцією, то зазначена операція виконується над останніми елементами (останнім елементом), записаними в стек, і ці елементи (елемент) замінюються в стеку результатом операції.

Якщо успішно пройшли лексичний та синтаксичний аналізи, то ми приступаємо до інтерпретації. Спочатку робимо із слів речення, потім переводимо вирази в постфіксний запис та обчислюємо.

Схема роботи інтерпретатора наведено у додатку B малюнку В.3.

2.3 Кодування

Програма реалізована мовою C# серед програмування Visual Studio 2010. Текст програми представлений у додатку А.

У програмі реалізовано п'ять класів. За допомогою класу MainForn реальзований інтерфейс користувача. За допомогою класу LexAnalysis реалізовано модуль лексичного аналізу, SynAnalysis - модуль синтаксичного аналізу, Intepreter - модуль інтерпретації, ProgramisciJakPolska - допоміжний клас перекладу виразів у зворотний польський запис (постфіксний).

Призначення процедур та функцій, реалізованих у програмі, описано у таблицях 6,7,8.

Таблиця 6 - Призначення процедур та функцій лексичного аналізу

Подібні документи

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

курсова робота , доданий 06.08.2013


Проектування лексичного та синтаксичного аналізаторів навчальної мови. Правила перетворення логічних виразів на ПОЛІЗ. Формування тріад, оптимізація їхнього списку. Логічна структура програми. Тестування модулів транслятора-інтерпретатора.

курсова робота , доданий 28.05.2013


Загальна характеристика та оцінка можливостей мови програмування сі-шарп, його подібні та відмінні риси від С++ та Java. Розробка за допомогою даної мови програмування лексичного та синтаксичного аналізатора. Складання таблиць аналізу.

курсова робота , доданий 11.06.2010


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

курсова робота , доданий 14.06.2010


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

курсова робота , доданий 23.02.2012


Методика розробки та часткова реалізація транслятора для мови "С" з використанням мови "С++", що робить розбиття на мінімальні неподільні конструкції мови вихідного ланцюжка символів, ґрунтуючись на лексиці мови. Аналіз роботи програми.

курсова робота , доданий 19.03.2012


Структура, класифікація та вимоги до реалізації компілятора. Проектування та реалізація аналізуючої частини компілятора мови С++. Методи реалізації лексичного аналізу. Алгоритм роботи синтаксичного аналізатора. Принципи програмної реалізації.

курсова робота , доданий 26.01.2013


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

курсова робота , доданий 02.07.2011


Методи граматичного аналізу. Розробка структури навчального транслятора базовою мовою програмування Object Pascal у середовищі об'єктно-орієнтованого візуального програмування Borland DELPHI 6.0 з використанням операційної системи Windows XP.

курсова робота , доданий 12.05.2013


Програмна реалізація настільного додаткуз використанням мови програмування C#. Проектування та структура інтерфейсу користувача, вимоги до нього та оцінка функціональності. Розробка посібника користувача та його використання.

Кожна обчислювальна машина має власну мову програмування – мову команд або машинну мову – і може виконувати програми, записані лише цією мовою. За допомогою машинної мови в принципі можна описати будь-який алгоритм, але витрати на програмування будуть надзвичайно великі. Це пов'язано з тим, що машинний мову дозволяє описувати і обробляти лише примітивні структури даних – біт, байт, слово. Програмування в машинних кодах вимагає надмірної деталізації програми і доступне лише програмістам, які добре знають пристрій та функціонування ЕОМ. Подолати цю труднощі і дозволили мови високого рівня (Фортран, ПЛ/1, Паскаль, Сі, Ада та інших.) з розвиненими структурами даних та засобами їх обробки, які залежать від мови конкретної ЕОМ.

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

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

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

Транслятор– це програма, яка допускає на вході вихідну програму та породжує на своєму виході програму, функціонально-еквівалентну вихідній, яка називається об'єктної. Об'єктна програма записується об'єктною мовою. В окремому випадку, об'єктною мовою може бути машинна мова, і в цьому випадку, отриману на виході транслятора програму можна відразу ж виконати на ЕОМ (проінтерпретувати). При цьому ЕОМ є інтерпретатором об'єктної програми у машинних кодах. У загальному випадку об'єктна мова не обов'язково має бути машинною або близькою до неї (автокодом). Як об'єктна мова може служити деяка проміжна мова– мова, що лежить між вхідною та машинною мовами.

Якщо як об'єктна мова використовується проміжна мова, то можливі два варіанти побудови транслятора.

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

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

Інтерпретатори використовуються також і при емуляції програм - виконання на технологічній машині програм, складених для іншої (об'єктної) машини. Даний варіант, зокрема, використовується при налагодженні на універсальній ЕОМ програм, які виконуватимуться на спеціалізованій ЕОМ.

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

У побудові компілятора за Останніми рокамидосягнуто значних успіхів. Перші компілятори використовували так звані прямі методи трансляції– це переважно евристичні методи, у яких на основі загальної ідеї для кожної конструкції мови розроблявся свій алгоритм переведення у машинний еквівалент. Ці методи були повільні і носили структурного характеру.

В основі методики проектування сучасних компіляторів лежить композиційний синтаксично-керований метод обробки мов. Композиційний у тому сенсі, що процес переведення вихідної програми в об'єктну реалізується композицією функціонально незалежних відображень з явно виділеними вхідними та вихідними структурами даних. Ці відображення будуються з розгляду вихідної програми, як композиції основних аспектів (рівнів) опису вхідної мови: лексики, синтаксису, семантики і прагматики, і виявлення цих аспектів з вихідної програми в ході її компіляції. Розглянемо ці аспекти для одержання спрощеної моделі компілятора.

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

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

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

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

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

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

Синтаксичний аналізатор приймає вихід лексичного аналізатора і переводить послідовність образів лексем у форму проміжної програми. Проміжна програма є по суті уявленням синтаксичного дерева програми. Останнє відбиває структуру вихідної програми, тобто. порядок та зв'язки між її операторами. У ході побудови синтаксичного дерева виконується синтаксичний контроль - Виявлення синтаксичних помилок у програмі.

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

Мал. 1.1. Спрощена функціональна модель транслятора

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

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

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

Цілі та завдання дисципліни. Основні поняття та визначення. Загальні особливостімов програмування та трансляторів. Узагальнена структура транслятора. Варіанти взаємодії блоків транслятора.

Цілі та завдання дисципліни

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

Незважаючи на те, що до теперішнього часу розроблено тисячі різних мов та їх трансляторів, процес створення нових додатків у цій галузі не припиняється. Це як з розвитком технології виробництва обчислювальних систем, і з необхідністю вирішення дедалі складніших прикладних завдань. Крім того, елементи теорії мов та формальних граматик застосовні і в інших різноманітних областях, наприклад, при описі структур даних, файлів, зображень, представлених не в текстовому, а в двійковому форматі. Ці методи корисні і розробки своїх трансляторів навіть там, де вже є відповідні аналоги. Така розробка може бути зумовлена ​​різними причинами, зокрема функціональними обмеженнями, відсутністю локалізації, низькою ефективністю. Наприклад, однією з останніх розробок компанії Microsoftє мова програмування C#, а однією з причин створення є прагнення до зниження популярності мови програмування Java. Можна навести безліч інших прикладів, коли розробка свого транслятора може бути актуальною. Тому, основи теорії мов та формальних граматик, а також практичні методирозробки трансляторів лежать у фундаменті інженерної освіти з інформатики та обчислювальної техніки.

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

Мета дисципліни: надати знання з основ теорії мов та формальних граматик, теорії автоматів, методів розробки трансляторів.

Досягнення поставленої мети під час викладання дисципліни вирішуються такі:

1. У ході лекційного курсу розглядаються загальні принципи організації процесу трансляції та структури трансляторів. Вивчаються основи теорії побудови трансляторів.
2. На лабораторних заняттях та в ході самостійної роботиздійснюється практичне закріплення одержаних теоретичних знань: розробляється транслятор для простої мови програмування.

Основні поняття та визначення

Більшість визначених визначень запозичено з [АРНФТС Англо-російсько-німецько-французький тлумачний словник з обчислювальної техніки та обробки даних, 4132 терміни. Під. ред. А.А. Дородніцина. М.: 1978. 416 с.) ].

Транслятор - обслуговуюча програма, що перетворює вихідну програму, надану вхідною мовою програмування, в робочу програму, представлену об'єктною мовою.

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

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

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

Компілятор - це обслуговуюча програма, що виконує трансляцію машинною мовою програми, записаної вихідною мовою програмування. Так само як і асемблер, компілятор забезпечує перетворення програми з однієї мови на іншу (найчастіше в мову конкретного комп'ютера). Разом з тим, команди вихідної мови значно відрізняються за організацією та потужністю від команд машинної мови. Існують мови, у яких одна команда вихідної мови транслюється у 7-10 машинних команд. Проте є й такі мови, у яких кожній команді може відповідати 100 і більше машинних команд (наприклад, Пролог). Крім того, у вихідних мовах досить часто використовується сувора типізація даних, що здійснюється через їх попередній опис. Програмування може спиратися не так на кодування алгоритму, але в ретельне обдумування структур даних чи класів. Процес трансляції з таких мов зазвичай називається компіляцією, а вихідні мови зазвичай належать до мов програмування високого рівня (чи високорівневих мов). Абстрагування мови програмування від системи команд комп'ютера призвело до незалежного створення найрізноманітніших мов, орієнтованих вирішення конкретних завдань. З'явилися мови для наукових розрахунків, економічних розрахунків, доступу до баз даних та інші.

Інтерпретатор - програма або пристрій, що здійснює пооператорну трансляцію та виконання вихідної програми. На відміну від компілятора, інтерпретатор не породжує на виході програму машинною мовою. Розпізнавши команду вихідної мови, він одразу виконує її. Як у компіляторах, так і в інтерпретаторах використовуються однакові методи аналізу вихідного текступрограми. Але інтерпретатор дозволяє розпочати обробку даних після написання навіть однієї команди. Це робить процес розробки та налагодження програм більш гнучким. Крім того, відсутність вихідного машинного коду дозволяє не "захаращувати" зовнішні пристрої додатковими файлами, а сам інтерпретатор можна досить легко адаптувати до будь-яких машинних архітектур, розробивши його лише один раз широко поширеною мовою програмування. Тому, інтерпретовані мови, типу Java Script, VB Script, набули широкого поширення. Недоліком інтерпретаторів є низька швидкість виконання програм. Зазвичай інтерпретовані програми виконуються в 50-100 разів повільніше за програми, написані в машинних кодах.

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

Емулятори використовуються досить часто в різних цілях. Наприклад, при розробці нових обчислювальних систем спочатку створюється емулятор, що виконує програми, що розробляються для ще неіснуючих комп'ютерів. Це дозволяє оцінити систему команд та напрацювати базове програмне забезпеченняще до того, як буде створено відповідне обладнання.

Дуже часто емулятор використовується для виконання старих програм на нових обчислювальних машинах. Зазвичай нові комп'ютери мають більш високу швидкодію і мають більш якісну периферійне обладнання. Це дозволяє емулювати старі програми більш ефективно, ніж їх виконання на старих комп'ютерах. Прикладом такого підходу є розробка емуляторів домашнього комп'ютера ZX Spectrum із мікропроцесором Z80. Досі знаходяться любителі пограти на емуляторі в застарілі, але все ще не втратили колишньої привабливості, ігрові програми. Емулятор може також використовуватися як більш дешевий аналог сучасних комп'ютерних систем, Забезпечуючи при цьому прийнятну продуктивність, еквівалентну молодшим моделям деякого сімейства архітектур. Як приклад можна навести емулятори IBM PC сумісних комп'ютерів, реалізовані більш потужних комп'ютерах фірми Apple. Ряд емуляторів, написаних для IBM PC, успішно замінюють різні ігрові приставки.

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

Перекодувальник - програма або програмний пристрій, що перекладають програми, написані машинною мовою однієї ЕОМ в програми машинною мовою іншої ЕОМ. Якщо емулятор є менш інтелектуальним аналогом інтерпретатора, то перекодувальник виступає в тій же якості по відношенню до компілятора. Точно також вихідний (і зазвичай двійковий) машинний код або проміжне уявлення перетворюються на інший аналогічний код по одній команді і без будь-якого загального аналізу структури вихідної програми. Перекодувальники бувають корисні при перенесенні програм з одних комп'ютерних архітектур на інші. Вони можуть також використовуватися для відновлення тексту програми мовою високого рівня за наявним двійковим кодом.

Макропроцесор - програма, що забезпечує заміну однієї послідовності символів на іншу[Браун]. Це різновид компілятора. Він здійснює генерацію вихідного тексту шляхом обробки спеціальних вставок, розміщених у вихідному тексті. Ці вставки оформляються спеціальним чином і належать конструкціям мови, яку називають макромовою. Макропроцесори часто використовуються як надбудови мов програмування, збільшуючи функціональні можливості систем програмування. Практично будь-який асемблер містить макропроцесор, що підвищує ефективність розробки машинних програм. Такі системи програмування зазвичай називаються макроассемблерів.

Макропроцесори використовують і з мовами високого рівня. Вони збільшують функціональні можливості мов PL/1, C, C++. Особливо широко макропроцесори застосовуються C і C++, дозволяючи спростити написання програм. Приклад широкого використання макропроцесорів є бібліотека класів Microsoft Foundation Classes (MFC). Через макровставки в ній реалізовано карти повідомлень та інші програмні об'єкти. При цьому макропроцесори підвищують ефективність програмування без зміни синтаксису та семантики мови.

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

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

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

Загальні особливості мов програмування та трансляторів

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

Мови програмування є інструментами на вирішення завдань у різних предметних галузях, що визначає специфіку їх організації та відмінності за призначенням. Як приклад можна навести такі мови як Фортран, орієнтований на наукові розрахунки, C, призначений для системного програмування, Пролог, що ефективно описує завдання логічного висновку, Лісп, що використовується для рекурсивної обробки списків. Ці приклади можна продовжити. p align="justify"> Кожна з предметних областей пред'являє свої вимоги до організації самої мови. Тому можна відзначити різноманітність форм подання операторів і виразів, відмінність у наборі базових операцій, зниження ефективності програмування під час вирішення завдань, які пов'язані з предметної областю. Мовні відмінності відбиваються у структурі трансляторів. Лісп і Пролог найчастіше виконуються як інтерпретації через те, що використовують динамічне формування типів даних під час обчислень. Для трансляторів з мови Фортран характерна агресивна оптимізація результуючого машинного коду, яка стає можливою завдяки відносно простій семантиці конструкцій мови - зокрема, через відсутність механізмів альтернативного іменування змінних через покажчики або посилання. Наявність вказівників у мові C пред'являє специфічні вимоги до динамічного розподілу пам'яті.

Структура мови характеризує ієрархічні відносини між його поняттями, що описуються синтаксичними правилами. Мови програмування можуть відрізнятися друг від друга з організації окремих понять і з відносинам з-поміж них. Мова програмування PL/1 допускає довільне вкладення процедур та функцій, тоді як у C всі функції повинні знаходитись на зовнішньому рівні вкладеності. Мова C++ допускає опис змінних у будь-якій точці програми перед першим її використанням, а Паскале змінні мають бути визначені у спеціальній області описи. Ще далі у цьому питанні йде PL/1, який допускає опис змінної після її використання. Або опис можна взагалі опустити та керуватися правилами, прийнятими за умовчанням. Залежно від прийнятого рішення транслятор може аналізувати програму за один або кілька проходів, що впливає на швидкість трансляції.

Семантика мов програмування змінюється у дуже широких межах. Вони відрізняються як по особливостям реалізації окремих операцій, а й у парадигмам програмування, визначальним важливі розбіжності у методах розробки програм. Специфіка реалізації операцій може стосуватися як структури даних, що обробляються, так і правил обробки одних і тих же типів даних. Такі мови, як PL/1 та APL підтримують виконання матричних та векторних операцій. Більшість мов працюють в основному зі скалярами, надаючи для обробки масивів процедури та функції, написані програмістами. Але навіть при виконанні операції додавання двох цілих чисел такі мови, як C і Паскаль можуть поводитися по-різному.

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

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

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

1. Мови програмування призначені для полегшення програмування. Тому їхні оператори та структури даних потужніші, ніж у машинних мовах.
2. Для підвищення наочності програм замість числових кодів використовуються символічні чи графічні уявлення конструкцій мови, зручніші їхнього сприйняття людиною.
3. Для будь-якої мови визначається:

• Безліч символів, які можна використовувати для запису правильних програм (алфавіту), є основними елементами.
• Безліч правильних програм (синтаксис).
• "Сенс" кожної правильної програми (семантика).

Незалежно від специфіки мови будь-який транслятор можна вважати функціональним перетворювачем F, що забезпечує однозначне відображення X в Y, де X - програма вихідною мовою, Y - програма вихідною мовою. Тому сам процес трансляції формально можна уявити досить просто і зрозуміло:

Формально кожна правильна програма X - це ланцюжок символів з деякого алфавіту A, що перетворюється на відповідний їй ланцюжок Y, складений із символів алфавіту B.

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

У зв'язку з цим для всіх мов та їх програм можна додатково виділити такі загальні риси: кожна мова повинна містити правила, що дозволяють породжувати програми, що відповідають цій мові або розпізнавати відповідність між написаними програмами та заданою мовою.

Зв'язок структури програми з мовою програмування називається синтаксичним відображенням.

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

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

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

<выражение> ::= <слагаемое> | <выражение> + <слагаемое>

<слагаемое> ::= <множитель> | <слагаемое> * <множитель>

<множитель> ::= <буква> | (<выражение>)

<буква>

Примітка. Знак "::=" читається як "це є". Вертикальна характеристика "|" читається як "або".

Якщо правила будуть записані інакше, то зміниться та ієрархічна структура. Як приклад можна навести такі спосіб запису правил:

<выражение> ::= <операнд> | <выражение> + < операнд > | <выражение> * < операнд >

<операнд> ::= <буква> | (<выражение>)

<буква>::= a | b | з | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

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

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

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

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

Його синтаксична структура описується правилами:

<выражение> ::= <буква> | <операнд> <операнд> <операция>

< операнд > ::= < буква > | < выражение >

< операция > ::= + | *

<буква>::= a | b | з | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Ієрархічне дерево, що визначає синтаксичну структуру, представлене на рис. 1.3.

Інший характерною рисою всіх мов є їхня семантика. Вона визначає зміст операцій мови, коректність операндів. Ланцюжки, що мають однакову синтаксичну структуру в різних мовах програмування, можуть різнитися за семантикою (що, наприклад, спостерігається в C++, Pascal, Basic для наведеного вище фрагмента арифметичного виразу).

Знання семантики мови дозволяє відокремити її від його синтаксису та використовувати для перетворення на іншу мову (здійснити генерацію коду).

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

Узагальнена структура транслятора

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

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

1. Фаза лексичного аналізу.
2. Фаза синтаксичного аналізу, що складається з:

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

Фаза генерації коду, що здійснює:

• семантичний аналіз компонент проміжного уявлення чи об'єктної моделі мови;
• переведення проміжного подання або об'єктної моделі в об'єктний код.

Поряд із основними фазами процесу трансляції можливі також додаткові фази:

2а. Фаза дослідження та оптимізації проміжного уявлення, що складається з:

2а.1. аналізу коректності проміжного уявлення;
2а.2. оптимізації проміжного уявлення.

3а. Фаза оптимізації об'єктного коду

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

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

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

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

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

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

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

Таким чином, синтаксичний аналізатор є складним блоком транслятора. Тому його можна розбити на такі:

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

Узагальнена структура синтаксичного аналізатора наведена на рис. 1.6.

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

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

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

Варіанти взаємодії блоків транслятора

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

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

На основі двох основних варіантів можна також створювати їх різноманітні поєднання.

Багатопрохідна організація взаємодії блоків транслятора

Даний варіант взаємодії блоків, з прикладу компілятора, представлений на рис 1.7.

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

До переваг такого підходу можна віднести:

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

До недоліків слід зарахувати.

1. Наявність великих обсягів проміжної інформації, з якої в Наразічасу потрібна лише невелика частина.
2. Уповільнення швидкості трансляції через послідовне виконання фаз і використання для економії оперативної пам'яті зовнішніх пристроїв.

Цей підхід може бути зручним при побудові трансляторів з мов програмування, що має складну синтаксичну та семантичну структуру (наприклад, PL/I). У таких ситуаціях трансляцію складно здійснити один прохід, тому результати попередніх проходів простіше представляти як додаткових проміжних даних. Слід зазначити, що складні семантична та синтаксична структури мови можуть призвести до додаткових проходів, необхідних встановлення необхідних залежностей. Загальна кількість проходів може бути понад десять. На число проходів може також впливати використання у програмі конкретних можливостей мови, таких як оголошення змінних та процедур після їх використання, застосування правил оголошення за умовчанням тощо.

Однопрохідна організація взаємодії блоків транслятора

Один із варіантів взаємодії блоків компілятора при однопрохідній організації представлено на рис. 1.8.

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

Генератор коду функціонує аналогічно. За отриманим фрагментом проміжного подання він створює відповідний фрагмент об'єктного коду. Після цього керування повертається синтаксичному аналізатору.

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

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

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

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

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

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

Комбіновані взаємодії блоків транслятора

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

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

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

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

Процес трансляції, включаючи генерацію коду, може бути виконаний за будь-яке число проходів (у прикладі використовується однопрохідна трансляція, представлена ​​раніше на ). Однак сформований об'єктний код не виконується на відповідній обчислювальній системі, а емулюється на комп'ютері з іншою архітектурою. Така схема застосовується у середовищі побудованої навколо мови програмуванні Java. Сам транслятор генерує код віртуальної Java-машини, емуляція якого здійснюється спеціальними засобамияк автономно, і у середовищі Internet браузера.

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

Контрольні питання та завдання

1. Назвіть відмінності:

• інтерпретатора від компілятора;
• компілятора від асемблера;
• перекодувальника від транслятора;
• емулятора від інтерпретатора;
• синтаксису від семантики.

1. Розкажіть про відомі Вам останні розробки мов програмування. Наведіть основні характеристики цих мов.
2. Наведіть конкретні приклади використання методів трансляції в областях, не пов'язаних із мовами програмування.
3. Наведіть конкретні приклади компілюваних мов програмування.
4. Наведіть конкретні приклади інтерпретованих мов програмування.
5. Наведіть конкретні приклади мов програмування, для яких є компілятори, так і інтерпретатори.
6. Основні переваги та недоліки компіляторів.
7. Основні переваги та недоліки інтерпретаторів.
8. Опишіть основні відмінності у синтаксисі двох відомих мов програмування.
9. Опишіть основні відмінності в семантиці двох відомих мов програмування.
10. Назвіть основні фази процесу трансляції та їх призначення.
11. Назвіть специфічні особливості однопрохідної трансляції.
12. Назвіть специфічні особливості багатопрохідної трансляції.
13. Наведіть приклади можливих комбінацій однопрохідної та багатопрохідної трансляції. Розкажіть про практичному використанніцих схем.