Как подойти к написанию интерпретатора с нуля

Некоторые говорят, что «все сводится к единицам и нулям», но действительно ли мы понимаем, как наши программы преобразуются в эти биты?

И компиляторы, и интерпретаторы берут необработанную строку, представляющую программу, анализируют ее и анализируют. Хотя интерпретаторы являются более простыми из двух, написание даже очень простого интерпретатора (который выполняет только сложение и умножение) будет поучительным. Мы сосредоточимся на том, что общего у компиляторов и интерпретаторов: лексическом анализе и разборе входных данных.

Что нужно и что нельзя делать при написании собственного интерпретатора

Читатели могут задаться вопросом , что не так с регулярным выражением? Регулярные выражения обладают мощными возможностями, но грамматика исходного кода недостаточно проста для их анализа. Ни один из них не является доменно-ориентированным языком (DSL), и клиенту может потребоваться собственный DSL, например, для выражений авторизации. Но даже не применяя этот навык напрямую, написание интерпретатора значительно упрощает оценку усилий, стоящих за многими языками программирования, форматами файлов и DSL.

Правильное написание синтаксических анализаторов вручную может быть сложной задачей со всеми задействованными пограничными случаями. Вот почему существуют популярные инструменты, такие как ANTLR, которые могут генерировать синтаксические анализаторы для многих популярных языков программирования. Существуют также библиотеки, называемые комбинаторами синтаксических анализаторов , которые позволяют разработчикам писать синтаксические анализаторы непосредственно на предпочитаемых ими языках программирования. Примеры включают FastParse для Scala и Parsec для Python.

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

Обзор компонентов интерпретатора

Интерпретатор — сложная программа, поэтому он состоит из нескольких этапов:

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

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

 val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res")

После трех этапов мы ожидаем, что этот код вычислит окончательное значение и напечатает Result is: 19 . В этом руководстве используется Scala, потому что это:

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

В частности, код здесь написан в синтаксисе Scala3 с необязательными фигурными скобками (синтаксис, похожий на Python, основанный на отступах). Но ни один из подходов не является специфичным для Scala , а Scala похож на многие другие языки: читатели найдут простым преобразование этих примеров кода в другие языки. За исключением этого, примеры можно запускать онлайн с помощью Scastie.

Наконец, разделы Lexer, Parser и Interpreter имеют разные примеры грамматик . Как показано в соответствующем репозитории GitHub, зависимости в более поздних примерах немного меняются для реализации этих грамматик, но общие концепции остаются прежними.

Компонент интерпретатора 1: написание лексера

Допустим, мы хотим лексировать эту строку: "123 + 45 true * false1" . Он содержит различные типы токенов:

• Целочисленные литералы
• + оператор
• А * оператор
• true буквальный
• Идентификатор, false1

В этом примере пробелы между токенами будут пропущены.

На данном этапе выражения не обязательно должны иметь смысл; лексер просто преобразует входную строку в список токенов. (Работа по «осмыслению токенов» возложена на синтаксический анализатор.)

Мы будем использовать этот код для представления токена:

 case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOF

Каждый токен имеет тип, текстовое представление и позицию в исходном вводе. Позиция может помочь конечным пользователям лексера с отладкой.

Токен EOF — это специальный токен, который отмечает конец ввода. Его нет в исходном тексте; мы используем его только для упрощения этапа парсера.

Это будет вывод нашего лексера:

 Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )

Разберем реализацию:

 class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toList

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

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

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

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

Будьте осторожны при работе с такими операторами, как < и <= . Там вы должны заглянуть вперед еще на один символ и посмотреть, является ли он = , прежде чем сделать вывод, что это оператор <= . В противном случае это просто < .

При этом наш лексер создал список токенов.

Компонент интерпретатора 2: написание синтаксического анализатора

Мы должны придать некоторую структуру нашим токенам — мы мало что можем сделать со списком. Например, нам нужно знать:

