C语言中AST的正确构造

xoshrz7s  于 2023-04-11  发布在  其他
关注(0)|答案(1)|浏览(191)

我正在尝试实现一个数学表达式解析器，它接收一个字符串作为输入，并最终将一个条件表示输出到控制台。我已经在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。

c

1条答案

按热度按时间
h6my8fg2

h6my8fg21#

这里有一个明确的问题：
我应该如何创建一个新的二元操作节点？
你需要一个在需要时创建的对象，但它的生命周期不会自动限制在它开始执行的函数中。这种组合需要动态分配。（在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;

如果你能给我指出其他的错误，我也会很高兴的
我担心这对SO的要求太宽泛了。但是一定要打开编译器的警告并注意它们。以你的经验水平，你应该假设每个警告都描述了一个会使你的程序错误运行的问题。

赞(0）分享  回复(0）举报  2023-04-11
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com