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

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

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

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

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

Інструкція

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

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

    Додайте в алгоритми синтаксичного аналізу функціонал побудови дерева обчислення функцій, методів класів. При правильній структурі алгоритмів розбору даний функціонал може бути впроваджений без особливих проблем. Це дозволить уникнути необхідності його реалізації у вигляді окремого модуля. Створені структури даних повинні містити списки інструкцій у вигляді «плоских» послідовностей (арифметичні вирази, розгорнуті в постфіксной форму, придатну для обчислення на стекової машині, цикли, перетворені в комбінації послідовностей обчислювальних інструкцій і умовних чи безумовних переходів, і т.д.).
  5. Створіть модуль оптимізації, якщо це необхідно. Він повинен обробляти і перетворювати структури даних, підготовлені на попередньому кроці. Алгоритми та методи оптимізації вельми різноманітні.
  6. Розробіть генератор коду. Обробляючи структури, підготовлені на четвертому чи п’ятому кроки, він повинен просто перетворювати послідовності абстрактних інструкцій в команди для виконання на конкретній платформі.
  7. Створіть програму зв’язування (линкер), якщо це необхідно. Вона повинна виробляти формування результуючого виконуваного модуля, здійснюючи вибір розташування сегментів коду, обчислення адрес міток і т.д.