基于C语言实现EBNF语法解析器的指针更新问题排查

我正在用C语言实现一个识别扩展巴科斯-瑙尔范式（EBNF）的解析器，词法分析器已经完成，能把输入转成Token链表，但解析器逻辑存在问题，怀疑是指针更新导致的。

Token定义 #

typedef enum {
    Identifier,
    Literal,
    LPar,
    RPar,
    LBrak,
    RBrak,
    LBrace,
    RBrace,
    Bar,
    Eql,
} TokenType;

typedef struct Token{
    TokenType type;
    char* value;
    struct Token* next;
} Token;

解析器代码 #

int parser(Token* input){
    parse_production(input);
    return 1;
}

void parse_production(Token* p){ // program: ident = expression
    if( p->type == Identifier ){
        p= p->next;
        if ( p->type == Eql ){
            p= p->next;
            p = parse_expression(p);
        }
        else{
            printf("\nerror: expected '='");
            exit(EXIT_FAILURE);
        }
    }
    else{
        printf("\nerror: expected 'Identifier'");
        exit(EXIT_FAILURE);
    }
    
}

Token* parse_expression(Token* p){
    if (p != NULL){
        p = parse_term(p);
        while( p->type == Bar ){
            p = p->next;
            p = parse_term(p);
        }
    }
    else{
        printf("\nerror: expected expression");
        exit(EXIT_FAILURE);
    }
    return p;
}

Token* parse_term(Token* p){
    while(( p->type == Identifier ) || ( p->type == Literal) || ( p->type == LPar ) || ( p->type == LBrak) || ( p->type == LBrace)){
        p = parse_factor(p);
    }
    return p;
}

Token* parse_factor(Token* p){
    switch (p->type){
        case Identifier:
            printf("here");
            p = p->next;
            break;
        case Literal:
            p = p->next;
            break;
        case LPar:
            p = p->next;
            p = parse_expression(p);
            if( p->type == RPar ){
                p = p->next;
            }
            else{
                printf("\nerror : expected ')' ");
                exit(EXIT_FAILURE);
            }
            break;
        case LBrak:
            p = p->next;
            p = parse_expression(p);
            if( p->type == RBrak ){
                p = p->next;
            }
            else{
                printf("\nerror : expected ']' ");
                exit(EXIT_FAILURE);
            }
            break;
        case LBrace:
            p = p->next;
            p = parse_expression(p);
            if( p->type == RBrace ){
                p = p->next;
            }
            else{
                printf("\nerror : expected '}' ");
                exit(EXIT_FAILURE);
            }
            break;
        default:
            printf("\nerror : syntax");
            exit(EXIT_FAILURE);
            break;
    }
    return p;
}

问题分析与修复 #

核心问题出在**parse_production函数的指针传递方式**，同时存在空指针访问隐患：

1. parse_production接收的是Token* p（值传递），函数内部对p的修改不会影响外部原始指针。当parse_expression返回更新后的指针时，parse_production里的p只是局部变量，修改后无法传递出去，后续无法验证输入是否完全符合语法（比如是否有多余Token未处理）。
2. parse_term和parse_expression的循环中，未先检查p是否为NULL就直接访问p->type，若Token链表提前结束会触发空指针解引用崩溃。

修复方案： #

1. 修改parse_production为返回更新后的Token指针

让parse_production返回处理后的指针，同时在parser函数中检查是否有未处理的多余Token：

Token* parse_production(Token* p){ // program: ident = expression
    if( p->type == Identifier ){
        p= p->next;
        if ( p->type == Eql ){
            p= p->next;
            p = parse_expression(p);
        }
        else{
            printf("\nerror: expected '='");
            exit(EXIT_FAILURE);
        }
    }
    else{
        printf("\nerror: expected 'Identifier'");
        exit(EXIT_FAILURE);
    }
    return p;
}

// 更新后的parser函数
int parser(Token* input){
    Token* p = parse_production(input);
    // 检查是否有未处理的多余Token
    if (p != NULL) {
        printf("\nerror: unexpected token after production");
        exit(EXIT_FAILURE);
    }
    return 1;
}

2. 修复parse_term的空指针检查

在循环条件中先判断p是否为NULL：

Token* parse_term(Token* p){
    while(p != NULL && ((p->type == Identifier) || (p->type == Literal) || 
                        (p->type == LPar) || (p->type == LBrak) || (p->type == LBrace))){
        p = parse_factor(p);
    }
    return p;
}

3. 补充parse_expression的空指针检查

在while循环迭代前检查p是否为NULL：

Token* parse_expression(Token* p){
    if (p == NULL){
        printf("\nerror: expected expression");
        exit(EXIT_FAILURE);
    }
    p = parse_term(p);
    while(p != NULL && p->type == Bar){
        p = p->next;
        p = parse_term(p);
    }
    return p;
}

这些修改解决了指针更新不传递的问题，避免了空指针崩溃，同时能验证输入是否完全匹配语法规则。

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