I think this is a very simple way of parsing expressions. It's called a
Pratt parser. Changing the associativity of the binary operators is as simple as subtracting 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 | enum {
LBP_ADD = 1,
LBP_MUL = 2,
LBP_NEG = 3,
LBP_POW = 4
}
int[256] lbps;
void init_lbps() {
lbps['+'] = LBP_ADD;
lbps['-'] = LBP_ADD;
lbps['*'] = LBP_MUL;
lbps['/'] = LBP_MUL;
lbps['%'] = LBP_MUL;
lbps[TOKEN_LEFT_SHIFT] = LBP_MUL;
lbps[TOKEN_RIGHT_SHIFT] = LBP_MUL;
lbps['&'] = LBP_MUL;
lbps[TOKEN_POW] = LBP_POW;
}
int lbp(TokenKind kind) { return lbps[kind]; }
int nud(Token token) {
switch (token.kind) {
case TOKEN_INT: return token.val;
case '-': return -parse_expr(LBP_NEG);
case '~': return ~parse_expr(LBP_NEG);
case '(':
int result = parse_expr(0);
expect(')');
return result;
default: assert(false);
}
}
int led(TokenKind kind, int lhs) {
int assoc = 0; // left associative
if (kind == TokenKind.Pow) {
assoc = 1; // right associative
}
int rhs = parse_expr(lbp(kind) - assoc);
switch (kind) {
case '+': return lhs + rhs;
case '-': return lhs - rhs;
case '*': return lhs * rhs;
case '/': assert(rhs != 0); return lhs / rhs;
case '%': return lhs % rhs;
case '&': return lhs & rhs;
case TOKEN_LEFT_SHIFT: return lhs << rhs;
case TOKEN_RIGHT_SHIFT: return lhs >> rhs;
case TOKEN_POW: return cast(int) pow(cast(float) lhs, cast(float) rhs);
default: assert(false);
}
}
int parse_expr(int rbp) {
Token curr_tok = token;
next_token();
int lhs = nud(curr_tok);
while (rbp < lbp(token.kind)) {
curr_tok = token;
next_token();
lhs = led(curr_tok.kind, lhs);
}
return lhs;
}
|