Недавно я столкнулся с университетским проектом, который требовал от нас написания программы, которая анализировала бы и оценивала одно выражение. Выражение может состоять из числовых литералов, а также математических операций, таких как умножение, деление, вычитание и т. д. Программа примет выражение в качестве первого аргумента и выведет вычисленный результат следующим образом.
$ ./bin/bc “10 + 4 * 3 *(2 + 1)" 46
Обратите внимание, что выражение оценивается с соблюдением обычного порядка операций, но при этом допускается использование круглых скобок, чтобы дать выражениям больший приоритет по сравнению с другими.
Чтобы решить эту проблему, я решил реализовать парсер рекурсивного спуска, который, вероятно, был немного излишним для этого проекта. Однако это была хорошая возможность лучше понять алгоритм, не прибегая к сложности полноценного синтаксического анализатора.
Программа состоит из двух основных строительных блоков: 1. токенизатора, который выдает токены по запросу синтаксического анализатора, и 2. парсера, который выводит упрощенный AST, состоящий из числовых литералов. а также следующие математические операторы.
- Дополнение (+)
- Вычитание (-)
- Разделение (/)
- Умножение (*)
- Модуль (%)
Я собираюсь использовать C для этой реализации, а исходный код доступен на Github.
Токенизатор
Как упоминалось выше, токенизатор отвечает за подачу токенов парсеру. Эти токены представляют собой структуры C, содержащие поля type и value. Ниже приведен заголовочный файл для модуля токенизатора.
tokenizerstruct помогает нам с базовой инкапсуляцией и разделением задач. Сначала мы загружаем выражение в поле tokenizer.str, вызывая метод tokenizer.load.
tokenizer.load(&tokenizer, “10 + 10”);
Затем вызов метода tokenizer.get_next_token вернет структуру token и переместит tokenizer.cursor в позицию индекса следующего числового литерала или оператора, подлежащего токенизации.
printf("%d\n", tokenizer.cursor); /* 0 */
token_t *token = tokenizer.get_next_token(&tokenizer);
printf("%ld\n", token->value); /* 10 */
printf("%d\n", tokenizer.cursor); /* 3 */
token = tokenizer.get_next_token(&tokenizer);
printf("%c\n", (char)token->value); /* + */
printf("%d\n", tokenizer.cursor); /* 5 */
Белые пробелы обрабатываются путем рекурсивного вызова get_next_token до тех пор, пока не будет достигнута позиция индекса для следующего токена. Обратите внимание на строку 20, как увеличивается позиция курсора перед рекурсивным вызовом.
Парсер
Парсер — это место, где происходит большая часть волшебства. Цель здесь состоит в том, чтобы вернуть синтаксическое дерево, в котором выражения с более высоким приоритетом расположены ближе к листьям. Рассмотрим выражение 10 + 4 * 3 * (2 + 1), дерево будет выглядеть примерно так:
Начнем с простейшего возможного выражения — одного числового литерала.
$ ./bin/bc “10"
Модуль синтаксического анализатора контролирует каждый раз, когда обслуживаются новые токены. Затем давайте передадим ссылку на структуру tokenizer в модуль синтаксического анализатора вместе с выражением для анализа.
tokenizer_t tokenizer; parser_t parser; parser.parse(&parser, &tokenizer, argv[1]);
Теперь, когда у нас есть доступ к структуре tokenizer в модуле анализатора, мы можем загрузить полное выражение в поле tokenizer->str. Модуль токенизатора теперь готов обслуживать токены.
В этой реализации используется предиктивный синтаксический анализ, который требует, чтобы синтаксический анализатор отслеживал следующий токен в очереди токенизатора. Структура парсера имеет поле parser->lookahead именно для этой цели. Позже мы увидим, как это позволит нам рекурсивно писать синтаксическое дерево от вершины (корня) к низу (конца) без необходимости возврата.
static node_t *parse(parser_t *parser, tokenizer_t *tokenizer, char *str)
{
/* load expression in the tokenizer */
tokenizer->load(tokenizer, str);
/* store next token to be parsed in the lookahead field*/
parser->lookahead = tokenizer->get_next_token(tokenizer);
return numeric_literal(tokenizer, parser);
}
Последняя строкаparser.parse возвращает результат вызоваnumeric_literal. Рассмотрим его реализацию.
Код здесь очень прост — numeric_literal вернет результат eat , который является функцией, отвечающей за потребление всех токенов в этой реализации. eat запросит у токенизатора следующий токен, загрузит его в поле toparser->lookahead и вернет узел дерева с данными из текущего токена.
Узел дерева определен в заголовке tree.h. Поля value и type используются для оценки выражения позже, а left и right являются указателями, которые позволяют нам перемещаться по дереву.
Анализ числового литерала вернет дерево с одним узлом.
node_t *root = parser.parse(&parser, &tokenizer, "10");
printf("%ld\n", root->value); /* 10 */
Двоичное выражение
Двоичные выражения, как следует из названия, состоят из двух операндов и одного оператора. Начнем с операций сложения/вычитания.
node_t *root = parser.parse(&parser, &tokenizer, "10 + 2");
Поскольку наша реализация теперь должна поддерживать двоичное выражение, нам нужно изменить код в методе parser.parse.
static node_t *parse(parser_t *parser, tokenizer_t *tokenizer, char *str)
{
tokenizer->load(tokenizer, str);
parser->lookahead = tokenizer->get_next_token(tokenizer);
return additive_expression(tokenizer, parser);
}
С этого момента я буду называть + и - аддитивными выражениями, а * , / и % - мультипликативными выражениями.
parse теперь возвращает результат функции additive_expression. Давайте посмотрим на это.
Во-первых, мы потребляем токен (10) из левой части выражения, возвращая узел дерева к указателю left. Затем мы выполняем то же самое действие точно для оператора (+) и правой (2) части. Ниже представлено полученное дерево:
Посмотрите, как additive_expression возвращает указатель left, и непосредственно перед возвратом функции мы устанавливаем operator как left внутри блока while. Таким образом, если условие в циклеwhile выполнено (т. е. у нас есть выражение), мы возвращаем корень/оператор, левый и правый узлы, иначе (т. е. у нас есть числовой литерал) возвращаем один узел.
static node_t *additive_expression(parser_t *parser, tokenizer_t *tokenizer)
{
node_t *left = multiplicative_expression(parser, tokenizer);
node_t *operator = NULL;
node_t *right = NULL;
while (parser->lookahead != NULL && parser->lookahead->type == ADDITIVE_OPERATOR)
{
operator = eat(parser, tokenizer, type);
right = multiplicative_expression(parser, tokenizer);
operator->left = left;
operator->right = right;
/* return the operator if while condition is true */
left = operator;
}
return left;
}
Цикл while также обрабатывает связанные аддитивные выражения, такие как 1 + 2 – 5, и гарантирует, что левая часть операции имеет больший приоритет при последовательном сложении и вычитании.
Прежде чем мы рассмотрим мультипликативные выражения (+, / и %), давайте рассмотрим взаимосвязь между порядком выполнения математических выражений и порядком вызова функций в нашем коде.
Как было установлено ранее, аддитивные выражения имеют самый низкий приоритет при вычислении математических выражений, поэтому функцияadditive_expression должна быть первой в цепочке вызовов функций. Функция numeric_literal, с другой стороны, выполняется всякий раз, когда мы сталкиваемся с одним числовым литералом для потребления. Тогда он имеет наивысший приоритет и, следовательно, является последним вызовом функции перед использованием токена с eat. Я также включил новую функцию под названиемprogram, которая послужит нашей точкой входа. Давайте посмотрим на код:
Обратите внимание, как первый вызов функции additive_expression выполняет функцию multiplicative_expression как для правого, так и для левого листьев, которая, в свою очередь, вызывает numerical_literal для своих собственных конечных узлов. Это рекурсивная магия этого алгоритма по своей сути.
Если бы нам нужно было разобрать выражение 10 + 20 * 2, мы бы получили такую рекурсию:
Рефакторинг
Как вы могли заметить, additive_expression и multiplicative_expression имеют очень похожий кузов. Единственное отличие состоит в том, что функция вызывает указатели left и right и условие цикла while.
Давайте реорганизуем код, чтобы у него была одна функция с именем binary_expression, которая обрабатывала бы оба случая.
Теперь мы передаем указатель на функцию, которую хотим вызвать, в качестве аргументов для binary_expression, а также token->type для условия цикла while.
Поскольку мы находимся в режиме рефакторинга, я воспользуюсь возможностью, чтобы обернуть всю нашу логику в функцию с именем expression на тот случай, если мы захотим расширить парсер для обработки присваиваний, операторов и т. д. в будущем.
Обработка скобок
Выражения в скобках должны иметь больший приоритет по сравнению с любым другим выражением. Давайте затем соответствующим образом обновим нашу диаграмму:
Обратите внимание, что мы добавили в нашу цепочку две совершенно новые функции — primary_expression и parenthesis_expression. Первый — это просто способ проверить скобки перед вызовом второго, который фактически обрабатывает выражение.
Функция parenthesis_expression сначала использует символ открывающей скобки, а затем вызывает expression для разбора выражения внутри скобки. Наконец, закрывающая скобка используется вторым вызовом eat.
С помощью приведенной выше реализации мы можем анализировать столько вложенных выражений в скобках, сколько нам нужно. Каждый раз, когда синтаксический анализатор встречает круглую скобку, он будет рекурсивно проходить через expression и обрабатывать выражение внутри.
Вы могли заметить, что eat не возвращает узел дерева. Это потому, что нам не нужны скобки в нашем дереве. Давайте соответствующим образом обновим нашу функцию eat.
Унарные выражения
Унарные операции имеют один операнд, например, факториал 4:
!4
Для этой реализации мы анализируем только положительные и отрицательные унарные операции, например:
-(+((-4)6))Поскольку на самом деле мы не вычисляем левое значение как правое, унарные операции имеют больший приоритет, чем бинарные выражения. Давайте снова обновим диаграмму приоритетов:
Реализация унарного оператора будет похожа на его бинарный аналог, но с одним операндом.
Функция uniary_expression либо найдет и проанализирует унарное выражение, возвращающее соответствующие узлы дерева, либо вызовет primary_expression. Обратите внимание, что мы возвращаем оператор в корень, а операнд всегда слева.
Оценка результата
Когда у нас есть полное синтаксическое дерево, вычисление становится довольно простым. Помните, что выражения с более высоким приоритетом располагаются в нижней части дерева. Все, что нам нужно сделать, это пройти по AST, чтобы сначала оценить листья.
Как и все рекурсивное, код выглядит обманчиво простым.
Обратите внимание, что мы оцениваем выражение после рекурсивного вызова, чтобы пройти по дереву в обратном порядке. Функция, оценивающая деление и умножение, имеет дополнительный аргумент, чтобы проверить, пытаемся ли мы разделить число на 0, и если да, то вернуть пользователю ошибку.
Заключение
Во время экспериментов с предиктивным синтаксическим анализом меня поразила элегантность и простота алгоритма. Даже с моим ограниченным опытом программиста я почувствовал себя способным расширить синтаксический анализатор, чтобы он поддерживал присваивания, операторы, блочные области видимости и, возможно, создал свой собственный язык программирования.
Что ж, возможно, это и есть следующая цель моего путешествия.
