Логика работы абстрактного синтаксического дерева

Рейтинг: 0Ответов: 0Опубликовано: 24.01.2023

Цель

Создать простой математический ЯП (строчный калькулятор).

Описание

Знаю, что создание ЯП делят на 3 основных и 2 дополнительных этапа. Основные:

  • Lexer - Читает код и разбирает его на токены.
  • Parser - Создается абстрактное синтаксическое дерево из полученных токенов.
  • Evaluator - Читает и выполняет вышеупомянутое дерево.

Первую часть сделал. Мой lexer понимает цифры, операторы +, -, *, /, и скобки.
Собственно вот он - eccs0103.github.io/AEL/ (Arithmetic Extended Language).


Дальше идет создание АСД.

То есть по логике у нас должен быть некий класс Operation, который будет иметь левые и правые стороны:

class Operation {
  constructor(operator, left, right) {
    this.operator = operator;
    this.left = left;
    this.right = right;
  }
  operator;
  left;
  right;
}

И надо будет описать все эти выражения с помощью него.

const result = new Operation(`/`, new Operation(`+`, 1.2, 2.8), 0.5);

Только у меня не получается придумать логику, как все это реализовать. Если даже в линейных выражениях (выражения без скобок - 1 + 2 / 3) получается писать какой-то алгоритм, то в некоторых выражениях ничего не получается.
Как программа должна в зависимости от типа скобки менять очередь операций? Как должна проверять синтаксис и кидать ошибки? Как правильно писать эту логику в конце концов?

Вопрос

Вот, прошу помочь с логикой данной задачи.

Дополнительно

Код lexer-а можете найти тут, класс Interpreter, функция tokenize.

Ответы

Ответов пока нет.