Пишем свой язык программирования без мам, пап и бизонов. Часть 0: теория
Тема написания своего ЯПа не дает мне покоя уже около полугода. Я не ставил перед собой цель «убить» CoffeeScript, TypeScript, ELM, тысячи их, я просто хотел понять кухню и как они вообще пишутся.
К моему неприятному удивлению, большинство из этих языков используют Jison (Bison для JavaScript), а это не совсем попадало под мою задачу — «понять», так как по сути дела Jison делает все за вас, собирает AST по заданным вами правилам (Jison как таковой отличный инструмент, который делает за вас львиную долю работы, но сейчас не о нем).
В конечном итоге я методом проб и ошибок (а если сказать точнее, чтения статей и реверс инжиниринга) научился писать свои полноценные языки программирования от разбития исходного текста на лексемы до его трансляции в JS код.
Стоит заметить, что данное руководство не привязано к JavaScript, он выбран исключительно из соображений скорости разработки и читаемости, так что вы можете написать свой «лисп»/»питон»/»ваш абсолютно новый синтаксис» на любом знакомом вам языке.
Также до момента написании компилятора (в нашем случае транслятора), процесс написания языка не отличается от процессов создания языков компилируемых в ASM/JVM bitcode/LLVM bitcode/etc, а это значит, что данное руководство не ограничивается созданием языка трансляцируемого в JavaScript.
Весь код, который будет написан в данной (и последующих статьях), лежит на Github’е. Тегами обозначены начало и концы статей для удобства.
Немного теории
Не углубляясь в википедийность, процесс трансляции исходного кода в конечный JS код протекает следующим образом:
Что тут происходит:
1) Lexer
Исходный код нашей программы разбивается на лексемы. По-простому это нахождение в исходном тексте ключевых слов, литералов, символов, идентификаторов и т.д.
Т.е. на выходе из этого (CoffeeScript):
Мы получаем это (сокращенная запись):
Так-как CoffeeScript отступо-чувствительный и не имеет явного выделения блока скобками < и >, блоки отделяются отступами ( INDENT ом и OUTDENT ом), которые по сути заменяет скобки.
2) Parser
Парсер составляет AST из токенов (лексем). Он обходит весь массив и рекурсивно подбирает подходящие паттерны, основываясь на типи токена или их последовательности.
Из полученных токенов в пункте 1, parser составит, примерно такое дерево (сокращенная запись):
Не стоит пугаться объема дерева, на деле он генерируется рекурсивно и его создание не вызывает трудностей.
3) Compiler
Построение конечного кода по AST. Этот пункт можно заменить на компиляцию в байткод, или даже рантайм, но в рамках данной серии статей мы рассмотрим реализацию транслятора в другой язык программирования.
Компилятор (читай транслятор) преобразует Абстрактно-Синтаксическое Дерево в JavaScript код:
Вот и все. Большинство компиляторов работают именно по такому принципу (с незначительными изменениями. Иногда добавляют процесс стримминга исходного текста в поток символов, иногда напротив объединяют парсинг и компиляцию в один этап, но не нам их судить).
Habrlang
Итак, разобравшись с теорией, нам предстоит собрать свой язык программирования, у которого будет примерно следующий синтаксис (что-бы не особо париться, мы будем делать смесь из Ruby, Python и CoffeeScript):
В следующей главе вы реализуем все основные классы нашего транслятора, и научим его транслировать комментарии Habrlang‘а в JavaScript.
Creating a Programming Language: Part 1 – The Lexer
In this series of posts I will walk you through creating your own programming language using JavaScript.
There are so many programming languages out there – hundreds, possibly thousands of different ways to write the same piece of code. Some are good for one thing, some are good for another, some are good for nothing at all. But have you ever wondered how those programming languages were made? That’s what I’ll teach you in this series of posts.
It should be noted that this not a great way to create a practical programming language. This series serves solely to demonstrate the concepts behind programming languages, but if you wish to build a programming language to actually use for your projects, I highly recommend you look into tools like llvm and yacc
Compiler vs. Interpreter
There are two mainstream ways to make programming languages: Compilers and Interpreters.
A compiler compiles a program ahead of time so that the computer can run it on it’s own. An example of a compiled language would be C.
An interpreter executes a program on the fly. Examples of this are javascript and python. For the sake of simplicity, this series will focus only on making an interpreted language.
Parts of an interpreter
When you run your program, the interpreter doesn’t execute it right away. There are a few things the interpreter does to prepare the program for execution. Let’s talk about those:
1. The Lexer
The lexer will be the focus of this tutorial. It takes your code and converts it into a list of something called "tokens". These tokens each have a type and a value.
2. The Parser
The parser takes the tokens and creates something called an "Abstract Syntax Tree", or "AST". The AST tells the interpreter what tokens belong together, and how. We’ll discuss this in more detail in the next post.
Execution
Once all these steps have run, the code will be executed. How exactly this works will also receive a dedicated post
Setting up our workspace
For this project, create a new folder whereever you store your projects. I have a folder called projects on my desktop. I called my project folder my-programming-language . Open your folder in VSCode or whatever IDE you use. Open up the integrated terminal.
In the terminal type the following commands:
Then, create a file, index.js . This will be the entry point for our program. In it, paste the following:
This program will infinitely prompt you for a command, run the lexer and print the results. However, this will not work at all until we start coding our lexer, so don’t be surprised if you receive an error.
The Token class
Now, let’s start working on our lexer. First, create a new folder in your project called lexer . In that folder, create a new file, token.js
In this file, create an empty class called Token :
Now, we add a constructor that takes a type and value and stores them:
And finally, add a method called toString() that stringifies the token in the form of <TYPE:VALUE> and export the class:
And that’s our token class, done!
Creating the actual Lexer
This part might get a little bit complicated, but bear with me here.
First, we create a new file in the lexer folder called index.js . This is where the main Lexer code will go. Into this file, paste the following code:
Each entry in this object represents a token type. The key (left of the : ) is the name of the type, the value (right of the : ) is a regex that explains to the lexer how to check whether a piece of text is equivalent to that token type or not.
Next, create a method called createTokens and export it so other files can access it. This method will run the lexer on a piece of code. (For now, our lexer will only be able to process simple mathematical expressions, but that will change later).
Below the createTokens method, add an empty class called Lexer .
In the Lexer class, add a constructor that takes in a string of code and a map of token types:
Representing postitions
This might not make sense now, but it will become important later to keep track of positions. For this, we will create a class called position. It stores a copy of the code, the current line, column and absolute index in the code. This class will be located in a file called pos.js in the project folder
Back to the lexer
In the Lexer constructor, initialize a position and add a method to advance by n characters:
Now, in the Lexer class, add a method called createTokens . Inside it, intialize an empty array of tokens.
In this method, loop until this.slice is falsy, e.g. There is no more code left over to work with:
In each iteration of this loop, we will iterate through the token types until we either find a token that matches the beginning of this.slice or run out of tokens, the latter of which means that the code is not valid and should result in an error.
Inside the loop, just below var token = null; , add the following code (it does exactly what I described above):
Also, at the top of the file, we need to import the Token class.
The lexer file should now look like this:
The lexer class is finished now, so let’s finally implement the createTokens method (not the one in the Lexer class). In the method, we create a lexer class, and run it:
Name already in use
writing-compiler-for-neophytes / tutorial / lexer.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
Теория компиляторов для неофитов
В этой лекции мы начнем изучать, как компилятор понимает, что написано в программе. Занимающаяся разбором исходного кода часть компилятора называется синтаксическим анализатором. Фундаментальная основа для работы синтакcического анализа заложена в теории формальных языков. В рамках этой теории язык задается с помощью формальной грамматики, которая позволяет получить все синтаксически верные исходные коды программ на рассматриваемом языке, и задает способ группировки слов языка в понятия.
Чтобы задать формальные язык, нужно сначала задать алфавит, т.е. множество всех символов, которые могут присутствовать в словах языка. В настоящее время в качестве множества символов предпочтительно использовать юникод, так как это значительно упрощает использование в программе разнообразных естественных языков. Формальных язык задается множеством всех слов, входящих в язык, причем под словом в данном случае подразумевается программа целиком. Количество слов в нетривиальном языке бесконечно, поэтому вместо перечисления всех слов используются конечный набор правил, по которым можно построить весь язык. В практическом плане удобно использовать правила максимально простого вида, вместо описания, например, на русском языке или на Java. Формальная грамматика задается правилами вида:
Строки что заменить и на что заменить состоят из букв алфавита, называемых терминалами, и из набора не входящих в алфавит символов, называемых нетерминалами. Среди нетерминалов выделяют особый, называемый стартовым символом. Вывод слов языка всегда начинается со строки, состоящей только из стартового символа. К этой строке начинают применяться правила формальной грамматике, причем каждое применение сводится замене подстроки, совпадающей с левой часть правила ( что заменить ) на строку из правой части правила ( на что заменить ). Важно отметить, что правила применяются в произвольном порядке и в любом количестве. Как только в результате применения правил грамматики получается строка целиком состоящая из терминалов, эта строка объявляется входящей в язык, причем все слова языка должны получаться таким образом.
Существует несколько уровней иерархии языков (см. иерархия Хомского) по сложности из разбора. Для задания программ на языках программирования почти всегда достаточно контекстно-свободных грамматик, т.е. грамматик, в левой части правил которых стоит один символ и он нетерминал. Символ в левой части часто выражает какое-то понятие, в этом случае правила объясняют, как понятие раскрывается через другие символы. Например, рассмотрим грамматику (воспользуемся для записи грамматики формой Бэкуса-Наура ) для десятичной записи целого числа:
В БНФ записи нетерминалы записываются в угловых скобках, символ | используется для перечисления вариантов замены левой части, и мы записываем правила для стартового символа первыми. Прочитать эту грамматику можно следующим образом: чтобы получить число нужно сначала написать знак, затем записать цифры. Знаком могут быть символы + и — или пустая строка. Цифры — это строка либо из одной цифры, либо из цифры, за которой идут другие цифры. Подробнее контекстно-свободные грамматики мы рассмотрим следующем уроке. Пока заметим, что правила для <цифры> имеют еще более специальный вид, чем диктуется контекстно-свободной грамматикой. Если все правила грамматики имеют один из двух видов:
то такая грамматика называется регулярной. Регулярные грамматики существенно проще контекстно-свободных, поэтому мы начнем изучение грамматик с регулярных. Регулярные грамматики используются достаточно широко, нас же будет интересовать конкретная задача: написание лексического анализатора.
Что делает лексический анализатор, и зачем нужен он нужен? Лексический анализатор выделяет в исходном коде программы лексемы, т.е. подстроки, которые с точки зрения последующего синтаксического анализа будут рассматриваться как один символ. Например, с точки зрения программы на C все числовые [литералы] (https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D1%82%D0%B5%D1%80%D0%B0%D0%BB_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)) ведут себя одним образом, не важно, какое конкретно числовое значение он имеет, поэтому числовое значение литерала восстанавливается на этапе лексического анализа, а последующий синтаксический анализ работает с числом, как с одним целым. Т.о. лексический анализатор преобразует цепочку символов алфавита программы (юникод) в цепочку лексем, где отдельные лексемы могут быть числом, идентификатором, оператором, комментарием и т.п. Как правило лексический анализатор выполняет разбор регулярного языка, а синтаксический анализатор — контекстно-свободного. Так как регулярная грамматика является также контекстно-свободной, то этап лексического анализа можно было бы опустить, однако использование лексического анализатора позволяет добиться двух вещей:
- Регулярная грамматика разбирается быстрее контекстно-свободной, т.е. использование лексера ускоряет работу компилятора.
- Сбор лексером нескольких символов в один позволяет уменьшить число символов для предпросмотра для синтаксического анализатора, что позволяет использовать меньше памяти или более простые анализаторы.
Для задания лексера необходимо указать перечень регулярных выражений и лексемы, которые будут выдаваться лексером, если регулярное выражение находится в исходном коде программы. Регулярное выражение является одним из способов задания регулярной грамматики. Регулярное выражение (часто сокращается до regexp) представляет собой последовательность символов, операторов + , * и ? , скобок ( , ) и регулярных выражений. С помощью формальной грамматики регулярное выражение можно определить следующим образом:
Скобки в регулярных выражениях служат только для выделения части выражения, к которой применяется оператор. В качестве операторов используются:
- + — повтор предшествующего оператору символа или группы один и более раз;
- * — повтор ноль и более раз;
- ? — предшествующее выражение может встречаться один раз или отсутствовать.
В качестве примера рассмотрим выражение (+|-)?(0|1|2|3|4|5|6|7|8|9)+ , которому соответствуют десятичные представления целых чисел со знаком, контекстно-свободную грамматику для которых мы рассмотрели выше.
Почему регулярная грамматика считается особенно простой? Как построить регулярную грамматику, соответствующую регулярному выражению? Как проверить, удовлетворяет ли строка регулярному выражению? Попробуем ответить на эти вопросы.
Регулярная грамматика считается особенно простой, так как каждой регулярной грамматике однозначно соответствует конечный автомат, который позволяет максимально быстро генерировать слова и проверять принадлежность слова языку.
Конечным автоматом называют устройство, имеющее конечное число состояний, между которыми оно может делать переходы. Автомат задается своими состояниями и множеством разрешенных переходов. Первоначально автомат находится в стартовом состоянии, которое мы будем обозначать 0 . Часть состояний помечаются как остановочные состояния, попадая в эти состояния автомат имеет право завершить работу. Автомат для порождения языка при переходе может добавлять в конец слова одну букву. В начале работы автомата генерируемое слово не содержит ни одной буквы, при последующей работе автомата к слову приписываются буквы, создание слова прекратится в одном из остановочных состояний. Переходы без приписывания буквы будем называть эпсилон переходами.
Покажем, как построить конечный автомат, соответствующий регулярной грамматике. Заметим, что частично выведенная строка для регулярной грамматики вседа содержит только один нетерминал, расположенный в конце строки. В начале вывода строка состоит из одного стартового символа, поэтому предположение выполняется. Рассмотрим, что произойдет со строкой при применении двух возможных правил регулярной грамматики. При применении правила <нетерминал> ::= <терминал> <нетерминал> , нетерминал в конце строки заменяется на новый нетерминал и перед ним добавляется один терминал. При применении правила <нетерминал> ::= <терминал> нетерминал в конце строки заменяется на терминал, и вывод заканчивается. Т.о. все правила порождают только строки с нетерминалом в конце. Возьмем в качестве состояний автомата множество нетерминальных символов. Частично выведенная строка будет соответствовать состоянию автомата для нетерминала в конце строки. Тогда правила вида <A> ::= a <B> соответствует переходу из состояния <A> в состояние <B> с добавлением к слову символа a . Очевидно, что стартовым состоянием автомата будет состояние для стартового символа в грамматике. Правила вида <A> ::= a соответствуют переходу в остановочное состояние с дописыванием к слову буквы a . Это остановочное состояния не соответствует ни одному нетерминалу, а является новым состоянием, причем только это состояние является остановочным.
В качестве примера рассмотрим грамматику:
Ей соответствует автомат, имеющий два состояния <N> , соответствующее нетерминалу, и новое состояние <T> . Только состояние <T> будет остановочным. Два правила грамматики соответствуют двум возможным переходам автомата: правило <N> ::= 0 соответствует переходу из <N> в <T> с добавлением к слову буквы 0 , а правило <N> ::= 0 <N> соответствует переходу из <N> в себя с добавлением буквы 0 .
Легко видеть, что по данному конечному автомату без эпсилон переходов можно построить соответствующую ему регулярную грамматику. Таким образом мы заключаем, что между регулярными грамматиками и конечными автоматами есть взаимно-однозначное соответствие.
Пусть нам дан конечный автомат, проверим, можно ли с его помощью породить данное слово. Возьмем автомат из предыдущего примера и попробуем разобрать с его помощью слово 00 . Будем обозначать переход из <A> в <B> по символу a следующим образом: <A> (a) -> <B> . Тогда выходя из стартового состояния и делаю переходы по буквам слова 00 , получаем следующую цепочку переходов:
т.е. слово 00 порождается автоматом. Заметим, что из состояния <N> есть два перехода по символу 0 , один в состояние <N> , другой в <T> . Автомат, в котором из одного состояния есть несколько переходов по одному символу, называют недетерминированным. Наоборот, если каждый символ однозначно задает переход для всех состояний, то автомат называют детерминированным. Так как автомат из примера был недетерминированным, то у нас не было возможности сразу определить, что первый переход должен быть осуществлен в состояние <N> . Чтобы на практике проверить возможность вывода слова недетерминированным автоматом, мы должны отслеживать все состояния, которые можно достичь переходами по данным буквам. Например, в нашем примере достижимы следующие состояния:
Программная реализация детерминированного конечного автомата требует только одного обращения к таблице переходов на каждую прочитанную букву слова, что можно выразить в нескольких машинных инструкциях. Отслеживание списка всех достижимых состояний требует значительно больше ресурсов, поэтому на практике удобно переходить от недетерминированного автомата к детерминированному, что к счастью можно сделать всегда. Чтобы детерминировать автомат, нужно объявить множеством состояний нового автомата все множества состояний исходного автомата, например, для нашего автомата таких состояний три: <<N>>, <<N>, <T>>, <<T>>. Если между двумя состояниями исходно автомата возможен переход <A> (a) -> <B> , то в новом автомате разрешены переходы S (a) -> D , где множество состояний S содержит <A> , а множество D содержит <B> . Более того, множество D содержит только состояния, в которые можно попасть переходом по символу a из одного из состояний из множества S , Например, в исходном автомате из <N> есть два перехода по 0 в <N> и в <T> , следовательно в новом автомате из состояния <<N>>переход осуществляется в состояние <<N>, <T>>. Из этого состояния можно попасть в <N> по 0 , так как в исходном автомате был переход <N> (0) -> <N> , но также можно попасть в <T> по переходу <N> (0) -> <T> . Мы также должны учесть все переходы из <T> , однако таковых в нашем случае нет. Таким образом переход из состояния <<N>, <T>>по символу 0 переходит в себя. Состояние <<T>>оказалось недостижимо. Из <<T>>также нет ни одного перехода, так как их не было из <T> в недетерминированном автомате. Состояния <<N>, <T>>и <<T>>остановочные, так как содержат остановочное состояние <T> . Окончательно мы получили следующий детерминированный автомат:
Перейдем к изучению того, как построить конечный автомат для регулярного выражения. Регулярное выражение определено рекуррентно, поэтому будем последовательно определять, как строить сложные регулярные выражения из составных частей.
Простейшее регулярное выражение состоит из одного литерала a . Соответствующий конечный автомат имеет стартовое состояние <0> и одно остановочное состояние <1> , и один переход между ними: <0> (a) -> <1> .
Рассмотрим конкатенацию двух регулярных выражений, которым соответствуют два автомата. Автомат для конкатенации получается добавлением эпсилон переходов из всех терминальных состояний первого автомата в стартовое состояние второго, и заменой всех остановочных состояний первого автомата на неостановочные.
Автомат для двух регулярных выражений соединенных оператора объединения | из автоматов для этих выражений получается введением нового стартового состояния и добавлением к существующим переходам эпсилон переходов из стартового состояния в стартовые состояния исходных автоматов.
Чтобы получить автомат для оператора опции ? , достаточно добавить в автомат для регулярного выражения, к которому применяется оператор, эпсилон переход из стартового состояния в новое остановочное состояние, из которого больше нет переходов.
Чтобы получить автомат для оператора повтора + , достаточно добавить в автомат для регулярного выражения, к которому применяется оператор, эпсилон переходы из каждого остановочного состояния в стартовое.
Чтобы получить автомат для оператора повтора * , нужно сделать то же преобразование, что и для + , но дополнительно нужно добавить эпсилон переход из стартового состояния в новое терминальное, как для оператора ? .
Вернемся наконец к лексеру. Лексер должен выделить в потоке символов префикс, удовлетворяющий одному из регулярных выражений, и вернуть соответствующее регулярное выражение и префикс. Т.е. лексер пытается одновременно удовлетворить не по одному, а нескольким регулярным выражениям. Если бы мы хотели узнать, удовлетворяет ли префикс хотя бы одному регулярному выражению, то можно было бы проверять объединение этих регулярных выражений оператором | . Наша же цель не просто проверить, сработало ли какое-то регулярное выражение, а найти, какое именно сработало. Чтобы достигнуть этой цели мы должны остановочные состояния каждого регулярного выражения пометить, как принадлежащее этому выражению, после чего строить объединение. По маркировке остановочного состояния мы можем понять, какую из лексем удалось выделить.
Эпсилон переходы в конечном автомате нельзя непосредственно записать в виде правила регулярной грамматики, так как правила вида <A> ::= <B> не входят в канонический вид правил регулярной грамматики. Однако конечному автомату с эпсилон правилами все же можно сопоставить эквивалентную грамматику. Укажите, как это можно сделать?
Можно ли составить регулярное выражение для правильных скобочных последовательностей?
При достижении остановочного состояния автомат может прекратить работу, однако может и продолжить, если в нем есть переходы по следующей букве. Какой из вариантов предпочтительнее?
Регулярные выражения в духе PERL дают больше возможностей, чем мы допустили выше. Они позволяют указывать начало и конец строки, задавать символьные классы, указывать число повторов. Побробуйте добавить эти возможности в рассмотренную выше схему.
Написание лексера: алгоритм
Здравствуйте! Пишу лексер. Делаю так: считываю один символ из файла, смотрю, что за символ:
Но чтобы определить, ключевое ли это слово, приходится считать еще символы. Вижу, что это плохой способ. Как сделать это лучше?
Смотрите. Во-первых, вы не можете выяснить, найдено ли ключевое слово до тех пор, пока вы не просмотрите входящий текст до конца этого самого ключевого слова. Отсюда выплывает простой алгоритм: прочитать символы до конца слова, и поискать это слово в таблице ключевых слов.
Для поиска в таблице можно использовать простой перебор, и этого обычно достаточно, если ключевых слов разумное количество.
Но можно и сделать сложнее/эффективнее: применить алгоритм наподобие Ахо—Корасик, который эффективно умеет искать набор строк в тексте. (Для этого внутри строиться trie , префиксное дерево, о котором шло обсуждение недавно.)
Заметьте, что существует популярная утилита lex (и её open source-аналог flex ), которая делает именно это: по набору ключевых слов (а также регулярных выражений, так что lex более продвинутая штука) строит нужное поисковое дерево, и выдаёт вам исходный код на C, который нужно просто подключить к проекту.
Если задача состоит в том, чтобы сделать самопальный парсер, то хорошим началом будет такой метод. Нужно создать в памяти массив объектов, каждый из которых будет отвечать за распознавание определённого слова. После считывания очередного символа из входного потока этот символ по очереди «показывается» каждому из этих объектов. На что каждый из них может «отреагировать» тремя способами:
- Символ вообще не в струю. Если объект уже продвинулся в распознавании своего слова, то он сбрасывает состояние и пробует начать распознавание с начала.
- Символ более-менее в тему, хотя ещё не известно, будет ли в итоге полное слово. Объект меняет своё состояние, продвигаясь на один шаг вперёд по тому слову, которое он умеет распознавать.
- Символ успешно завершает то слово, которое начало распознаваться ранее. Объект как-то сообщает об успехе.
Всякий раз, когда происходит 3), состояние всех объектов нужно принудительно сбросить в начальное.
В принципе, ситуации 1) и 2) отличаются лишь тем, как меняется внутренее состояние распознающего объекта. С точки зрения внешнего цикла обе ситуации должны выглядеть одинаково: пока ничего не обнаружено, нужны ещё символы. Но для большей эффективности можно эти ситуации различать, передвигая в начало очереди те объекты, которые уже частично что-то распознали. Вероятность ситуации 3) для них выше, поэтому следующие символы лучше «показывать» в первую очередь им.