Простой синтаксический анализ. Или выражение со скобками

WladDrakula · 30.Март.2025 13:35:00

Раз уже подняли тему парсинга чего-бы-то-ни-было. И ЕП опубликовал табличный автомат, я поддержу бесплатное обучение и расскажу про один из самых простых способов синтаксического анализа - Метод Рекурсивного Спуска.
Синтаксический анализ рекурсивным спуском – это один из самых простых и интуитивно понятных методов разбора выражений. Он основан на непосредственном сопоставлении кода с грамматикой языка, где каждая функция соответствует определенному правилу. Это подходит только для LL-грамматик (левая рекурсия запрещена, но возможен разбор слева направо). Удобно для простых арифметических выражений, конфигурационных файлов и интерпретируемых языков.

Вот грамматика в БНФ для простых скобочных выражений, без унарного минуса и без экспоненциальной (“научной”) записи чисел.

<Выражение> ::= <Терм> { ("+" | "-") <Выражение> }  
<Терм> ::= <Фактор> { ("*" | "/") <Терм> }  
<Фактор> ::= <Число> | "(" <Выражение> ")"  
<Число> ::= <Целая_часть> [ "." <Дробная_часть> ]  
<Целая_часть> ::= <Цифра> { <Цифра> }  
<Дробная_часть> ::= <Цифра> { <Цифра> }  
<Цифра> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

WladDrakula · 30.Март.2025 13:40:42

Поехали разбирать!

Спойлер

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” потому, что я Влад. Никакой тайны.
Вся реализация “в лоб”. Это настолько общеизвестные строки, что генерятся автоматически.

WladDrakula · 30.Март.2025 13:51:39

далее пишем собственно функции под правила грамматики:

Спойлер

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; // Вывод результата
}

WladDrakula · 30.Март.2025 14:00:58

Так можно разбирать много грамматик без левой рекурсии. Собственно список страниц, который породил желание поговорить о парсерах.

Там же какая грамматика:

<Список_страниц> ::= <Диапазон> { "," <Диапазон> }  
<Диапазон> ::= <Число> | <Число> "-" <Число>  
<Число> ::= <Цифра> { <Цифра> }  
<Цифра> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

В рекурсивной форме первое правило:

<Список_страниц> ::= <Диапазон> [ "," <Список_страниц> ]

WladDrakula · 30.Март.2025 14:09:08

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

Ну например, в скобочном выражении мы в функции 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/ открывается из РФ.

WladDrakula · 30.Март.2025 14:46:54

Подумал о конкурсе. Но без деанонимизации это трудно.

Я могу в меру своих возможностей заинтересовать только так, если без деанона:
Призовой фонд 20 долларов в крипте. Для простоты пусть в Биткоине. Это почти 2000 рублей по текущему курсу.

Задачи улучшения парсера максимально интересно и минимальный объем изменений.

Базовые задачи:

Унарный минус.
Операция возведения в степень.
Функции, например синус, для демонстрации достаточно одной.
переменные, тогда нужно переделать main() на работу в цикле.
Пользовательские функции. (это уже почти Бейсик получится )

1 место $10, второе $5, третье $3, и два поощрения по $1!

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

vvb333007 · 02.Апрель.2025 07:18:08

Хороший, годный текст.

От себя добавлю, что сам я перестал писать парсеры, как только освоился с flex и byacc (для тех, кто эти слова видит впервые - это генераторы анализаторов текста; на вход подаете синтаксические и прочие правила, на выходе получаете - С-код, который будет разбирать ваш синтаксис).

Для простых дел обходился флексом.

Когда что-то надо было серьезное писать (встроенный интерпретатор языка C для игрушки, для скриптования игровой логики), то добавлялся
byacc.

Может быть это для @ЕвгенийП будет хорошей идеей - сделать серию уроков по lex/yacc. Классика, как-никак.

MMM · 02.Апрель.2025 08:13:19

