如何用EBNF驱动解析器并构建抽象语法树？

核心解析流程明确 #

完全按照EBNF的起始规则<program>开始：

• 解析入口是对应<program>的函数（比如parse_program()），因为你的EBNF里<program>仅等价于<function>，所以这个函数直接调用parse_function()；
• 如果parse_function()成功返回节点，就用它构建PROG类型的根节点；
• 如果parse_function()失败，直接抛出语法错误（因为你的语法定义里程序只能是一个函数，没有其他分支）。

前置准备工作 #

1. 给Token补充类型与位置信息 #

你的现有Token结构体缺少类型标识和位置行号，解析时必须依赖这些信息，先扩展：

enum TokenType {
    TOK_INT, TOK_RETURN, TOK_IDENT, TOK_INT_LIT,
    TOK_LPAREN, TOK_RPAREN, TOK_LBRACE, TOK_RBRACE, TOK_SEMI,
    TOK_EOF
};

struct Token {
    char *ndx;
    size_t length;
    enum TokenType type;
    int pos;    // Token在源文件中的起始位置
    int line;   // Token所在行号
    struct Token *next;
};

同时实现token_type()辅助函数，根据Token的ndx和length判断类型：

• 匹配关键字：比如长度为3且strncmp(tok->ndx, "int", 3) == 0则为TOK_INT；
• 标识符：首字符是字母/下划线，后续为字母/数字/下划线；
• 整数字面量：首字符是数字；
• 符号：直接匹配单个字符（比如tok->ndx[0] == '('则为TOK_LPAREN）。

2. 维护当前Token指针 #

解析时不要每次从头遍历Token链表，全局或用结构体维护一个current_tok指针，指向当前待处理的Token，消耗Token时直接current_tok = current_tok->next即可。

各解析函数实现（对应EBNF规则） #

1. parse_program() - 解析程序 #

对应<program> ::= <function>

struct ExprNode* parse_program() {
    struct ExprNode* func_node = parse_function();
    if (!func_node) {
        fprintf(stderr, "Syntax error: Expected function definition\n");
        return NULL;
    }
    struct ExprNode* prog_node = malloc(sizeof(struct ExprNode));
    prog_node->type = PROG;
    prog_node->term = NULL; // 或设为"program"
    prog_node->pos = func_node->pos;
    prog_node->line = func_node->line;
    prog_node->left = func_node;
    prog_node->right = NULL;
    return prog_node;
}

2. parse_function() - 解析函数定义 #

对应<function> ::= int <id> ( ) { <statement> }

struct ExprNode* parse_function() {
    // 匹配关键字int
    if (current_tok->type != TOK_INT) {
        fprintf(stderr, "Line %d: Expected 'int' at start of function\n", current_tok->line);
        return NULL;
    }
    int func_line = current_tok->line;
    int func_pos = current_tok->pos;
    current_tok = current_tok->next;

    // 匹配标识符（函数名）
    if (current_tok->type != TOK_IDENT) {
        fprintf(stderr, "Line %d: Expected function name\n", current_tok->line);
        return NULL;
    }
    struct ExprNode* ident_node = malloc(sizeof(struct ExprNode));
    ident_node->type = IDNT;
    ident_node->term = malloc(current_tok->length + 1);
    strncpy(ident_node->term, current_tok->ndx, current_tok->length);
    ident_node->term[current_tok->length] = '\0';
    ident_node->pos = current_tok->pos;
    ident_node->line = current_tok->line;
    ident_node->left = ident_node->right = NULL;
    current_tok = current_tok->next;

    // 匹配左括号(
    if (current_tok->type != TOK_LPAREN) {
        fprintf(stderr, "Line %d: Expected '(' after function name\n", current_tok->line);
        free(ident_node->term);
        free(ident_node);
        return NULL;
    }
    current_tok = current_tok->next;

    // 匹配右括号)
    if (current_tok->type != TOK_RPAREN) {
        fprintf(stderr, "Line %d: Expected ')' after '('\n", current_tok->line);
        free(ident_node->term);
        free(ident_node);
        return NULL;
    }
    current_tok = current_tok->next;

    // 匹配左大括号{
    if (current_tok->type != TOK_LBRACE) {
        fprintf(stderr, "Line %d: Expected '{' after function signature\n", current_tok->line);
        free(ident_node->term);
        free(ident_node);
        return NULL;
    }
    current_tok = current_tok->next;

    // 解析函数体语句
    struct ExprNode* stmt_node = parse_statement();
    if (!stmt_node) {
        free(ident_node->term);
        free(ident_node);
        return NULL;
    }

    // 匹配右大括号}
    if (current_tok->type != TOK_RBRACE) {
        fprintf(stderr, "Line %d: Expected '}' to end function\n", current_tok->line);
        free(ident_node->term);
        free(ident_node);
        free_expr_node(stmt_node); // 需要实现递归释放节点的函数
        return NULL;
    }
    current_tok = current_tok->next;

    // 构建函数节点
    struct ExprNode* func_node = malloc(sizeof(struct ExprNode));
    func_node->type = FUNC;
    func_node->term = NULL; // 或设为"function"
    func_node->pos = func_pos;
    func_node->line = func_line;
    func_node->left = ident_node; // left存函数名
    func_node->right = stmt_node; // right存函数体语句
    return func_node;
}

3. parse_statement() - 解析语句 #

对应<statement> ::= return <expr> ;

struct ExprNode* parse_statement() {
    // 匹配关键字return
    if (current_tok->type != TOK_RETURN) {
        fprintf(stderr, "Line %d: Expected 'return' statement\n", current_tok->line);
        return NULL;
    }
    int stmt_line = current_tok->line;
    int stmt_pos = current_tok->pos;
    current_tok = current_tok->next;

    // 解析返回表达式
    struct ExprNode* expr_node = parse_expr();
    if (!expr_node) {
        return NULL;
    }

    // 匹配分号;
    if (current_tok->type != TOK_SEMI) {
        fprintf(stderr, "Line %d: Expected ';' after return expression\n", current_tok->line);
        free_expr_node(expr_node);
        return NULL;
    }
    current_tok = current_tok->next;

    // 构建语句节点
    struct ExprNode* stmt_node = malloc(sizeof(struct ExprNode));
    stmt_node->type = STMT;
    stmt_node->term = NULL; // 或设为"return"
    stmt_node->pos = stmt_pos;
    stmt_node->line = stmt_line;
    stmt_node->left = expr_node; // left存返回表达式
    stmt_node->right = NULL;
    return stmt_node;
}

4. parse_expr() - 解析表达式 #

对应<expr> ::= <int>

struct ExprNode* parse_expr() {
    // 匹配整数字面量
    if (current_tok->type != TOK_INT_LIT) {
        fprintf(stderr, "Line %d: Expected integer literal\n", current_tok->line);
        return NULL;
    }
    struct ExprNode* int_node = malloc(sizeof(struct ExprNode));
    int_node->type = INT_LIT;
    int_node->term = malloc(current_tok->length + 1);
    strncpy(int_node->term, current_tok->ndx, current_tok->length);
    int_node->term[current_tok->length] = '\0';
    int_node->pos = current_tok->pos;
    int_node->line = current_tok->line;
    int_node->left = int_node->right = NULL;
    current_tok = current_tok->next;
    return int_node;
}

测试用例的解析流程 #

针对你的测试源文件，Token链表顺序为：
TOK_INT → TOK_IDENT("main") → TOK_LPAREN → TOK_RPAREN → TOK_LBRACE → TOK_RETURN → TOK_INT_LIT("2") → TOK_SEMI → TOK_RBRACE → TOK_EOF

解析步骤：

1. parse_program()调用parse_function()；
2. parse_function()依次消耗int、main、(、)、{，然后调用parse_statement()；
3. parse_statement()消耗return，调用parse_expr()得到INT_LIT节点，消耗;后返回STMT节点；
4. parse_function()消耗}，构建FUNC节点返回给parse_program()；
5. parse_program()构建PROG根节点，最终得到完整AST。

补充说明 #

• 内存管理：必须实现free_expr_node()递归释放所有节点的内存，避免泄漏；
• 错误处理：示例中仅做了基础的错误提示，实际可以更详细（比如提示预期Token类型）；
• 扩展：如果后续EBNF规则变复杂，比如支持多个函数、多语句，只需要对应修改解析函数的逻辑（比如parse_program()循环调用parse_function()直到EOF）。

内容的提问来源于stack exchange，提问作者IAbstract