Вы знаете… в жизни каждого программиста время, когда ваши ультра-фреймворковые веб-приложения на основе библиотек перестают его сокращать, вы начинаете все больше и больше думать о том, что вам делать дальше.
В то же время, когда интересно не делать то, что хочется, комфортно оставаться на одном месте.
В один из таких дней я просто вскочил с кровати, и решил, что хочу сделать что-то классное, побродил пару часов в инете, нашел несколько симпатичных проектов, но тут пришла идея, из выдающейся книги от Боб Нистром : Создание интерпретаторов.
Это было, когда я впервые начал документировать свой прогресс и то, что я узнал о Notion, и теперь это моя первая серия в моем блоге на Medium! 😃
Итак, вы готовы?
P.S: Большая часть моего кода в основном идентична коду книги, за исключением некоторых комментариев и имен переменных/методов. Основное отличие этой серии состоит в том, что большую часть своего обучения я продолжу из прочитанного в этой книге и объясню своими словами (более простыми словами, чем слова автора).
Как на самом деле работают языки?
Процесс, с которым сталкивается язык программирования, похож на переход через гору. У него есть свои проблемы на всем пути вверх, а затем и вниз. Возьмем высокоуровневый подход.
1. Сканирование
Первым шагом является сканирование, также известное как лексика или (если вы пытаетесь произвести на кого-то впечатление) лексический анализ. Все они означают примерно одно и то же.
Сканер (или «лексер») принимает линейный поток из символов и объединяет их в последовательность, более близкую к «словам». . В языках программирования каждое из этих слов называется токен.
Некоторые токены состоят из одного символа, например ( и ,. Другие могут состоять из нескольких символов, например числа (123), строковые литералы («привет!») и идентификаторы ( мин).
💡 «Лексический» происходит от греческого корня «lex», что означает «слово».
Некоторые символы в исходном файле на самом деле ничего не значат.
Пробелы часто незначительны, а комментарии по определению игнорируются языком. Сканер обычно отбрасывает их, оставляя чистую последовательность значимых токенов.
2. Разбор
Следующим шагом является анализ. Именно здесь наш синтаксис получает грамматику — возможность составлять более крупные выражения и операторы из более мелких частей.
Синтаксический анализатор берет плоскую последовательность токенов и строит древовидную структуру, отражающую вложенный характер грамматики. Эти деревья имеют несколько разных названий — «дерево синтаксического анализа» или «абстрактное синтаксическое дерево» — в зависимости от того, насколько они близки к голой синтаксической структуре исходного языка. На практике языковые хакеры обычно называют их «синтаксическими деревьями», «AST» или часто просто «деревьями».
💡 Синтаксический анализ имеет долгую и богатую историю в компьютерных науках, тесно связанных с сообществом искусственного интеллекта. Многие методы, используемые сегодня для анализа языков программирования, изначально были придуманы для анализа человеческих языков исследователями ИИ, которые пытались заставить компьютеры разговаривать с нами.
3. Статический анализ
Первые два этапа очень похожи во всех реализациях. Теперь в игру вступают индивидуальные особенности каждого языка. На данный момент мы знаем синтаксическую структуру кода — такие вещи, как приоритет операций и вложенность выражений — но мы не знаем ничего большего.
В таком выражении, как a + b, мы знаем, что добавляем a и b, но не знаем, к чему относятся эти имена. Это локальные переменные? Глобальный? Где они определены?
Первый этап анализа, выполняемый большинством языков, называется связыванием или разрешением. Для каждого идентификатора мы выясняем, где определено это имя, и связываем их вместе. Здесь в игру вступает область действия — область исходного кода, где определенное имя может использоваться для ссылки на определенное объявление.
Если язык статически типизирован, то мы набираем check. Как только мы узнаем, где объявлены a и b, мы также можем выяснить их типы. Затем, если эти типы не поддерживают добавление друг к другу, мы сообщаем об ошибке типа.
Если язык является динамически типизированным, проверка типа будет происходить только во время выполнения.
4. Промежуточное представление
Вы можете думать о компиляторе как о конвейере, где задачей каждого этапа является организация кода таким образом, чтобы упростить реализацию следующего этапа. Передняя часть конвейера зависит от исходного языка, на котором программирует пользователь. Задняя часть связана с окончательной архитектурой, на которой будет выполняться код.
В середине код может храниться в каком-то промежуточном представлении (или «IR»), которое не тесно связано ни с исходной, ни с целевой формой (отсюда «промежуточное»). Вместо этого IR действует как интерфейс между этими двумя языками.
5. Оптимизация
Как только мы понимаем, что означает программа пользователя, мы можем заменить ее другой программой, которая имеет ту же семантику, но реализует ее более эффективно — мы можем ее оптимизировать.
Простой пример — свертывание констант: если какое-то выражение всегда возвращает одно и то же значение, мы можем выполнить оценку во время компиляции и заменить код выражения его результатом. Если пользователь ввел:
pennyArea = 3.14159 * (0.75 / 2) * (0.75 / 2);Мы можем сделать всю эту арифметику в компиляторе и изменить код на:
pennyArea = 0.4417860938;6. Генерация кода
Мы применили все возможные оптимизации к программе пользователя. Последним шагом является преобразование его в форму, на которой машина может работать. Другими словами, генерация кода, где «код» относится к типу примитивных инструкций, подобных ассемблеру, которые выполняет ЦП, а не к «исходному коду», который человек может захотеть прочитать.
Если ваш компилятор создает байт-код, ваша работа на этом не заканчивается. Поскольку не существует чипа, который произносит этот байт-код, ваша задача — перевести его. Опять же, у вас есть два варианта. Вы можете написать небольшой мини-компилятор для каждой целевой архитектуры, который преобразует байт-код в собственный код для этой машины. Вам по-прежнему нужно выполнять работу для каждого поддерживаемого чипа, но последний этап довольно прост, и вы можете повторно использовать оставшуюся часть конвейера компилятора на всех поддерживаемых вами машинах. Вы в основном используете свой байт-код в качестве промежуточного представления.
В обоих случаях для всех низкоуровневых языков, кроме самого базового, нам обычно нужны некоторые сервисы, которые наш язык предоставляет во время работы программы. Например, если язык автоматически управляет памятью, нам нужен сборщик мусора, чтобы освободить неиспользуемые биты. Если наш язык поддерживает «экземпляры» тестов, чтобы вы могли видеть, какой у вас объект, то нам нужно какое-то представление, чтобы отслеживать тип каждого объекта во время выполнения.
Все это происходит во время выполнения, поэтому это называется «время выполнения». В полностью скомпилированном языке код, реализующий среду выполнения, вставляется непосредственно в результирующий исполняемый файл. Скажем, в Go каждое скомпилированное приложение имеет собственную копию среды выполнения Go, непосредственно встроенную в него. Если язык запускается внутри интерпретатора или виртуальной машины, то среда выполнения живет там. Именно так работает большинство реализаций таких языков, как Java, Python и JavaScript.
💡Лексемы x Токены Лексемы представляют собой все небольшие фрагменты информации при сканировании исходного кода, каждое слово или сигнал, допустимый для фактической грамматики языка. Токены с другой стороны — это лексемы, которые также являются зарезервированными словами (живут while или if в случае Lox).
Сканер
После того, как все эти концепции переполнили наши головы, пришло время по-настоящему построить сканер. Взгляните простым и быстрым взглядом на весь код, который нам нужен, а затем я шаг за шагом объясню все, что мы сделали до сих пор.
package com.joaoaugustoperin.jLox;import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;/* * A import static isn't the best practice in the world but here * it kinda makes sense. If you don't know about static importing * I suggest you look after this. To resume, this keeps me from calling * TokenType [dot] something everytime I want some static content from * that class. And as Enum that it is, I would do this so many times * across this file. Pretty handy, uh? * * */ import static com.joaoaugustoperin.jLox.TokenType.*;class Scanner { private final String source; private final List<Token> tokens = new ArrayList<>(); private static final Map<String, TokenType> keywords; private int start = 0; private int current = 0; private int line = 1;static { keywords = new HashMap<>(); keywords.put("and", AND); keywords.put("class", CLASS); keywords.put("else", ELSE); keywords.put("false", FALSE); keywords.put("for", FOR); keywords.put("fun", FUN); keywords.put("if", IF); keywords.put("nil", NIL); keywords.put("or", OR); keywords.put("print", PRINT); keywords.put("return", RETURN); keywords.put("super", SUPER); keywords.put("this", THIS); keywords.put("true", TRUE); keywords.put("var", VAR); keywords.put("while", WHILE); } Scanner(String source) { this.source = source; } List<Token> scanTokens() { while (!isAtEnd()) { // We are at the beginning of the next lexeme. start = current; scanToken(); }tokens.add(new Token(EOF, "", null, line)); return tokens; } private void scanToken() { char c = advance(); switch (c) { case '(': addToken(LEFT_PAREN); break; case ')': addToken(RIGHT_PAREN); break; case '{': addToken(LEFT_BRACE); break; case '}': addToken(RIGHT_BRACE); break; case ',': addToken(COMMA); break; case '.': addToken(DOT); break; case '-': addToken(MINUS); break; case '+': addToken(PLUS); break; case ';': addToken(SEMICOLON); break; case '*': addToken(STAR); break; case '!': addToken(match('=') ? BANG_EQUAL : BANG); break; case '=': addToken(match('=') ? EQUAL_EQUAL : EQUAL); break; case '<': addToken(match('=') ? LESS_EQUAL : LESS); break; case '>': addToken(match('=') ? GREATER_EQUAL : GREATER); break; case '/': if (match('/')) { // A comment goes until the end of the line. while (peek() != '\n' && !isAtEnd()) advance(); } else { addToken(SLASH); } break;case ' ': case '\r': case '\t': break; case '\n': line++; break; case '"': string(); break; default: if (isDigit(c)) { number(); }else if(isAlpha(c)) { identifier(); } else { Lox.error(line, "Unexpected character."); } break; } } private void identifier() { while (isAlphaNumeric(peek())) advance();// See if the identifier is a reserved word. String text = source.substring(start, current);TokenType type = keywords.get(text); if (type == null) type = IDENTIFIER; addToken(type); } private void number() { while (isDigit(peek())) advance();// Look for a fractional part. if (peek() == '.' && isDigit(peekNext())) { // Consume the "." advance();while (isDigit(peek())) advance(); }addToken(NUMBER, Double.parseDouble(source.substring(start, current))); } private void string() { while (peek() != '"' && !isAtEnd()) { if (peek() == '\n') line++; advance(); }// Unterminated string. if (isAtEnd()) { Lox.error(line, "Unterminated string."); return; }// The closing ". advance();// Trim the surrounding quotes. String value = source.substring(start + 1, current - 1); addToken(STRING, value); } private boolean match(char expected) { if (isAtEnd()) return false; if (source.charAt(current) != expected) return false;current++; return true; } private char peek() { if (isAtEnd()) return '\0'; return source.charAt(current); } private char peekNext() { if (current + 1 >= source.length()) return '\0'; return source.charAt(current + 1); } private boolean isAlpha(char c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_'; }private boolean isAlphaNumeric(char c) { return isAlpha(c) || isDigit(c); } private boolean isDigit(char c) { return c >= '0' && c <= '9'; }private boolean isAtEnd() { return current >= source.length(); } private char advance() { current++; return source.charAt(current - 1); }private void addToken(TokenType type) { addToken(type, null); }private void addToken(TokenType type, Object literal) { String text = source.substring(start, current); tokens.add(new Token(type, text, literal, line)); } }
Я знаю, здесь так много всего происходит, но не паникуйте, по крайней мере, пока. Выпейте кофе и поехали!
Лексемы и токены
В моем последнем посте здесь мы немного говорили о разнице между этими двумя концепциями, но теперь нам нужно сделать ее кристально ясной.
Возьмите эту простую строку кода Lox:
var language = "lox";Здесь var — ключевое слово для объявления переменной. Эта трехсимвольная последовательность «v-a-r» что-то значит. Но если мы выдернем три буквы из середины языка, например «г-у-а», они сами по себе ничего не значат.
Вот что такое лексический анализ. Наша задача — просмотреть список символов и сгруппировать их в наименьшие последовательности, которые все еще что-то представляют. Каждый из этих блоков символов называется лексемой. В этой примерной строке кода лексемы:
Однако в процессе группировки последовательностей символов в лексемы мы натыкаемся и на другую полезную информацию. Когда мы берем лексему и связываем ее с другими данными, в результате получается токен.
Синтаксический анализатор может категоризировать токены из необработанной лексемы, сравнивая строки, но, в конце концов, сравнение строк заканчивается просмотром отдельных символов, и разве это не работа сканера?
Именно тогда мы ОПРЕДЕЛЯЕМ ТИПЫ ТОКЕНОВ. Это не похоже на правило или что-то, что вам НЕОБХОДИМО сделать, чтобы сделать компилятор, но это необходимо, чтобы сделать ВЕЛИКИЙ компилятор.😉
Для этого создадим Java Enum:
package com.joaoaugustoperin.jLox;enum TokenType { // Single-character tokens. LEFT_PAREN, RIGHT_PAREN, LEFT_BRACE, RIGHT_BRACE, COMMA, DOT, MINUS, PLUS, SEMICOLON, SLASH, STAR,// One or two character tokens. BANG, BANG_EQUAL, EQUAL, EQUAL_EQUAL, GREATER, GREATER_EQUAL, LESS, LESS_EQUAL,// Literals. IDENTIFIER, STRING, NUMBER,// Keywords. AND, CLASS, ELSE, FALSE, FUN, FOR, IF, NIL, OR, PRINT, RETURN, SUPER, THIS, TRUE, VAR, WHILE,EOF }
Токен нуждается в своем представлении, давайте сделаем это через класс Java:
package com.joaoaugustoperin.jLox;class Token { final TokenType type; final String lexeme; final Object literal; final int line;Token(TokenType type, String lexeme, Object literal, int line) { this.type = type; this.lexeme = lexeme; this.literal = literal; this.line = line; }public String toString() { return type + " " + lexeme + " " + literal; } }
Теперь мы подошли к самой сложной части здания сканера. Сам класс Scanner с его свойствами и методами. Но давайте шаг за шагом, вдох, и поехали!
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;import static com.craftinginterpreters.lox.TokenType.*;class Scanner { private final String source; private final List<Token> tokens = new ArrayList<>();Scanner(String source) { this.source = source; } }
Для начала мы сначала реализуем класс Scanner с простотой. Это делает:
- Возьмите весь исходный код (в виде строки).
- Создает список всех токенов, которые мы находим в нашем исходном коде.
💡
Статический импорт — не лучшая практика в мире, но здесь это имеет смысл. Если вы не знаете о статическом импорте, я предлагаю вам позаботиться об этом. Чтобы возобновить, это не позволяет мне вызывать TokenType [dot] каждый раз, когда мне нужен статический контент из этого класса. И как Enum, я бы сделал это много раз в этом файле. Довольно удобно, а?
И здесь начинается движок нашего Сканера, метод, который будет всем управлять… метод scanTokens:
private int start = 0; private int current = 0; private int line = 1;List<Token> scanTokens() { while (!isAtEnd()) { // We are at the beginning of the next lexeme. start = current; scanToken(); }tokens.add(new Token(EOF, "", null, line)); return tokens; }
Мы создаем еще 3 поля свойств класса Scanner, чтобы отслеживать, где считывается код.
Сканер работает с исходным кодом, добавляя токены, пока не закончатся символы. Когда это будет сделано, он добавляет один последний токен «конец файла» (в данном случае это «\0»). Это не обязательно, но делает наш синтаксический анализатор немного чище.
Поля start и current представляют собой смещения в строке — первый символ в текущей сканируемой лексеме и символ, который мы сейчас рассматриваем.
💡 Например, учитывая эти две переменные. Если бы мы сканировали слово «солнце», это было бы примерно так:
Конечно, если рассматривать «солнце» как первую лексему в первой позиции первой строки в первом первом из первого первого.
Другое поле отслеживает, какой ток в линии источника включен, поэтому мы можем создавать токены, которые знают их местоположение.
Теперь мы определяем небольшую вспомогательную функцию, чтобы убедиться, что мы еще не дошли до конца файла (не получили токен «\0»).
private boolean isAtEnd() {
return current >= source.length();
}Распознавание лексем
Вот где начинается беспорядок, будьте бдительны!
На каждом обороте цикла мы сканируем один токен. Это настоящее сердце сканера. Мы начнем с простого. Представьте, если бы каждая лексема состояла из одного символа. Все, что вам нужно сделать, это использовать следующий символ и выбрать для него тип токена. Несколько лексем — это всего лишь один символ в Lox, так что давайте начнем с них:
private void scanToken() {
char c = advance();
switch (c) {
case '(': addToken(LEFT_PAREN); break;
case ')': addToken(RIGHT_PAREN); break;
case '{': addToken(LEFT_BRACE); break;
case '}': addToken(RIGHT_BRACE); break;
case ',': addToken(COMMA); break;
case '.': addToken(DOT); break;
case '-': addToken(MINUS); break;
case '+': addToken(PLUS); break;
case ';': addToken(SEMICOLON); break;
case '*': addToken(STAR); break;
}
}переменная c содержит значение текущего символа, проходящего через сканер, после чего мы передаем (на основе оператора switch Java) вспомогательной функции addToken ниже:
private void addToken(TokenType type) { addToken(type, null); }private void addToken(TokenType type, Object literal) { String text = source.substring(start, current); tokens.add(new Token(type, text, literal, line)); }
Другая вспомогательная функция, которую мы используем здесь:
private char advance() {
current++;
return source.charAt(current - 1);
}Это не сложно, перейдите к следующему символу и верните значение времени его вызова (которое входит непосредственно в эту переменную c оператора switch).
Прежде чем мы зайдем слишком далеко, давайте подумаем об ошибках на лексическом уровне. Что произойдет, если пользователь бросит исходный файл, содержащий некоторые символы, которые Lox не использует, например @#^, нашему интерпретатору? Прямо сейчас эти символы автоматически добавляются к следующему токену. Это неправильно.
Хорошо, как сказал нам автор, начнем:
default:
Lox.error(line, "Unexpected character.");
break;Обратите внимание, что ошибочный символ все еще используется предыдущим вызовом advance(), это означает, что он уже поместил переменную c. Это важно, чтобы мы не застряли в бесконечном цикле (но правильно логировать найденную ошибку). И мы продолжаем сканирование даже после этого, сканер не обязан обнаруживать синтаксические ошибки, он просто переваривает символы и ALERTS с ошибкой, в которую пользователь вставил недопустимые символы.
У нас есть односимвольные лексемы, но они не охватывают все операторы Lox. Как насчет !? Это один персонаж, да? Иногда да, но не тогда, когда за ним следует знак =. В этом случае это должна быть лексема !=. Аналогично, за символами ‹, › и = может следовать знак =.
case '!': addToken(match('=') ? BANG_EQUAL : BANG); break;
case '=': addToken(match('=') ? EQUAL_EQUAL : EQUAL); break;
case '<': addToken(match('=') ? LESS_EQUAL : LESS); break;
case '>': addToken(match('=') ? GREATER_EQUAL : GREATER); break;Как видите, мы используем еще одну вспомогательную функцию, называемую match:
private boolean match(char expected) { if (isAtEnd()) return false; if (source.charAt(current) != expected) return false;current++; return true; }
В основном он принимает ожидаемый ввод и возвращает true, если фактический ввод его удовлетворяет. С другой стороны, возвращает false, если мы доходим до маркера конца файла («/0») или если фактический ввод отличается от ожидаемого.
Нам все еще не хватает одного оператора, /. С этим нужно немного поработать, потому что комментарии тоже начинаются с косой черты. Итак, вот оно:
case '/':
if (match('/')) {
// A comment goes until the end of the line.
while (peek() != '\n' && !isAtEnd()) advance();
} else {
addToken(SLASH);
}
break;Как вы, наверное, заметили, здесь мы используем еще одну вспомогательную функцию, называемую peek, и вот она:
private char peek() {
if (isAtEnd()) return '\0';
return source.charAt(current);
}Это точно так же, как продвижение, за исключением того, что оно не использует символ, то есть не увеличивает счетчик текущего.
Сейчас самое время пропустить и другие бессмысленные символы, символы новой строки и пробелы:
case ' ': case '\r': case '\t': // Ignore whitespace. break;case '\n': line++; break;
Теперь, когда мы привыкли к более длинным лексемам, мы готовы заняться литералами. Сначала мы создадим строки, так как они всегда начинаются с определенного символа “:
case '"': string(); break;Это, очевидно, вызовет метод string(), который определен здесь:
private void string() { while (peek() != '"' && !isAtEnd()) { if (peek() == '\n') line++; advance(); }// Unterminated string. if (isAtEnd()) { Lox.error(line, "Unterminated string."); return; }// The closing ". advance();// Trim the surrounding quotes. String value = source.substring(start + 1, current - 1); addToken(STRING, value); }
Код объясняет сам себя, но комментарии над каждой строкой должны вам немного помочь.
Теперь… к цифрам!
Чтобы распознать начало числовой лексемы, мы ищем любую цифру. Добавлять регистры для каждой десятичной цифры довольно утомительно, поэтому вместо этого мы впишем регистр по умолчанию:
default:
if (isDigit(c)) {
number();
} else {
Lox.error(line, "Unexpected character.");
}
break;И, конечно же, здесь мы переходим к двум вспомогательным методам: idDigit() и number(), а также к другим вспомогательным функциям, которые нам понадобятся внутри функции number():
private boolean isDigit(char c) { return c >= '0' && c <= '9'; }private char peekNext() { if (current + 1 >= source.length()) return '\0'; return source.charAt(current + 1); }private void number() { while (isDigit(peek())) advance();// Look for a fractional part. if (peek() == '.' && isDigit(peekNext())) { // Consume the "." advance();while (isDigit(peek())) advance(); }addToken(NUMBER, Double.parseDouble(source.substring(start, current))); }
А вот и немного скучная часть: вы можете подумать, что мы могли бы сопоставлять ключевые слова, такие как или, так же, как мы обрабатываем многосимвольные операторы, такие как ‹=:
case 'o':
if (peek() == 'r') {
addToken(OR);
}
break;Подумайте, что произойдет, если пользователь назовет переменную orchid. А здесь, для получения дополнительной информации, я советую вам прочитать этот раздел исходной книги для этого проекта.
Вместо этого мы предполагаем, что любая лексема, начинающаяся с буквы или символа подчеркивания, является идентификатором:
default:
if (isDigit(c)) {
number();
} else if (isAlpha(c)) {
identifier();
} else {
Lox.error(line, "Unexpected character.");
}Это вызовет:
private void identifier() { while (isAlphaNumeric(peek())) advance();// See if the identifier is a reserved word. String text = source.substring(start, current);TokenType type = keywords.get(text); if (type == null) type = IDENTIFIER; addToken(type); }
И используйте эти помощники:
private boolean isAlpha(char c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_'; }private boolean isAlphaNumeric(char c) { return isAlpha(c) || isDigit(c); }
Итак, теперь мы определим и будем использовать ключевые слова в нашем классе сканера:
private static final Map<String, TokenType> keywords;static { keywords = new HashMap<>(); keywords.put("and", AND); keywords.put("class", CLASS); keywords.put("else", ELSE); keywords.put("false", FALSE); keywords.put("for", FOR); keywords.put("fun", FUN); keywords.put("if", IF); keywords.put("nil", NIL); keywords.put("or", OR); keywords.put("print", PRINT); keywords.put("return", RETURN); keywords.put("super", SUPER); keywords.put("this", THIS); keywords.put("true", TRUE); keywords.put("var", VAR); keywords.put("while", WHILE); }
И это все! Наконец-то мы сделали наш класс Scanner! Очевидно, что он не самый точный и безошибочный из всех, но он действительно работает, он делает то, что должен делать.
Итак, поздравляем нас! 👏👏👏
