Як написати транслятор

Як написати транслятор

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

Вам знадобиться

  • - природна граматика або БНФ вихідної мови;
  • - засоби розробки.

Інструкція

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

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

3. Підготуйте дані для синтаксичного аналізу. На основі природної граматики або БНФ вихідної мови складіть її LL1 граматику. На основі граматики даного типу складіть схему синтаксичного розбору в термінах категорій допустимих лексем і семантичних конструкцій мови.

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

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

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

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