Пожалуй да.
Как уже отмечал в прошлой теме, писать парсер на голом Си в наше время - это нонсенс. Столько языков для синтаксического разбора…

переводить призы тоже в крипте будешь? это чтобы приз в $1 получить - придется крипту заводить?

WladDrakula · 02.Апрель.2025 09:55:34

Я предложил крипту, так как это единственный механизм, который позволит сохранить анонимность, как получателю, так и спонсору.
Альтернатива - перевод по телефону или на кошелек Телеги потребует посредника, которому будут известны обе персоны.

В первом, моем, конкурсе я, как инициатор, буду и спонсором тоже. Потом может идея понравится.
Завести себе кошелек для крипты требует ровно 1 минуты времени и не требует никаких личных данных. Это пока еще так. Про левачьё, желающее взять все платежи под контроль мы поговорим в другом месте, если будет интересно. Пока крипта достаточно анонимна .

WladDrakula · 02.Апрель.2025 10:05:28

Собственно первой мыслью и было написать пример на flex. Я давно хотел сделать по ним обзор, но подумал, что и так никто не читает сложные темы.
Что у ЕП в табличном автомате, что у меня - нет читателей.

Я первый доклад по yacc и улучшениям к нему делал в 1986 году, весной, будучи еще школьником 10 класса матшколы. На детской конференции в Дубне. Я предложил сделать табличку приоритетов операций. Я конечно знаю, что ни при чем!!! Но прикольно то, что в современных версиях давно уже есть табличка приоритетов! Я чуть большее предлагал тогда, 39 лет назад: приоритеты у лексем сделать, но то, что сегодня есть в yacc - вполне себе эквивалентно.

Выше был ответ только коллеге vvb333007. Если никто другой не понял слова выше - не страшно. Я сейчас напишу короткий вводной текст и далее скажите - хотите слушать или нет.

В отдельном посте напишу, Так потом проще будет.

MMM · 02.Апрель.2025 10:12:22

я вас обоих с удовольствием читаю, если что

WladDrakula · 02.Апрель.2025 10:37:26

Итак парсеры на Си. В далекие 70-е года Юникс был целиком детищем компании AT&T. Подразделение Bell Labs. Там были сделаны множество вещей, которые сейчас основа-основ программирования.
Среди них два пакета Lex и YACC. Генераторы лексических и синтаксических анализаторов.
Это “надстройки” над языком Си. То есть на основе программы, написанной на Lex, генератор создает код лексического анализатора и включает в него код пользователя.
Вот пример поиска в тексте слова “хрен” и заменой его на слово “редька” на flex.

%{
#include <stdio.h>
%}

%%
хрен    { printf("редька"); }
\.       { putchar(yytext[0]); }
%%

int main() {
    yylex();
    return 0;
}

Вот и вся программа. ДЛя тех, кого жизни заставила учить Перл и пХп - не составит труда разобраться в синтаксисе регулярок. Вместо слова “хрен” можно писать любую стандартную регулярку.

Далее так же коротко про yacc

WladDrakula · 02.Апрель.2025 10:50:42

YACC это “еще один компилятор компиляторов” Yet Another Compiler Compiler.
Тоже разработка и собственность БелЛабз АТиТ.
Часть кода того же калькулятора на Бизоне покажу:

%{
#include <stdio.h>
#include <stdlib.h>
%}

%token NUMBER

%%
expr: expr '+' term   { printf("+ "); }
    | term            { }
    ;
term: term '*' factor { printf("* "); }
    | factor          { }
    ;
factor: NUMBER       { printf("num "); }
    ;
%%

int main() {
    printf("Введите выражение: ");
    yyparse();
    return 0;
}

int yyerror(const char *s) {
    fprintf(stderr, "Ошибка: %s\n", s);
    return 0;
}

Это пример уже именно компилятора инфиксной нотации в постфиксную. Он должен работать в связке с Lex - на это указывает %token NUMBERS.
Как запустить и скомпилировать такую связку я покажу, если будет интерес.

В следующем посте коротко о том, почему Lex, fLex, fLex++, YACC, Bison и что это за зоопарк

WladDrakula · 02.Апрель.2025 10:58:09

Коротко - так: Lex и YACC собственность AT&T. При развитии GNU появились опенсорс альтернативы и именно они получили развитие.
Я не стану погружаться в теорию автоматов, но первые версии, еще от АТиТ, были очень простенькими. Потом появилось много алгоритмов оптимизации таблиц переходов и способов их хранения.
И синтаксический анализ тоже не стоял на месте. В Бизоне много отличий от старого Яка.
Кроме того, и это очень важно! Появился Си++ и потребовал изменения генераторов. FLex++ и Bison в паре позволяют создать современный компилятор на Си++.
Про средства генерации кода, единый промежуточный языка большого семейства компиляторов и средства оптимизации можно поговорить отдельно.

WladDrakula · 02.Апрель.2025 11:20:41

В завершении короткого цикла нужно отметить роль этих пакетов.
В настоящее время Бизон - фактический стандарт написания синтаксических анализаторов. Он поддерживает огромнейший класс LALR(1) грамматик. Фактически любой мыслимый ЯП можно разобрать с его помощью. Бизон работает в связке с Лексом. Лекс разбивает текст на последовательность токенов, а их собирает в правила грамматики - Бизон.

Для лексического анализа (разбивки на токены) сейчас практически во всех ЯП есть средства разбора регулярных выражений. Тут использовать Лекс нет необходимости.
В нашем мире - мире микроконтроллеров, лексер, порожденный Лексом, будет тяжеловат. Для ЕСП32 вероятно нормально, но для восьмибитных МК лучше делать таблицу руками и самому её оптимизировать.
Тут я посоветую внимательно разобрать пример со списком диапазонов от ЕП.
То есть если анализ текста вполне укладывается в лексер (можно разобрать через регулярные выражения), то во многих ЯП есть готовые модули или библиотеки. Ранее я писал про Дельфи. В Си++ есть куча, да хоть std::regex. И так далее. Для Ардуино тоже полно. и Regex, и tinyregex и еще много всяких.
Если желание программиста идет дальше и нужно разбить весь поток на лексемы (токены) и далее работать с грамматикой, то связка Flex+Bison даже в наше время практически безальтернативна.

WladDrakula · 02.Апрель.2025 11:38:36

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

ПОЭТОМУ я начал тему с простейшего анализа - рекурсивным спуском. Удивительно то, что можно написать интерпретатор ЯП только средствами разбора сверху вниз.
Коллега vvb333007 немного отвлек в сложную сторону.
Я хотел показать, что примитивный интерпретатор можно уложить в 300-400 строк кода. Прием неважно компилятор это или интерпретатор.

andriano · 03.Апрель.2025 18:40:31

То есть это уже завершение?
А где же начало?
Мне показалось мы еще не вышли за рамки предисловия…

Влад, тогда мне вообще непонятно, для кого ты писал:

если человек “в теме”, полагаю, ничего нового ты ему не сообщил.
если человек “не в теме”, думаю, он тебя не понял. Вероятно потому, что ты пользуешься терминологией “для тех, кто в теме”.

Мне, по крайней мере, эта терминология непонятна.
Собственно, как уже можно сделать вывод, я не в теме. Слова LEX и YACC я, конечно слышал. То утверждение, что они называются лексическим и синтаксическим анализаторами, мне тоже известно. И последнее, что я в этой области знаю, так это то, что они как-то используются при разработке компиляторов для ЯВУ.
В общем, никогда ранее этим не интересовался.
Но, прочитав твое сообщение №10, решил, что уж теперь-то ликвидирую пробел вы своем образовании.
Не тут-то было!

