Синтаксический анализ выражений методом рекурсивного спуска



В данной работе разрабатывается программный код для вычисления арифметических выражений методом рекурсивного спуска. Для понимания статьи читатель должен обладать начальными сведениями о C#: уметь компилировать и запускать приложение; знать синтаксис, основные типы данных и структуры управления.

Ключевые слова: рекурсивный спуск, синтаксический анализ, лексический анализ, арифметическое выражение.

Давайте рассмотрим следующую задачу. Пусть у нас есть строка, в которой содержится математическое выражение, например 4 + (20–3) * 2. Необходимо написать алгоритм, который вычислит значение этого выражения. Такая процедура называется синтаксический разбор выражений и является основой всех компиляторов и интерпретаторов языков, электронных таблиц и всех остальных программ, в которых требуется превращать числовые выражения в форму, понятную компьютеру.

Хоть синтаксический разбор может показаться сложным для восприятия, но является достаточно прямолинейным процессом благодаря четко определённой задаче и строгим правилам алгебры. В настоящей статье будет разработан рекурсивный нисходящий синтаксический анализатор, или синтаксический анализатор методом рекурсивного спуска (recursive-descent parser). Для этого будет использован язык программирования C#.

Для начала разберемся, что из себя представляет арифметическое выражение. У арифметических выражений, также как и у других языков, есть определённые правила, по которым они составляются. Эти правила называются грамматикой. Рассмотрим один из вариантов грамматики, который и будет использоваться для написания программы.

// Parser Rules

// expr: plus_minus^ EOF;

// plus_minus: mult_div ((‘+’ | ‘-‘) mult_div)^;

// mult_div: factor ((‘*’ | ‘/’) factor)^;

// factor: number | ‘(‘ expr ‘)’;

Здесь символ ‘^’ означает, что эта часть выражения может повторятся ноль или более раз; factor — подвыражение, которое может содержать число и/или выражение типа expr в скобках; mult_div — подвыражение, которое может содержать одно или несколько подвыражений factor , соединённых знаком умножения или деления; plus_minus — подвыражение, которое может содержать одно или несколько подвыражений mult_div , соединённых знаком сложения или вычитания; expr — выражение, которое содержит конец строки и может содержать подвыражение plus_minus (или не содержать его).

Процесс анализа выражений можно разделить на два этапа: лексический анализ (разбиение выражения на отдельные значащие единицы — лексемы) и синтаксический анализ (вычисление значения выражения по массиву лексем). Но перед этим нам потребуется несколько вспомогательных классов.

Опишем перечисление для типов лексем, которые могут встречаться в выражении. Оно будет содержать элементы, такие как LEFT_BRACKET, RIGHT_BRACKET — открывающаяся и закрывающаяся скобки, OP_PLUS, OP_MINUS, OP_MUL, OP_DIV — операции сложения, вычитания, умножения и деления, NUMBER — число, EOF — конец строки. На Рисунке 1 представлен соответствующий код.

Рис. 1. Перечисление типов лексем [создано автором]

Для хранения сведений об лексемах опишем класс, который будет содержать два поля: тип лексемы ( LexemeType ) и саму лексему в переменной строкового типа. Код представлен на Рисунке 2.

Рис. 2. Класс Lexeme [создано автором]

Сама функция лексического анализа (расположена в теле основной класса вместе с функцией Main() ), представленная на Рисунке 3, будет принимать строковую переменную с арифметическим выражением и возвращать массив лексем. В ней будем идти по строке и с помощью оператора switch() анализировать встречающиеся символы и генерировать лексемы, добавляя их в список. Эти символы можно разделить на три группы.

1) Если символ является математическим знаком, который поддерживает наша грамматика (т. е. это символы: ‘(’, ‘)’, ‘+’, ‘-’, ‘*’, ‘/’). Без дополнительных операций добавляем его в список с соответствующим типом лексемы.

2) Если символ является цифрой, то это значит, что мы начинаем считывать число. Для этого создаем переменную sb типа StringBuilder , в которую будем добавлять символы. Далее уместно использовать цикл do-while , в котором будем добавлять текущий символ в переменную sb и переходить к следующему символу в строке, пока текущий символ является цифрой, проверяя при этом не является ли он концом строки.

3) Если символ не является пробелом (пробелы игнорируем, они не несут смысловой нагрузки в нашем случае), то это посторонний символ, который не может встречаться в нашем выражении. Выводим ошибку.

Рис. 3. Функция лексического анализа [создано автором]

Необходимо написать еще один вспомогательный класс — буфер лексем, представленный на Рисунке 4. Вся информация, касаемая прохода по массиву, будет сосредоточена в нем, а именно: текущая позиция, рассматриваемой лексемы, в списке; само арифметическое выражение в виде списка лексем; метод для получения следующей лексемы; метод для изменения текущего положения назад.

Рис. 4. Класс LexemeBuffer [создано автором]

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

1) public static string expr(LexemeBuffer lexemes) — метод принимающий в качестве параметра LexemeBuffer — вычисляемую строку и возвращающий вещественное значение — результат выполнения программы, а также сообщение об ошибке типа «Пустая строка»;

2) public static double plusminus(LexemeBuffer lexemes) — метод принимающий в качестве параметра LexemeBuffer — вычисляемую строку и возвращающий вещественное значение — результат выполнения сложения или вычитания;

3) public static double multdiv(LexemeBuffer lexemes) — метод принимающий в качестве параметра LexemeBuffer — вычисляемую строку и возвращающий вещественное значение — результат выполнения умножения или деления;

4) public static double factor(LexemeBuffer lexemes) — метод принимающий в качестве параметра LexemeBuffer — вычисляемую строку и возвращающий вещественное значение — число. А также возвращает такие сообщения об ошибках как «Деление на ноль» и «Отсутствует закрывающаяся скобка».

Рис. 5. Класс синтаксического анализа [создано автором]

Для проверки демонстрации использования анализатора, напишем функцию Main(), представленную на Рисунке 6. В ней будем считывать строку с клавиатуры и выводить форматированный результат на экран.

Рис. 6. Функция Main() [создано автором]

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

32 + 16 / 2

При вызове функции exp() — входной точки анализатора — из входной строки выбирается лексема. Если она является пустой строкой, то функция выводит ошибку «Пустая строка» и завершает работу. Однако в данном случае лексемой является число 32. Поскольку это не пустая строка, вызывается функция plusminus() . В результате функция plusminus() вызывает multdiv() , а та в свою очередь вызывает factor() . Затем функция factor() может либо рекурсивно вызвать функцию exp() (в случае выражения заключенного в скобки), либо определить значение числа. В нашем случае она возвращает число 32, и управление возвращается функции plusminus() .

Затем происходит выборка следующей лексемы, которой становится оператор + и которая сохраняется в переменную lexeme , и спуск по цепочке начинается снова. Как и раньше, вызывается функция factor() , которая возвращает значение 16. В функции multdiv() считывается следующая лексема — оператор /. Аналогично возвращается последняя лексема 2 и выполняется первая арифметическая операция — деление 16 на 2. Полученный результат возвращается функции plusminus() , где выполняется сложение. В результате вычитания в ответе получается 40.

Литература:

1. Герберт Шилдт — C# 2.0. Полное руководство, 4-е изд.
2. Руководство по C# от Microsoft [Электронный ресурс] — https://docs.microsoft.com/
3. Курс лекции по дисциплине «Технологии программирования» Молчанова С. И. 2021