Как создать свой язык программирования на c

Как написать свой язык программирования

Веб разработчик вот уже 10 лет. Начинал по классике, с бекенда на PHP. Постепенно расширял кругозор: пробовал разные языки и технологии, занимался DevOps и поднимал сервера, управлял проектами и собирал команды. Последние 4 года акцентирую свое внимание на front-end и на работе с командами. Работаю в компании ЦИАН руководителем группы front-end разработки.

Разрабатывал транспиляторы для ES6, когда babel еще не существовал. Создавал собственные языки программирования (на поиграть) и DSL (для работы). Сейчас работаю над оптимизирующем компилятором для React и TypeScript.

У каждого программиста рано или поздно появляется желание создать собственный язык программирования 🙂 У меня это желание появилось несколько лет назад и тогда я не знал с чего начать.

На этом мастер-классе я хочу концентрированно поделиться своим опытом и показать вам на примерах, как сделать так, чтобы из исходного кода придуманного вами языка получилась работающая программа.

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

На мастер-классе мы создадим простейший интерпретируемый язык и пройдем через несколько этапов:

— Как прочитать исходный файл (токенизация);
— Как понять, что написано в исходном файле (парсинг);
— Как из исходного файла сделать исполняемый код (компиляция);
— Как запустить исполняемый код (интерпретация).

Бонус темы:
— Как оптимизировать исполняемый код (оптимизация);
— Как проверить валидность кода (статический анализ).

В работе будем использовать JavaScript, потому что это самый общеизвестный язык программирования в веб отрасли. Подготовьтесь заранее и установите себе на компьютер стабильную LTS версию Node.js (>=6.10.0 <7.0.0).

Пишем свой язык программирования, часть 1: пишем языковую ВМ

Итак, пожалуй стоит сказать, что целью моей работы, на основе которой будет написан ряд статеек было пройти весь путь создания полнофункционального ЯП самому с 0 и затем поделиться своими знаниями, наработками и опытом с интересующимися этим людьми.

Я буду описывать создание языка, который описал ранее тут.

Он заинтересовал многих и вызвал бурную дискуссию в комментариях. Следовательно — тема интересна многим.

Думаю, что сразу стоит выложить информацию о проекте:

Сайт (будет заполнен документацией чуть позже).
Репозиторий

Чтобы самому потрогать проект и увидеть все в действии, лучше скачать репозиторий и запускать все из папки bin. В релиз я не спешу выкладывать последние версии языка и среды выполнения, т.к. мне порой бывает просто лень это делать.

Кодить я умею на C/C++ и на Object Pascal. Проект я писал на FPC, т.к. на мой взгляд этот язык гораздо проще и лучше подходит для написание подобного. Вторым определяющим фактором стало то, что FPC поддерживает огромное количество целевых платформ и пересобрать проект под нужную платформу можно с минимумом переделок. Если вы по непонятным мне причинам не любите Object Pascal, то не спешите закрывать пост и бежать кидаться камнями в комментарии. Этот язык весьма красив и нагляден, а кода я буду приводить не так уж и много. Только то, что нужно.

Итак, начну пожалуй я своё повествование.

Ставим цели

Прежде всего, любому проекту нужны поставленные цели и ТЗ, которые придется в будущем реализовывать. Нужно заранее определиться, какого типа язык будет создаваться, чтобы написать первичную ВМ для него.

Ключевые моменты, которые определяли дальнейшую разработку моей ВМ следующие:

• Динамическая типизация и приведение типов. Её поддержку я решил организовать на этапе разработки вм.
• Поддержка многопоточности. Включил этот пункт в этот список заранее, чтобы должным образом спроектировать архитектуру ВМ и организовать поддержку многопоточности на уровне ядра ВМ, а не в дальнейшем с помощью костылей.
• Экспорт внешних методов. Без этого язык будет бесполезен. Разве что его встраивать в какой-нибудь проект.
• Компилируемость языка (в цельный абстрактный исполняемый файл). Частично компилируемый или интерпретируемый? От этого многое зависит.
• Общая архитектура ВМ. Стековая или регистровая будет наша ВМ? Я попробовал реализовать и то и то. Выбрал для поддержки стековую ВМ.
• Как вы видите работу с переменными, массивами, структурами? Лично я в тот момент хотел реализовать язык, в котором автоматически почти все завязывается на неявных указателях, ведь такой подход сильно экономил бы память и упрощал жизнь разработчику. Если мы допустим передаем в методы что-нибудь большое, то автоматом передастся лишь указатель на это большое.

Сразу скажу, что ВМ я назвал максимально красноречиво — SVM (Stack-based Virtual Machine).

Начнем, пожалуй, с реализации класса переменной

Изначально я просто использовал variant тип, потому что так проще и быстрее. Это был костыль, но он подпирал проект и позволил мне быстренько реализовать первую версию ВМ и языка. Позже я засел за код и написал реализацию своего «variant». По-сути нужно написать класс, который хранит указатель на значение в памяти, в моей реализации это null/cardinal/int64/double/string/array . Можно было бы использовать case типизацию, но я посчитал, что будет лучше реализовать так, как я реализовал.

Перед тем, как начать писать код класса, я решил сразу закинуть директиву в заголовок модуля для более гибкой поддержки строк будущим языком.

П.с. для тех, кто может быть не в курсе, в чем разница между H- и H+ режимом FPC.

При сборке кода в режиме H- строки будут представлены в виде массива символов. При H+ — в виде указателя на кусок памяти. В первом случае строки будут изначально фиксированной длины и ограничены по дефолту 256 символами. Во втором случае — строки будут динамически расширяемыми и в них можно будет запихнуть гораздо больше символов. Будут работать немного медленнее, зато более функционально. При H+ можно также объявлять строки как массив символов, например таким вот образом:

var s:string[256]; 

Итак, для начала объявим Enum тип, который будем использовать как некий флажок, для определения типа данных по указателю:

type TSVMType = (svmtNull, svmtWord, svmtInt, svmtReal, svmtStr, svmtArr); 

Далее опишем основную структуру нашего типа переменной и некоторые методы:

 TSVMMem = class m_val: pointer; m_type: TSVMType; constructor Create; destructor Destroy; procedure Clear; end; . constructor TSVMMem.Create; begin m_val := nil; m_type := svmtNull; end; destructor TSVMMem.Destroy; begin Clear; end; procedure TSVMMem.Clear; inline; begin case m_type of svmtNull: < nop >; svmtWord: Dispose(PCardinal(m_val)); svmtInt: Dispose(PInt64(m_val)); svmtReal: Dispose(PDouble(m_val)); svmtStr: Dispose(PString(m_val)); svmtArr: begin SetLength(PMemArray(m_val)^, 0); Dispose(PMemArray(m_val)); end; else Error(reVarInvalidOp); end; end; 

Класс ни от чего не наследуется, поэтому inherited вызовы в конструкторе и деструкторе можно не делать. Уделю внимание директиве inline. В заголовок файла лучше добавить , чтоб наверняка. Её активное использование в ВМ довольно ощутимо повысило производительность (мб где-то аж на 15-20%!). Она говорит компилятору, что тело метода лучше встроить на место его вызова. Выходной код будет немного больше в итоге, но работать будет быстрее. В данном случае, использование inline целесообразно.

Ок, запилили мы на этом этапе основу нашего класса. Теперь нужно описать ряд сеттеров и геттеров (setter & getter) у нашего класса.

Задача в чем — написать пару методов, которые позволят запихнуть и в дальнейшем получить обратно значения из нашего класса.

Для начала разберемся с присвоением значения для нашего класса. Первым можно написать обобщенный сеттер, ну а дальше, для отдельных типов данных:

procedure TSVMMem.SetV(const value; t:TSVMType); inline; begin if (m_val <> nil) and (m_type = t) then begin case t of svmtWord: PCardinal(m_val)^ := Cardinal(value); svmtInt: PInt64(m_val)^ := Int64(value); svmtReal: PDouble(m_val)^ := Double(value); svmtStr: PString(m_val)^ := String(value); end; end else begin if m_val <> nil then FreeMem(m_val); m_type := t; case t of svmtWord: begin New(PCardinal(m_val)); PCardinal(m_val)^ := Cardinal(value); end; svmtInt: begin New(PInt64(m_val)); PInt64(m_val)^ := Int64(value); end; svmtReal: begin New(PDouble(m_val)); PDouble(m_val)^ := Double(value); end; svmtStr: begin New(PString(m_val)); PString(m_val)^ := String(value); end; else Error(reVarTypeCast); end; end; end; . procedure TSVMMem.SetW(value:cardinal); inline; begin if (m_val <> nil) and (m_type = svmtWord) then PCardinal(m_val)^ := value else begin if m_val <> nil then FreeMem(m_val); m_type := svmtWord; New(PCardinal(m_val)); PCardinal(m_val)^ := value; end; end; 

Теперь можно и для пары геттеров написать код:

function TSVMMem.GetW:cardinal; inline; begin Result := 0; case m_type of svmtWord: Result := PCardinal(m_val)^; svmtInt: Result := PInt64(m_val)^; svmtReal: Result := Trunc(PDouble(m_val)^); svmtStr: Result := StrToQWord(PString(m_val)^); else Error(reVarTypeCast); end; end; 

Ок, замечательно, теперь, после того, как вы просидели некоторое время пялясь в IDE и с энтузиазмом печатая код сеттеров и геттеров, мы стоим перед задачей реализации поддержки нашим типом математических и логических операций. В качестве примера я приведу реализацию операции сложения:

procedure TSVMMem.OpAdd(m:TSVMMem); inline; begin case m_type of svmtWord: case m.m_type of svmtWord: SetW(GetW + m.GetW); svmtInt: SetI(GetW + m.GetI); svmtReal: SetD(GetW + m.GetD); svmtStr: SetD(GetW + StrToFloat(m.GetS)); else Error(reVarInvalidOp); end; svmtInt: case m.m_type of svmtWord: SetI(GetI + m.GetW); svmtInt: SetI(GetI + m.GetI); svmtReal: SetD(GetI + m.GetD); svmtStr: SetD(GetI + StrToFloat(m.GetS)); else Error(reVarInvalidOp); end; svmtReal: case m.m_type of svmtWord: SetD(GetD + m.GetW); svmtInt: SetD(GetD + m.GetI); svmtReal: SetD(GetD + m.GetD); svmtStr: SetD(GetD + StrToFloat(m.GetS)); else Error(reVarInvalidOp); end; svmtStr: case m.m_type of svmtWord: SetS(GetS + IntToStr(m.GetW)); svmtInt: SetS(GetS + IntToStr(m.GetI)); svmtReal: SetS(GetS + FloatToStr(m.GetD)); svmtStr: SetS(GetS + m.GetS); else Error(reVarInvalidOp); end; else Error(reVarInvalidOp); end; end; 

Все просто. Аналогичным образом можно описать и дальнейшие операции и вот наш класс готов.
Для массивов ещё конечно нужны пара методов, пример получения элемента по индексу:

function TSVMMem.ArrGet(index: cardinal; grabber:PGrabber): pointer; inline; begin Result := nil; case m_type of svmtArr: Result := PMemArray(m_val)^[index]; svmtStr: begin Result := TSVMMem.CreateFW(Ord(PString(m_val)^[index])); grabber^.AddTask(Result); end; else Error(reInvalidOp); end; end; 

Супер. Теперь мы можем двигаться дальше.

Реализуем стек

Спустя время я пришел к таким мыслям. Стек должен быть и статичным (для быстродействия) и динамичным (для гибкости) одновременно.

Поэтому стек реализован блочно. Т.е. как это должно работать — изначально массив стека имеет определенный размер (я решил поставить размер блока в 256 элементов, чтобы было красиво и не мало). Соответственно, в комплекте с массивом идет счетчик, указывающий на текущую вершину стека. Перевыделение памяти — это лишняя долгая операция, которую можно выполнять реже. Если в стек будет ложиться больше значений, то его размер можно будет всегда расширить на размер ещё одного блока.

Привожу реализацию стека целиком:

type TStack = object public items: array of pointer; size, i_pos: cardinal; parent_vm: pointer; procedure init(vm: pointer); procedure push(p: pointer); function peek: pointer; procedure pop; function popv: pointer; procedure swp; procedure drop; end; PStack = ^TStack; procedure TStack.init(vm: pointer); begin SetLength(items, StackBlockSize); i_pos := 0; size := StackBlockSize; parent_vm := vm; end; procedure TStack.push(p: pointer); inline; begin items[i_pos] := p; inc(i_pos); if i_pos >= size then begin size := size + StackBlockSize; SetLength(items, size) end; end; function TStack.peek: pointer; inline; begin Result := items[i_pos - 1]; end; procedure TStack.pop; inline; begin dec(i_pos); if size - i_pos > StackBlockSize then begin size := size - StackBlockSize; SetLength(items, size); end; end; function TStack.popv: pointer; inline; begin dec(i_pos); Result := items[i_pos]; if size - i_pos > StackBlockSize then begin size := size - StackBlockSize; SetLength(items, size); end; end; procedure TStack.swp; inline; var p: pointer; begin p := items[i_pos - 2]; items[i_pos - 2] := items[i_pos - 1]; items[i_pos - 1] := p; end; procedure TStack.drop; inline; begin SetLength(items, StackBlockSize); size := StackBlockSize; i_pos := 0; end; 

Во внешние методы ВМ будет передавать указатель на стек, чтобы они могли взять оттуда нужные аргументы. Указатель на поток ВМ добавил позже, чтобы можно было реализовывать callback вызовы из внешних методов да и в общем, для передачи большей власти над ВМ методам.

Итак, как с тем, как устроен стек вы ознакомились. Таким же образом устроен callback стек, для простоты и удобства call & return операций и стек сборщика мусора. Единственное — другие размеры блоков.

Поговорим о мусоре

Его, как правило много, очень много. И с ним нужно что-то делать.

Первым делом хочу рассказать о том, как устроены сборщики мусора в других языках, например в Lua, Ruby, Java, Perl, PHP и т.д. Они работают по принципу подсчета указателей на объекты в памяти.

