Parsing Expressions
Build a parse tree.
From Tokens to Tree
Parsing turns a flat token stream into a structured Abstract Syntax Tree (AST). The tree encodes precedence and grouping that the raw tokens only imply.
For 3 + 4 * 2, the AST nests the multiplication under the addition, so it evaluates to 11, not 14.
AST Node Shape
Each node is either a number leaf or a binary operation with two children. A tagged struct with a union keeps memory compact.
The operator character distinguishes +, -, *, and / at runtime.
typedef struct Node {
enum { N_NUM, N_BINOP } kind;
union {
int value; /* N_NUM */
struct { /* N_BINOP */
char op;
struct Node *left, *right;
} bin;
};
} Node;All lessons in this course
- Tokenizing Input
- Parsing Expressions
- Evaluating the Tree
- Adding Variables