В этом посте я расскажу о создании простого интерпретатора Lisp, написанного на JavaScript, поддерживающего базовый синтаксис Clojure.

Инфиксные выражения и приоритет операторов

В арифметических выражениях оператор всегда помещается между операндами. Например, выражение для умножения 2, 3 и 4 будет записано следующим образом: 2 * 3 * 4. Поскольку оператор расположен между операндами, эти выражения также называются инфиксными выражениями.

Но когда в одном выражении есть разные операторы, это может привести к некоторой путанице. Возьмем, к примеру, выражение 2 * 3 + 4. Если сначала умножить 2 и 3, а затем добавить 4, результатом будет 10. Однако если сначала добавить 3 и 4, а затем умножить на 2, результатом будет 14.

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

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

Префиксные и постфиксные выражения

Ясно, что приоритет операций — это набор правил, которые необходимы, чтобы избежать путаницы, возникающей при чтении инфиксного выражения. Это делает необходимым предварительное знание приоритета оператора: если у кого-то нет предварительного знания о приоритете оператора, он не может правильно вычислить выражение. Есть ли способ представить выражения, которые не зависят от приоритета оператора для оценки?

Есть две альтернативы инфиксным выражениям: префиксные и постфиксные выражения. В префиксном выражении оператор пишется перед операндами. Таким образом, выражение 2 * 3 + 4 будет выражено как + 4 * 2 3. Это поясняет, что операцию умножения следует применять к 2 и 3, а их результат следует прибавлять к 4. Префиксное выражение устраняет любую двусмысленность в отношении применения операторов к операндам. Это устраняет необходимость разработки сложных соглашений или правил, определяющих приоритет операторов.

Подобно префиксному выражению, в постфиксном выражении оператор помещается после набора операндов. Таким образом, приведенное выше выражение будет выражено как: 2 3 * 4 +.

S-выражения

Учитывая преимущества префиксных выражений по сравнению с традиционными инфиксными выражениями, некоторые языки программирования полагаются исключительно на них для написания логики. Обычно в таких языках программирования выражения делятся на одну или несколько «частей» или «блоков». Каждая такая часть или блок будет заключена в пару круглых скобок. Такие выражения называются s-выражениями. Таким образом, s-выражение — это особый вид префиксного выражения, в котором каждая операция содержится в паре круглых скобок. Подобно арифметическим выражениям, в одном s-выражении могут быть вложенные выражения.

S-выражение по существу содержит два строительных блока: списки и атомы. атом – это основная единица выражения, которая больше не делится. Каждый атом отличается от другого с помощью пробелов. В приведенных выше примерах числа 2 3 и 4 являются атомами. Другие типы данных, такие как строки и значения boolean, также могут быть атомами. Переменная также может быть атомом.

Список относится к каждому блоку или сегменту s-выражения, заключенному в пару круглых скобок. Первый атом в списке означает функцию или оператор. Таким образом, если f представляет функцию, а args представляет ее аргументы, синтаксис списка можно представить следующим образом: (f arg1 arg2 ... argn). Следуя этому синтаксису, простой список будет (+ 1 2). Список может быть вложен в другой список. Таким образом, список может состоять из одного или нескольких атомов и/или других списков.

Вот список допустимых s-выражений:

Лисп

Lisp был первым языком программирования, использующим эту «полностью заключенную в скобки префиксную нотацию» (s-выражения). Лисп, производный от термина процессор списков, был разработан Джоном Маккарти в 1960 году. После этого появилось множество разновидностей и диалектов Лиспа. Из них Common Lisp и Clojure — два самых известных диалекта Lisp.

Clojure широко распространен в наше время, как видно из последнего Опроса Stackoverflow. Это язык программирования, построенный на основе Java, который предоставляет синтаксис Lisp для написания программ. Диалект Lisp, интерпретатор которого создается в этом проекте, частично основан на синтаксисе Clojure.

Цель

Цель этого проекта — написать крошечную версию Clojure REPL, которая может выполнять определенные основные математические операции.

REPL означает цикл чтения-оценки-печати. Это относится к интерактивной среде программирования, которая принимает ввод от пользователя, оценивает его и печатает результат. Как только результат напечатан, среда возвращается в состояние чтения, чтобы принять новые входные данные от пользователя, тем самым создавая цикл. Приглашение оболочки в системах на основе Unix похоже на REPL.

