Давайте создадим интерпретатор Python с нуля
Теперь, когда мы выполнили синтаксический анализ арифметического выражения. Мы напишем парсер для операторов на языке программирования. Начнем с присвоения переменной. Как только вы узнаете, как выполнять синтаксический анализ одного оператора, остальные будут такими же.
Позвольте заявление
Мы используем операторы let для присваивания переменных. Его можно использовать только один раз, после чего мы можем продолжать обновлять значение с помощью оператора присваивания, который будет кратко обсуждаться позже. Мы можем резюмировать оператор let в следующей форме: let <identifier> = <expresssion>; . Здесь есть два значения, которые нас интересуют identifier и expresssion . Выражение, которое мы уже определили, немного изменим для накопления идентификатора. Идентификатор просто хранит имя переменной. Его можно представить ниже.
Storage — это диктофон, в котором мы храним все значения. Когда мы вызываем идентификатор в каком-либо выражении, мы читаем значение из dict. Если это не так, мы поднимем и исключение. Теперь, когда этот идентификатор убран, давайте объявим узел для оператора Let.
Здесь name , в котором хранится информация об идентификаторе. И value для выражения, которое дает значение. Теперь, когда узлы определены, нам нужно создать парсер в классе Parse .
Простой не так ли? Если текущий токен пуст, это идентификатор. Мы проверим это после проверки типа данных в выражении разбора.
Теперь мы можем определить идентификатор. Мы можем построить наш класс let поверх этого. Разбор грамматики — это прямой процесс. Если мы видим ключевое слово let , это указывает на то, что это оператор let. Затем мы переходим к следующему шагу и проверяем, следует ли за его идентификатором ( ID ) токен назначения ( ASSIGN ). В этом случае, если мы его найдем, мы продолжим поиск выражения, чтобы получить значение. В конце мы проверим, что в конце токен ( SEMICOLON ) существует.
Это оно. Если бы вы могли запомнить процесс, это было бы скорее громоздко, чем сложно. Однако наша работа еще не завершена. Как только переменная объявлена, нам нужно обновить ее с помощью оператора присваивания. Определим узел:
Узел похож на оператор let с одним отличием. Мы будем обновлять переменную только в том случае, если она уже определена с помощью let. Разбор оператора assign также полностью аналогичен, за исключением того, что мы не начинаем с let . Мы начинаем с узла Token.ID и возвращаем узел AssignStatement .
Выписки для печати
В нашем языке программирования есть два типа операторов печати: print и prinln . Формальный не добавляет новую строку в конце, в отличие от последнего. Давайте определим узел в операторах печати в nodes.py. Значение хранит информацию, которая должна быть сохранена. Пока состояние решает, выбираем ли мы print или println .
Наш оператор печати требует круглых скобок до и после выражения. Проверяем то же самое в его парсере.
Единственное, что расширяется, — это интеграция оператора Let и оператора Print в синтаксический анализатор. parse_statement — это функция, которая определяет, какой тип оператора мы создаем. Звучит сложно!. Не просто смотреть на код.
Мы помещаем анализатор арифметических выражений из последнего скрипта в parse_expression_statement , так что у нас может быть красивое выражение или в parse_statement .
Оценщик
Оценка является последним и последним шагом интерпретатора. Мы уже проделали тяжелую работу при создании парсера. Функция eval() , которую мы создали в каждом узле, автоматически обходит дерево. Все, что нам нужно сделать, это вызвать eval.
Мы уже создали REPL для запуска терминала и скрипт для чтения файла в предыдущих статьях. Я только что интегрировал его так, что он будет запускать интерпретатор, когда с терминала не будет указано имя файла. Когда файл задан, он будет анализировать файл.
В папке примера у нас есть файл с именем variable_declaration.nmi , который содержит следующий код.
Теперь момент истины.
вывод:
Неплохо. Но для строки отображается “ . Очевидно, будут и другие ошибки. Но мы справимся.
Introduction
After studying compilers and programming languages, I felt like internet tutorials and guides are way too complex for beginners or are missing some important parts about these topics.
My goal with this post is to help people that are seeking a way to start developing their first programming language/compiler.
Requirements
On this guide, I’ll be using PLY as lexer and parser, and LLVMlite as low level intermediate language to do code generation with optimizations (if you don’t know what I’m talking about, don’t worry, I’ll explain it later).
So, the requirements for this project are:
-
(way simpler to install LLVMlite through conda than pip)
- LLVMlite
- RPLY (same as PLY but with a better API)
-
(LLVM static compiler) (or other linking tool)
Getting Started
“Where to begin?”. This is the most common question when trying to create your programming language.
I’ll start by defining my own language. Let’s call it TOY, here’s a simple example of a TOY program:
Although this example is really simple, it is not so easy to be implemented as a programming language. So let’s start with a simpler example:
But how do you formally describe a language grammar? It is way to hard to create all possible examples of a language to show everything it can do.
To do this, we do what is called an EBNF. It is a metalanguage to define with one document, all possible grammar structures of a language. You can find most programming languages EBNFs easily.
To understand better how a EBNF grammar works, I recommend reading this post.
Let’s create a EBNF that describes the minimal possible functionality of TOY, only a sum operation. It will describe the following example:
It’s EBNF can be described as:
This example is way too simple to be useful as a programming language, so let’s add some functionalities. The first one, is to be able to add as many numbers as you want, and the second one, is to to be able to subtract numbers as well.
Here’s an example of our new programming language:
And it’s EBNF can be described as:
And finally, adding print to our programming language:
We get to this EBNF:
Now that we’ve defined our grammar, how do we translate it to code? So we can validate and understand a program? And after that, how can we compile it to a binary executable?
Compiler
A compiler is a program that turns a programming language into machine language or other languages. In this guide, I’m going to compile our programming language into LLVM IR and then into machine language.
Using LLVM, it is possible to optimize your compilation without learning compiling optimization, and LLVM has a really good library to work with compilers.
Our compiler can be divided into three components:
- Lexer
- Parser
- Code Generator
For the Lexer and Parser we’ll be using RPLY, really similar to PLY: a Python library with lexical and parsing tools, but with a better API. And for the Code Generator, we’ll use LLVMlite, a Python library for binding LLVM components.
Lexer
The first component of our compiler is the Lexer. It’s role is to take the program as input and divide it into Tokens.
We use the minimal structures from our EBNF to define our tokens. For example, with the following input:
Our Lexer would divide this string into this list of tokens:
So, let’s start coding our compiler. First, create a file named lexer.py . We’ll define our tokens on this file. We’ll only use LexerGenerator class from RPLY to create our Lexer.
After this, create your main file named main.py . We’ll combine all three compiler components on this file.
If you run $ python main.py , the output of tokens will be the same as described above. You can change the name of your tokens if you want, but I recommend keeping the same to keep consistency with the Parser.
Parser
The second component in our compiler is the Parser. It’s role is to do a syntax check of the program. It takes the list of tokens as input and create an AST as output. This concept is more complex than a list of tokens, so I highly recommend a little bit of research about Parsers and ASTs.
To implement our parser, we’ll use the structure created with out EBNF as model. Luckly, RPLY’s parser uses a format really similar to the EBNF to create it’s parser, so it is really straightforward.
The most challenging is to attach the Parser with the AST, but when you get the idea, it becomes really mechanical.
First, create a new file named ast.py . It will contain all classes that are going to be called on the parser and create the AST.
Second, we need to create the parser. For that, we’ll use ParserGenerator from RPLY. Create a file name parser.py:
And finally, we’ll update our file main.py to combine Parser with Lexer.
Now, if you run $ python main.py , you’ll see the output being the result of print(4 + 4 — 2) , which is equal to printing 6.
With these two components, we have a functional compiler that interprets TOY language with Python. However, it still doesn’t create a machine language code and is not well optimized. To do this, we’ll enter the most complex part of the guide, code generation with LLVM.
Code Generator
The third and last component of out compiler is the Code Generator. It’s role is to transform the AST created from the parser into machine language or an IR. In this case, it’s going to transform the AST into LLVM IR.
This component is the main reason why I’m writing this post. There aren’t good guides on how to implement code generation with LLVM on Python.
LLVM can be really complex to understand, so if you wish to fully understand what is going on, I recommend reading LLVMlite docs.
LLVMlite doesn’t have a implementation to a print function, so you have to define your own.
So, to start, let’s create a file named codegen.py that will contain the class CodeGen . This class is responsible to configure LLVM and create and save the IR code. We also declare the Print function on it.
After this, let’s update our main.py file to call CodeGen methods:
As you can see, I removed the input program from this file and created a new file called input.toy to simulate a external program. It’s content is the same as the input described.
Another change that was made is passing module , builder and printf objects to the Parser. This was made so we could pass this objects to the AST, where the LLVM AST is created. So, we change parser.py to receive these objects and pass them to the AST.
And finally, and most important, we change the ast.py to receive these objects and create the LLVM AST using LLVMlite methods.
With these changes, our compiler is ready to transform a TOY program into an LLVM IR file output.ll . To compile this .ll file into a executable, we’ll use LLC to create a object file output.o , and finally, GCC (you could use other linking programs) to create the final executable file.
And you can finally run your executable file compiled from the initial program.
Next Steps
After this guide, I hope you can understand an EBNF and the three basic concepts of a compiler. With this knowledge, you now can create your own programming language and write a optimized compiler to it with Python. I encourage you to go further and add new elements to your language and compiler, here are some ideas:
- Statements
- Variables
- New Binary Operators ( Multiplication, Division)
- Unary Operators
- If Statement
- While Stametement
Feel free to send me any compiler projects. I’ll be happy to help you with anything.
You can contact me at marceloga1@al.insper.edu.br
Hope you all enjoyed this post and got some love to programming languages and compilers!
More from Journal
There are many Black creators doing incredible work in Tech. This collection of resources shines a light on some of us:
Простой интерпретатор с нуля на Python (перевод) #1
Вещь, которая привлекла меня изучать компьютерную науку была компилятором. Я думал, что это все магия, как они могут читать даже мой плохо написанный код и компилировать его. Когда я прошел курс компиляторов, я стал находить этот процесс очень простым и понятным.
Сущность языка IMP
Прежде всего, давайте обсудим, для чего мы будем писать интерпретатор. IMP есть нереально простой язык со следующими конструкциями:
Присвоения (все переменные являются глобальные и принимают только integer):
Составные операторы (разделенные ;):
Это всего-лишь игрушечный язык. Но вы можете расширить его до уровня полезности как у Python или Lua. Я лишь хотел сохранить его настолько простым, насколько смогу.
А вот тут пример программы, которая вычисляет факториал:
Язык IMP не умеет читать входные данные (input), т.е. в начале программы нужно создать все нужные переменные и присвоить им значения. Также, язык не умеет выводить что-либо: интерпретатор выведет результат в конце.
Структура интерпретатора
Ядро интерпретатора является ничем иным, как промежуточным представлением (intermediate representation, IR). Оно будет представлять наши IMP-программы в памяти. Так как IMP простой как 3 рубля, IR будет напрямую соответствовать синтаксису языка; мы создадим по классу для каждой единицы синтаксиса. Конечно, в более сложном языке вы хотели бы использовать еще и семантическую представление, которое намного легче для анализа или исполнения.
- Разобрать символы исходного кода на токены.
- Собрать все токены в абстрактное синтаксическое дерево (abstract syntax tree, AST). AST и есть наша IR.
- Исполнить AST и вывести результат в конце.
Процессом разделения символов на токены называется лексинг (lexing), а занимается этим лексер (lexer). Токены являют собой короткие, удобоваримые строки, содержащие самые основные части программы, такие как числа, идентификаторы, ключевые слова и операторы. Лексер будет пропускать пробелы и комментарии, так как они игнорируются интерпретатором.
Процесс сборки токенов в AST называется парсингом. Парсер извлекает структуру нашей программы в форму, которую мы можем исполнить. 
Эта статься будет сосредоточена исключительно на лексере. Сначала мы напишем общую лекс-библиотеку а затем уже лексер для IMP. Следующие части будут сфокусированы на парсере и исполнителе.
Лексер
По правде говоря, лексические операции очень просты и основываются на регулярных выражениях. Если вы с ними не знакомы, то можете прочитать официальную документацию.
Входными данными для лексера будет простой поток символов. Для простоты мы прочитаем инпут в память. А вот выходящими данными будет список токенов. Каждый токен включает в себя значение и метку (тег, для идентификации вида токена). Парсер будет использовать это для построения дерева (AST).
Итак, давайте сделаем обычнейший лексер, который будет брать список регэкспов и разбирать на теги код. Для каждого выражения он будет проверять, соответствует ли инпут текущей позиции. Если совпадение найдено, то соответствующий текст извлекается в токен, наряду с тегом регулярного выражения. Если регулярное выражение ни к чему не подходит, то текст отбрасывается. Это позволяет нам избавиться от таких вещей как комментарии и пробелы. Если вообще ничего не совпало, то мы рапортуем об ошибке и скрипт становится героем. Этот процесс повторяется, пока мы не разберем весь поток кода.
Вот код из библиотеки лексера:
Отметим, что порядок передачи в регулярные выражения является значительным. Функция lex будет перебирать все выражения и примет только первое найденное совпадение. Это значит, что при использовании этой функции, первым делом нам следует передавать специфичные выражения (соответствующие операторам и ключевым словам), а затем уже обычные выражения (идентификаторы и числа).
Лексер IMP
С учетом кода выше, создание лексера для нашего языка становится очень простым. Для начала определим серию тегов для токенов. Для языка нужно всего лишь 3 тега. RESERVED для зарезервированных слов или операторов, INT для чисел, ID для идентификаторов.
Теперь мы определим выражения для токенов, которые будут использованы в лексере. Первые два выражения соответствуют пробелам и комментариям. Так как у них нету тегов, лексер их пропустит.
После этого следуют все наши операторы и зарезервированные слова.
Наконец, нам нужны выражения для чисел и идентификаторов. Обратите внимание, что регулярным выражениям для идентификаторов будут соответствовать все зарезервированные слова выше, поэтому очень важно, чтобы эти две строчки шли последними.
Когда наши регэкспы определены, мы можем создать обертку над функцией lex:
Если вы дочитали до этих слов, то вам, скорее всего, будет интересно как работает наше чудо. Вот код для теста:
Скачать полный исходный код: imp-interpreter.tar.gz
Автор оригинальной статьи — Jay Conrod.
UPD: Спасибо пользователю zeLark за исправление бага, связанного с порядком определения шаблонов.
Простой интерпретатор с нуля на Python #4
В предыдущих трех частях мы создали лексер, парсер и AST для нашего игрушечного языка IMP. Мы даже написали нашу собственную библиотеку парсеров комбинаторов. В этой, финальной статье мы напишем последний компонент интерпретатора — исполнитель.
Давайте подумаем, как обычно исполняются программы. В любой момент времени есть некоторые «точки контроля», которые указывает на то, какое выражение программа собирается выполнить дальше. Когда следующее выражение исполняется, оно модифицирует состояние программы, путем улучшения «точки контроля» и изменения значений переменных.
Чтобы исполнить IMP-программу, нам нужны три вещи:
- Точка контроля — мы должны знать следующее выражение для исполнения.
- Среда — нам нужно смоделировать «изменение состояния программы».
- Функции исполнения — нам нужно знать, как состояние и точка контроля должны быть модифицированы для каждого выражения.
Самое простое — точка контроля, по крайней мере для IMP. Мы устроили наше промежуточное представление в виде древовидной структуры. Мы будем просто вызывать функции исполнения (evaluation) для топ-левел выражений, которая будет рекурсивно вызывать функцию исполнения для выражений внутри. По сути, мы будем использовать точку контроля Python в качестве нашей собственной. Это не было бы так просто, для языков с более сложными структурами управления, как функций или исключений, но мы можем сохранить его простым для IMP.
Среда также проста. У IMP есть только глобальные переменные, так что мы можем смоделировать среду, использую стандартные питоновские словари. Когда значение изменяется, мы будем обновлять значение переменной в словаре.
Функции исполнения — единственная вещь, о которой мы должны думать. Каждый тип выражения будем иметь собственную функцию исполнения, которая использует актуальную среду и вернет значение. Арифметические выражения возвращают интеджеры, булевые — true или false. Выражения не имеют никаких побочных эффектов, так что среду не будет модифицирована. Каждый тип выражения также имеет функцию исполнения. Утверждения действуют путем модифицирования среды, так что никакого результата не вернется.
Определяем функции исполнения
Мы определим их как методы на наших AST-классах. Это даст прямой доступ каждой функции к структуре, которую она исполняет. Вот арифметические функции:
Вы можете увидеть здесь немного экстра-логики в случае, где программист юзает переменную, которая не определена ранее (та, которая не определена в словаре среды). Для простоты и для того, чтобы избежать написание системы отлова ошибок, мы дадим всем неопределенным переменным 0.
В BinopAexp мы обрабатываем случай «неизвестного оператора» путем выбрасывания RuntimeError. Парсер не может создать AST из неизвестных операторов, так что нам становится только легче. Но если кто-то делает свой собственный AST, там нужно будет учитывать и это.
Вот функции булевых операций:
Это довольно просто. Мы используем питоньи реляционные и логические операторы.
А здесь функции исполнения для каждого типа выражений:
AssignStatement: мы просто исполняем арифметическое выражение на правой стороне, а затем обновляем среду с результирующим значением. Программист не ограничен в переопредлении переменных, которые уже были определены.
CompoundStatement: мы исполняем каждое выражение, одно за другим. Запомните, что CompoundStatement разрешен везде, где разрешено выражение, так что длинные цепи выражений раскодируются как вложенные.
IfStatement: сначала мы исполняем булевое условие выражения. Если true, мы исполняем true-выражение. Если false и false-выражение было определено, мы исполняем false-выражение.
WhileStatement: мы исполняем условие для проверки, должно ли тело цикла исполнится один раз. Условие исполняется каждую итерацию цикла, для проверки условия.
Собираем все в кучу
Ну что же, мы создали главные компоненты нашего интерпретатора и теперь остается только написать объединяющую программу:
В программу подается только один аргумент — имя для интерпретации. Она читает файл и отправляет его в лексер и парсер, рапортуя об ошибке (если таковая имеется). Затем мы извлекаем AST из результата парсера и исполняем его, используя пустую среду. Так как IMP не имеет никакого аутпута, мы просто выводим всю среду в терминал.
Каноничный пример вычисления факториала:
Заключение
В последней статье мы написали интерпретатор для нашего простого языка с нуля. Сам язык мало полезен, но интерпретатор вполне расширяем и его главные компоненты могут быть использованы в чем-то другом.
Я надеюсь этот материал предоставит хороший старт для людей экспериментировать с дизайном языка. Немного идей: