Я написав мову програмування. Ось як ти теж можеш.

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

  • змінні
  • функції
  • визначені користувачем структури

Якщо вас це цікавить, перевірте цільову сторінку Pinecone або його репозитарій GitHub.

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

І все ж, я все-таки зробив абсолютно нову мову. І це працює. Тож я, мабуть, роблю щось правильно.

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

Я також торкнуся деяких компромісів, які я вже робив, і чому я приймав рішення, які я приймав.

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

Починаємо

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

Складено проти інтерпретовано

Існує два основних типи мов: компіляція та інтерпретація:

  • Компілятор з’ясовує все, що зробить програма, перетворює його на “машинний код” (формат, який комп’ютер може запустити дуже швидко), а потім зберігає, що буде виконано пізніше.
  • Інтерпретатор проходить через вихідний код рядок за рядком, з’ясовуючи, що він робить по ходу.

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

Я високо ціную продуктивність, і я побачив відсутність мов програмування, які одночасно мають високу продуктивність та орієнтуються на простоту, тому я пішов із компіляцією для Pinecone.

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

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

Вибір мови

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

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

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

Дизайн високого рівня

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

Перший етап - це рядок, що містить весь вихідний файл. Заключний етап - це те, що можна запустити. Це все стане зрозумілим, коли ми крок за кроком проходимо трубопровід Pinecone.

Лексінг

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

Токени

Лексема - це невелика одиниця мови. Маркером може бути ім'я змінної або функції (AKA - ідентифікатор), оператор або число.

Завдання Лексера

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

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

Гнучка

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

Переважним таким інструментом є програма Flex, яка генерує лексери. Ви надаєте йому файл, який має спеціальний синтаксис для опису граматики мови. З цього він генерує програму C, яка використовує лексему рядок і видає бажаний результат.

Моє рішення

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

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

Розбір

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

Обов'язки аналізатора

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

Зубри

Знову ж таки, було прийнято рішення про залучення сторонніх бібліотек. Переважною бібліотекою синтаксичного аналізу є Bison. Зубри багато працюють як Flex. Ви пишете файл у власному форматі, який зберігає інформацію про граматику, а потім Bison використовує його для створення програми C, яка виконуватиме ваш синтаксичний аналіз. Я не вирішив використовувати Бізона.

Чому замовлення краще

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

З синтаксичним аналізатором справа зовсім інша. Зараз мій парсер Pinecone має 750 рядків, і я написав три з них, оскільки перші два були сміттям.

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

  • Мінімізуйте перемикання контексту в робочому процесі: перемикання контексту між C ++ і Pinecone досить погано, не вводячи граматику граматики Бізона
  • Будьте простішими у збірці: кожного разу, коли граматика змінюється, Bison повинен запускатися перед збіркою. Це можна автоматизувати, але це стає болем при перемиканні між системами побудови.
  • Мені подобається створювати круте лайно: я не робив Pinecone, тому що думав, що це буде легко, так чому б мені відводити центральну роль, коли я міг це робити сам? Спеціальний аналізатор може бути нетривіальним, але це цілком здійсненно.

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

"Дещо суперечливіше, я не став би витрачати час на генератори лексерів або аналізаторів та інші так звані" компілятори компіляторів ". Вони марно витрачають час. Написання лексера та синтаксичного аналізатора - це незначний відсоток роботи по написанню компілятора. Використання генератора займе приблизно стільки ж часу, скільки писати його вручну, і це одружить вас із генератором (що важливо при перенесенні компілятора на нову платформу). А генератори також мають невдалу репутацію видавати паршиві повідомлення про помилки ".

Дерево дій

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

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

Дерево дій проти AST

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

Запуск дерева дій

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

Параметри компіляції

"Але почекай!" Я чую, ти кажеш: "Хіба Pinecone не повинен складати?" Так. Але складати складніше, ніж інтерпретувати. Є кілька можливих підходів.

Створіть власний компілятор

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

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

Навіть команди, що стоять за Свіфтом, Рустом і Клангом, не хочуть морочитися з цим усім самостійно, тому натомість усі вони використовують ...

LLVM

LLVM - це колекція інструментів компілятора. По суті, це бібліотека, яка перетворить вашу мову на складений виконуваний двійковий файл. Це здавалося ідеальним вибором, тому я стрибнув прямо. На жаль, я не перевірив, наскільки глибока вода, і одразу потонув.

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

Транспіляція

Я хотів якийсь зібраний Pinecone, і я хотів його швидко, тому я звернувся до одного методу, який, як я знав, міг би зробити роботу: транслірування.

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

Майбутнє

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

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

Висновок

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

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

  • Якщо ви сумніваєтесь, переходьте до тлумачення. Інтерпретовані мови, як правило, легше проектувати, будувати та вивчати. Я не відбиваю вас писати складений, якщо ви знаєте, що це те, що ви хочете зробити, але якщо ви знаходитесь на паркані, я піду в інтерпретацію.
  • Що стосується лексерів та парсерів, робіть все, що завгодно. Є вагомі аргументи за і проти написання власного. Врешті-решт, якщо ти продумуєш свій дизайн і реалізуєш усе розумно, це насправді не має значення.
  • Вчіться з трубопроводу, у якого я опинився. Багато спроб і помилок пішло на проектування трубопроводу, який я маю зараз. Я намагався ліквідувати AST, AST, які перетворюються на дерева дій на місці, та інші жахливі ідеї. Цей конвеєр працює, тому не змінюйте його, якщо у вас немає справді гарної ідеї.
  • Якщо у вас немає часу чи мотивації для реалізації складної мови загального призначення, спробуйте застосувати таку езотеричну мову, як Brainfuck. Ці перекладачі можуть складати від кількох сотень рядків.

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

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