Раз уже подняли тему парсинга чего-бы-то-ни-было. И ЕП опубликовал табличный автомат, я поддержу бесплатное обучение и расскажу про один из самых простых способов синтаксического анализа - Метод Рекурсивного Спуска.
Синтаксический анализ рекурсивным спуском – это один из самых простых и интуитивно понятных методов разбора выражений. Он основан на непосредственном сопоставлении кода с грамматикой языка, где каждая функция соответствует определенному правилу. Это подходит только для LL-грамматик (левая рекурсия запрещена, но возможен разбор слева направо). Удобно для простых арифметических выражений, конфигурационных файлов и интерпретируемых языков.
Вот грамматика в БНФ для простых скобочных выражений, без унарного минуса и без экспоненциальной (“научной”) записи чисел.
<Выражение> ::= <Терм> { ("+" | "-") <Выражение> }
<Терм> ::= <Фактор> { ("*" | "/") <Терм> }
<Фактор> ::= <Число> | "(" <Выражение> ")"
<Число> ::= <Целая_часть> [ "." <Дробная_часть> ]
<Целая_часть> ::= <Цифра> { <Цифра> }
<Дробная_часть> ::= <Цифра> { <Цифра> }
<Цифра> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Поехали разбирать!
Спойлер
void wSpace (char *&in)
{
while (isspace(*in))
{ // Пропуск пробелов
in++;
}
}
bool wEOL (char *in)
{
if (*in == '\0')
{ // Проверка на конец строки
return true;
}
return false;
}
int wInt (char *&in)
{
int num = 0;
while (isdigit(*in))
{ // Преобразование строки в число
num = num * 10 + (*in - '0');
in++;
}
return num;
}
double wDouble (char *&in)
{
double num = 0;
while (isdigit(*in))
{ // Преобразование строки в число
num = num * 10 + (*in - '0');
in++;
}
if (*in == '.')
{
in++;
double decimal = 0.1;
while (isdigit(*in))
{ // Преобразование дробной части
num += (*in - '0') * decimal;
decimal *= 0.1;
in++;
}
}
return num;
}
Все функции я называю с первой буквой “w” потому, что я Влад. Никакой тайны. 
Вся реализация “в лоб”. Это настолько общеизвестные строки, что генерятся автоматически.
далее пишем собственно функции под правила грамматики:
Спойлер
double wExpr (char *&in)
{
if (wEOL(in))
{ // Проверка на конец строки
return 0;
}
double result = wTerm(in); // Получение первого терма
while (true)
{
wSpace(in); // Пропуск пробелов
if (*in == '+')
{
in++;
wSpace(in); // Пропуск пробелов
result += wExpr(in); // Сложение
}
else if (*in == '-')
{
in++;
wSpace(in); // Пропуск пробелов
result -= wExpr(in); // Вычитание
}
else
{
break; // Выход из цикла, если нет операций сложения/вычитания
}
}
return result;
}
double wTerm (char *&in)
{
double result = wFactor(in); // Получение первого фактора
while (true)
{
wSpace(in); // Пропуск пробелов
if (*in == '*')
{
in++;
wSpace(in); // Пропуск пробелов
result *= wTerm(in); // Умножение
}
else if (*in == '/')
{
in++;
wSpace(in); // Пропуск пробелов
result /= wTerm(in); // Деление
}
else
{
break; // Выход из цикла, если нет операций умножения/деления
}
}
return result;
}
double wFactor (char *&in)
{
double result = 0;
if (*in == '(')
{
in++;
wSpace(in); // Пропуск пробелов
result = wExpr(in); // Рекурсивный вызов для выражения в скобках
if (*in == ')')
{
in++;
}
}
else
{
result = wDouble(in); // Получение числа
}
return result;
}
Сравните правило для Выражения и функцию Wexpr().
Функция wExpr() полностью следует структуре грамматики:
- Она сначала вычисляет Терм (
wTerm(in)).
- Затем в цикле проверяет, есть ли в строке
+ или -, и, если да, рекурсивно вызывает wExpr(), выполняя сложение или вычитание.
Подобное соответствие можно увидеть и в других частях кода:
wTerm() реализует правило <Терм>, обрабатывая * и /.wFactor() соответствует <Фактор>, отличая числа от выражений в скобках.wDouble() реализует <Число>.
Такой способ написания парсера делает код структурированным и интуитивно понятным: каждая функция соответствует одному правилу грамматики, а сам разбор следует естественной рекурсивной структуре выражения.
Обратите внимание на неточность в моем коде. Он рабочий, конечно, но цикл while остался в wExpr от НЕрекурсивной реализации . То есть можно и так и этак писать. В скобочных выражениях реально рекурсия нужна только при анализе скобок, но тут я её два раза написал, просто для примера.
ну и main для всего кода, чтобы проверять.
Спойлер
int main ()
{
char input[256]; // Массив для хранения входной строки
std::cout << "Введите выражение: ";
std::cin.getline(input, 256); // Чтение строки с ограничением длины
char *in = input; // Указатель на текущую позицию в строке
double result = wExpr(in); // Вычисление выражения
std::cout << "Результат: " << result << std::endl; // Вывод результата
}
Так можно разбирать много грамматик без левой рекурсии. Собственно список страниц, который породил желание поговорить о парсерах.
Там же какая грамматика:
<Список_страниц> ::= <Диапазон> { "," <Диапазон> }
<Диапазон> ::= <Число> | <Число> "-" <Число>
<Число> ::= <Цифра> { <Цифра> }
<Цифра> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
В рекурсивной форме первое правило:
<Список_страниц> ::= <Диапазон> [ "," <Список_страниц> ]
В процессе анализа правила всегда возможно обнаружение ошибок. Причем при написании кода не в табличной форме, а рекурсивным спуском, программист в каждый момент видит в какой точке грамматики он находится и может сравнить ожидаемый следующий символ (токен, если перед синтаксическим работает лексический анализатор) и прочитанный.
Ну например, в скобочном выражении мы в функции wFactor можем обнаружить отсутствие закрывающей скобки.
Или неизвестный знак аддитивной операции в wExpt, или мультипликативной в wTerm.
Если найдутся интересующиеся люди, то попробуйте добавить унарную операцию. Хотя бы только унарный минус к этому коду. При этом возникнут вопросы, честное слово! Попробуйте самостоятельно!
в конце приведу весь код. (wExpr и wTerm без “следов” нерукурсивной реализации, моя цель была показать именно рекурсивную)
Спойлер
#include <iostream>
#include <cctype> // Для работы с isdigit и isspace
double wTerm(char *&in);
double wFactor(char *&in);
void wSpace(char *&in)
{
while (isspace(*in))
{ // Пропуск пробелов
in++;
}
}
bool wEOL(char *in)
{
if (*in == '\0')
{ // Проверка на конец строки
return true;
}
return false;
}
int wInt(char *&in)
{
int num = 0;
while (isdigit(*in))
{ // Преобразование строки в число
num = num * 10 + (*in - '0');
in++;
}
return num;
}
double wDouble(char *&in)
{
double num = 0;
while (isdigit(*in))
{ // Преобразование строки в число
num = num * 10 + (*in - '0');
in++;
}
if (*in == '.')
{
in++;
double decimal = 0.1;
while (isdigit(*in))
{ // Преобразование дробной части
num += (*in - '0') * decimal;
decimal *= 0.1;
in++;
}
}
return num;
}
double wExpr(char *&in)
{
if (wEOL(in))
{ // Проверка на конец строки
return 0;
}
double result = wTerm(in); // Получение первого терма
wSpace(in); // Пропуск пробелов
if (*in == '+')
{
in++;
wSpace(in); // Пропуск пробелов
result += wExpr(in); // Сложение
}
else if (*in == '-')
{
in++;
wSpace(in); // Пропуск пробелов
result -= wExpr(in); // Вычитание
}
return result;
}
double wTerm(char *&in)
{
double result = wFactor(in); // Получение первого фактора
wSpace(in); // Пропуск пробелов
if (*in == '*')
{
in++;
wSpace(in); // Пропуск пробелов
result *= wTerm(in); // Умножение
}
else if (*in == '/')
{
in++;
wSpace(in); // Пропуск пробелов
result /= wTerm(in); // Деление
}
return result;
}
double wFactor(char *&in)
{
double result = 0;
if (*in == '(')
{
in++;
wSpace(in); // Пропуск пробелов
result = wExpr(in); // Рекурсивный вызов для выражения в скобках
if (*in == ')')
{
in++;
}
}
else
{
result = wDouble(in); // Получение числа
}
return result;
}
int main()
{
char input[256]; // Массив для хранения входной строки
std::cout << "Введите выражение: ";
std::cin.getline(input, 256); // Чтение строки с ограничением длины
char *in = input; // Указатель на текущую позицию в строке
double result = wExpr(in); // Вычисление выражения
std::cout << "Результат: " << result << std::endl; // Вывод результата
}
Запустить можно в любой онлайн С++ среде.
Я проверил, что вот эта https://www.online-cpp.com/ открывается из РФ.
Подумал о конкурсе. Но без деанонимизации это трудно.
Я могу в меру своих возможностей заинтересовать только так, если без деанона:
Призовой фонд 20 долларов в крипте. Для простоты пусть в Биткоине. Это почти 2000 рублей по текущему курсу.
Задачи улучшения парсера максимально интересно и минимальный объем изменений.
Базовые задачи:
- Унарный минус.
- Операция возведения в степень.
- Функции, например синус, для демонстрации достаточно одной.
- переменные, тогда нужно переделать main() на работу в цикле.
- Пользовательские функции. (это уже почти Бейсик получится )
1 место $10, второе $5, третье $3, и два поощрения по $1!
Если идея зайдет, можно будет делать конкурсы сохраняя анонимность и получателя и спонсоров.