Привет! Сегодня мы попробуем простой эвалюатор с поддержкой нескольких операций. Зачем это нужно?
Эвалюатор это подсистема, которая получает на вход текстовые данные (обычно из препроцессора) и конвертирует их в специальные стурктуры данных, для того, чтобы получить значение выражения, записанного в текстовом формате. В нашем случае, структурой данных будет абстрактное синтаксическое дерево, AST. Что такое AST?
Допустим, у нас есть выражение, 3 * (2 + 2). С точки зрения человеческой логики, порядок исчисления довольно очевиден. Однако, как нам объяснить компилятору, какие инструкции и в каком порядке необходимо сгененировать? Именно тут нам поможет дерево, как структура данных. В жизни мы используем, так называемую, инфиксную нотацию. Инфиксная нотация означает, что оператор пишется между двумя операндами, т.е. 2[операнд] +[оператор] 2[операнд].
Лирическое отступление -- инфиксная нотация не единственный способ описывать арифметику. К примеру, можно использовать обратную польскую (постфиксную) нотацию. Ее преимуществами является то, что в ней не используются скобки совсем, порядок операций всегда определен, а так же то, что вычисления в ней хорошо ложатся на архитектуру стековой машины. Однако, это тема для следующей статьи, пока сосредоточимся на парсере для инфиксной нотации.
В таком случае, попробуем подружить понятия инфиксной нотации и дерева. Любая операция всегда имеет два операнда, левый и правый. Назовем это "выражение" или "expression". Операндами выражений могут быть другие выражения, как к примеру сверху выражение (2 + 2) является операндом для выражения 3 * X. Естественным образом, мы получаем выражения, как узлы, которые имеют два дочерних узла. В таком случае, для вычисления выражения достаточно пройти по дереву снизу вверх, и мы всегда получим правильный результат. Числа, константы, тоже являются выражением, самым простым. Вычисление этого выражения просто возвращает эту константу.
Нарисуем дерево вычислений для выражения 3 * (2 + 2):
В таком случае, для вычисления выражения, нам достаточно пройти по дереву и вызвать вычисления на каждом узле, слева направо.
1. Корневой узел -- умножение, вычисляем левое выражение.
2. Левое выражение, узел константы, вычисление возвращает 3.
3. Поднимаемся наверх, начинаем вычислять правое выражение.
4. Это узел -- сложение, вычисляем левое выражение.
5. Левое выражение, узел константы, вычисление возвращает 2.
6. Поднимаемся наверх, начинаем вычислять правое выражение.
7. Правое выражение, узел константы, вычисление возвращает 2.
8. Вычислили оба выражения, выполняем сложение, получаем 4.
9. Вычислили оба выражения, выполняем умножение, получаем 12, итоговое значение.
Теперь рассмотрим имплементацию этих концепций на C#.
Для того, чтобы данные могли попасть в парсер, нам нужно построить просто лексер. Лексер -- это просто обертка над тестовым буффером, которая определяет несколько служебных функций:
1. void SkipWhiteSpace() -- пропускает все пробельные символы до следующего непробельного
2. bool TryReadInt(out int res) -- возвращает true и значение числа в res, если текущий токен является числом, false, если токен не является числом
3. bool TryReadChar(char expected) -- возвращает true, если следующий токен равен ожидаемому, иначе false
Не будем подробно останавливаться на имплементации этой подсистемы, исходный код можно увидеть тут -- тык.
Продолжим с базовым классом Node -- узел, абстракное выражение. Все остальные операции будут наследоваться от него.
public interface Node
{
Node Left { get; }
Node Right { get; }
int Compute();
}
Мы определяем левое правое дочернее выражение, и функцию Compute(), которая должна возвращать результат данного выражения. Определим подмножество операций, которые мы имплементируем в рамках данного проекта:
1. Число, константа
2. +, сложение
3. -, вычитание
4. *, умножение
5. /, деление
6. >> <<, битовые сдвиги
7. ^, исключающее ИЛИ
8. &, логичское И
9. |, логическое ИЛИ
Определим классы узлов для каждой операции. Учтем, что при вычислении значений, мы будем вызывать Compute() на левом и правом узле. Таким образом, мы автоматически имплементируем правильную логику обхода дерева для вычисления итогового выражения.
public class IntNode : Node
{
public int Value { get; }
public Node Left => null;
public Node Right => null;
public IntNode(int value) => Value = value;
public int Compute() => Value;
}
public class PlusNode : Node
{
public Node Left { get; }
public Node Right { get; }
public PlusNode(Node left, Node right)
{
Left = left;
Right = right;
}
public int Compute() => Left.Compute() + Right.Compute();
}
public class MinusNode : Node
{
public Node Left { get; }
public Node Right { get; }
public MinusNode(Node left, Node right)
{
Left = left;
Right = right;
}
public int Compute() => Left.Compute() - Right.Compute();
}
public class MulNode : Node
{
public Node Left { get; }
public Node Right { get; }
public MulNode(Node left, Node right)
{
Left = left;
Right = right;
}
public int Compute() => Left.Compute() * Right.Compute();
}
public class DivNode : Node
{
public Node Left { get; }
public Node Right { get; }
public DivNode(Node left, Node right)
{
Left = left;
Right = right;
}
public int Compute() => Left.Compute() / Right.Compute();
}
public class BitwiseShiftNode : Node
{
public Node Left { get; }
public Node Right { get; }
public bool RightDirection { get; }
public BitwiseShiftNode(Node left, Node right, bool rightDir = true)
{
Left = left;
Right = right;
RightDirection = rightDir;
}
public int Compute() => RightDirection
? Left.Compute() >> Right.Compute()
: Left.Compute() << Right.Compute();
}
public class AndNode : Node
{
public Node Left { get; }
public Node Right { get; }
public AndNode(Node left, Node right)
{
Left = left;
Right = right;
}
public int Compute() => Left.Compute() & Right.Compute();
}
public class XorNode : Node
{
public Node Left { get; }
public Node Right { get; }
public XorNode(Node left, Node right)
{
Left = left;
Right = right;
}
public int Compute() => Left.Compute() ^ Right.Compute();
}
public class OrNode : Node
{
public Node Left { get; }
public Node Right { get; }
public OrNode(Node left, Node right)
{
Left = left;
Right = right;
}
public int Compute() => Left.Compute() | Right.Compute();
}
Осталось только реализовать сам парсер. Порядок операций определяется естественным образом, мы предполагаем, что узел является следующим по порядку операций, но если мы определям правильный оператор при помощи лексера, мы считаем, что текущее выражение является нужным узлом. Добавим служебные функции Parse(), которая конструирует AST дерево и отдает корневой элемент, и Evaluate(), которая вычисляет значение текущего выражения. Исходный код можно увидеть тут -- тык.
Тесты для итогового проекта -- тык . Можно увидеть, что даже такие выражения, как (4200 & 39 + 313000 & 255 >> 1 & 70) | 32 ^ 15 & 10 + 3 << 2 вычисляются так же, как это происходит при использовании стандартного эвалюатора C#.
