Розробка компілятора з вхідної мови програмування (стр. 2 из 5)

Загальна схема компілятора

Можна виділити сім різних логічних задач:

а. Інтерпретація – визначення точного змістового навантаження, створення матриці та таблиць з допомогою програм інтерпретації;

б. Машинно-незалежна оптимізація – створення оптимальнішої матриці;

в. Лексичний аналіз – розпізнавання базових елементів та створення стандартних символів;

г. Синтаксичний аналіз – розпізнавання базових синтаксичних конструкцій з використанням редукцій;

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

е. Генерація коду – використання макропроцесора для отримання більш оптимального вихідного коду;

Фази з першої по четверту машинно-незалежні і визначаються тільки мовою. Фази з п’ятої по сьому – машинно-залежні і не залежать від мови. З метою забезпечення вищої ефективності ці фази можуть не розділятись так чітко.

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

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

3.1 Розробка лексичного аналізатора

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

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

Транслятор – програма, що обробляє вхідну програму, написану на вхідній мові і генерує програму на об’єктній мові. Об’єктна мова як правило є мовою деякої ЕОМ і таку програму одразу можна виконувати. Транслятори можна поділити на асемблери і компілятори, які транслюють відповідно мови низького і високого рівня.

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

Процес розробки компілятора можна зобразити такою схемою:

Рисунок 1 - Процес розробки компілятора.

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

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

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

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

Покажемо на прикладі дерево конструкції while мови С.

While (f+a*d) a=a+5;

Рисунок 2 Конструкції while мови С

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

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

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

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

Вибір структур вхідних даних

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

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

NODE

{ int line;– номер рядка лексеми

int idlexem;– код лексеми (номер у таблиці)

int type;– тип, якщо це ідентифікатор

int is_int;– чи це ідентифікатор, чи рядкова константа, чи число

int is_ar;– кількість індексів масиву (для простої змінної – 0)

NODE* next; }– вказівник на наступний елемент списку

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

FPAR {

int type;– тип параметра (1..4)

FPAR* next; }– вказівник на наступний елемент списку

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

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

Порміжний файл з розширенням с транслюється у ехе-файл стандартним компілятором bсс.ехе.

3.1.1 Розробка блок-схеми програми

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

Загальну структуру програми можна подати в такому спрощеному вигляді:

Рисунок 3 Загальна структура програми у спрощеному вигляді

3.2 Розробка синтаксичного аналізатора

Синтаксичний аналіз – це процес, в якому досліджується послідовність лексем, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що сформульовані у визначені синтаксису мови.

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