Парсер для арифметико-логических выражений
Парсер, выполняющий разбор арифметико-логических выражений, можно назвать фундаментальным, поскольку именно он должен обеспечить корректность выполнения вычислений в программе. Реализация этого парсера примечательна тем, что использует алгоритм преобразования арифметико-логического выражения в «обычной» (инфиксной) форме в выражение в постфиксной форме для упрощения дальнейшего построения дерева для этого выражения. Этот алгоритм основан на использовании стека для эффективной работы с выражением.
Стек – схема запоминания информации, при которой каждый вновь поступающий ее элемент как бы «проталкивает» вглубь отведенного участка памяти находящиеся там элементы и занимает крайнее положение (так называемую вершину стека). При выдаче информации из стека выдается элемент, расположенный в вершине стека, а оставшиеся элементы продвигаются к вершине; следовательно, элемент, поступивший последним, выдается первым.
Алгоритм
Теперь приведем подробный алгоритм по переводу выражения из инфиксной формы в постфиксную:
На вход алгоритму подается список токенов, содержащий арифметико-логическое выражение в инфиксной форме (считаем, что выражение верное – каждый символ является либо оператором, либо операндом).
Входной список просматривается слева направо от начала до конца. Токены попадают в один из стеков: стек №1 (для операций) или стек №2 (для операндов и операций). На i-м шаге от 1 до N, где N – длина списка токенов, относящихся к выражению (под текущим токеном будем понимать i-й элемент списка):
если текущий токен – операнд, то кладем его в стек №2;
если текущий токен – открывающая скобка, то кладем его в стек №1;
если текущий токен – закрывающая скобка, то последовательно перекладываем операции из стека №1 в стек №2 до тех пор, пока не встретим токен – открывающую скобку, после чего удаляем его из стека №1;
если текущий токен – оператор, то, в случае если приоритет соответствующей ему операции больше либо равен приоритету операции, находящейся на вершине стека №1, кладем ее в стек №1, иначе перекладываем более приоритетные либо равные по приоритету операции из стека №1 в стек №2.
После прохождения N шагов в пункте 2 необходимо переложить все токены из стека №1 в стек №2.
В результате в стеке №2 будет находиться арифметическое выражение в постфиксной форме, причем в обратном порядке – при извлечении токенов необходимо записывать их в список, начиная с его конца.
Приоритет операций
В описании алгоритма были упомянуты приоритеты операций. Для корректности каждой операции были сопоставлены некоторые целые неотрицательные числа, использующиеся для сравнения двух любых операций следующим образом: если число, соответствующее первой операции, меньше числа, соответствующего второй операции, то приоритет первой операции считается выше приоритета второй операции. Операции, которым соответствуют равные числа, имеют одинаковый приоритет и должны вычисляться слева направо в случае инфиксной формы записи выражения. В текущей реализации парсера используются значения из следующей таблицы.
Значение |
Операции |
|---|---|
10 |
Умножение, деление, вычисление остатка от деления |
20 |
Сложение, вычитание |
30 |
Меньше, меньше или равно, больше, больше или равно, равно, не равно |
40 |
Логическое «и» |
50 |
Логическое «или» |
60 |
Присваивание |
Построение дерева для выражения
Полученное таким способом выражение в постфиксной форме довольно удобно использовать впоследствии для построения дерева. Опишем используемый алгоритм, полагая, что изначально текущим узлом синтаксического дерева является «корневой» узел выражения, то есть, узел с типом «выражение», а текущим токеном – элемент на вершине стека №2, то есть, добавленный в него в последнюю очередь. Итак, пока стек не пуст, выполняется следующее:
Если текущий токен – бинарный оператор, то в начало списка потомков текущего узла добавляется узел типа «бинарная операция» со значением конкретной операции в зависимости от оператора, и этот новый узел становится текущим.
Если текущий токен – операнд, то:
если это идентификатор, то считается, что это имя переменной, и в начало списка потомков текущего узла добавляется узел типа «имя переменной» с идентификатором в качестве значения;
если это целочисленный литерал, то в начало списка потомков текущего узла добавляется узел типа «целочисленный литерал» с соответствующим числовым значением;
если это дробный литерал с плавающей точкой, то в начало списка потомков текущего узла добавляется узел типа «дробный литерал с плавающей точкой» с соответствующим числовым значением;
если это строковый литерал, то в начало списка потомков текущего узла добавляется узел типа «строковый литерал» с соответствующим значением;
Верхний элемент стека извлекается, и текущим вновь становится токен на вершине.
Понятие составного операнда
Особенностью описываемого парсера является то, что помимо обычных операндов, состоящих из одного токена, арифметико-логическое выражение может содержать вызовы функций. Поэтому приведенные в этом разделе алгоритмы были расширены с помощью обобщенного понятия «составной операнд». Полагается, что составной операнд является операндом и может содержать одну из двух структур:
токен, если в качестве операнда не предполагается подстановка результата вызова функции;
заранее созданный узел, являющийся результатом разбора подвыражения, состоящего из вызова функции, в противном случае.
Таким образом, если при построении постфиксной формы был встречен идентификатор с непосредственно следующим за ним оператором «открывающая круглая скобка», то считается, что в этом месте начинается подвыражение с вызовом функции. Парсер выполняет поиск конца подвыражения (соответствующую закрывающую круглую скобку с учетом вложенности), получает список выражений – аргументов функции и рекурсивно вызывает построение постфиксной формы и дерева выражения для каждого из них. После этого все «корневые» узлы этих выражений объединяются под родительским узлом типа «аргументы функции», который, в свою очередь попадет в новый узел «вызов функции». Этот узел объявляется составным операндом и кладется в стек при построении постфиксной формы наряду с другими составными операндами и остальными токенами, содержащимися в выражении с вызовом функции.