Т.е. вот выделили мы память под что-то, логично — указатель сразу поместили в переменную/массив/куда-то ещё. Сборщик мусора среды выполнения сразу же добавляет этот указатель себе с список возможных мусорных объектов. В фоне, сборщик мусора постоянно мониторит все переменные, массивы и т.д. Если там не оказывается указателя на что-то из списка возможного мусора — значит это мусор и память из под него нужно убрать.

Я решил реализовать свой велосипед. Мне более привычна работа с памятью по принципу Тараса Бульбы. Я тебя породил — я тебя и убью, подразумеваю я, когда вызываю очередной Free у очередного класса. Поэтому сборщик мусора у моей ВМ полуавтоматический. Т.е. его нужно вызывать в ручном режиме и работать с ним соответственно. В его очередь добавляются указатели на объявляемые временные объекты (эта роль ложится на по большей мере на транслятор и немного на разработчика). Для освобождения памяти из под других объектов можно использовать отдельный опкод.

Т.е. у сборщика мусора на момент вызова есть уже готовый список указателей, по которому нужно пробежаться и освободить память.

Итак, теперь разберемся с компиляцией в абстрактный исполняемый файл

Идея изначально заключалась в том, что приложения, написанные на моём языке смогут выполняться без исходников, как это происходит с многими похожими языками. Т.е. его можно будет использовать в коммерческих целях.

Для этого нужно определить формат исполняемых файлов. У меня получилось следующее:

1. Заголовок, например «SVMEXE_CNS».
2. Секция, содержащая список библиотек, из которых будут импортироваться методы.
3. Секция импорта нужных методов, библиотеки из которых импортируются методы указываются по их номеру в секции выше.
4. Секция констант.
5. Секция кода.

Выполнение кода

После разбора вышеперечисленных секций и инициализации ВМ у нас остается одна секция с кодом. В моей ВМ выполняется не выровненный байткод, т.е. инструкции могут быть произвольной длины.

Набор опкодов — инструкций для виртуальной машины с небольшими комментариями я показываю заранее ниже:

type TComand = ( <** for stack **>bcPH, // [top] = [var] bcPK, // [var] = [top] bcPP, // pop bcSDP, // stkdrop bcSWP, // [top] [top-1] <** jump's **>bcJP, // jump [top] bcJZ, // [top] == 0 ? jp [top-1] bcJN, // [top] <> 0 ? jp [top-1] bcJC, // jp [top] & push callback point as ip+1 bcJR, // jp to last callback point & rem last callback point <** for untyped's **>bcEQ, // [top] == [top-1] ? [top] = 1 : [top] = 0 bcBG, // [top] > [top-1] ? [top] = 1 : [top] = 0 bcBE, // [top] >= [top-1] ? [top] = 1 : [top] = 0 bcNOT, // [top] = ![top] bcAND, // [top] = [top] and [top-1] bcOR, // [top] = [top] or [top-1] bcXOR, // [top] = [top] xor [top-1] bcSHR, // [top] = [top] shr [top-1] bcSHL, // [top] = [top] shl [top-1] bcNEG, // [top] = -[top] bcINC, // [top]++ bcDEC, // [top]-- bcADD, // [top] = [top] + [top-1] bcSUB, // [top] = [top] - [top-1] bcMUL, // [top] = [top] * [top-1] bcDIV, // [top] = [top] / [top-1] bcMOD, // [top] = [top] % [top-1] bcIDIV, // [top] = [top] \ [top-1] bcMV, // [top]^ = [top-1]^ bcMVBP, // [top]^^ = [top-1]^ bcGVBP, // [top]^ = [top-1]^^ bcMVP, // [top]^ = [top-1] <** memory operation's **>bcMS, // memory map size = [top] bcNW, // [top] = @new bcMC, // copy [top] bcMD, // double [top] bcRM, // rem @[top] bcNA, // [top] = @new array[ [top] ] of pointer bcTF, // [top] = typeof( [top] ) bcSF, // [top] = sizeof( [top] ) <** array's **>bcAL, // length( [top] as array ) bcSL, // setlength( [top] as array, ) bcPA, // push ([top] as array)[top-1] bcSA, // peek [top-2] -> ([top] as array)[top-1] <** memory grabber **>bcGPM, // add pointer to TMem to grabber task-list bcGC, // run grabber <** constant's **>bcPHC, // push copy of const bcPHCP, // push pointer to original const <** external call's **>bcPHEXMP, // push pointer to external method bcINV, // call external method bcINVBP, // call external method by pointer [top] <** for thread's **>bcPHN, // push null bcCTHR, // [top] = thread(method = [top], arg = [top+1]):id bcSTHR, // suspendthread(id = [top]) bcRTHR, // resumethread(id = [top]) bcTTHR, // terminatethread(id = [top]) <** for try..catch..finally block's **>bcTR, // try @block_catch = [top], @block_end = [top+1] bcTRS, // success exit from try/catch block bcTRR, // raise exception, message = [top] <** for string's **>bcSTRD, // strdel bcCHORD, bcORDCH, <** [!] directly memory operations **>bcALLC, //alloc memory bcRALLC, //realloc memory bcDISP, //dispose memory bcGTB, //get byte bcSTB, //set byte bcCBP, //mem copy bcRWBP, //read word bcWWBP, //write word bcRIBP, //read int bcWIBP, //write int bcRFBP, //read float bcWFBP, //write float bcRSBP, //read string bcWSBP, //write string bcTHREXT,//stop code execution bcDBP //debug method call ); 

Итак, вы бегло ознакомились с тем, какие операции может выполнять написанная мной ВМ. Теперь хочется сказать о том, как это все работает.

ВМ реализована как object, благодаря чему можно без проблем реализовать поддержку многопоточности.

Имеет указатель на массив с опкодами, IP (Instruction Pointer) — смещение выполняемой инструкции и указатели на прочие структуры ВМ.

Выполнение кода идет большим switch-case.

Просто приведу описание ВМ:

type TSVM = object public ip, end_ip: TInstructionPointer; mainclasspath: string; mem: PMemory; stack: TStack; cbstack: TCallBackStack; bytes: PByteArr; grabber: TGrabber; consts: PConstSection; extern_methods: PImportSection; try_blocks: TTRBlocks; procedure Run; procedure RunThread; procedure LoadByteCodeFromFile(fn: string); procedure LoadByteCodeFromArray(b: TByteArr); end; 

Немного об обработке исключений

Для этого в ВМ есть стек обработчиков исключений и большой try/catch блок, в который завернуто выполнение кода. С стек можно положить структуру, которая имеет смещение точек входа на catch и finally/end блока обработки исключений. Также я предусмотрел опкод trs, который ставится перед catch и перебрасывает код на finally/end, если он выполнился успешно, попутно удаляя блок с информацией об обработчиках исключений с вершины соответствующего стека. Просто? Просто. Удобно? Удобно.

Поговорим о внешних методах и библиотеках

Я уже упоминал о них ранее. Импорты, библиотеки… Без них язык не будет обладать желаемой гибкостью и функционалом.

Первым делом в реализации ВМ объявим тип внешнего метода и протокол его вызова.

type TExternalFunction = procedure(PStack: pointer); cdecl; PExternalFunction = ^TExternalFunction; 

Парсер секции импорта заполняет при ицициализации ВМ массив указателей на внешние методы. Следовательно каждый метод имеет статичный адрес, который вычисляется на этапе сборке приложения под ВМ и по которому может быть вызван нужный метод.

Вызов в дальнейшем происходит таким вот образом в процессе выполнения кода:

TExternalFunction(self.extern_methods^.GetFunc(TSVMMem(self.stack.popv).GetW))(@self.stack); 

Напишем простую библиотеку для нашей ВМ

И пусть она будет реализовывать для начала метод Sleep:

library bf;  uses SysUtils, svm_api in '..\svm_api.pas'; procedure DSleep(Stack:PStack); cdecl; begin sleep(TSVMMem(Stack^.popv).GetW); end; exports DSleep name 'SLEEP'; end. 

Итоги

На этом я пожалуй закончу свою первую статью из задуманного цикла.

Сегодня я довольно подробно описал создание среды выполнения языка. Считаю, что данная статья будет очень полезна людям, которые решат попробовать написать свой ЯП или же разобраться с тем, как работают подобные языки программирования.

Полный код ВМ доступен в репозитории, в ветке /runtime/svm.

Если вам понравилась эта статья, то не ленитесь закинуть плюс в карму и поднять её в топе, я старался и буду стараться для вас.

Если вам что-то непонятно — то добро пожаловать в комментарии или на форум.

Возможно ваши вопросы и ответы на них будут интересны не только вам.

• разработка языков программирования
• разработка стековой вм
• новый язык программирования
• обучающий материал
• архитектура виртуальных машин
• абстракции

• Высокая производительность
• Open source
• Виртуализация
• Софт
• Мозг

Как создать свой язык программирования: теория, инструменты и советы от практика

На протяжении последних шести месяцев я работал над созданием языка программирования (ЯП) под названием Pinecone. Я не рискну назвать его законченным, но использовать его уже можно — он содержит для этого достаточно элементов, таких как переменные, функции и пользовательские структуры данных. Если хотите ознакомиться с ним перед прочтением, предлагаю посетить официальную страницу и репозиторий на GitHub.

Введение

Я не эксперт. Когда я начал работу над этим проектом, я понятия не имел, что делаю, и всё еще не имею. Я никогда целенаправленно не изучал принципы создания языка — только прочитал некоторые материалы в Сети и даже в них не нашёл для себя почти ничего полезного.

Тем не менее, я написал абсолютно новый язык. И он работает. Наверное, я что-то делаю правильно.

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

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

Первые шаги

«А с чего вообще начинать?» — вопрос, который другие разработчики часто задают, узнав, что я пишу свой язык. В этой части постараюсь подробно на него ответить.

Компилируемый или интерпретируемый?

Компилятор анализирует программу целиком, превращает её в машинный код и сохраняет для последующего выполнения. Интерпретатор же разбирает и выполняет программу построчно в режиме реального времени.

Технически любой язык можно как компилировать, так и интерпретировать. Но для каждого языка один из методов подходит больше, чем другой, и выбор парадигмы на ранних этапах определяет дальнейшее проектирование. В общем смысле интерпретация отличается гибкостью, а компиляция обеспечивает высокую производительность, но это лишь верхушка крайне сложной темы.

Я хотел создать простой и при этом производительный язык, каких немного, поэтому с самого начала решил сделать Pinecone компилируемым. Тем не менее, интерпретатор у Pinecone тоже есть — первое время запуск был возможен только с его помощью, позже объясню, почему.

Выбор языка

Своеобразный мета-шаг: язык программирования сам является программой, которую надо написать на каком-то языке. Я выбрал C++ из-за производительности, большого набора функциональных возможностей, и просто потому что он мне нравится.

Но в целом совет можно дать такой:

• интерпретируемый ЯП крайне рекомендуется писать на компилируемом ЯП (C, C++, Swift). Иначе потери производительности будут расти как снежный ком, пока мета-интерпретатор интерпретирует ваш интерпретатор;
• компилируемый ЯП можно писать на интерпретируемом ЯП (Python, JS). Возрастёт время компиляции, но не время выполнения программы.

Проектирование архитектуры

У структуры языка программирования есть несколько ступеней от исходного кода до исполняемого файла, на каждой из которых определенным образом происходит форматирование данных, а также функции для перехода между этими ступенями. Поговорим об этом подробнее.

Лексический анализатор / лексер

Первый шаг в большинстве ЯП — это лексический анализ. Говоря по-простому, он представляет собой разбиение текста на токены, то есть единицы языка: переменные, названия функций (идентификаторы), операторы, числа. Таким образом, подав лексеру на вход строку с исходным кодом, мы получим на выходе список всех токенов, которые в ней содержатся.

Обращения к исходному коду уже не будет происходить на следующих этапах, поэтому лексер должен выдать всю необходимую для них информацию.

Flex

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

Одним из основных таких инструментов является Flex — генератор лексических анализаторов. Он принимает на вход файл с описанием грамматики языка, а потом создаёт программу на C, которая в свою очередь анализирует строку и выдаёт нужный результат.

Моё решение

Я решил оставить написанный мной анализатор. Особых преимуществ у Flex я в итоге не увидел, а его использование только создало бы дополнительные зависимости, усложняющие процесс сборки. К тому же, мой выбор обеспечивает больше гибкости — например, можно добавить к языку оператор без необходимости редактировать несколько файлов.

Синтаксический анализатор / парсер

Следующая стадия — парсер. Он преобразует исходный текст, то есть список токенов (с учётом скобок и порядка операций), в абстрактное синтаксическое дерево, которое позволяет структурно представить правила создаваемого языка. Сам по себе процесс можно назвать простым, но с увеличением количества языковых конструкций он сильно усложняется.

Bison

На этом шаге я также думал использовать стороннюю библиотеку, рассматривая Bison для генерации синтаксического анализатора. Он во многом похож на Flex — пользовательский файл с синтаксическими правилами структурируется с помощью программы на языке C. Но я снова отказался от средств автоматизации.

Преимущества кастомных программ

С лексером моё решение писать и использовать свой код (длиной около 200 строк) было довольно очевидным: я люблю задачки, а эта к тому же относительно тривиальная. С парсером другая история: сейчас длина кода для него — 750 строк, и это уже третья попытка (первые две были просто ужасны).

Тем не менее, я решил делать парсер сам. Вот основные причины:

• минимизация переключения контекста;
• упрощение сборки;
• желание справиться с задачей самостоятельно.

В целесообразности решения меня убедило высказывание Уолтера Брайта (создателя языка D) в одной из его статей:

Абстрактный семантический граф

В этой части я реализовал структуру, по своей сути наиболее близкую к «промежуточному представлению» (intermediate representation) в LLVM. Существует небольшая, но важная разница между абстрактным синтаксическим деревом (АСД) и абстрактным семантическим графом (АСГ).

АСГ vs АСД

Грубо говоря, семантический граф — это синтаксическое дерево с контекстом. То есть, он содержит информацию наподобие какой тип возвращает функция или в каких местах используется одна и та же переменная. Из-за того, что графу нужно распознать и запомнить весь этот контекст, коду, который его генерирует, необходима поддержка в виде множества различных поясняющих таблиц.

Запуск

После того, как граф составлен, запуск программы становится довольно простой задачей. Каждый узел содержит реализацию функции, которая получает некоторые данные на вход, делает то, что запрограммировано (включая возможный вызов вспомогательных функций), и возвращает результат. Это — интерпретатор в действии.

Варианты компиляции

Вы, наверное, спросите, откуда взялся интерпретатор, если я изначально определил Pinecone как компилируемый язык. Дело в том, что компиляция гораздо сложнее, чем интерпретация — я уже упоминал ранее, что столкнулся с некоторыми проблемами на этом шаге.

Написать свой компилятор

Сначала мне понравилась эта мысль — я люблю делать вещи сам, к тому же давно хотел изучить язык ассемблера. Вот только создать с нуля кроссплатформенный компилятор — сложнее, чем написать машинный код для каждого элемента языка. Я счёл эту идею абсолютно не практичной и не стоящей затраченных ресурсов.

LLVM

LLVM — это коллекция инструментов для компиляции, которой пользуются, например, разработчики Swift, Rust и Clang. Я решил остановиться на этом варианте, но опять не рассчитал сложности задачи, которую перед собой поставил. Для меня проблемой оказалось не освоение ассемблера, а работа с огромной многосоставной библиотекой.

Транспайлинг

Мне всё же нужно было какое-то решение, поэтому я написал то, что точно будет работать: транспайлер (transpiler) из Pinecone в C++ — он производит компиляцию по типу «исходный код в исходный код», а также добавил возможность автоматической компиляции вывода с GCC. Такой способ не является ни масштабируемым, ни кроссплатформенным, но на данный момент хотя бы работает почти для всех программ на Pinecone, это уже хорошо.

Дальнейшие планы

Сейчас мне не достаёт необходимой практики, но в будущем я собираюсь от начала и до конца реализовать компилятор Pinecone с помощью LLVM — инструмент мне нравится и руководства к нему хорошие. Пока что интерпретатора хватает для примитивных программ, а транспайлер справляется с более сложными.

Заключение

Надеюсь, эта статья окажется кому-нибудь полезной. Я крайне рекомендую хотя бы попробовать написать свой язык, несмотря на то, что придётся разбираться во множестве деталей реализации — это обучающий, развивающий и просто интересный эксперимент.

Вот общие советы от меня (разумеется, довольно субъективные):

• если у вас нет предпочтений и вы сомневаетесь, компилируемый или интерпретируемый писать язык, выбирайте второе. Интерпретируемые языки обычно проще проектировать, собирать и учить;
• с лексерами и парсерами делайте, что хотите. Использование средств автоматизации зависит от вашего желания, опыта и конкретной ситуации;
• если вы не готовы / не хотите тратить время и силы (много времени и сил) на придумывание собственной стратегии разработки ЯП, следуйте цепочке действий, описанной в этой статье. Я вложил в неё много усилий и она работает;
• опять же, если не хватает времени / мотивации / опыта / желания или ещё чего-нибудь для написания классического ЯП, попробуйте написать эзотерический, типа Brainfuck. (Советуем помнить, что если язык написан развлечения ради, это не значит, что писать его — тоже сплошное развлечение. — прим. перев.)

Я делал довольно много ошибок по ходу разработки, но большую часть кода, на которую они могли повлиять, я уже переписал. Язык сейчас неплохо функционирует и будет развиваться (на момент написания статьи его можно было собрать на Linux и с переменным успехом на macOS, но не на Windows).

О том, что ввязался в историю с созданием Pinecone, ни в коем случае не жалею — это отличный эксперимент, и он только начался.

Must read. 5 статей о том, как создать свой язык программирования

Что Гвидо ван Россум думает о Julia и Go, какие книги о создании языков рекомендует комьюнити и 12 самых крутых фич языков программирования.

Мария Грегуш

В бэкграунде — программирование, французский язык, академическое рисование, капоэйра. Сейчас учит финский. Любит путешествия и Балтийское море.

Каждую неделю мы отбираем несколько интересных материалов по одной теме из англоязычного интернета и рассказываем, почему их обязательно надо прочитать. В этом выпуске — теория языков программирования и советы о том, как создать собственный.

Как вкатиться в тему?

Где читать: обсуждение на Reddit.

Зачем читать: чтобы не утонуть в море информации о том, как устроены языки, и разобраться с базовыми знаниями.

Топикстартер спросил, с чего лучше начать создание собственного языка программирования. В первую очередь ему порекомендовали узнать побольше о трёх важных блоках:

1. Лексический анализ (токенизация) — процесс, который разделяет входные данные на отдельные части, то есть токены.
2. Синтаксический анализ (парсинг) — создание дерева абстрактного синтаксиса с помощью тех самых токенов.
3. Кодогенерация — процесс создания кода. Код обычно создаётся рекурсивно, с помощью дерева абстрактного синтаксиса.

Кроме того, дали несколько советов:

• вникнуть в историю создания других языков (например, по «Википедии»);
• изучить сайт с руководством по созданию языка программирования;
• присмотреться к книге Альфреда Ахо и Джеффри Ульмана Principles of Compiler Design, в которой разобран процесс создания компилятора.

В оригинальном посте советы более подробные — есть и ссылки на источники, и длинные текстовые сообщения с толковой информацией.

Что почитать по теории языков?

Где читать: обсуждение на Reddit.

Зачем читать: чтобы найти книги по теории программирования для начинающих.

В другом обсуждении на Reddit участники сообщества собрали классные рекомендации книг, в которых не слишком сложным языком описаны основы теории языков программирования.

• «Типы в языках программирования» Бенджамина Пирса: хорошее введение в теорию, которое советуют многие. В отличие от остальных книг, она переведена на русский язык. Правда, Пирс написал её в 2002 году, поэтому она не освещает ряд актуальных тем.
• Practical Foundations for Programming Languages («Практические основы языков программирования») Роберта Харпера. Эту книгу советуют читать уже после Пирса: в ней разобраны более подробные детали и для новичка она может быть сложновата.
• Concepts in Programming Languages («Концепты в языках программирования») Джона Митчелла — книга рассказывает о традиционных парадигмах программирования и больше сосредоточена на практике, а не на теории.
• Programming Languages: Application and Interpretation — книга бесплатна и доступна онлайн.

Кроме того один из комментаторов упомянул интересный сайт, на котором собрано огромное количество книг, видео и прочих материалов по самым разным темам, связанным с теорией языков программирования.

Самые классные фичи языков программирования

Где читать: в блоге The Renegade Coder.

Зачем читать: чтобы узнать об интересных фичах языков и понять, что бы вы хотели видеть в своём идеальном языке.

Джереми Грифски изучил почти 50 языков программирования и сделал список самых классных и необычных наворотов. Интересная особенность статьи — она постоянно обновляется. Пока в статье 12 пунктов, вот некоторые из них:

• Макросы (макрокоманды) — функция метапрограммирования, которая позволяет менять язык, добавляя собственные правила в дерево абстрактного синтаксиса.
• Лямбда-выражения — они похожи на анонимные функции, только лямбда-выражения можно использовать в качестве данных. Например, с их помощью можно сделать так, чтобы функция в качестве результата возвращала… функцию.
• Последовательная типизация — совмещает в себе элементы статической и динамической типизаций. Она позволяет определять, когда типизация будет статической, хотя по умолчанию использует динамическую типизацию.
• Инлайн (встроенное) тестирование — в языке Pyret, например, тестирование встроено в сам синтаксис языка, а тесты запускаются вместе с кодом. Благодаря этому вы никогда не забудете о них.

На каком языке писать свой язык программирования?

Где читать: обсуждение на Quora.

Зачем читать: чтобы получше разобраться в особенностях создания языков программирования.

Недавно на Quora появился вопрос — какой язык выбрать для того, чтобы создать свой язык программирования. Вот что ответили автору вопроса:

1. Вопрос некорректен: сами языки программирования не пишут на других языках. Они пишутся на так называемых метаязыках, которые описывают правила и синтаксис. Пример метаязыка — БНФ (Формула Бэкуса — Наура).
2. Зато на других языках пишут компиляторы. Для этого можно использовать любой язык общего назначения, однако чаще всего рекомендуют C, на котором написаны компиляторы Java, Python, PHP, JavaScript.

Кроме того, в обсуждении посоветовали много классных инструментов для создания языков.

Интервью с создателем Python. Что он думает о других языках?

Где смотреть: запись прямого эфира на YouTube.

Зачем смотреть: чтобы узнать немного об истории создания Python, планах на будущее и отношении Гвидо ван Россума к другим языкам.

Создатель Python ещё в мае дал интервью Microsoft. Он рассказал, что думает о Rust, Go, Julia и TypeScript.

• Rust, по его мнению, — отличный язык для своих целей. Ван Россум также отметил, что в Rust неплохо решена проблема с аллокацией памяти — в отличие от того же С++.
• Язык Go он назвал «самым питонистым» языком общего назначения.
• Julia, по мнению Гвидо, тоже напоминает Python — но с некоторыми отличиями. Поэтому он не советует программировать на Python и Julia в один день. Сравнивая эти два языка, Гвидо сказал, что в своей нише Julia явно выигрывает, зато сфера её применения не такая широкая.
• TypeScript тоже получил высокую оценку мэтра. Ван Россум признался, что Python нередко вдохновляется TypeScript, хотя и отметил, что TypeScript тоже учится у Python.

Гвидо также рассказал об истории создания Python, переходе с Python 2 на 3 и о том, планируется ли выход Python 4.

Хотите в будущем создать свой язык программирования? Начните с курсов из раздела «Программирование» на сайте Skillbox — возможно, среди них уже есть ваш идеальный язык.