Правильное построение AST в C

Я пытаюсь реализовать анализатор математических выражений, который получает строку в качестве входных данных и в конечном итоге выводит условное представление на консоль. Я уже реализовал аналогичную рабочую программу на Python:

def term(self):
     result = self.factor()
     while self.current_token.type in (MUL, DIV):
         token = self.current_token
         if token.type == MUL:
             self.eat(MUL)
             result = result * self.factor()
         elif token.type == DIV:
             self.eat(DIV)
             result = result / self.factor()  

Но сейчас из-за моей неопытности в языке C у меня возникли некоторые проблемы. Я приложил эскиз будущей программы, и в нем меня интересует функция parser_term.

AST_T* parser_term(Parser_T* parser) {
    AST_T* result;

    while (parser->current_token->type == TOKEN_MUL
           || parser->current_token->type == TOKEN_DIV) {
        if (parser->current_token->type == TOKEN_MUL) {
            parser_eat(parser, TOKEN_MUL);
        } else if (parser->current_token->type == TOKEN_DIV) {
            parser_eat(parser, TOKEN_DIV);
        }
    }

    return result;
}

Как мне создать новый узел бинарной операции? Возможно, это несколько глупый вопрос, но я надеюсь, что вы поможете мне разобраться.

Я также буду рад, если вы укажете мне на другие ошибки, которых может быть достаточно в моем коде.

Полный код:

#include <stdio.h>
#include <stdlib.h>

//============================ LEXICAL ANALYSIS ============================================

//---------------------------- Token -------------------------------------------------------
typedef struct TOKEN_STRUCT
{
    enum
    {
        TOKEN_INTEGER,
        TOKEN_PLUS, TOKEN_MINUS,
        TOKEN_MUL,  TOKEN_DIV,
        TOKEN_LBRA, TOKEN_RBRA,
        TOKEN_EOF
    } type;

    char* value;

} Token_T;

Token_T* init_token(int type, char* value)
{
    Token_T* token = calloc(1, sizeof(struct TOKEN_STRUCT));
    token->type = type;
    token->value = value;

    return token;
}

void token_debug_print(Token_T* token)
{
    printf(
        "Token( type: '%d', value: '%s' )\n",
        token->type, token->value
    );

}
//------------------------------------------------------------------------------------------

//---------------------------- Lexer -------------------------------------------------------
typedef struct LEXER_STRUCT
{
    char current_char;
    unsigned int position;
    char* content;

} Lexer_T;

Lexer_T* init_lexer(char* content)
{
    Lexer_T* lexer = calloc(1, sizeof(struct LEXER_STRUCT));
    lexer->content = content;
    lexer->position = 0;
    lexer->current_char = lexer->content[lexer->position];

    return lexer;
}

void lexer_advance(Lexer_T* lexer)
{
    if (lexer->current_char != '\0')
    {
        lexer->position += 1;
        lexer->current_char = lexer->content[lexer->position];
    }
}

void lexer_skip_whitespace(Lexer_T* lexer)
{
    while (lexer->current_char == ' ')
    {
        lexer_advance(lexer);
    }
}

char* lexer_get_current_char_as_string(Lexer_T* lexer)
{
    char* stringus = calloc(1, sizeof(char));
    stringus[0] = lexer->current_char;
    stringus[1] = '\0';

    return stringus;
}

Token_T* lexer_get_digit(Lexer_T* lexer)
{
    char* lexem = calloc(1, sizeof(char));
    lexem[0] = '\0';

    while (lexer->current_char >= '0' && lexer->current_char <= '9')
    {
        char* part = lexer_get_current_char_as_string(lexer);
        lexem = realloc(lexem, (strlen(lexem) + strlen(part) + 1) * sizeof(char));
        strcat(lexem, part);
        lexer_advance(lexer);

    }

    return init_token(TOKEN_INTEGER, lexem);
}

Token_T* lexer_get_op(Lexer_T* lexer)
{
    switch (lexer->current_char)
    {
        case '+':
            lexer_advance(lexer);
            return init_token(TOKEN_PLUS, "+");

        case '-':
            lexer_advance(lexer);
            return init_token(TOKEN_MINUS, "-");

        case '*':
            lexer_advance(lexer);
            return init_token(TOKEN_MUL, "*");

        case '/':
            lexer_advance(lexer);
            return init_token(TOKEN_DIV, "/");
    }
}

Token_T* lexer_get_next_token(Lexer_T* lexer)
{
    while (lexer->current_char != '\0')
    {
        if (lexer->current_char == ' ')
            lexer_skip_whitespace(lexer);

        else if (lexer->current_char >= '0' && lexer->current_char <= '9')
            return lexer_get_digit(lexer);

        else if (lexer->current_char == '+' || lexer->current_char == '-' ||
                 lexer->current_char == '*' || lexer->current_char == '/')
            return lexer_get_op(lexer);

        else if (lexer->current_char == '(')
        {
            lexer_advance(lexer);
            return init_token(TOKEN_LBRA, "(");
        }

        else if (lexer->current_char == ')')
        {
            lexer_advance(lexer);
            return init_token(TOKEN_RBRA, ")");
        }
    }

    return init_token(TOKEN_EOF, "\\0");
}
//-----------------------------------------------------------------------------------------

//=========================================================================================

//============================ SYNTAX ANALYSIS ============================================
//---------------------------- AST --------------------------------------------------------
typedef struct AST_STRUCT
{
    enum{
        AST_NUMBER,
        AST_BINOP,
        AST_PAREN_EXPR
    } type;

    char* number_value;

    char* bin_operator;
    struct AST_STRUCT* left;
    struct AST_STRUCT* right;

    struct AST_STRUCT* paren_expr;

} AST_T;

AST_T* init_AST(int type)
{
    AST_T* ast = calloc(1, sizeof(struct AST_STRUCT));
    ast->type = type;

    return ast;
}
//-----------------------------------------------------------------------------------------

//---------------------------- Parser -----------------------------------------------------
typedef struct PARSER_STRUCT
{
    Lexer_T* lexer;
    Token_T* current_token;

} Parser_T;

Parser_T* init_parser(Lexer_T* lexer)
{
    Parser_T* parser = calloc(1, sizeof(struct PARSER_STRUCT));
    parser->lexer = lexer;
    parser->current_token = lexer_get_next_token(parser->lexer);

    return parser;
}

AST_T* parser_factor(Parser_T* parser);
AST_T* parser_term(Parser_T* parser);
AST_T* parser_expr(Parser_T* parser);

void parser_eat(Parser_T* parser, int type)
{
   if (parser->current_token->type == type)
   {
       parser->current_token = lexer_get_next_token(parser->lexer);
   }
   else
   {
       printf("Unexpected token");
       exit(0);
   }
}

AST_T* parser_expr(Parser_T* parser)
{

}

AST_T* parser_factor(Parser_T* parser)
{
    if (parser->current_token->type == TOKEN_INTEGER)
    {
        AST_T* node = init_AST(TOKEN_INTEGER);
        node->number_value = parser->current_token->value;
        parser_eat(parser, TOKEN_INTEGER);

        return node;
    }

}

AST_T* parser_term(Parser_T* parser)
{
    AST_T* result;

    while (parser->current_token->type == TOKEN_MUL || parser->current_token->type == TOKEN_DIV)
    {
        if (parser->current_token->type == TOKEN_MUL)
        {
            parser_eat(parser, TOKEN_MUL);
        }
        else if (parser->current_token->type == TOKEN_DIV)
        {
            parser_eat(parser, TOKEN_DIV);
        }
    }

    return result;

}

//-----------------------------------------------------------------------------------------
//=========================================================================================

//============================ VISITOR ====================================================
typedef struct VISITOR_STRUCT
{

} Visitor_T;

Visitor_T* init_visitor(AST_T* ast)
{
    Visitor_T* visitor = calloc(1, sizeof(struct VISITOR_STRUCT));

    return visitor;
}

void visitor_visit_number(Visitor_T* visitor, AST_T* node)
{
    printf("Number {\n");
    printf(" %s\n", node->number_value);
    printf("}\n");

}

void visitor_visit_bin_op(Visitor_T* visitor, AST_T* node)
{
    printf("Binop {\n");
    visitor_visit(visitor, node->left);
    visitor_visit(visitor, node->right);
    printf("\n}\n");

}

void visitor_visit_paren_expr(Visitor_T* visitor, AST_T* node)
{
    visitor_visit(visitor, node);

}

void visitor_visit(Visitor_T* visitor, AST_T* ast)
{
    if (ast->type == AST_NUMBER)
    {
        visitor_visit_number(visitor, ast);
    }
    else if (ast->type == AST_BINOP)
    {
        visitor_visit_bin_op(visitor, ast);
    }
    else if (ast->type == AST_PAREN_EXPR)
    {
        visitor_visit_paren_expr(visitor, ast);
    }
}
//=========================================================================================
int main()
{
    char* code = "77 * 12 * 9 * 2";
    Lexer_T* lexer = init_lexer(code);

    Parser_T* parser = init_parser(lexer);
    AST_T* ast = parser_term(parser);

    Visitor_T* visitor = init_visitor(ast);
    visitor_visit(visitor, ast);

    return 0;
}

Я пытался сначала получить значение фактора и добавить его к узлу, а затем продолжить разбор выражения, но это меня только смутило. Я ожидаю, что эта программа сможет обрабатывать подобные бинарные операции и превращать их в один AST.