Сфера

Проект будет оценивать допустимые s-выражения. Если выражения неполные (например, незакрытые скобки) или если они не написаны в соответствии с синтаксисом s-выражения, будет отображено соответствующее сообщение об ошибке.

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

Проект также обрабатывает переменные. Для инициализации переменной следует использовать ключевое слово def. Это ключевое слово действует как оператор и принимает следующие два аргумента: имя переменной и ее значение. Вот как можно инициализировать переменные: (def nameOfVariable 9). Одна и та же переменная может быть повторно инициализирована новым значением в одном s-выражении. Кроме того, во время сеанса REPL после инициализации переменной в одном s-выражении ее можно повторно использовать в последующих s-выражениях.

S-выражение может содержать два непересекающихся s-выражения, так что в конце оценки может быть более одного результирующего значения. Например, в следующем выражении (+ 7 8) (* 1 10) есть два значения: 15 и 10. Проект реализован для отображения только самого правого результата. В приведенном выше примере будет отображаться 10.

Запуск проекта

Для запуска кода этого проекта потребуется клонировать данный репозиторий Github:

git clone [email protected]:oitee/crisp.git

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

npm install

Для запуска проекта (должен быть установлен Node.js):

npm run repl

Детали реализации

Как читаются выражения

Цель состоит в том, чтобы преобразовать входную строку (содержащую последовательность символов) в дерево, которое четко устанавливает структуру для оценки каждого списка в допустимом выражении. Это называется анализом LR. Для этого входная строка читается слева направо, не возвращаясь назад.

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

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

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

Таким образом, синтаксическое дерево будет создаваться постепенно и снизу вверх. Например, если входное выражение равно (* 1 (* 5 6) (+ 7 8 9) 10), атомы и списки будут построены следующим образом:

Сначала в стек будет помещен оператор * вместе с открывающей скобкой (. Затем будут вытолкнуты следующие атомы: 1 ( * 5 и 6. (Для простоты скобки в синтаксическом дереве не показаны).

Теперь, когда есть ), это будет означать конец текущего списка. Таким образом, будут вытолкнуты все атомы из настоящего списка, а именно 6 5 * и (. Вместо этих атомов в стек будет помещено значение (* 5 6). Синтаксическое дерево теперь будет выглядеть так:

Аналогичным образом будет выталкиваться следующий набор атомов, т. е. ( + 7 8 9 будет выталкиваться:

Опять же, наличие ) означало бы конец текущего списка. Таким образом, все атомы этого списка будут извлечены, а их результат будет помещен в стек. Наконец, будет помещен предпоследний атом, 10, а затем все оставшиеся значения в стеке будут переданы оператору умножения вместе с 1.

Теперь, когда в выражении не осталось другого элемента, возвращаемое значение этого вызова функции будет окончательным выходом, то есть 7200.

Системный дизайн

Проект можно разделить на три основных компонента:

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

Синтаксический анализатор. Компонент синтаксического анализатора анализирует каждый атом входной строки слева направо. Каждый атом хранится в структуре данных стека. Как только список сформирован, он переносит все атомы этого списка из стека в компонент вычислителя. Значение, сгенерированное оценщиком, помещается в стек.

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

Дальнейшие улучшения

Лиспы обширны и имеют много функций, которые не реализованы в этом крошечном проекте. Цель состояла в том, чтобы иметь первую версию интерпретатора Лиспа, которая могла бы выполнять основные операции. Некоторые из основных недостающих функций, которые могут быть добавлены в первую очередь:

  • Локальная область действия: хотя проект поддерживает инициализацию и повторную инициализацию переменных, он не поддерживает инициализацию локальных переменных в заданной области. Например, в Clojure ключевое слово let позволяет инициализировать локальные переменные в заданном лексическом контексте. Проект не поддерживает эту функцию.
  • Определяемые пользователем функции. Проект не поддерживает синтаксический анализ функций. Программа построена только для выполнения предопределенных операторов. Нет возможности добавлять новых операторов.

Проект размещен в этом репозитории GitHub. Запросы на вытягивание вышеупомянутых улучшений (или чего-либо еще) будут высоко оценены!

Первоначально опубликовано на https://otee.dev 24 августа 2021 г.