Написах език за програмиране. Ето как можете и вие.

През последните 6 месеца работех върху език за програмиране, наречен Pinecone. Все още не бих го нарекъл зрял, но вече има достатъчно функции, които да работят, като например:

  • променливи
  • функции
  • дефинирани от потребителя структури

Ако се интересувате от него, разгледайте целевата страница на Pinecone или неговото репо GitHub.

Не съм експерт. Когато стартирах този проект, нямах представа какво правя и все още не знам. Взех нула уроци по създаване на език, прочетох само малко за него онлайн и не спазих много от съветите, които ми дадоха.

И все пак, все пак направих напълно нов език. И работи. Значи трябва да правя нещо правилно.

В този пост ще се потопя под капака и ще ви покажа конвейера, който Pinecone (и други езици за програмиране) използват, за да превърнат изходния код в магия.

Ще засегна и някои от компромисите, които съм правил, и защо взех решенията, които взех.

Това в никакъв случай не е пълен урок за писане на език за програмиране, но е добра отправна точка, ако сте любопитни за развитието на езика.

Приготвяме се да започнем

„Нямам абсолютно никаква представа откъде бих започнал“ е нещо, което чувам много, когато казвам на други разработчици, че пиша език. В случай, че това е вашата реакция, сега ще премина през някои първоначални решения, които са взети, и стъпки, които се предприемат при стартиране на който и да е нов език.

Съставено срещу интерпретирано

Има два основни типа езици: компилирани и интерпретирани:

  • Компилаторът измисля всичко, което една програма ще направи, превръща го в „машинен код“ (формат, който компютърът може да изпълнява много бързо), след което записва това, за да бъде изпълнено по-късно.
  • Интерпретатор стъпва през изходния код ред по ред, като разбере какво прави, докато върви.

Технически всеки език може да бъде компилиран или интерпретиран, но единият или другият обикновено има повече смисъл за конкретен език. Като цяло, тълкуването е по-гъвкаво, докато компилирането има по-висока производителност. Но това е само надраскване на повърхността на много сложна тема.

Високо ценя производителността и видях липса на езици за програмиране, които са едновременно високопроизводителни и ориентирани към простота, така че отидох с компилиран за Pinecone.

Това беше важно решение, което трябва да се вземе рано, тъй като много решения за езиков дизайн са засегнати от него (например статичното въвеждане е голяма полза за компилираните езици, но не толкова за интерпретираните).

Въпреки факта, че Pinecone е проектиран с мисъл за компилиране, той има напълно функционален интерпретатор, който беше единственият начин да го стартирате известно време. За това има редица причини, които ще обясня по-късно.

Избор на език

Знам, че е малко мета, но езикът за програмиране сам по себе си е програма и затова трябва да го напишете на език. Избрах C ++ поради неговата производителност и голям набор от функции. Освен това наистина ми харесва да работя в C ++.

Ако пишете интерпретиран език, има много смисъл да го пишете на компилиран (като C, C ++ или Swift), тъй като ефективността, загубена на езика на вашия преводач и преводача, който интерпретира вашия преводач, ще се съчетае.

Ако планирате да компилирате, по-бавен език (като Python или JavaScript) е по-приемлив. Времето за компилация може да е лошо, но според мен това не е толкова голяма работа, колкото лошото време на работа.

Дизайн на високо ниво

Езикът за програмиране обикновено е структуриран като конвейер. Тоест има няколко етапа. Всеки етап има данни, форматирани по специфичен, добре дефиниран начин. Той също така има функции за трансформиране на данни от всеки етап в следващия.

Първият етап е низ, съдържащ целия входен изходен файл. Последният етап е нещо, което може да се изпълни. Всичко това ще стане ясно, когато преминем през тръбопровода Pinecone стъпка по стъпка.

Лексинг

Първата стъпка в повечето езици за програмиране е лексиране или токенизиране. „Lex“ е съкращение от лексикален анализ, много изискана дума за разделяне на куп текст в символи. Думата „tokenizer“ има много по-голям смисъл, но „lexer“ е толкова забавно да се каже, че я използвам така или иначе.

Токени

Лекенът е малка единица от езика. Токенът може да бъде име на променлива или функция (AKA идентификатор), оператор или номер.

Задача на Lexer

Лексерът трябва да поеме низ, съдържащ изходен код на цели файлове и да изплюе списък, съдържащ всеки маркер.

Бъдещите етапи на конвейера няма да се отнасят обратно към оригиналния изходен код, така че lexer трябва да предостави цялата информация, необходима за тях. Причината за този относително строг конвейерен формат е, че лексерът може да изпълнява задачи като премахване на коментари или откриване дали нещо е число или идентификатор. Искате да запазите тази логика заключена в лексера, така че да не се налага да мислите за тези правила, когато пишете останалата част от езика, и така можете да промените този тип синтаксис на едно място.

Flex

В деня, в който започнах езика, първото нещо, което написах, беше прост лексер. Скоро след това започнах да научавам за инструменти, които уж улесняват лексинга и по-малко бъги.

Преобладаващият такъв инструмент е Flex, програма, която генерира лексери. Давате му файл, който има специален синтаксис, за да опише граматиката на езика. От това той генерира C програма, която лексира низ и произвежда желания изход.

Моето решение

Реших да запазя лексера, който написах за момента. В крайна сметка не видях значителни ползи от използването на Flex, поне не достатъчно, за да оправдая добавянето на зависимост и усложняването на процеса на изграждане.

Лексерът ми е дълъг само няколкостотин реда и рядко ми създава проблеми. Преобръщането на собствения ми lexer също ми дава по-голяма гъвкавост, като например възможността да добавя оператор към езика, без да редактирам множество файлове.

Разбор

Вторият етап на тръбопровода е парсерът. Анализаторът превръща списък с жетони в дърво от възли. Дърво, използвано за съхраняване на този тип данни, е известно като абстрактно синтаксисно дърво или AST. Поне в Pinecone AST няма информация за типовете или кои идентификатори кои са. Това са просто структурирани символи.

Задължения на анализатора

Анализаторът добавя структура към подредения списък с токени, които лексерът произвежда. За да спре двусмислията, анализаторът трябва да вземе предвид скобите и реда на операциите. Простото анализиране на операторите не е ужасно трудно, но с добавянето на повече езикови конструкции синтактичният анализ може да стане много сложен.

Бизони

Отново беше взето решение за включване на библиотека на трета страна. Преобладаващата библиотека за разбор е Bison. Bison работи много като Flex. Пишете файл в персонализиран формат, който съхранява граматичната информация, след което Bison използва това, за да генерира програма на C, която ще извърши вашия анализ. Не избрах да използвам Бизон.

Защо потребителският е по-добър

С lexer решението да използвам собствения си код беше доста очевидно. Лексерът е толкова тривиална програма, че ако не напиша собственото си, се чувствах почти толкова глупаво, колкото да не пиша собствената си "лява подложка".

С парсерът е съвсем друг въпрос. Понастоящем моят парсер Pinecone е с дължина 750 реда и съм написал три от тях, тъй като първите два бяха боклук.

Първоначално взех решението си по редица причини и макар да не е минало напълно гладко, повечето от тях са верни. Основните са следните:

  • Минимизиране на превключването на контекста в работния процес: превключването на контекста между C ++ и Pinecone е достатъчно лошо, без да се хвърля граматиката на граматиката на Bison
  • Продължете да правите компилация: всеки път, когато се променя граматиката, Bison трябва да се изпълнява преди компилацията. Това може да се автоматизира, но се превръща в болка при превключване между компилационни системи.
  • Харесва ми да създавам готини лайна: не направих Pinecone, защото мислех, че ще бъде лесно, така че защо да делегирам централна роля, когато мога да го направя сам? Персонализиран парсер може да не е тривиален, но е напълно изпълним.

В началото не бях напълно сигурен дали вървя по жизнеспособен път, но ми беше дадено увереност от това, което Уолтър Брайт (разработчик на ранна версия на C ++ и създателят на езика D) трябваше да каже на тема:

„Малко по-противоречиво, не бих си направил труда да губя време с генератори на lexer или parser и други така наречени„ компилаторски компилатори “. Те са загуба на време. Писането на лексер и парсер е малък процент от работата по писане на компилатор. Използването на генератор ще отнеме около толкова време, колкото и писането му на ръка и ще ви ожени за генератора (което има значение при пренасяне на компилатора към нова платформа). А генераторите също имат злощастната репутация, че излъчват лоши съобщения за грешки. "

Дърво за действие

Сега напуснахме областта на общи, универсални термини или поне вече не знам какви са термините. От моето разбиране това, което наричам „дърво на действията“, е най-близко до IR на LLVM (междинно представяне).

Съществува фина, но много съществена разлика между дървото за действие и дървото на абстрактния синтаксис. Отне ми доста време, за да разбера, че дори трябва да има разлика между тях (което допринесе за необходимостта от пренаписване на парсера).

Дърво на действие срещу AST