Прежде всего, для любого компилятора, который вы используете, включите предупреждения. На gcc или clang это будет -Wall -Wextra, а если вы хотите сойти с ума, -Wpedantic. Это уже укажет на несколько вещей. Работает ли parser_term в Python, как вы ожидаете? Если да, не могли бы вы опубликовать этот код?

Jason 05.04.2023 15:56

Однако, возможно, чтобы ответить на вопрос... Если это парсер рекурсивного спуска, вы захотите сначала использовать операции с меньшим приоритетом (например, + и -). Таким образом, вы можете сначала разделить выражение на них. Например, 2 * 5 + 7 * 3. Вы хотите потреблять и делиться на + в первую очередь. Затем вы можете заняться разбором 2 * 5 и 7 * 3 по отдельности.

Jason 05.04.2023 16:01

Я скопировал функцию Python term() в сам вопрос. Но мне непонятно, как это делает ту же работу, которую вы хотите, чтобы функция C выполняла. Похоже, что он вычисляет значение, возможно, на основе уже построенного AST, а не строит AST.

John Bollinger 05.04.2023 16:42

Вам необходимо написать свой лексер с нуля? Возможно, да, но если нет, то генерация кода для лексеров — это именно то, для чего предназначены традиционная lex программа и ее аналог GNU flex.

John Bollinger 05.04.2023 16:54

Да, вы правы, это не совсем то, что нам нужно. Могу предположить, что на питоне это должно выглядеть примерно так class BinOp(AST): class Num(AST): class Parser(): def term(self): node = self.factor() while self.current_token.type in (MUL, DIV): token = self.current_token if token.type == MUL: self.eat(MUL) elif token.type == DIV: self.eat(DIV) node = BinOp(left=node, op=token, right=self.factor()) return node

Anton A 05.04.2023 17:02

Пожалуйста, прекратите публиковать многострочные фрагменты Python в комментариях. Их просто невозможно читать. Если вопрос будет прояснен или иным образом улучшен путем добавления дополнительного кода Python или редактирования того, что уже есть, используйте ссылку «Редактировать», чтобы внести такие изменения.

John Bollinger 05.04.2023 17:06

Также обратите внимание, что если вы хотите реализовать обычные правила арифметического старшинства, такие как, например, 1 + 2 * 3 оценивается как 7 вместо 9, вам нужно различать разные виды двоичных операций. Похоже, вы можете сделать это с помощью AST_T.bin_operator, но я предполагаю, что будет проще разделить ваши бинарные операторы на разные виды по уровню приоритета, скажем, ADDITIVE_OP и MULTIPLICATIVE_OP.

John Bollinger 05.04.2023 17:12

извините, я все еще не могу привыкнуть к этому сайту. А что касается использования готового решения типа lex или flex, то это возможно, так как у этого проекта нет особых требований. Я не хочу использовать готовые решения, потому что я хочу понять для себя, как это работает, и не чувствовать себя таким глупым и беспомощным)

Anton A 05.04.2023 17:14

Кажется, я начал понимать, в каком направлении следует двигаться в отношении. Большое спасибо

Anton A 05.04.2023 17:17

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

John Bollinger 05.04.2023 17:18

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

Jason 05.04.2023 17:33
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
11
73
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Один явный вопрос здесь таков:

Как мне создать новый узел бинарной операции?

Вам нужен объект, который создается по мере необходимости, но время жизни которого не ограничивается автоматически выполнением функции, в которой он начинается. Эта комбинация требует динамического распределения. (Вы получаете это автоматически в Python все время, но в C вам нужно попросить об этом.) Например:

    AST_T *result = malloc(sizeof(*result));

В соответствии с передовой практикой вы всегда должны проверять, что выделение прошло успешно, прежде чем пытаться использовать выделенный объект. Если нет, вам следует вернуться к какой-либо альтернативной операции или операции восстановления или, что чаще всего, просто потерпеть неудачу. В программе, в отличие от библиотеки, разумно потерпеть неудачу, напечатав диагностику и завершив работу. Например:

    if (result == NULL) {
        fputs("fatal error: memory allocation failure\n", stderr);
        abort();
    }

Но очень маловероятно, что аллокации в вашей программе потерпят неудачу, если только что-то еще не пойдет не так.

Предположим, что выделение прошло успешно, вы захотите соответствующим образом установить члены нового объекта. Может что-то в этом роде:

    result->type = /* as appropriate */; // ...
    result->number_value = NULL;
    result->bin_operator = // ...
    result->left = NULL; // probably something other than NULL in some cases
    result->right = NULL;
    result->paren_expr = NULL;  // WTH?

В конечном итоге вам нужно будет либо вернуть указатель на новый узел (что, похоже, вы и ожидаете сделать), либо, возможно, назначить его члену парсера. Или оба. Это легко. Например,

    return result;

Также буду рад, если вы укажете мне на другие ошибки

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

Другие вопросы по теме