Parser

Learn to write a parser.

Parser and grammar

A parser turns a token stream into a tree. Unlike the lexer it checks syntactic rules; these rules are written as a grammar.

A common method is recursive descent. One C function is written per grammar rule; the function consumes tokens and calls subrules. For instance if expr is term + term, parse_expr calls parse_term first, then expects +. On error the parser reports the expected token. The output is usually an AST.

Recursive descent

Recursive descent models each grammar rule as a C function. The function consumes tokens in order and calls subrules. This structure is readable and produces clear error messages.

A typical calculator starts like this: parse_expr calls parse_term; then it expects + or -. parse_term similarly handles * and /. parse_factor returns a number or a parenthesised expression. Each function returns an AST node. Precedence falls out naturally: multiplication is in a deeper rule, so it binds tighter.

Exercise Print parser nodes

Define enum node_type { NUM_NODE, BINOP_NODE }. Define void print_node(int type, const char *op) with body printf("node%d:%s\n", type, op);. In main call it for four nodes: (NUM_NODE, "42"), (BINOP_NODE, "+"), (BINOP_NODE, "*"), (NUM_NODE, "7").

Show example solution

#include <stdio.h>

enum node_type { NUM_NODE, BINOP_NODE };

void print_node(int type, const char *op) {
    printf("node%d:%s\n", type, op);
}

int main(void) {
    print_node(NUM_NODE, "42");
    print_node(BINOP_NODE, "+");
    print_node(BINOP_NODE, "*");
    print_node(NUM_NODE, "7");
    return 0;
}

Test yourself

Match parser concepts

grammar

Syntax rules
recursive descent

Recursive method
parse_expr

Expression rule
expected token

Error message
What does a parser produce?
- Tokens
- AST
- Lexer state
- Symbol table
Show answer

AST — The parser builds an AST from the token stream.

Complete the parse call

ast_t *node = parse_____();

Show answer

ast_t *node = parse_expr();

Next lesson: AST

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies