使用Bison将含标识符的公式转换为AST时出错的解决方法

我正在尝试用Bison把数学公式转换成节点树形式的抽象语法树（AST），已经定义了节点结构体、创建函数和遍历函数，但处理含变量的公式时，AST的输出不符合预期，下面是详细的代码和问题情况：

节点结构体与创建函数 #

typedef enum {null, opera, var, val} NodeType;
typedef struct Node {
    float val;
    char * name; // val_name
    char * opr; // operator
    NodeType node_type;
    struct Node * left;
    struct Node * right;
} Node;

Node create_op_node(char * op){
    Node node;
    node.opr = op;
    node.node_type = opera;
    return node;
}

Node create_var_node(char * op){
    Node node;
    node.name = op;
    node.node_type = var;
    return node;
}

Node create_val_node(float value){
    Node node;
    node.val = value;
    node.node_type = val;
    return node;
}

树遍历函数 #

void run_through_tree (Node *node){
    switch (node->node_type){
        case var:
            printf("varable name:%s\n",node->name);
            break;
        case val:
            printf("num value:%f\n",node->val);
            break;
        case opera:
            printf("\noperator:%s\n",node->opr);
            printf("LFS\n");
            run_through_tree(node->left);
            printf("RHS\n");
            run_through_tree(node->right);
    }
}

Bison语法规则 #

S : S E T_NEWLINE { main_node = $2;run_through_tree(main_node);} // run through the node tree
  | {} ;

E : E T_ADD E 
    {Node * op_node = (Node *) malloc(sizeof(Node));
     *op_node = create_op_node("+");
     connect_node(op_node,$1,$3);
     $$ = op_node;}
  | E T_SUB E 
    {Node * op_node = (Node *) malloc(sizeof(Node));
     *op_node = create_op_node("-");
     connect_node(op_node,$1,$3);
     $$ = op_node;}
  | E T_MUL E 
    {Node * op_node = (Node *) malloc(sizeof(Node));
     *op_node = create_op_node("*");
     connect_node(op_node,$1,$3);
     $$ = op_node;}
  | E T_DIV E 
    {Node * op_node = (Node *) malloc(sizeof(Node));
     *op_node = create_op_node("/");
     connect_node(op_node,$1,$3);
     $$ = op_node;}
  | T_SUB E %prec NEG 
    { Node * op_node = (Node *) malloc(sizeof(Node));
      Node * zero_node = (Node *) malloc(sizeof(Node));
      * zero_node = create_val_node(0.0);
      * op_node = create_op_node("-");
      connect_node(op_node,zero_node,$2);
      $$ = op_node;}
  | T_NUM 
    {Node * val_node = (Node *) malloc(sizeof(Node));
     * val_node = create_val_node($1);
     $$ = val_node;}
  | T_VAR 
    {Node * var_node = (Node *) malloc(sizeof(Node));
     * var_node = create_var_node($1);
     $$ = var_node;}
  | T_LPATH E T_RPATH {$$ = $2;} ;

问题现象 #

正常情况（无变量公式） #

输入2 * ( 3 + 2)时，输出符合预期：

operator:*
LFS
num value:2.000000
RHS
operator:+
LFS
num value:3.000000
RHS
num value:2.000000

异常情况（含变量公式） #

输入2 * a - a + 7时，实际输出不符合预期：

operator:-
LFS
operator:*
LFS
num value:2.000000
RHS
varable name:a - a + 7
RHS
varable name:a + 7
RHS
num value:7.000000

预期输出应该是：

operator:-
LFS
operator:*
LFS
num value:2.000000
RHS
varable name:a
RHS
varable name:a
RHS
num value:7.000000

问题分析与解决方案 #

从实际输出里的varable name:a - a + 7能直接看出：词法分析器（Flex）没有正确识别单个变量名，它错误地把a后面的空格、运算符和其他内容都当成了变量名的一部分。这是问题的核心原因。

1. 修正Flex的词法规则 #

你需要确保Flex能正确区分变量名、运算符和空白字符，给出参考规则：

// 忽略空白字符（空格、制表符、换行）
[ \t\n]+                  { /* do nothing */ }

// 运算符单独识别
"+"                       { return T_ADD; }
"-"                       { return T_SUB; }
"*"                       { return T_MUL; }
"/"                       { return T_DIV; }
"("                       { return T_LPATH; }
")"                       { return T_RPATH; }

// 变量名：字母/下划线开头，后续可跟字母/数字/下划线
[a-zA-Z_][a-zA-Z0-9_]*    { yylval.str = strdup(yytext); return T_VAR; }

// 数字（整数或浮点数）
[0-9]+(\.[0-9]+)?         { yylval.num = atof(yytext); return T_NUM; }

关键要保证：空白字符被单独忽略，运算符被识别为独立的词法单元，变量名的正则表达式不会匹配到非变量字符。

2. 修复变量名的内存管理问题 #

当前create_var_node直接使用传入的op指针，如果这个指针指向的是Flex的yytext临时缓冲区，后续会被覆盖导致野指针。需要复制字符串：

Node create_var_node(char * op){
    Node node;
    node.name = strdup(op); // 复制字符串，避免临时缓冲区被覆盖
    node.node_type = var;
    return node;
}

记得后续销毁AST时要释放这些复制的字符串，避免内存泄漏。

3. 确认Bison的优先级与结合性 #

为了保证表达式运算顺序正确（比如乘法优先级高于加减），需要在Bison文件顶部明确优先级：

%left T_ADD T_SUB       // 加减优先级相同，左结合
%left T_MUL T_DIV       // 乘除优先级相同，左结合
%nonassoc NEG           // 负号（一元运算符）的优先级高于乘除

验证修正效果 #

当Flex规则正确后，输入2 * a - a + 7会被拆分为正确的词法单元：T_NUM(2)、T_MUL、T_VAR(a)、T_SUB、T_VAR(a)、T_ADD、T_NUM(7)，Bison就能按照语法规则构建出符合预期的AST，遍历输出也会和预期一致。

内容的提问来源于stack exchange，提问作者Tan Kian-teng