Казано по-просто, дървото за действие е AST с контекст. Този контекст е информация, като например какъв тип връща функция или че две места, в които се използва променлива, всъщност използват една и съща променлива. Тъй като трябва да разбере и запомни целия този контекст, кодът, който генерира дървото за действие, се нуждае от много таблици за търсене в пространството от имена и други thingamabobs.

Стартиране на дървото за действие

След като имаме дървото за действие, стартирането на кода е лесно. Всеки възел за действие има функция „изпълнение“, която взема някакъв вход, прави каквото трябва действието (включително евентуално извикване на поддействие) и връща изхода на действието. Това е преводачът в действие.

Опции за компилиране

"Но почакай!" Чувам, че казвате, „не трябва ли Pinecone да компилира?“ Да, така е. Но компилирането е по-трудно от тълкуването. Има няколко възможни подхода.

Изградете мой собствен компилатор

Отначало това ми прозвуча като добра идея. Обичам да правя нещата сам и ме е сърбеж за оправдание да се справя добре в сглобяването.

За съжаление, писането на преносим компилатор не е толкова лесно, колкото писането на някакъв машинен код за всеки езиков елемент. Поради броя на архитектурите и операционните системи е непрактично всеки човек да напише бекенд на компилатор на различни платформи.

Дори екипите зад Swift, Rust и Clang не искат да се занимават сами с всичко това, така че вместо това всички използват ...

LLVM

LLVM е колекция от инструменти на компилатора. Това е основно библиотека, която ще превърне вашия език в компилиран изпълним двоичен файл. Изглеждаше идеалният избор, затова скочих направо. За съжаление не проверих колко дълбока е водата и веднага се удавих.

LLVM, макар и да не е трудно за асемблерен език, е гигантска сложна библиотека. Не е невъзможно да се използва и те имат добри уроци, но осъзнах, че ще трябва да се упражня, преди да съм готов да внедря напълно компилатор на Pinecone с него.

Транспилиране

Исках някакъв компилиран Pinecone и го исках бързо, затова се обърнах към един метод, за който знаех, че мога да направя работа: преписване.

Написах Pinecone на C ++ транпилатор и добавих възможност за автоматично компилиране на изходния източник с GCC. Понастоящем това работи за почти всички програми на Pinecone (въпреки че има няколко крайни случая, които го нарушават). Това не е особено преносимо или мащабируемо решение, но засега работи.

Бъдеще

Ако приемем, че продължавам да разработвам Pinecone, рано или късно ще получи поддръжка за компилиране на LLVM. Подозирам, че няма значение колко работя върху него, транпилерът никога няма да бъде напълно стабилен и ползите от LLVM са многобройни. Въпросът е само кога ще имам време да направя няколко примерни проекта в LLVM и да го разбера.

Дотогава интерпретаторът е чудесен за тривиални програми, а C ++ пренаписването работи за повечето неща, които се нуждаят от повече производителност.

Заключение

Надявам се да съм направил езиците за програмиране малко по-загадъчни за вас. Ако все пак искате да си направите сами, горещо го препоръчвам. Има много подробности за изпълнението, които трябва да разберете, но очертанията тук трябва да са достатъчни, за да започнете.

Ето моите съвети на високо ниво за започване (не забравяйте, че всъщност не знам какво правя, така че го вземете с малко сол):

  • Ако се съмнявате, отидете на тълкуване. Тълкуваните езици обикновено са по-лесни за проектиране, изграждане и изучаване. Не ви обезсърчавам да пишете компилиран, ако знаете, че това искате да направите, но ако сте на оградата, бих отишъл да го интерпретирам.
  • Що се отнася до лексерите и парсерите, правете каквото искате. Има валидни аргументи за и против да напишете своя. В крайна сметка, ако обмислите своя дизайн и внедрите всичко по разумен начин, това всъщност няма значение.
  • Научете се от тръбопровода, с който се озовах. Много опити и грешки влязоха в проектирането на тръбопровода, който имам сега. Опитах се да елиминирам AST, AST, които се превръщат в дървета за действия и други ужасни идеи. Този тръбопровод работи, така че не го променяйте, освен ако нямате наистина добра идея.
  • Ако нямате време или мотивация да внедрите сложен език с общо предназначение, опитайте да внедрите езотеричен език като Brainfuck. Тези тълкуватели могат да бъдат кратки до няколкостотин реда.

Съжалявам много малко по отношение на развитието на Pinecone. По пътя направих редица лоши избори, но пренаписах по-голямата част от кода, засегнат от такива грешки.

В момента Pinecone е в достатъчно добро състояние, за да функционира добре и лесно да се подобри. Писането на Pinecone беше изключително образователно и приятно преживяване за мен и тепърва започва.