building a parser that recognizes extended backus-naur form grammar in C

115 Views Asked by At

I am trying to build a parser that recognizes grammar expressions written in the extended Backus-naur form.

I have already built a lexer that takes in the input of a String and turns a list of tokens.

here is the definition of a 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;

the lexer works correctly. now I took the list of tokens and give it to the parser and expect it to return 1 if there is no errors or exits in case of a syntax error.

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;
}

based on my attempts of debugging, I think that the issue has to do with the pointer update. but I couldn't figure it out.

0

There are 0 best solutions below