Документація українською/ Програмування/ Створення компілятора

Автор - Корнійко Ілля, k_liya на ukr крапка net

Теоретичний вступ

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

  1. Аналіз (parsing) – розбиття початкової програми на складові частини та створення проміжного представлення
  2. Синтез – побудова цільової програми з проміжного представлення

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

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

  1. Лексичний аналізатор
  2. Синтаксичний аналізатор
  3. Семантичний аналізатор
  4. Генератор проміжного коду
  5. Оптимізатор
  6. Генератор цільового коду

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

len := 3.14 * r;

складається з наступних токенів

  1. Ідентифікатор len
  2. Символ присвоєння :=
  3. Числова стала 3.14
  4. Знак множення *
  5. Ідентифікатор r
  6. Роздільник операторів ;

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

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

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

Програма є послідовністю терміналів, яку можна вивести зі стартового символу послідовно застосовуючи правила виводу (продукції). Продукція – це заміна послідовності символів S1 на послідовність символів S2 (Позначається. S1 : S2 або S1 -> S2). Продукція називається контесктно-незалежною, якщо S1 – один символ. Звичайно розглядаються лише контесктно-незалежні продукції.

Задача синтаксичного аналізатора – встановити шлях, яким вхідна програма виводиться з стартового символа.

Наприклад, наступна граматика із трьох продукцій описує вирази (expression), що можуть складатись з ідентифікаторів (identifier), чисел (number), та знаку додавання +

expression : identifier
expression : number
expression : expression + expression

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

В цій граматиці символами є expression, number, identifier та +. Expression є стартовим символом і нетерміналом, решта символів є терміналами.

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

В Unix поширені генератор лексичних аналізаторів ?(F)Lex, та генератори синтаксичних аналізаторів Bison та ?Yacc.

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

Далі буде...