Создание собственного языка программирования с нуля: часть II — двухстековый алгоритм Дейкстры

1. Введение

В этой статье мы улучшим вычисление математических выражений для нашего языка программирования (см. [Часть I] (https://hackernoon.com/building-your-own-programming-language-from-scratch)) с использованием алгоритма двух стеков Дейкстры. . Суть этого алгоритма в том, что любое сложное выражение в конечном итоге сводится к простому выражению. В конце концов, это будет унарная или бинарная операция над одним/двумя операндами.

Как работает алгоритм двух стеков Дейкстры:

• Мы повторяем выражение токенов

• Если наш токен является операндом (например, числом), мы помещаем его в стек операндов

• Если мы находим оператор, мы помещаем его в стек операторов

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

• Если обнаружена открывающая скобка, мы помещаем ее в стек операндов.

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

Пример

Предположим, у нас есть следующее выражение: 2 * (3 + 4) - 5. Когда мы сначала вычисляем это выражение, мы суммируем «3» и «4» в скобках. После этого умножаем результат на 2. И в конце мы вычитаем из результата 5. Ниже приведена оценка выражения с использованием алгоритма двух стеков Дейкстры:

1. Поместите 2 в стек операндов:

1. Отправьте * операторам:

1. Вставьте ( в операнды:

1. Вставьте 3 в операнды:

1. Нажмите + для операторов:

1. Нажмите 4 для операндов:

1. Отправьте ) операторам. Закрывающая скобка извлекает операцию до ближайшей открывающей скобки (. Поэтому мы извлекаем top оператор и применяем его к двум верхним операндам:

1. Нажмите - для операторов. Верхний элемент стека операторов * имеет больший приоритет, чем текущий оператор -. Поэтому сначала мы применяем оператор top к двум главным операндам:

1. Вставьте 5 в операнды:

1. Вытолкнуть левый оператор -:

2 оператора

Давайте углубимся в код. Во-первых, мы обновим наше перечисление Operator, включая приоритет операторов, и введем несколько новых операторов:

```java

@RequiredArgsConstructor

@Геттер

оператор публичного перечисления {

Не("!", NotOperator.class, 5),

StructureValue("::", StructureValueOperator.class, 5),

Дополнение("+", AdditionOperator.class, 3),

Вычитание ("-", SubtractionOperator.class, 3),

МеньшеЧем("<", МеньшеЧемОператор.класс, 2),

GreaterThan(">", GreaterThanOperator.class, 2);

закрытый конечный символ строки;

частный окончательный класс<? расширяет тип OperatorExpression>;

private final Целочисленный приоритет;

Оператор (Строковый символ, Целочисленный приоритет) {

это (символ, ноль, приоритет);

общедоступный статический оператор getType (строковый символ) {

вернуть Arrays.stream (значения ())

.filter(t -> Objects.equals(t.getCharacter(), символ))

.findAny().orElse(null);

общественный логический больше чем (оператор o) {

вернуть getPrecedence().compareTo(o.getPrecedence()) > 0;

```java

открытый класс StatementParser {

частное выражение readExpression() {

в то время как (заглянуть (TokenType.Operator)) {

Операция токена = следующая (TokenType.Operator);

Оператор operator = Operator.getType(operation.getValue());

Класс<? расширяет OperatorExpression> operatorType = operator.getType();

2.1 Структурный экземпляр

Мы больше не будем отмечать new как лексему ключевого слова, это будет оператор, который поможет нам создать экземпляр объекта структуры внутри более сложного выражения:

```java

общественное перечисление TokenType {

Keyword("(if|then|end|print|input|struct|arg)"),

Оператор("(\+|\-|\>|\<|\={1,2}|\!|\:{2}|новый)");

Ставим ему наивысший приоритет:

```java

оператор публичного перечисления {

StructureInstance("новый", StructureInstanceOperator.class, 5),

```java

открытый класс StructureInstanceOperator расширяет UnaryOperatorExpression {

public StructureInstanceOperator (значение выражения) {

супер(значение);

@Override

public Value<?> calc(Value<?> value) {

возвращаемое значение; //вернет значение toString()

2.2 Умножение и деление

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

```java

общественное перечисление TokenType {

Оператор("(\+|\-|\>|\<|\={1,2}|\!|\:{2}|новый|\*|\/) ");

```java

оператор публичного перечисления {

Умножение ("*", MultiplicationOperator.class, 4),

Дивизион("/", ДивизионОператор.класс, 4),

2.3 Параметр LeftParen и RightParen

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

```java

общественное перечисление TokenType {

Оператор("(\+|\-|\>|\<|\={1,2}|\!|\:{2}|новый|\*|\/| \(|\))");

```java

оператор публичного перечисления {

ЛеваяПарен("(", 1),

ПравыйПарен(")", 1),

2.4 Назначение

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

```java

оператор публичного перечисления {

Назначение("=", AssignmentOperator.class, 6),

```java

открытый класс AssignOperator расширяет BinaryOperatorExpression {

public AssignOperator (выражение слева, выражение справа) {

супер(слева, справа);

@Override

public Value<?> calc(Value<?> слева, Value<?> справа) {

if (getLeft() instanceof VariableExpression) {

((VariableExpression) getLeft()).setValue(right);

вернуться влево;

Во время выполнения мы ожидаем получить левое выражение как VariableExpression — переменную, которой мы присваиваем значение. Таким образом, мы вводим новый метод в наше VariableExpression для установки значения переменной. Как вы помните, наша карта переменных хранится в StatementParser. Чтобы установить доступ к нему и установить новое значение, мы вводим экземпляр BiConsumer, передавая имя переменной в качестве ключа и значение переменной в качестве нового значения:

```java

открытый класс VariableExpression реализует Expression {

частный окончательный BiConsumer<String, Value<?>> setter;

public void setValue(Value<?> value) {

setter.accept(имя, значение);

```java

открытый класс StatementParser {

частное выражение nextExpression() {

вернуть новое ВыражениеПеременной(значение, переменные::получить, переменные::поместить);

2.5 Разделители выражений

2.5.1 Конец строки

Раньше для построения математического выражения мы ожидали получить оператор после каждого операнда:

```java

Выражение слева = следующееВыражение();

// рекурсивно читаем выражение

в то время как (заглянуть (TokenType.Operator)) {

Операция токена = следующая (TokenType.Operator);

Оператор operator = Operator.getType(operation.getValue());

Класс<? расширяет OperatorExpression> operatorType = operator.getType();

if (BinaryOperatorExpression.class.isAssignableFrom(operatorType)) {

Выражение справа = следующееВыражение();

слева = тип оператора

.getConstructor(Выражение.класс, Выражение.класс)

.newInstance (слева, справа);

} else if (UnaryOperatorExpression.class.isAssignableFrom(operatorType)) {

слева = тип оператора

.getConstructor(выражение.класс)

.новый экземпляр (слева);

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

``рубин

стоимость + новый автомобиль ["E30" "325i"] :: модель

или

( ( 1 + 2) * 3) - 4

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

```java

открытый класс StatementParser {

Разрыв строки("[\
\r]"),

Пробел ("[\s\t]"),

2.5.2 Аргументы структуры

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

```java

новый автомобиль ["E30" "325i" новый двигатель ["M20B25"] :: модель ]

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

```java

общественное перечисление TokenType {

Разделитель("(\[|\]|\,)"),

``рубин

новый автомобиль ["E30", "325i", новый двигатель ["M20B25"] :: модель ]

3 Оценка выражения

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

3.1 Следующий токен

Во-первых, мы введем метод skipLineBreaks(), который будет увеличивать позицию токена, когда мы достигаем токена LineBreak:

```java

частная пустота skipLineBreaks () {

в то время как (tokens.get(position).getType() == TokenType.LineBreak

&& ++position != tokens.size()) ;

Он будет использоваться поверх каждого метода next() и peek(), чтобы избежать перехвата токена LineBreak:

```java

частный токен следующий (тип TokenType, типы TokenType...) {

пропуститьРазрывыЛинии();

частный токен следующий (тип TokenType, строковое значение) {

пропуститьРазрывыЛинии();

частный логический просмотр (тип TokenType, содержимое String) {

пропуститьРазрывыЛинии();

частный логический просмотр (тип TokenType) {

пропуститьРазрывыЛинии();

Мы также переопределим метод next() без каких-либо аргументов, просто вернув следующий токен:

```java

частный токен следующий () {

пропуститьРазрывыЛинии();

вернуть tokens.get(position++);

3.2 ExpressionReader

Чтобы прочитать и вычислить выражение целиком с помощью алгоритма двух стеков Дейкстры, нам понадобятся два стека: стек операторов и стек операндов. Первый стек операторов будет содержать типы перечисления Operator. Второй стек операндов будет иметь тип «Выражение», он поможет нам хранить все типы выражений, включая значения, переменные и составные операторы. Будет понятнее, если мы выполним чтение выражения в отдельном внутреннем классе ExpressionReader:

```java

частный класс ExpressionReader {

закрытые окончательные операнды Stack;

приватные конечные операторы Stack;

частный ExpressionReader() {

this.operands = новый стек<>();

this.operators = новый стек<>();

Затем мы создаем метод readExpression() с циклом while для чтения всего выражения. Наше математическое выражение может начинаться с типов токенов «Оператор», «Переменная», «Числовой», «Логический» или «Текст». В этом случае мы не можем исключить токен LineBreak во время извлечения токена, потому что этот токен означает конец выражения. Поэтому мы вводим дополнительный метод peek() внутри нашего внутреннего класса, который будет читать выражение до тех пор, пока мы не достигнем конца строки:

```java

частный класс ExpressionReader {

частное выражение readExpression() {

в то время как (заглянуть (TokenType.Operator, TokenType.Variable, TokenType.Numeric, TokenType.Logical, TokenType.Text)) {

Токен токен = следующий();

переключатель (токен.getType()) {

кейс Оператор:

По умолчанию:

частный логический просмотр (тип TokenType, типы TokenType...) {

TokenType[] tokenTypes = ArrayUtils.add(типы, тип);

если (позиция < tokens.size()) {

Токен токен = tokens.get(position);

return Stream.of(tokenTypes).anyMatch(t -> t == token.getType());

вернуть ложь;

3.2.1 Оператор

Первый тип лексемы, который мы будем обрабатывать, это Оператор. Мы получаем перечисление Operator по значению токена и используем его в блоке switch. Есть 3 случая, с которыми мы будем иметь дело:

1. LeftParen - просто поместите оператор в стек операторов

1. RightParen - вычисляем ранее введенные выражения, пока не достигнем левой круглой скобки LeftParen.

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

```java

кейс Оператор:

Оператор operator = Operator.getType(token.getValue());

переключатель (оператор) {

случай LeftParen:

operator.push(оператор);

перерыв;

случай RightParen:

//пока левая скобка не будет достигнута

в то время как (!operators.empty() && operator.peek() != Operator.LeftParen)

применитьВерхнийОператор();

операторы.поп(); // открываем левую скобку

перерыв;

По умолчанию:

//до тех пор, пока верхний оператор не будет иметь больший приоритет

в то время как (!operators.isEmpty() && operator.peek().greaterThan(оператор))

применитьВерхнийОператор();

operator.push(оператор); // наконец, добавляем оператор с меньшим приоритетом

перерыв;

Чтобы применить верхний оператор к верхнему операнду(ам), мы создаем дополнительный метод applyTopOperator(). Сначала мы извлекаем оператор и первый операнд. Затем, если наш оператор бинарный, мы извлекаем второй операнд. Чтобы создать объект OperatorExpression, мы извлекаем подходящий конструктор для реализации унарного или бинарного оператора и создаем экземпляр с ранее извлеченными операндами. В конце мы помещаем экземпляр OperatorExpression в стек операндов. Таким образом, этот операнд Выражение может быть использован позже другими операторами внутри более сложного выражения:

```java

@SneakyThrows

частная пустота applyTopOperator() {

// например а + б

Оператор operator = operator.pop();

Класс<? расширяет OperatorExpression> operatorType = operator.getType();

Выражение слева = операнды.pop();

if (BinaryOperatorExpression.class.isAssignableFrom(operatorType)) {

Выражение справа = операнды.pop();

операнды.push(operatorType

.getConstructor(Выражение.класс, Выражение.класс)

.newInstance(справа, слева));

} else if (UnaryOperatorExpression.class.isAssignableFrom(operatorType)) {

// например новый экземпляр []

операнды.push(operatorType

.getConstructor(выражение.класс)

.новый экземпляр (слева));

} еще {

throw new SyntaxException(String.format("Оператор %s не поддерживается", operatorType));

3.2.2 Значение и выражение переменной

Если наш токен является переменной или литералом, мы преобразуем его в соответствующий объект «Выражение» внутри следующего блока переключателей, а затем помещаем результат в стек операндов:

```java

По умолчанию:

Строковое значение = token.getValue();

операнд выражения;

переключатель (токен.getType()) {

случай Числовой:

операнд = новое числовое значение (Integer.parseInt (значение));

перерыв;

случай Логический:

операнд = новое логическое значение (логическое значение. значение из (значение));

перерыв;

кейс Текст:

операнд = новое TextValue (значение);

перерыв;

case Переменная:

По умолчанию:

if (!operators.isEmpty() && operator.peek() == Operator.StructureInstance) {

операнд = readInstance (маркер);

} еще {

операнд = новое ВыражениеПеременной(значение, переменные::получить, переменные::поместить);

операнды.push(операнд);

Токен переменной также может указывать на начало создания экземпляра структуры. В этом случае мы читаем целое структурное выражение с аргументами в квадратных скобках и только потом присваиваем его значению StructureExpression. Мы переместим существующий метод readInstance() из класса StatementParser во внутренний класс ExpressionReader со следующими изменениями:

```java

частное выражение readInstance (маркер токена) {

Определение StructureDefinition = Structures.get(token.getValue());

Аргументы List = new ArrayList<>();

если (StatementParser.this.peek(TokenType.GroupDivider, "[")) {

следующий (TokenType.GroupDivider, "["); //пропустить открытую квадратную скобку

в то время как (!StatementParser.this.peek(TokenType.GroupDivider, "]")) {

Значение выражения = new ExpressionReader().readExpression();

аргументы.добавить (значение);

если (StatementParser.this.peek(TokenType.GroupDivider, ","))

следующий();

следующий(TokenType.GroupDivider, "]"); //пропустить закрывающую квадратную скобку

если (определение == ноль) {

throw new SyntaxException(String.format("Структура не определена: %s", token.getValue()));

вернуть новое СтруктурноеВыражение(определение, аргументы, переменные::получить);

3.2.3 Оценка

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

```java

частное выражение readExpression() {

в то время как (!operators.isEmpty()) {

применитьВерхнийОператор();

вернуть операнды.pop();

3.3 Заявление об присвоении

Теперь мы можем построить AssignmentStatement в методе parseExpression(). AssignStatement может начинаться с типа токена Variable или Operator (в случае, если у нас есть new оператор для создания экземпляра структуры). Когда мы читаем выражение, мы ожидаем прочитать все выражение «Присвоение», накапливая левое значение в качестве имени переменной и правое выражение в качестве значения переменной. Поэтому мы идем на одну позицию токена назад и начинаем читать выражение с помощью ExpressionReader, начиная с объявления имени переменной:

```java

частное выражение parseExpression() {

Token token = next(TokenType.Keyword, TokenType.Variable, TokenType.Operator);

переключатель (токен.getType()) {

case Переменная:

кейс Оператор:

позиция--;

Значение выражения = new ExpressionReader().readExpression();

чехол Ключевое слово:

По умолчанию:

В конце мы ожидаем получить полный AssignmentOperator, и мы можем создать экземпляр AssignmentStatement:

```java

case Переменная:

кейс Оператор:

позиция--;

Значение выражения = new ExpressionReader().readExpression();

если (значение instanceof AssignmentOperator) {

VariableExpression variable = (VariableExpression) ((AssignmentOperator) value).getLeft();

вернуть новый AssignmentStatement(variable.getName(), ((AssignmentOperator) value).getRight(), variable::put);

} еще {

throw new SyntaxException(String.format("Неподдерживаемый оператор: %s", значение));

Последнее, что нам нужно сделать, это обновить чтение выражений для операторов input и if, используя наш новый внутренний класс ExpressionReader. Это позволит нам читать сложные выражения внутри операторов print и if:

```java

чехол Ключевое слово:

По умолчанию:

переключатель (токен.getValue()) {

случай "печать":

Выражение выражения = new ExpressionReader().readExpression();

случай "если":

Условие выражения = new ExpressionReader().readExpression();

4 Подведение итогов

В этой статье мы улучшили наш собственный язык программирования с вычислением математических выражений с использованием алгоритма двух стеков Дейкстры. Мы внедрили приоритет операторов с возможностью его изменения с помощью круглых скобок, в том числе с помощью сложных экземпляров структуры. Полный исходный код доступен [на GitHub] (https://github.com/alexandermakeev/toy-language).