Skip to content

Instantly share code, notes, and snippets.

@pervognsen
Last active October 23, 2022 10:58
Show Gist options
  • Save pervognsen/74e9c00781503525913f434e958cf62c to your computer and use it in GitHub Desktop.
Save pervognsen/74e9c00781503525913f434e958cf62c to your computer and use it in GitHub Desktop.
// frontend with abstract backend
void parse_expr(expr_t *expr);
void parse_base_expr(expr_t *expr) {
if (token == NUMBER) {
do_number_expr(expr, token_value);
next_token();
} else if (match_token('(')) {
parse_expr(expr);
expect_token(')');
do_paren_expr(expr);
} else {
error();
}
}
void parse_mul_div_expr(expr_t *expr) {
parse_base_expr(expr);
for (;;) {
expr_t right;
if (match_token('*')) {
parse_base_expr(&right);
do_mul_expr(expr, &right);
} else if (match_token('/')) {
parse_base_expr(&right);
do_div_expr(expr, &right);
} else {
break;
}
}
}
void parse_add_sub_expr(expr_t *expr) {
parse_mul_div_expr(expr);
for (;;) {
expr_t right;
if (match_token('+')) {
parse_mul_div_expr(&right);
do_add_expr(expr, &right);
} else if (match_token('-')) {
parse_mul_div_expr(&right);
do_sub_expr(expr, &right);
} else {
break;
}
}
}
void parse_expr(expr_t *expr) {
parse_add_sub_expr(expr);
}
// backend #1 - evaluator
struct val_expr_t {
int value;
};
void val_do_number_expr(val_expr_t *expr, int value) {
expr->value = value;
}
void val_do_paren_expr(val_expr_t *expr) {
}
void val_do_mul_expr(val_expr_t *left, const val_expr_t *right) {
left->value *= right->value;
}
void val_do_div_expr(val_expr_t *left, const val_expr_t *right) {
left->value /= right->value;
}
void val_do_add_expr(val_expr_t *left, const val_expr_t *right) {
left->value += right->value;
}
void val_do_sub_expr(val_expr_t *left, const val_expr_t *right) {
left->value -= right->value;
}
// backend #2 - ast builder
struct node_t {
enum { NUMBER, PAREN, MUL, DIV, ADD, SUB } kind;
union {
int value;
struct {
node_t *first;
node_t *second;
};
};
};
static node_t *make_node(int kind) {
node_t *node = (node_t *)malloc(sizeof(node_t));
node->kind = kind;
return node;
}
static node_t *make_number_node(int value) {
node_t *node = make_node(NUMBER);
node->value = value;
return node;
}
static node_t *make_unary_node(int kind, node_t *first) {
node_t *node = make_node(kind);
node->first = first;
return node;
}
static node_t *make_binary_node(int kind, node_t *first, node_t *second) {
node_t *node = make_node(kind);
node->first = first;
node->second = second;
return node;
}
struct node_expr_t {
node_t *node;
};
void node_do_number_expr(node_expr_t *expr, int value) {
expr->node = make_number_node(NUMBER, value);
}
void node_do_paren_expr(node_expr_t *expr) {
expr->node = make_unary_node(PAREN, expr->node);
}
void node_do_mul_expr(node_expr_t *left, const node_expr_t *right) {
left->node = make_binary_node(MUL, left->node, right->node);
}
void node_do_div_expr(node_expr_t *left, const node_expr_t *right) {
left->node = make_binary_node(DIV, left->node, right->node);
}
void node_do_add_expr(node_expr_t *left, const node_expr_t *right) {
left->node = make_binary_node(ADD, left->node, right->node);
}
void node_do_sub_expr(node_expr_t *left, const node_expr_t *right) {
left->node = make_binary_node(SUB, left->node, right->node);
}
// backend #3 - both in parallel, without replicating code
struct val_node_expr_t {
val_expr_t val_expr;
node_expr_t node_expr;
};
void val_node_do_number_expr(val_node_expr_t *expr, int value) {
val_do_number_expr(&expr->val_expr, value);
node_do_number_expr(&expr->node_expr, value);
}
// etc for other expr functions
// ast representation is "universal" - can convert to anything else without re-parsing
void redo_expr(expr_t *expr, const node_t *node) {
expr_t right;
switch (node->kind) {
case NUMBER:
do_number_expr(expr, node->value);
break;
case PAREN:
redo_expr(expr, node->first);
do_paren_expr(expr);
break;
case MUL:
redo_expr(expr, node->first);
redo_expr(&right, node->second);
do_mul_expr(expr, right);
break;
case DIV:
redo_expr(expr, node->first);
redo_expr(&right, node->second);
do_div_expr(expr, right);
break;
case ADD:
redo_expr(expr, node->first);
redo_expr(&right, node->second);
do_add_expr(expr, right);
break;
case SUB:
redo_expr(expr, node->first);
redo_expr(&right, node->second);
do_sub_expr(expr, right);
break;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment