Gymbo

parser.h
Go to the documentation of this file.
1
7 #pragma once
8 #include <vector>
9
10 #include "tokenizer.h"
11
15 char LETTER_EQ[] = "==";
16
20 char LETTER_NEQ[] = "!=";
21
25 char LETTER_LQ[] = "<";
26
30 char LETTER_LEQ[] = "<=";
31
35 char LETTER_GQ[] = ">";
36
40 char LETTER_GEQ[] = ">=";
41
45 char LETTER_PLUS[] = "+";
46
50 char LETTER_MINUS[] = "-";
51
55 char LETTER_MUL[] = "*";
56
60 char LETTER_DIV[] = "/";
61
65 char LETTER_AND[] = "&&";
66
70 char LETTER_OR[] = "||";
71
75 char LETTER_NOT[] = "!";
76
80 char LETTER_LP[] = "(";
81
85 char LETTER_RP[] = ")";
86
90 char LETTER_SC[] = ";";
91
95 char LETTER_ELSE[] = "else";
96
100 char LETTER_LB[] = "{";
101
105 char LETTER_RB[] = "}";
106
107 namespace gymbo {
108
113 typedef enum {
114 ND_ADD, // +
115 ND_SUB, // -
116 ND_MUL, // *
117 ND_DIV, // /
118 ND_AND, // &&
119 ND_OR, // ||
120 ND_NOT, // !
121 ND_EQ, // ==
122 ND_NE, // !=
123 ND_LT, // <
124 ND_LE, // <=
125 ND_ASSIGN,
126 ND_LVAR,
127 ND_NUM, // Integer
128 ND_RETURN,
129 ND_IF,
130 ND_FOR,
131 ND_BLOCK,
132 } NodeKind;
133
137 struct Node {
138 NodeKind kind;
139 Node *lhs;
140 Node *rhs;
141 Node *cond;
142 Node *then;
143 Node *els;
144 std::vector<Node *> blocks;
145 float val;
146 int offset;
147 };
148
149 Node *assign(Token *&token, char *user_input);
150 Node *expr(Token *&token, char *user_input);
151 Node *equality(Token *&token, char *user_input);
152 Node *relational(Token *&token, char *user_input);
153 Node *logical(Token *&token, char *user_input);
154 Node *add(Token *&token, char *user_input);
155 Node *mul(Token *&token, char *user_input);
156 Node *unary(Token *&token, char *user_input);
157 Node *primary(Token *&token, char *user_input);
158 Node *stmt(Token *&token, char *user_input);
159
166 Node *new_node(NodeKind kind) {
167 Node *node = new Node();
168 node->kind = kind;
169 return node;
170 }
171
181 Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) {
182 Node *node = new_node(kind);
183 node->lhs = lhs;
184 node->rhs = rhs;
185 return node;
186 }
187
195 Node *new_num(float val) {
196 Node *node = new_node(ND_NUM);
197 node->val = val;
198 return node;
199 }
200
210 Node *expr(Token *&token, char *user_input) {
211 return assign(token, user_input);
212 }
213
223 Node *assign(Token *&token, char *user_input) {
224 char LETTER_ASS[] = "=";
225 Node *node = logical(token, user_input);
226 if (consume(token, LETTER_ASS))
227 node = new_binary(ND_ASSIGN, node, assign(token, user_input));
228 return node;
229 }
230
240 Node *logical(Token *&token, char *user_input) {
241 Node *node = equality(token, user_input);
242
243 for (;;) {
244 if (consume(token, LETTER_AND))
245 node = new_binary(ND_AND, node, equality(token, user_input));
246 else if (consume(token, LETTER_OR))
247 node = new_binary(ND_OR, node, equality(token, user_input));
248 else
249 return node;
250 }
251 }
252
262 Node *equality(Token *&token, char *user_input) {
263 Node *node = relational(token, user_input);
264
265 for (;;) {
266 if (consume(token, LETTER_EQ))
267 node = new_binary(ND_EQ, node, relational(token, user_input));
268 else if (consume(token, LETTER_NEQ))
269 node = new_binary(ND_NE, node, relational(token, user_input));
270 else
271 return node;
272 }
273 }
274
284 Node *relational(Token *&token, char *user_input) {
285 Node *node = add(token, user_input);
286
287 for (;;) {
288 if (consume(token, LETTER_LQ))
289 node = new_binary(ND_LT, node, add(token, user_input));
290 else if (consume(token, LETTER_LEQ))
291 node = new_binary(ND_LE, node, add(token, user_input));
292 else if (consume(token, LETTER_GQ))
293 node = new_binary(ND_LT, add(token, user_input), node);
294 else if (consume(token, LETTER_GEQ))
295 node = new_binary(ND_LE, add(token, user_input), node);
296 else
297 return node;
298 }
299 }
300
310 inline Node *add(Token *&token, char *user_input) {
311 Node *node = mul(token, user_input);
312
313 for (;;) {
314 if (consume(token, LETTER_PLUS))
315 node = new_binary(ND_ADD, node, mul(token, user_input));
316 else if (consume(token, LETTER_MINUS))
317 node = new_binary(ND_SUB, node, mul(token, user_input));
318 else
319 return node;
320 }
321 }
322
333 inline Node *mul(Token *&token, char *user_input) {
334 Node *node = unary(token, user_input);
335
336 for (;;) {
337 if (consume(token, LETTER_MUL))
338 node = new_binary(ND_MUL, node, unary(token, user_input));
339 else if (consume(token, LETTER_DIV))
340 node = new_binary(ND_DIV, node, unary(token, user_input));
341 else
342 return node;
343 }
344 }
345
356 inline Node *unary(Token *&token, char *user_input) {
357 if (consume(token, LETTER_PLUS)) return unary(token, user_input);
358 if (consume(token, LETTER_MINUS))
359 return new_binary(ND_SUB, new_num(0), unary(token, user_input));
360 return primary(token, user_input);
361 }
362
372 inline Node *primary(Token *&token, char *user_input) {
373 if (consume(token, LETTER_LP)) {
374 Node *node = expr(token, user_input);
375 expect(token, user_input, LETTER_RP);
376 return node;
377 }
378
379 Token *tok = consume_ident(token);
380 if (tok) {
381 Node *node = (Node *)std::calloc(1, sizeof(Node));
382 node->kind = ND_LVAR;
383 node->offset = tok->var_id;
384 return node;
385 }
386
387 return new_num(expect_number(token, user_input));
388 }
389
397 inline Node *stmt(Token *&token, char *user_input) {
398 Node *node;
399
400 if (consume(token, LETTER_LB)) {
401 node = new Node();
402 node->kind = ND_BLOCK;
403 while (true) {
404 node->blocks.emplace_back(stmt(token, user_input));
405 if (consume(token, LETTER_RB)) {
406 break;
407 }
408 }
409 } else if (consume_tok(token, TOKEN_RETURN)) {
410 node = new Node();
411 node->kind = ND_RETURN;
412 node->lhs = expr(token, user_input);
413 expect(token, user_input, LETTER_SC);
414 } else if (consume_tok(token, TOKEN_IF)) {
415 node = new Node();
416 node->kind = ND_IF;
417 expect(token, user_input, LETTER_LP);
418 node->cond = expr(token, user_input);
419 expect(token, user_input, LETTER_RP);
420 node->then = stmt(token, user_input);
421 if (consume_tok(token, TOKEN_ELSE)) {
422 node->els = stmt(token, user_input);
423 }
424 } else {
425 node = expr(token, user_input);
426 expect(token, user_input, LETTER_SC);
427 }
428
429 return node;
430 }
431
439 inline void generate_ast(Token *&token, char *user_input,
440 std::vector<Node *> &code) {
441 while (!at_eof(token)) code.emplace_back(stmt(token, user_input));
442 code.emplace_back(nullptr);
443 }
444 } // namespace gymbo
gymbo
Definition: compiler.h:11
gymbo::stmt
Node * stmt(Token *&token, char *user_input)
Parse and construct an AST node representing a statement.
Definition: parser.h:397
gymbo::consume_tok
bool consume_tok(Token *&token, TokenKind tok)
Consumes the current token if it matches tok.
Definition: tokenizer.h:120
gymbo::NodeKind
NodeKind
Enumeration representing different node kinds in the Abstract Syntax Tree (AST).
Definition: parser.h:113
gymbo::ND_BLOCK
@ ND_BLOCK
Definition: parser.h:131
gymbo::ND_MUL
@ ND_MUL
Definition: parser.h:116
gymbo::ND_DIV
@ ND_DIV
Definition: parser.h:117
gymbo::ND_NUM
@ ND_NUM
Definition: parser.h:127
gymbo::ND_SUB
@ ND_SUB
Definition: parser.h:115
gymbo::ND_ASSIGN
@ ND_ASSIGN
Definition: parser.h:125
gymbo::ND_LVAR
@ ND_LVAR
Definition: parser.h:126
gymbo::ND_RETURN
@ ND_RETURN
Definition: parser.h:128
gymbo::ND_EQ
@ ND_EQ
Definition: parser.h:121
gymbo::ND_NE
@ ND_NE
Definition: parser.h:122
gymbo::ND_ADD
@ ND_ADD
Definition: parser.h:114
gymbo::ND_LT
@ ND_LT
Definition: parser.h:123
gymbo::ND_OR
@ ND_OR
Definition: parser.h:119
gymbo::ND_LE
@ ND_LE
Definition: parser.h:124
gymbo::ND_IF
@ ND_IF
Definition: parser.h:129
gymbo::ND_AND
@ ND_AND
Definition: parser.h:118
gymbo::ND_FOR
@ ND_FOR
Definition: parser.h:130
gymbo::ND_NOT
@ ND_NOT
Definition: parser.h:120
gymbo::new_binary
Node * new_binary(NodeKind kind, Node *lhs, Node *rhs)
Create a new binary AST node with the given kind, left-hand side, and right-hand side.
Definition: parser.h:181
gymbo::new_node
Node * new_node(NodeKind kind)
Create a new AST node with the given kind.
Definition: parser.h:166
gymbo::consume
bool consume(Token *&token, char *op)
Consumes the current token if it matches op.
Definition: tokenizer.h:105
gymbo::assign
Node * assign(Token *&token, char *user_input)
Parses an assignment statement from a C-like language program.
Definition: parser.h:223
gymbo::at_eof
bool at_eof(Token *token)
Checks if the current token is at the end of the program.
Definition: tokenizer.h:183
gymbo::mul
Node * mul(Token *&token, char *user_input)
Parse and construct an AST node representing multiplication or division.
Definition: parser.h:333
gymbo::generate_ast
void generate_ast(Token *&token, char *user_input, std::vector< Node * > &code)
Parses a C-like language program into an AST.
Definition: parser.h:439
gymbo::relational
Node * relational(Token *&token, char *user_input)
Parses a relational expression from a C-like language program.
Definition: parser.h:284
gymbo::add
Node * add(Token *&token, char *user_input)
Parse and construct an AST node representing addition or subtraction.
Definition: parser.h:310
gymbo::expect_number
float expect_number(Token *&token, char *user_input)
Ensures that the current token is a number.
Definition: tokenizer.h:166
gymbo::TOKEN_ELSE
@ TOKEN_ELSE
Token representing the 'else' keyword.
Definition: tokenizer.h:79
gymbo::TOKEN_RETURN
@ TOKEN_RETURN
Token representing the 'return' keyword.
Definition: tokenizer.h:77
gymbo::TOKEN_IF
@ TOKEN_IF
Token representing the 'if' keyword.
Definition: tokenizer.h:78
gymbo::equality
Node * equality(Token *&token, char *user_input)
Parses an equality expression from a C-like language program.
Definition: parser.h:262
gymbo::expr
Node * expr(Token *&token, char *user_input)
Parses an expression from a C-like language program.
Definition: parser.h:210
gymbo::primary
Node * primary(Token *&token, char *user_input)
Parse and construct an AST node representing primary expressions.
Definition: parser.h:372
gymbo::unary
Node * unary(Token *&token, char *user_input)
Parse and construct an AST node representing unary operations.
Definition: parser.h:356
gymbo::new_num
Node * new_num(float val)
Create a new AST node representing a numeric value with the given value.
Definition: parser.h:195
gymbo::expect
void expect(Token *&token, char *user_input, char *op)
Ensures that the current token matches op.
Definition: tokenizer.h:150
gymbo::consume_ident
Token * consume_ident(Token *&token)
Consumes the current token if it is an identifier.
Definition: tokenizer.h:135
gymbo::logical
Node * logical(Token *&token, char *user_input)
Parses a logical expression from a C-like language program.
Definition: parser.h:240
LETTER_NEQ
char LETTER_NEQ[]
Array representing the inequality operator "!=".
Definition: parser.h:20
LETTER_OR
char LETTER_OR[]
Array representing the logical OR operator "||".
Definition: parser.h:70
LETTER_LEQ
char LETTER_LEQ[]
Array representing the less than or equal to operator "<=".
Definition: parser.h:30
LETTER_RB
char LETTER_RB[]
Array representing the right brace "}".
Definition: parser.h:105
LETTER_DIV
char LETTER_DIV[]
Array representing the division operator "/".
Definition: parser.h:60
LETTER_NOT
char LETTER_NOT[]
Array representing the logical NOT operator "!".
Definition: parser.h:75
LETTER_LQ
char LETTER_LQ[]
Array representing the less than operator "<".
Definition: parser.h:25
LETTER_EQ
char LETTER_EQ[]
Array representing the equality operator "==".
Definition: parser.h:15
LETTER_LB
char LETTER_LB[]
Array representing the left brace "{".
Definition: parser.h:100
LETTER_MINUS
char LETTER_MINUS[]
Array representing the subtraction operator "-".
Definition: parser.h:50
LETTER_RP
char LETTER_RP[]
Array representing the right parenthesis ")".
Definition: parser.h:85
LETTER_ELSE
char LETTER_ELSE[]
Array representing the keyword "else".
Definition: parser.h:95
LETTER_GQ
char LETTER_GQ[]
Array representing the greater than operator ">".
Definition: parser.h:35
LETTER_MUL
char LETTER_MUL[]
Array representing the multiplication operator "*".
Definition: parser.h:55
LETTER_LP
char LETTER_LP[]
Array representing the left parenthesis "(".
Definition: parser.h:80
LETTER_PLUS
char LETTER_PLUS[]
Array representing the addition operator "+".
Definition: parser.h:45
LETTER_GEQ
char LETTER_GEQ[]
Array representing the greater than or equal to operator ">=".
Definition: parser.h:40
LETTER_SC
char LETTER_SC[]
Array representing the semicolon ";".
Definition: parser.h:90
LETTER_AND
char LETTER_AND[]
Array representing the logical AND operator "&&".
Definition: parser.h:65
gymbo::Node
Structure representing a node in the Abstract Syntax Tree (AST).
Definition: parser.h:137
gymbo::Node::lhs
Node * lhs
Left-hand side.
Definition: parser.h:139
gymbo::Node::blocks
std::vector< Node * > blocks
Vector of child blocks.
Definition: parser.h:144
gymbo::Node::offset
int offset
Offset.
Definition: parser.h:146
gymbo::Node::kind
NodeKind kind
Node kind.
Definition: parser.h:138
gymbo::Node::cond
Node * cond
Condition.
Definition: parser.h:141
gymbo::Node::val
float val
Used if kind is ND_NUM.
Definition: parser.h:145
gymbo::Node::rhs
Node * rhs
Right-hand side.
Definition: parser.h:140
gymbo::Node::els
Node * els
'Else' branch
Definition: parser.h:143
gymbo::Node::then
Node * then
'Then' branch
Definition: parser.h:142
gymbo::Token
Structure representing a token.
Definition: tokenizer.h:89
gymbo::Token::var_id
int var_id
Variable ID.
Definition: tokenizer.h:95
tokenizer.h
Implementation of tokenizer.