Какие выражения являются вложенными? Какие операторы применяются в каком порядке? Какие правила области применения применяются, если таковые имеются?

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

Обратите внимание, что следующий синтаксический анализатор не использует предыдущий пример лексера . Этот предназначен для сложения чисел, поэтому его грамматика имеет только две лексемы, '+' и NUM :

 expr -> expr '+' expr expr -> NUM

Эквивалент с использованием вертикальной черты ( | ) в качестве символа «или», как в регулярных выражениях:

 expr -> expr '+' expr | NUM

В любом случае у нас есть два правила: одно говорит, что мы можем суммировать два expr , а другое говорит, что expr может быть токеном NUM , что здесь будет означать неотрицательное целое число.

Правила обычно определяются формальной грамматикой . Формальная грамматика состоит из: самих правил, как показано выше; начального правила (первое указанное правило согласно соглашению); двух типов символов, определяющих правила: терминалы: «буквы» (и другие символы) нашего языка — неприводимые символы, из которых состоят токены. Нетерминалы: промежуточные конструкции, используемые для синтаксического анализа (т. е. символы, которые можно заменить).

Только нетерминал может находиться в левой части правила; правая часть может иметь как терминалы, так и нетерминалы. В приведенном выше примере терминалами являются '+' и NUM , а единственным нетерминалом является expr . Для более широкого примера, в языке Java у нас есть терминалы, такие как 'true' , '+' , Identifier и '[' , и нетерминалы, такие как BlockStatements , ClassBody и MethodOrFieldDecl .

Есть много способов реализовать этот парсер. Здесь мы будем использовать метод разбора «рекурсивный спуск». Это наиболее распространенный тип, потому что его проще всего понять и реализовать.

Анализатор рекурсивного спуска использует одну функцию для каждого нетерминала в грамматике. Он начинается с начального правила и спускается оттуда (отсюда «спуск»), выясняя, какое правило применить в каждой функции. «Рекурсивная» часть жизненно важна, потому что мы можем рекурсивно вкладывать нетерминалы! Регулярные выражения не могут этого сделать: они даже не могут обрабатывать сбалансированные скобки. Поэтому нам нужен более мощный инструмент.

Парсер для первого правила будет выглядеть примерно так (полный код):

 def expr() = expr() eat('+') expr()

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

Грамматическая неоднозначность

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

 expr -> expr '+' expr | NUM

Учитывая входные данные 1 + 2 + 3 , наш синтаксический анализатор может сначала вычислить либо левое expr , либо правое expr в результирующем AST:

Вот почему нам нужно ввести некоторую асимметрию :

 expr -> expr '+' NUM | NUM

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

Это делает нашу операцию + левой ассоциативной , но это станет очевидным, когда мы перейдем к разделу Interpreter.

Леворекурсивные правила

К сожалению, приведенное выше исправление не решает другую нашу проблему, левую рекурсию:

 def expr() = expr() eat('+') eat(NUM)

Здесь у нас бесконечная рекурсия . Если бы мы вошли в эту функцию, то в конечном итоге получили бы ошибку переполнения стека. Но теория разбора может помочь!

Предположим, у нас есть такая грамматика, где alpha может быть любой последовательностью терминалов и нетерминалов:

 A -> A alpha | B

Мы можем переписать эту грамматику как:

 A -> BA' A' -> alpha A' | epsilon

Здесь epsilon — это пустая строка — ничего, нет токена.

Возьмем текущую версию нашей грамматики:

 expr -> expr '+' NUM | NUM

Следуя методу переписывания правил синтаксического анализа, подробно описанному выше, где alpha является нашими '+' NUM , наша грамматика принимает следующий вид:

 expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilon

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

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head

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

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

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

Если во входной строке больше токенов, то они должны выглядеть как + 123 . Вот где рекурсия в exprOpt() !

Генерация AST

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

 case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case Epsilon

Это напоминает наши правила, использующие простые классы данных.

Теперь наш парсер возвращает полезную структуру данных:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon

Для eat() , error() и других деталей реализации см. соответствующий репозиторий GitHub.

Упрощение правил

Наш нетерминал ExprOpt еще можно улучшить:

 '+' NUM exprOpt | epsilon

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

 ('+' NUM)*

Эта конструкция просто означает, что '+' NUM встречается ноль или более раз.

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

 expr -> NUM exprOpt* exprOpt -> '+' NUM

И наш AST выглядит красивее:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int)

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

Здесь нам даже не понадобился класс ExprOpt . Мы могли бы просто case class Expr(num: Int, exprOpts: Seq[Int]) или в формате грамматики NUM ('+' NUM)* . Так почему же мы этого не сделали?

Учтите, что если бы у нас было несколько возможных операторов, таких как - или * , то у нас была бы такая грамматика:

 expr -> NUM exprOpt* exprOpt -> [+-*] NUM

В этом случае AST требуется ExprOpt для размещения типа оператора:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int)

Обратите внимание, что синтаксис [+-*] в грамматике означает то же самое, что и в регулярных выражениях: «один из этих трех символов». Мы скоро увидим это в действии.

Компонент интерпретатора 3: написание интерпретатора

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

В реализации нашего примера интерпретатора мы будем использовать эту простую грамматику:

 expr -> NUM exprOpt* exprOpt -> [+-] NUM

И этот АСТ:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)

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

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

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp

Если мы проанализировали наши входные данные в AST без ошибок, мы уверены, что у нас всегда будет хотя бы один NUM . Затем мы берем необязательные числа и добавляем их к нашему результату (или вычитаем из него).

Замечание с самого начала о левой ассоциативности + теперь ясно: мы начинаем с самого левого числа и добавляем другие слева направо. Это может показаться неважным для сложения, но рассмотрим вычитание: выражение 5 - 2 - 1 оценивается как (5 - 2) - 1 = 3 - 1 = 2 , а не как 5 - (2 - 1) = 5 - 1 = 4 . !

Но если мы хотим выйти за рамки интерпретации операторов плюс и минус, нужно определить еще одно правило.

Приоритет

Мы знаем, как анализировать простое выражение, такое как 1 + 2 + 3 , но когда дело доходит до 2 + 3 * 4 + 5 , у нас возникает небольшая проблема.

Большинство людей согласны с тем, что умножение имеет более высокий приоритет, чем сложение. Но парсер этого не знает. Мы не можем просто оценить его как ((2 + 3) * 4) + 5 . Вместо этого мы хотим (2 + (3 * 4)) + 5 .

Это означает, что нам нужно сначала оценить умножение . Умножение должно быть дальше от корня AST , чтобы принудительно оценить его перед добавлением. Для этого нам нужно ввести еще один уровень косвенности.

Исправление наивной грамматики от начала до конца

Это наша исходная леворекурсивная грамматика, в которой нет правил приоритета:

 expr -> expr '+' expr | expr '*' expr | NUM

Во-первых, мы даем ему правила приоритета и устраняем его двусмысленность :

 expr -> expr '+' term | term term -> term '*' NUM | NUM

Затем он получает нелеворекурсивные правила :

 expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUM

В результате получается красиво выразительный AST:

 case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)

Это оставляет нам краткую реализацию интерпретатора:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmp

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

Следующие шаги в написании интерпретаторов

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

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

• Осциллографы и таблицы символов
• Статические типы
• Оптимизация времени компиляции
• Статические анализаторы программ и линтеры
• Форматирование кода и красивая печать
• Языки для предметной области

Для дальнейшего чтения я рекомендую эти ресурсы:

• Шаблоны языковой реализации Теренса Парра
• Бесплатная онлайн-книга Crafting Interpreters Боба Нистрома.
• Введение в грамматику и синтаксический анализ Пола Клинта
• Написание хороших сообщений об ошибках компилятора Калеб Мередит
• Заметки из курса Университета Восточной Каролины «Перевод и компиляция программ»