src/debugger/parser.c (view raw)
1#include "parser.h"
2
3static struct LexVector* _lexOperator(struct LexVector* lv, char operator) {
4 struct LexVector* lvNext = malloc(sizeof(struct LexVector));
5 lvNext->token.type = TOKEN_OPERATOR_TYPE;
6 switch (operator) {
7 case '+':
8 lvNext->token.operatorValue = OP_ADD;
9 break;
10 case '-':
11 lvNext->token.operatorValue = OP_SUBTRACT;
12 break;
13 case '*':
14 lvNext->token.operatorValue = OP_MULTIPLY;
15 break;
16 case '/':
17 lvNext->token.operatorValue = OP_DIVIDE;
18 break;
19 default:
20 lvNext->token.type = TOKEN_ERROR_TYPE;
21 break;
22 }
23 lvNext->next = lv->next;
24 lv->next = lvNext;
25 lv = lvNext;
26 lvNext = malloc(sizeof(struct LexVector));
27 lvNext->next = lv->next;
28 lv->next = lvNext;
29 return lvNext;
30}
31
32size_t lexExpression(struct LexVector* lv, const char* string, size_t length) {
33 if (!string || length < 1) {
34 return 0;
35 }
36
37 uint32_t next = 0;
38 size_t adjusted = 0;
39
40 enum LexState state = LEX_ROOT;
41 const char* tokenStart = 0;
42
43 while (length > 0 && string[0] && string[0] != ' ' && state != LEX_ERROR) {
44 char token = string[0];
45 ++string;
46 ++adjusted;
47 --length;
48 switch (state) {
49 case LEX_ROOT:
50 tokenStart = string - 1;
51 switch (token) {
52 case '1':
53 case '2':
54 case '3':
55 case '4':
56 case '5':
57 case '6':
58 case '7':
59 case '8':
60 case '9':
61 state = LEX_EXPECT_DECIMAL;
62 next = token - '0';
63 break;
64 case '0':
65 state = LEX_EXPECT_PREFIX;
66 break;
67 case '$':
68 state = LEX_EXPECT_HEX;
69 next = 0;
70 break;
71 default:
72 if (tolower(token) >= 'a' && tolower(token <= 'z')) {
73 state = LEX_EXPECT_IDENTIFIER;
74 } else {
75 state = LEX_ERROR;
76 }
77 break;
78 };
79 break;
80 case LEX_EXPECT_IDENTIFIER:
81 switch (token) {
82 case '+':
83 case '-':
84 case '*':
85 case '/':
86 lv->token.type = TOKEN_IDENTIFIER_TYPE;
87 lv->token.identifierValue = strndup(tokenStart, string - tokenStart);
88 lv = _lexOperator(lv, token);
89 state = LEX_ROOT;
90 break;
91 default:
92 break;
93 }
94 break;
95 case LEX_EXPECT_DECIMAL:
96 switch (token) {
97 case '0':
98 case '1':
99 case '2':
100 case '3':
101 case '4':
102 case '5':
103 case '6':
104 case '7':
105 case '8':
106 case '9':
107 // TODO: handle overflow
108 next *= 10;
109 next += token - '0';
110 break;
111 case '+':
112 case '-':
113 case '*':
114 case '/':
115 lv->token.type = TOKEN_UINT_TYPE;
116 lv->token.uintValue = next;
117 lv = _lexOperator(lv, token);
118 state = LEX_ROOT;
119 break;
120 default:
121 state = LEX_ERROR;
122 }
123 break;
124 case LEX_EXPECT_HEX:
125 switch (token) {
126 case '0':
127 case '1':
128 case '2':
129 case '3':
130 case '4':
131 case '5':
132 case '6':
133 case '7':
134 case '8':
135 case '9':
136 // TODO: handle overflow
137 next *= 16;
138 next += token - '0';
139 break;
140 case 'A':
141 case 'B':
142 case 'C':
143 case 'D':
144 case 'E':
145 case 'F':
146 // TODO: handle overflow
147 next *= 16;
148 next += token - 'A' + 10;
149 break;
150 case 'a':
151 case 'b':
152 case 'c':
153 case 'd':
154 case 'e':
155 case 'f':
156 // TODO: handle overflow
157 next *= 16;
158 next += token - 'a' + 10;
159 break;
160 case '+':
161 case '-':
162 case '*':
163 case '/':
164 lv->token.type = TOKEN_UINT_TYPE;
165 lv->token.uintValue = next;
166 lv = _lexOperator(lv, token);
167 state = LEX_ROOT;
168 break;
169 default:
170 state = LEX_ERROR;
171 break;
172 }
173 break;
174 case LEX_EXPECT_PREFIX:
175 switch (token) {
176 case 'X':
177 case 'x':
178 next = 0;
179 state = LEX_EXPECT_HEX;
180 break;
181 default:
182 state = LEX_ERROR;
183 break;
184 }
185 break;
186 case LEX_ERROR:
187 // This shouldn't be reached
188 break;
189 }
190 }
191
192 switch (state) {
193 case LEX_EXPECT_DECIMAL:
194 case LEX_EXPECT_HEX:
195 lv->token.type = TOKEN_UINT_TYPE;
196 lv->token.uintValue = next;
197 break;
198 case LEX_EXPECT_IDENTIFIER:
199 lv->token.type = TOKEN_IDENTIFIER_TYPE;
200 lv->token.identifierValue = strndup(tokenStart, string - tokenStart);
201 break;
202 case LEX_ERROR:
203 default:
204 lv->token.type = TOKEN_ERROR_TYPE;
205 break;
206 }
207 return adjusted;
208}
209
210static const int _operatorPrecedence[] = {
211 2,
212 1,
213 1,
214 0
215};
216
217static struct ParseTree* _parseTreeCreate() {
218 struct ParseTree* tree = malloc(sizeof(struct ParseTree));
219 tree->token.type = TOKEN_ERROR_TYPE;
220 tree->rhs = 0;
221 tree->lhs = 0;
222 return tree;
223}
224
225static struct LexVector* _parseExpression(struct ParseTree* tree, struct LexVector* lv, int precedence) {
226 struct ParseTree* newTree = 0;
227 while (lv) {
228 int newPrecedence;
229 switch (lv->token.type) {
230 case TOKEN_IDENTIFIER_TYPE:
231 case TOKEN_UINT_TYPE:
232 if (tree->token.type == TOKEN_ERROR_TYPE) {
233 tree->token = lv->token;
234 lv = lv->next;
235 } else {
236 tree->token.type = TOKEN_ERROR_TYPE;
237 return 0;
238 }
239 break;
240 case TOKEN_OPERATOR_TYPE:
241 newPrecedence = _operatorPrecedence[lv->token.operatorValue];
242 if (newPrecedence < precedence) {
243 newTree = _parseTreeCreate();
244 *newTree = *tree;
245 tree->lhs = newTree;
246 tree->rhs = _parseTreeCreate();
247 tree->token = lv->token;
248 lv = _parseExpression(tree->rhs, lv->next, newPrecedence);
249 if (tree->token.type == TOKEN_ERROR_TYPE) {
250 tree->token.type = TOKEN_ERROR_TYPE;
251 }
252 } else {
253 return lv;
254 }
255 break;
256 case TOKEN_ERROR_TYPE:
257 tree->token.type = TOKEN_ERROR_TYPE;
258 return 0;
259 }
260 }
261
262 return 0;
263}
264
265void parseLexedExpression(struct ParseTree* tree, struct LexVector* lv) {
266 if (!tree) {
267 return;
268 }
269
270 tree->token.type = TOKEN_ERROR_TYPE;
271 tree->lhs = 0;
272 tree->rhs = 0;
273
274 _parseExpression(tree, lv, _operatorPrecedence[OP_ASSIGN]);
275}
276
277void lexFree(struct LexVector* lv) {
278 while (lv) {
279 struct LexVector* lvNext = lv->next;
280 free(lv);
281 lv = lvNext;
282 }
283}
284
285void parseFree(struct ParseTree* tree) {
286 if (!tree) {
287 return;
288 }
289
290 parseFree(tree->lhs);
291 parseFree(tree->rhs);
292
293 if (tree->token.type == TOKEN_IDENTIFIER_TYPE) {
294 free(tree->token.identifierValue);
295 }
296 free(tree);
297}