В течение последнего месяца или около того я работал над реализацией собственного языка программирования в качестве хобби. Этот проект во многом основан на книге Роберта Нистрома Crafting Interpreters. Язык программирования, над созданием которого я работал, называется Lox. Она была разработана и реализована Робертом Нистромом, и книга в основном представляет собой пошаговое руководство по шагам, связанным с созданием вашего собственного языка. Мне было очень весело следить за этим и я многому научился, так как сам написал интерпретатор для этого языка!
Lox — это язык программирования с динамической типизацией, который поддерживает парадигмы как функционального, так и объектно-ориентированного программирования. В книге рассматриваются две реализации этого языка программирования — одна написана на Java, а другая — на C. Интерпретатор Java — это очень простая и понятная реализация, которая в значительной степени использует код Lox и полагается на JVM для его выполнения. Реализация таким образом оказывается очень неэффективной и делает язык чрезвычайно медленным. Именно над этим интерпретатором Java я работал, и именно ему посвящена статья. Однако интерпретатор C немного сложнее. Он переводит код Lox в байт-код и запускает его на виртуальной машине, что приводит к значительному приросту производительности.
Вкус языка
Синтаксис языка довольно прост для понимания. Это язык в стиле C, в котором для объявлений переменных используется ключевое слово var, а для объявлений функций используется funобъявления ключевых слов и классов используют ключевое слово class. Ниже показано, как выглядит фрагмент кода Lox.
class Pixel {
init(red, blue, green, alpha) {
this.red = red;
this.blue = blue;
this.green = green;
this.alpha = alpha;
}
incrRed() {
if (this.red < 255) {
this.red = this.red + 1;
}
}
incrBlue() {
if (this.blue < 255) {
this.blue = this.blue + 1;
}
}
incrGreen() {
if (this.green < 255) {
this.green = this.green + 1;
}
}
}
fun incrNTimes(pixel, n, color) { // probably the worst possible way to modify color values
for (var i = 0; i < n; i++) { // it just gets worse
if (color == "red") pixel.red = pixel.red + 1;
if (color == "green") pixel.green = pixel.green + 1;
if (color == "blue") pixel.blue = pixel.blue + 1;
}
}
var pixel = Pixel(25, 50, 75);
incrNTimes(pixel, 75, "red");
incrNTimes(pixel, 50, "green");
incrNTimes(pixel, 25, "blue");
print pixel;
Грамматика
Прежде чем приступить к реализации языка, важно иметь формальное определение синтаксиса языка. Такой синтаксис может быть точно и лаконично представлен в грамматике. Грамматика языка описывает, как формировать строки из алфавита языка, которые допустимы в контексте синтаксиса языка. Грамматика не описывает значение строк или то, что можно сделать с ними в заданном контексте, и поэтому ее часто называют контекстно-свободной грамматикой. Вот вся грамматика Локса (это небольшой язык точно)
program → declaration* EOF ;
declaration → funDecl | varDecl | statement | classDecl ;
varDecl → "var" IDENTIFIER ( "=" expression )? ";" ;
statement → exprStmt
| printStmt
| block
| ifStmt
| whileStmt
| returnStmt ;
block → "{" declaration* "}" ;
ifStmt → "if" "(" expression ")" statement
( "else" statement )?
whileStmt → "while" "(" expression ")" stmt ;
funDecl → "fun" function ;
function → IDENTIFIER "(" parameters? ")" block ;
parameters → IDENTIFIER ( ',' IDENTIFIER )* ;
returnStmt → "return" expression? ";" ;
exprStmt → expression ";" ;
printStmt → "print" expression ";" ;
expression → assignment ;
assignment → IDENTIFIER "=" assignment | logic_or ;
logic_or → logic_and ( "or" logic_and )* ;
logic_and → equality ( "and" equality )* ;
equality → comparison ( ( "!=" | "==" ) comparison )* ;
comparison → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term → factor ( ( "-" | "+" ) factor )* ;
factor → unary ( ( "/" | "*" ) unary )* ;
unary → ( "!" | "-" ) unary | call ;
call → primary ( "(" arguments? ")" )* ;
arguments → expression ( "," expression )* ;
primary → "true" | "false" | "nil"
| NUMBER | STRING
| "(" expression ")"
| IDENTIFIER ;
Программа Lox должна придерживаться правил грамматики, а в местах, где она отклоняется от грамматики, сообщается о синтаксической ошибке. Программа Lox рассматривается как серия «объявлений», за которыми следует символ EOF (конец файла). Каждое объявление может иметь тип varDecl, funDecl, classDecl или оператор. Точно так же каждая часть пользовательской программы разбивается на более мелкие и простые представления, пока мы не достигнем основного. Эти правила в грамматике также известны как терминалы. Каждое правило, упомянутое выше, называется производством. Способ написания этих правил грамматики также аналогичен приоритету языка.
Реализация языка
Сканер
Первым шагом интерпретатора является сканирование или лексический анализ. Сканер принимает код пользователя в качестве входных данных и пытается связать последовательности символов в Tokens. Токен — это основной компонент исходного кода. Токены могут быть в форме ключевых слов, таких как var, fun и class. Это могут быть имена переменных, числа, строки, логические значения или даже отдельные символы, такие как '{', '(', '.' . При идентификации этих токенов сканер также отслеживает номер строки и начальную точку каждого из этих токенов. что впоследствии может помочь выявить синтаксические ошибки в пользовательском коде.
Представление абстрактного синтаксического дерева (AST)
Абстрактное синтаксическое дерево (АСТ) — это древовидное представление синтаксической структуры текста. Учитывая рекурсивный характер языка, в котором операторы, выражения и операторы могут быть вложены друг в друга с произвольной глубиной, деревья являются самым простым способом представления грамматики. Как следует из названия, AST инкапсулируют не каждую деталь (абстрактную), а только структурную информацию. Рассмотрим уравнение
x = a * (b + c) / 2
В AST это будет представлено как
При реализации синтаксического дерева я наткнулся на интересный шаблон проектирования, известный как шаблон посетителя. Паттерн посетитель возникает из-за фундаментальной проблемы в представлении дерева. Интерпретатору необходимо выбрать отдельный фрагмент кода для обработки каждого типа выражения, с которым он сталкивается. При представлении дерева каждый тип выражения получает свой собственный класс, поэтому логичный способ для интерпретатора узнать, что делать, когда он получает узел дерева любого конкретного класса, - это иметь длинный список тестов типов, где он может проверить тип выражения, прежде чем знать, что делать. Для решения этой проблемы можно использовать шаблон проектирования, известный как Шаблон интерпретатора, но он плохо масштабируется.
Парсер
Интерпретатор Java реализует синтаксический анализатор с рекурсивным спуском, который является самым простым способом создания синтаксического анализатора. Несмотря на свою простоту, парсеры рекурсивного спуска быстрые, надежные и могут поддерживать обработку ошибок. GCC, V8 и многие другие реализации производственного языка используют рекурсивный спуск. Это буквальный перевод правил грамматики в код, где каждое правило становится функцией.
У синтаксического анализатора две задачи: он создает синтаксические деревья при задании допустимой последовательности токенов, а при задании недопустимой последовательности токенов обнаруживает ошибки и уведомляет о них пользователя. Для синтаксического анализатора даже недопустимый код является допустимым входом, поэтому важно убедиться, что он надежен и может обрабатывать все, что ему брошено. Парсер должен быть быстрым. В современных IDE код анализируется в реальном времени почти каждый раз, когда вводится новый символ. Парсер также должен продолжать синтаксический анализ даже после обнаружения ошибки. Сообщать об одной ошибке за раз — плохой дизайн, поскольку пользователю придется перекомпилировать после исправления каждой ошибки. Тип восстановления после ошибки, который реализует синтаксический анализатор Java, называется восстановлением после ошибки режима паники. Здесь всякий раз, когда синтаксический анализатор сталкивается с ошибкой, он переходит в состояние, называемое режимом паники, когда он знает, что что-то не так с текущей последовательностью передаваемых токенов. Прежде чем снова начать синтаксический анализ, синтаксический анализатор должен пройти процесс, называемый синхронизацией, где он пытается найти следующую точку, с которой токены снова начинают иметь смысл.
К тому времени, когда код выходит из синтаксического анализатора, он полностью представлен в виде набора синтаксических деревьев. Каждый оператор имеет свой собственный узел в дереве и состоит из выражений.
Резолвер
Преобразователь — это компонент интерпретатора Java, который выполняет второй проход AST, прежде чем интерпретатор сможет начать оценку пользовательского кода. Задача Resolver состоит в том, чтобы правильно определить, к какой области принадлежит каждая переменная. Способ обработки области видимости заключается в том, что каждый блок кода имеет свою новую область видимости. На верхнем уровне есть глобальная область видимости. Каждая новая создаваемая область видимости имеет ссылку на свою внешнюю область видимости. Всякий раз, когда необходимо разрешить переменную, функцию или класс, интерпретатор может просмотреть текущую область видимости и найти ссылку. Если ссылка не существует в текущей области, то она может искать в окружающей ее внешней области. Этот поиск продолжается полностью в глобальной области видимости, и если ссылка не найдена, может быть сообщено об ошибке.
Переводчик
Интерпретатор — это то, что отвечает за то, чтобы компьютер делал то, что пользователь хочет от исходного кода. Реализация Java состоит из интерпретатора обхода дерева. Интерпретаторы могут взять пользовательский код и скомпилировать его непосредственно в машинный код, перевести его на другой язык высокого уровня или преобразовать в формат байт-кода и запустить на виртуальной машине. Интерпретатор обхода дерева — это самый простой и прямой подход к реализации интерпретатора. Он буквально проходит по каждому узлу синтаксического дерева и оценивает его. Листья синтаксического дерева являются первичными выражениями. Они имеют тип число, строка, true, false и nil. Числа в Lox по умолчанию представлены как типы данных Double в Java, строки напрямую сопоставляются со строками Java. То же самое и с истинными и ложными значениями. Lox использует ключевое слово nil для представления нулевых значений в Java. Поскольку Lox является языком с динамической типизацией, до момента выполнения невозможно узнать, какое значение представляет тот или иной элемент. Реализация также отражает это и использует метод Java instanceof для определения типа каждого объекта Lox во время выполнения.
Это был краткий обзор языка Lox и того, как сделать простой интерпретатор. Вы можете найти мою java-реализацию языка здесь. Оригинальные реализации для языка находятся здесь. Спасибо Роберту Нистрому за такое веселое и интересное чтение. Здорово иметь возможность реализовать язык программирования!
