Lex & Yacc自定义循环语句陷入无限循环的修复求助

问题根源 #

你遇到的核心问题是循环条件的表达式在语法分析阶段就被直接求值并固化，后续循环迭代时不会重新计算表达式的当前值。比如你的测试用例里，初始a=5时条件a==5被计算为真，但循环体把a改成20后，条件没有重新求值，导致循环一直认为条件为真，陷入无限循环。

修复方案 #

要解决这个问题，你需要调整Yacc的规则设计，从「边解析边直接求值」改为「构建抽象语法树（AST）后再解释执行」，确保每次循环迭代都能重新计算条件表达式的当前值。

1. 调整表达式规则，生成AST节点 #

首先定义表达式的AST结构体，让Yacc中所有表达式规则返回AST节点指针，而非直接返回计算结果：

// 表达式节点类型枚举
typedef enum { EXPR_EQ, EXPR_VAR, EXPR_NUM } ExprType;

// 表达式AST节点结构体
typedef struct ExprNode {
    ExprType type;
    union {
        struct { struct ExprNode *left; struct ExprNode *right; } eq; // 相等表达式
        char var_name[10]; // 变量名
        int num_val; // 数值
    } data;
} ExprNode;

对应的Yacc表达式规则修改为：

expr: expr EQ expr {
    ExprNode *node = malloc(sizeof(ExprNode));
    node->type = EXPR_EQ;
    node->data.eq.left = $1;
    node->data.eq.right = $3;
    $$ = node;
}
| ID {
    ExprNode *node = malloc(sizeof(ExprNode));
    node->type = EXPR_VAR;
    strcpy(node->data.var_name, $1);
    $$ = node;
}
| NUM {
    ExprNode *node = malloc(sizeof(ExprNode));
    node->type = EXPR_NUM;
    node->data.num_val = $1;
    $$ = node;
};

2. 修改循环语句规则，保存AST节点 #

循环语句规则需要保存条件表达式的AST和循环体的语句块AST，而非直接求值：

// 语句节点类型枚举
typedef enum { STMT_LOOP, STMT_ASSIGN, STMT_PRINT } StmtType;

// 循环语句AST节点结构体
typedef struct LoopStmtNode {
    StmtType type;
    ExprNode *cond; // 循环条件AST
    struct StmtListNode *body; // 循环体语句列表AST
} LoopStmtNode;

// 语句列表结构体
typedef struct StmtListNode {
    struct StmtNode *stmt;
    struct StmtListNode *next;
} StmtListNode;

loopstmt: LOOP '(' expr ')' '{' stmt_list '}' {
    LoopStmtNode *loop = malloc(sizeof(LoopStmtNode));
    loop->type = STMT_LOOP;
    loop->cond = $3;
    loop->body = $6;
    $$ = (StmtNode*)loop; // StmtNode为所有语句节点的父类型
};

3. 实现AST解释执行函数 #

编写遍历AST的执行函数，确保循环每次迭代都重新计算条件表达式：

// 从变量环境中获取当前值的辅助函数
int get_var_value(const char *var_name);

// 计算表达式的值
int evaluate_expr(ExprNode *node) {
    switch(node->type) {
        case EXPR_EQ:
            return evaluate_expr(node->data.eq.left) == evaluate_expr(node->data.eq.right);
        case EXPR_VAR:
            return get_var_value(node->data.var_name);
        case EXPR_NUM:
            return node->data.num_val;
        default:
            return 0;
    }
}

// 执行循环语句
void execute_loop(LoopStmtNode *loop) {
    while (evaluate_expr(loop->cond)) { // 每次循环重新计算条件
        execute_stmt_list(loop->body);
    }
}

测试用例验证 #

对于你的测试用例loop(a==5){a=20; printbet a;}：

1. 第一次循环：计算a==5，此时a初始值为5，条件为真，进入循环体。
2. 循环体执行：将a赋值为20，打印a的值。
3. 第二次循环：重新计算a==5，此时a的值是20，条件为假，循环终止，不会陷入无限循环。

内容的提问来源于stack exchange，提问作者Mert Batuhan ÜNVERDİ