cparsingrecursive-descent

How to write code for part of a recursive descent parser?


I'm looking for an answer to this Stack Overflow question: Can somebody walk me through what this question is trying to ask of me?

It asks to do the following, as the person who replied to it explains:

Write two functions,

ifblock
logic_expr

as part of a recursive descent parser in a language of your choosing.

<ifblock> --> if(<logic_expr>){<stmts>} [else {<stmts>}]
<logic_expr> --> <value> == <value> | <value> != <value>

For other non terminal symbols, 'stmts' and 'value' you are allowed to assume the existence of pre-written functions by the same names.

To get the next token from the input stream you can call 'lex()' which returns a code, as listed in the codes for the terminal symbols. Implement the 'ifblock' by requesting token codes by calling 'lex()' and to evaluate and match those with the required tokens according to the language grammar.

To evaluate the logical expression of the 'if' you need to step into a function 'logic_expr', which you need to write, for evaluating a logical expression as defined in the grammar, and you may assume that the non-terminal 'value' does already exist.


Solution

  • The answer could be like this. Of course, this is just a truncated pseudo-code for the grammar parser with not much in the way of error handling or an AST builder.

    void parse() {
        while (!EOF)
           if (lex() == IF)
              ifblock()
           else // what is it?
    }
    
    void ifblock () {
        if (lex() != LP) 
           return_error;
        le = logic_expr();
        if (lex() != RP) 
           return_error;
        // parse statements in {}, optional else (if (lex() == ELSE) with {}
        // if no errors
        create_if_node(le, st, ...);
    }
    
    void logic_expr()
        v1 = value();
        op = lex();
        v2 = value();
    
        if (op == EQ)
           return create_eq_node(v1, v2);
        else if (op == NEQ)
           return create_neq_node(v1, v2);
    
        return_error();
    }