Parser
- C course
- Expert
- Lesson 14/47
- 5 min
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.
Practice 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").
Starter code
#include <stdio.h>
// Define node_type enum
// Define print_node function and call it for four nodes
int main(void) {
return 0;
}Sample 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;
}Expected output
node0:42 node1:+ node1:* node0:7
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Match parser concepts
| Term | Meaning |
|---|---|
grammar |
Syntax rules |
recursive descent |
Recursive method |
parse_expr |
Expression rule |
expected token |
Error message |
2 What does a parser produce?
- Tokens
- AST Correct answer
- Lexer state
- Symbol table
Explanation: The parser builds an AST from the token stream.
3 Complete the parse call
ast_t *node = parse_____();ast_t *node = parse_expr();Explanation: parse_expr parses an expression.