climp - parser.c

  1#include <stdio.h>
  2#include <errno.h>
  3#include <stdarg.h>
  4#include <string.h>
  5#include <stdlib.h>
  6#include <pthread.h>
  7#include <semaphore.h>
  8
  9#include <sys/queue.h>
 10
 11#include "util.h"
 12#include "scanner.h"
 13#include "parser.h"
 14
 15#define EXPTXT(T, M) \
 16	do { if (T->type != TOK_VAR || strcmp(T->text, M)) \
 17		return error(T->line, "Expected '%s' got '%s'", M, T->text); \
 18	   } while (0)
 19
 20statement *stmt(parser *p);
 21void freeexpr(expr *e);
 22expr *expression(parser *p);
 23
 24parser*
 25newpar(char *str)
 26{
 27	parser *par;
 28
 29	par = emalloc(sizeof(parser));
 30	par->scr = scanstr(str);
 31	par->max = 5 * 1024;
 32	par->cur = 0;
 33	par->buf = emalloc(par->max * sizeof(token));
 34	par->peektok = NULL;
 35
 36	for (int i = 0; i <= par->max; i++)
 37		par->buf[i] = NULL;
 38
 39	return par;
 40}
 41
 42void
 43freepar(parser *par)
 44{
 45	freescr(par->scr);
 46	if (par->peektok)
 47		free(par->peektok);
 48
 49	free(par->buf);
 50	free(par);
 51}
 52
 53void
 54reset(parser *par)
 55{
 56	for (int i = 0; i <= par->cur; i++)
 57		par->buf[i] = NULL;
 58
 59	par->cur = 0;
 60	if (par->peektok != NULL)
 61		par->buf[0] = par->peektok;
 62}
 63
 64void
 65backup(parser *par)
 66{
 67	par->cur = 0;
 68}
 69
 70token*
 71peek(parser *par)
 72{
 73	token *tok;
 74
 75	if (par->cur > par->max)
 76		reset(par); /* FIXME */
 77
 78	tok = par->buf[par->cur];
 79	if (tok == NULL) {
 80		tok = nxttok(par->scr);
 81		par->buf[par->cur] = tok;
 82		par->peektok = tok;
 83	} else {
 84		par->peektok = NULL;
 85	}
 86
 87	return tok;
 88}
 89
 90token*
 91next(parser *par)
 92{
 93	token *tok;
 94
 95	tok = peek(par);
 96	par->cur++;
 97
 98	return tok;
 99}
100
101statement*
102newstmt(void)
103{
104	return emalloc(sizeof(statement));
105}
106
107void
108freestmts(statement **stmts)
109{
110	int i = 0;
111
112	if (!stmts) return;
113	while (stmts[i])
114		freestmt(stmts[i++]);
115	free(stmts);
116}
117
118void
119freestmt(statement *stmt)
120{
121	if (!stmt) return;
122
123	switch (stmt->type) {
124		case STMT_ERROR:
125			free(stmt->d.error.msg);
126			break;
127		case STMT_DEFINE:
128			freeexpr(stmt->d.define.exp);
129			free(stmt->d.define.var);
130			break;
131		case STMT_ASSIGN:
132			freeexpr(stmt->d.assign.exp);
133			free(stmt->d.assign.var);
134			break;
135		case STMT_READ:
136			free(stmt->d.read.var);
137			break;
138		case STMT_WRITE:
139			freeexpr(stmt->d.write.exp);
140			break;
141		case STMT_COND:
142			freeexpr(stmt->d.cond.cond);
143			freestmts(stmt->d.cond.brn1);
144			freestmts(stmt->d.cond.brn2);
145			break;
146		case STMT_LOOP:
147			freeexpr(stmt->d.loop.cond);
148			freestmts(stmt->d.loop.brn);
149			break;
150	}
151
152	free(stmt);
153}
154
155statement*
156define(char *var, expr *exp)
157{
158	statement *stmt;
159
160	stmt = newstmt();
161	stmt->type = STMT_DEFINE;
162	stmt->d.define.var = estrdup(var);
163	stmt->d.define.exp = exp;
164	return stmt;
165}
166
167statement*
168assign(char *var, expr *exp)
169{
170	statement *stmt;
171
172	stmt = newstmt();
173	stmt->type = STMT_ASSIGN;
174	stmt->d.assign.var = estrdup(var);
175	stmt->d.assign.exp = exp;
176	return stmt;
177}
178
179statement*
180newread(char *var)
181{
182	statement *stmt;
183
184	stmt = newstmt();
185	stmt->type = STMT_READ;
186	stmt->d.read.var = estrdup(var);
187	return stmt;
188}
189
190statement*
191newwrite(expr *exp)
192{
193	statement *stmt;
194
195	stmt = newstmt();
196	stmt->type = STMT_WRITE;
197	stmt->d.write.exp = exp;
198	return stmt;
199}
200
201statement*
202newcond(expr *cexp, statement **brn1, statement **brn2)
203{
204	statement *stmt;
205
206	stmt = newstmt();
207	stmt->type = STMT_COND;
208	stmt->d.cond.cond = cexp;
209	stmt->d.cond.brn1 = brn1;
210	stmt->d.cond.brn2 = brn2;
211	return stmt;
212}
213
214statement*
215newloop(expr *cexp, statement **brn)
216{
217	statement *stmt;
218
219	stmt = newstmt();
220	stmt->type = STMT_LOOP;
221	stmt->d.loop.cond = cexp;
222	stmt->d.loop.brn  = brn;
223	return stmt;
224}
225
226statement*
227error(int line, char *msg, ...)
228{
229	int slen;
230	statement *stmt;
231	va_list ap;
232	char *dest;
233
234	va_start(ap, msg);
235	slen = vsnprintf(NULL, 0, msg, ap);
236	va_end(ap);
237
238	dest = emalloc(slen * sizeof(char));
239
240	va_start(ap, msg);
241	vsnprintf(dest, slen, msg, ap);
242	va_end(ap);
243
244	stmt = newstmt();
245	stmt->type = STMT_ERROR;
246	stmt->d.error.msg = dest;
247	stmt->d.error.line = line;
248	return stmt;
249}
250
251expr*
252newexpr(void)
253{
254	return emalloc(sizeof(expr));
255}
256
257void
258freeexpr(expr *exp)
259{
260	if (!exp) return;
261
262	switch (exp->type) {
263		case EXP_LIT:
264			/* Nothing to free here. */
265			break;
266		case EXP_VAR:
267			free(exp->d.variable.var);
268			break;
269		case EXP_BIN:
270			freeexpr(exp->d.operation.expr1);
271			freeexpr(exp->d.operation.expr2);
272			break;
273	}
274
275	free(exp);
276}
277
278expr*
279literal(int num)
280{
281	expr *exp;
282
283	exp = newexpr();
284	exp->type = EXP_LIT;
285	exp->d.literal.num = num;
286	return exp;
287}
288
289expr*
290variable(char *name)
291{
292	expr *exp;
293
294	exp = newexpr();
295	exp->type = EXP_VAR;
296	exp->d.variable.var = strdup(name);
297	return exp;
298}
299
300expr*
301operation(binop op, expr *expr1, expr *expr2)
302{
303	expr *exp;
304
305	exp = newexpr();
306	exp->type = EXP_BIN;
307	exp->d.operation.op = op;
308	exp->d.operation.expr1 = expr1;
309	exp->d.operation.expr2 = expr2;
310	return exp;
311}
312
313expr*
314factor(parser *par)
315{
316	expr *exp;
317	token *tok;
318
319	tok = next(par);
320	if (tok->type == TOK_DIG) {
321		return literal(atoi(tok->text));
322	} else if (tok->type == TOK_VAR) {
323		return variable(tok->text);
324	}
325
326	tok = next(par);
327	if (tok->type == TOK_LBRACKET) {
328		if (!(exp = expression(par)))
329			return NULL;
330
331		tok = next(par);
332		if (tok->type != TOK_RBRACKET)
333			return NULL;
334
335		return exp;
336	}
337
338	return NULL;
339}
340
341expr*
342term(parser *par)
343{
344	binop op;
345	expr *fac1, *fac2;
346	token *tok;
347
348	if (!(fac1 = factor(par)))
349		return NULL;
350
351	tok = peek(par);
352	switch (tok->type) {
353		case TOK_MULTI:
354			op = OP_MULTI;
355			next(par);
356			break;
357		case TOK_DIVIDE:
358			op = OP_DIVIDE;
359			next(par);
360			break;
361		default:
362			return fac1;
363	}
364
365	if (!(fac2 = factor(par)))
366		return NULL;
367
368	return operation(op, fac1, fac2);
369}
370
371expr*
372expression(parser *par)
373{
374	binop op;
375	expr *term1, *term2;
376	token *tok;
377
378	if (!(term1 = term(par)))
379		return NULL;
380
381	tok = peek(par);
382	switch (tok->type) {
383		case TOK_PLUS:
384			op = OP_PLUS;
385			next(par);
386			break;
387		case TOK_MINUS:
388			op = OP_MINUS;
389			next(par);
390			break;
391		default:
392			return term1;
393	}
394
395	if (!(term2 = term(par)))
396		return NULL;
397
398	return operation(op, term1, term2);
399}
400
401statement**
402cmdblock(parser *par, statement *err)
403{
404	int i = -1;
405	token *tok;
406	statement **cmds;
407	size_t max = 512;
408
409	cmds = malloc(max * sizeof(statement));
410	for (i = 0, tok = peek(par); tok != TOK_EOF;
411			i++, tok = peek(par)) {
412		if (i > max) {
413			err->d.error.msg  = estrdup("Exceeded maximum amount of cmdblock");
414			err->d.error.line = 0;
415			goto err;
416		}
417
418		if ((cmds[i] = stmt(par)) && cmds[i]->type == STMT_ERROR) {
419			err->d.error.msg  = estrdup(cmds[i]->d.error.msg);
420			err->d.error.line = cmds[i++]->d.error.line;
421			goto err;
422		}
423
424		tok = peek(par);
425		if (tok->type == TOK_SEMICOLON)
426			next(par);
427		else
428			break;
429	}
430
431	if (i == -1) {
432		err = error(-1, "Unexpected EOF");
433		free(cmds);
434		return NULL;
435	}
436
437	cmds[++i] = NULL;
438	return cmds;
439
440err:
441	err->type = STMT_ERROR;
442	cmds[i] = NULL;
443	freestmts(cmds);
444	return NULL;
445}
446
447statement*
448letstmt(parser *par)
449{
450	token *tok;
451	char *var;
452	expr *exp;
453
454	tok = next(par);
455	EXPTXT(tok, "let");
456	
457	tok = next(par);
458	if (tok->type != TOK_VAR)
459		return error(tok->line, "Expected variable after 'let'");
460	else
461		var = tok->text;
462
463	tok = next(par);
464	if (tok->type != TOK_ASSIGN)
465		return error(tok->line, "Expected ':=', got '%s'", tok->text);
466
467	if (!(exp = expression(par)))
468		return error(tok->line, "Expected expression after ':='");
469
470	return define(var, exp);
471}
472
473statement*
474assignstmt(parser *par)
475{
476	token *tok;
477	expr *val;
478	char *var;
479
480	tok = next(par);
481	if (tok->type != TOK_VAR)
482		return error(tok->line, "Expected variable for assigment");
483	else
484		var = tok->text;
485
486	tok = next(par);
487	if (tok->type != TOK_ASSIGN)
488		return error(tok->line, "Expected ':=', got '%s'",
489				tok->text);
490
491	if (!(val = expression(par)))
492		return error(tok->line, "Expected expression after ':='");
493
494	return assign(var, val);
495}
496
497statement*
498readstmt(parser *par)
499{
500	token *tok;
501
502	tok = next(par);
503	if (tok->type != TOK_QUESTION)
504		return error(tok->line, "Expected '?' got '%s'",
505				tok->text);
506
507	tok = next(par);
508	if (tok->type != TOK_VAR)
509		return error(tok->line, "Expected variable after operator");
510
511	return newread(tok->text);
512}
513
514statement*
515writestmt(parser *par)
516{
517	token *tok;
518	expr *val;
519
520	tok = next(par);
521	if (tok->type != TOK_EXCLAMATION)
522		return error(tok->line, "Expected '!' got '%s'",
523				tok->text);
524
525	if (!(val = expression(par)))
526		return error(tok->line, "Expected expression after operator");
527
528	return newwrite(val);
529}
530
531statement*
532condstmt(parser *par)
533{
534	statement **cmds1, **cmds2, *err;
535	token *tok;
536	expr *cexp;
537
538	tok = next(par);
539	EXPTXT(tok, "if");
540
541	if (!(cexp = expression(par)))
542		return error(tok->line, "Expected conditional expression");
543
544	tok = next(par);
545	EXPTXT(tok, "then");
546
547	err = newstmt();
548	cmds1 = cmdblock(par, err);
549	if (cmds1 == NULL) {
550		freeexpr(cexp);
551		return err;
552	}
553
554	tok = next(par);
555	if (tok->type != TOK_VAR || strcmp(tok->text, "else")) {
556		free(err);
557		freeexpr(cexp);
558		freestmts(cmds1);
559		return error(tok->line, "Expected '%s', got '%s'", "else", tok->text);
560	}
561
562	cmds2 = cmdblock(par, err);
563	if (cmds2 == NULL) {
564		freestmts(cmds1);
565		freeexpr(cexp);
566		return err;
567	} else {
568		free(err);
569	}
570
571	tok = next(par);
572	EXPTXT(tok, "end");
573
574	return newcond(cexp, cmds1, cmds2);
575}
576
577statement*
578loopstmt(parser *par)
579{
580	token *tok;
581	statement **cmds, *err;
582	expr *cexp;
583
584	tok = next(par);
585	EXPTXT(tok, "while");
586
587	if (!(cexp = expression(par)))
588		return error(tok->line, "Expected conditional expression");
589
590	tok = next(par);
591	EXPTXT(tok, "do");
592
593	err = newstmt();
594	cmds = cmdblock(par, err);
595	if (cmds == NULL) {
596		freeexpr(cexp);
597		return err;
598	} else {
599		free(err);
600	}
601
602	tok = next(par);
603	EXPTXT(tok, "end");
604
605	return newloop(cexp, cmds);
606}
607
608statement*
609stmt(parser *par)
610{
611	statement *val;
612	statement *(*sfuncs[])(parser *p) = {
613		letstmt,
614		assignstmt,
615		readstmt,
616		writestmt,
617		condstmt,
618		loopstmt,
619	};
620	size_t funclen = sizeof(sfuncs) / sizeof(sfuncs[0]);
621
622	reset(par);
623	for (int i = 0; i < funclen; i++) {
624		val = (*sfuncs[i])(par);
625		if (val->type != STMT_ERROR)
626			break;
627
628		if (i + 1 < funclen) {
629			freestmt(val);
630			backup(par);
631		}
632	}
633
634	return val;
635}
636
637statement**
638parseprog(parser *par, statement *err)
639{
640	token *tok;
641	size_t emlen;
642	statement **cmds;
643
644	cmds = cmdblock(par, err);
645	if (cmds == NULL) {
646		freestmts(cmds);
647		return NULL;
648	}
649
650	tok = peek(par);
651	if (tok->type != TOK_EOF) {
652		err->type = STMT_ERROR;
653		err->d.error.line = tok->line;
654
655		if (tok->type == TOK_ERROR) {
656			err->d.error.msg = estrdup(tok->text);
657		} else {
658			emlen = 24 + strlen(tok->text);
659			err->d.error.msg = emalloc(emlen * sizeof(char*));
660			snprintf(err->d.error.msg, emlen - 1,
661					"Expected ';', found '%s'", tok->text);
662			err->d.error.msg[emlen] = '\0';
663		}
664
665		freestmts(cmds);
666		return NULL;
667	}
668
669	return cmds;
670}