Далее пишу в высказанном выше предположении, что я практически ничего не понял из-за использования терминологии, ориентированной “на тех, кто в теме”.
Поэтому вопросы, касающиеся терминологии.

Что такое генератор?
Что такое лексический анализатор?
Что такое синтаксический анализатор?
Что такое “надстройка” над языком программирования? Чем она отличается, скажем, от библиотеки?

То есть на LEX можно написать программу? Ну, в принципе, если это надстройка над ЯВУ, логично.
5. А что должна делать эта программа? Каковы ее назначение и какие у нее функции?

Вот это непонятно.
То есть пользователь, чтобы LEX заработал, должен написать программу на LEX, на основе которой генератор что-то там создаст, и код пользователя, который этот генератор включит код лексического анализатора.
Что-то получается слишком много сущностей:

программа пользователя на LEX,
сам LEX,
генератор,
код лексического анализатора,
код пользователя, включаемый в созданный на основе программы пользователя в анализатор.

Как все эти сущности соотносятся друг с другом?

А зачем нужно менять одно слово на другое? Какой в этом смысл?
И что, чтобы заменить одно слово на другое, нужен целый “пакет”? Одной простенькой программы для этого недостаточно?

Единственное, что понятно из примера, что на входе (8. Кстати, на входе чего именно: LEX, генератора, анализатора, программы пользователя?) стандартного устройства ввода - текст, и на стандартном устройстве вывода - тоже текст.
Непонятно только - зачем. И как это все связано с компиляторами.

Собственно, уже видно, что отсутствие ответов на первые вопросы порождает вопросы последующие. Поэтому пока на этом остановлюсь.

WladDrakula · 03.Апрель.2025 18:50:44

Если есть хоть один читатель, я постараюсь тебе объяснить!
Задай вопросы и я избавлюсь от лишней терминологии.
Мне полезна практика преподавания.

WladDrakula · 03.Апрель.2025 20:18:16

Андриано, дорогой! Давай определимся с форматом занятий. Я сделаю смелое предположение, что это не индивидуальные, а групповые занятия.
Поэтому я не стану выяснять начальный уровень знаний.

Завтра начнем, но я попрошу самостоятельно, по доступным источникам, изучить понятия: “лексема”, “лексический анализ”, “синтаксис” и “синтаксический анализ”. И задать вопросы, которые возникли после Вики или чатЖПТ.
Утром я начну со своих определений и попытки их разъяснить, но продуктивнее будет, если я стану отвечать не на мной придуманные вопросы, а на те, что возникли при самостоятельной работе. ОК?

Если и правда тебе интересно, я рад буду рассказать то, что знаю.

Дополнительно хотелось бы знать о том, понятно ли, что такое “регулярное выражение”? Насколько нужно погружаться в эту тему?

WladDrakula · 04.Апрель.2025 10:07:04

Ок. Вопросов по основным терминам нет и понятие “регулярное выражение” знакомо всем слушателям. Примем это за основу.

Пройдусь по этим понятиям.

В математическую лингвистику и теорию формальных грамматик все эти термины пришли из обычной, гуманитарной лингвистики. И это объясняет некоторые неоднозначности в принятых определениях.
Я не стану скрупулезно следовать теоретико-множественной прозрачности определений, как в математическом анализе. “Пределом называется, такое вещественное А, что для любого эпсилон, больше ноля…” Нет, так мы работать не станем. Потому, что в разных источниках есть слегка отличающиеся определения и можно тратить кучу времени на выяснения различий или доказательство их отсутствия.

Я буду рассчитывать на здравый смысл, подготовку и самостоятельную работу слушателей. При появлении вопросов в стиле; “Ты сказал, что Луна зеленая, значит ли это наличие на ней сырной плесени?”, или “в Вики написано, одно, а в учебнике древней Греции - другое”, я с удовольствием объясню и уточню нужное.

בסדר, בואו נמשיך