262 lines
7.9 KiB
C
262 lines
7.9 KiB
C
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
#include <stdarg.h>
|
|
#include <ctype.h>
|
|
|
|
#define da_dim(name, type) type *name = NULL; \
|
|
int _qy_ ## name ## _p = 0; \
|
|
int _qy_ ## name ## _max = 0
|
|
#define da_rewind(name) _qy_ ## name ## _p = 0
|
|
#define da_redim(name) do {if (_qy_ ## name ## _p >= _qy_ ## name ## _max) \
|
|
name = realloc(name, (_qy_ ## name ## _max += 32) * sizeof(name[0]));} while (0)
|
|
#define da_append(name, x) do {da_redim(name); name[_qy_ ## name ## _p++] = x;} while (0)
|
|
#define da_len(name) _qy_ ## name ## _p
|
|
#define da_add(name) do {da_redim(name); _qy_ ## name ## _p++;} while (0)
|
|
|
|
typedef enum {
|
|
nd_Ident, nd_String, nd_Integer, nd_Sequence, nd_If, nd_Prtc, nd_Prts, nd_Prti, nd_While,
|
|
nd_Assign, nd_Negate, nd_Not, nd_Mul, nd_Div, nd_Mod, nd_Add, nd_Sub, nd_Lss, nd_Leq,
|
|
nd_Gtr, nd_Geq, nd_Eql, nd_Neq, nd_And, nd_Or
|
|
} NodeType;
|
|
|
|
typedef struct Tree Tree;
|
|
struct Tree {
|
|
NodeType node_type;
|
|
Tree *left;
|
|
Tree *right;
|
|
int value;
|
|
};
|
|
|
|
// dependency: Ordered by NodeType, must remain in same order as NodeType enum
|
|
|
|
struct {
|
|
char *enum_text;
|
|
NodeType node_type;
|
|
} atr[] = {
|
|
{"Identifier" , nd_Ident, }, {"String" , nd_String, },
|
|
{"Integer" , nd_Integer,}, {"Sequence" , nd_Sequence,},
|
|
{"If" , nd_If, }, {"Prtc" , nd_Prtc, },
|
|
{"Prts" , nd_Prts, }, {"Prti" , nd_Prti, },
|
|
{"While" , nd_While, }, {"Assign" , nd_Assign, },
|
|
{"Negate" , nd_Negate, }, {"Not" , nd_Not, },
|
|
{"Multiply" , nd_Mul, }, {"Divide" , nd_Div, },
|
|
{"Mod" , nd_Mod, }, {"Add" , nd_Add, },
|
|
{"Subtract" , nd_Sub, }, {"Less" , nd_Lss, },
|
|
{"LessEqual" , nd_Leq, }, {"Greater" , nd_Gtr, },
|
|
{"GreaterEqual", nd_Geq, }, {"Equal" , nd_Eql, },
|
|
{"NotEqual" , nd_Neq, }, {"And" , nd_And, },
|
|
{"Or" , nd_Or, },
|
|
};
|
|
|
|
FILE *source_fp;
|
|
da_dim(string_pool, const char *);
|
|
da_dim(global_names, const char *);
|
|
da_dim(global_values, int);
|
|
|
|
void error(const char *fmt, ... ) {
|
|
va_list ap;
|
|
char buf[1000];
|
|
|
|
va_start(ap, fmt);
|
|
vsprintf(buf, fmt, ap);
|
|
printf("error: %s\n", buf);
|
|
exit(1);
|
|
}
|
|
|
|
Tree *make_node(NodeType node_type, Tree *left, Tree *right) {
|
|
Tree *t = calloc(sizeof(Tree), 1);
|
|
t->node_type = node_type;
|
|
t->left = left;
|
|
t->right = right;
|
|
return t;
|
|
}
|
|
|
|
Tree *make_leaf(NodeType node_type, int value) {
|
|
Tree *t = calloc(sizeof(Tree), 1);
|
|
t->node_type = node_type;
|
|
t->value = value;
|
|
return t;
|
|
}
|
|
|
|
int interp(Tree *x) { /* interpret the parse tree */
|
|
if (!x) return 0;
|
|
switch(x->node_type) {
|
|
case nd_Integer: return x->value;
|
|
case nd_Ident: return global_values[x->value];
|
|
case nd_String: return x->value;
|
|
|
|
case nd_Assign: return global_values[x->left->value] = interp(x->right);
|
|
case nd_Add: return interp(x->left) + interp(x->right);
|
|
case nd_Sub: return interp(x->left) - interp(x->right);
|
|
case nd_Mul: return interp(x->left) * interp(x->right);
|
|
case nd_Div: return interp(x->left) / interp(x->right);
|
|
case nd_Mod: return interp(x->left) % interp(x->right);
|
|
case nd_Lss: return interp(x->left) < interp(x->right);
|
|
case nd_Gtr: return interp(x->left) > interp(x->right);
|
|
case nd_Leq: return interp(x->left) <= interp(x->right);
|
|
case nd_Eql: return interp(x->left) == interp(x->right);
|
|
case nd_Neq: return interp(x->left) != interp(x->right);
|
|
case nd_And: return interp(x->left) && interp(x->right);
|
|
case nd_Or: return interp(x->left) || interp(x->right);
|
|
case nd_Negate: return -interp(x->left);
|
|
case nd_Not: return !interp(x->left);
|
|
|
|
case nd_If: if (interp(x->left))
|
|
interp(x->right->left);
|
|
else
|
|
interp(x->right->right);
|
|
return 0;
|
|
|
|
case nd_While: while (interp(x->left))
|
|
interp(x->right);
|
|
return 0;
|
|
|
|
case nd_Prtc: printf("%c", interp(x->left));
|
|
return 0;
|
|
case nd_Prti: printf("%d", interp(x->left));
|
|
return 0;
|
|
case nd_Prts: printf("%s", string_pool[interp(x->left)]);
|
|
return 0;
|
|
|
|
case nd_Sequence: interp(x->left);
|
|
interp(x->right);
|
|
return 0;
|
|
|
|
default: error("interp: unknown tree type %d\n", x->node_type);
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
void init_in(const char fn[]) {
|
|
if (fn[0] == '\0')
|
|
source_fp = stdin;
|
|
else {
|
|
source_fp = fopen(fn, "r");
|
|
if (source_fp == NULL)
|
|
error("Can't open %s\n", fn);
|
|
}
|
|
}
|
|
|
|
NodeType get_enum_value(const char name[]) {
|
|
for (size_t i = 0; i < sizeof(atr) / sizeof(atr[0]); i++) {
|
|
if (strcmp(atr[i].enum_text, name) == 0) {
|
|
return atr[i].node_type;
|
|
}
|
|
}
|
|
error("Unknown token %s\n", name);
|
|
return -1;
|
|
}
|
|
|
|
char *read_line(int *len) {
|
|
static char *text = NULL;
|
|
static int textmax = 0;
|
|
|
|
for (*len = 0; ; (*len)++) {
|
|
int ch = fgetc(source_fp);
|
|
if (ch == EOF || ch == '\n') {
|
|
if (*len == 0)
|
|
return NULL;
|
|
break;
|
|
}
|
|
if (*len + 1 >= textmax) {
|
|
textmax = (textmax == 0 ? 128 : textmax * 2);
|
|
text = realloc(text, textmax);
|
|
}
|
|
text[*len] = ch;
|
|
}
|
|
text[*len] = '\0';
|
|
return text;
|
|
}
|
|
|
|
char *rtrim(char *text, int *len) { // remove trailing spaces
|
|
for (; *len > 0 && isspace(text[*len - 1]); --(*len))
|
|
;
|
|
|
|
text[*len] = '\0';
|
|
return text;
|
|
}
|
|
|
|
int fetch_string_offset(char *st) {
|
|
int len = strlen(st);
|
|
st[len - 1] = '\0';
|
|
++st;
|
|
char *p, *q;
|
|
p = q = st;
|
|
|
|
while ((*p++ = *q++) != '\0') {
|
|
if (q[-1] == '\\') {
|
|
if (q[0] == 'n') {
|
|
p[-1] = '\n';
|
|
++q;
|
|
} else if (q[0] == '\\') {
|
|
++q;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < da_len(string_pool); ++i) {
|
|
if (strcmp(st, string_pool[i]) == 0) {
|
|
return i;
|
|
}
|
|
}
|
|
da_add(string_pool);
|
|
int n = da_len(string_pool) - 1;
|
|
string_pool[n] = strdup(st);
|
|
return da_len(string_pool) - 1;
|
|
}
|
|
|
|
int fetch_var_offset(const char *name) {
|
|
for (int i = 0; i < da_len(global_names); ++i) {
|
|
if (strcmp(name, global_names[i]) == 0)
|
|
return i;
|
|
}
|
|
da_add(global_names);
|
|
int n = da_len(global_names) - 1;
|
|
global_names[n] = strdup(name);
|
|
da_append(global_values, 0);
|
|
return n;
|
|
}
|
|
|
|
Tree *load_ast() {
|
|
int len;
|
|
char *yytext = read_line(&len);
|
|
yytext = rtrim(yytext, &len);
|
|
|
|
// get first token
|
|
char *tok = strtok(yytext, " ");
|
|
|
|
if (tok[0] == ';') {
|
|
return NULL;
|
|
}
|
|
NodeType node_type = get_enum_value(tok);
|
|
|
|
// if there is extra data, get it
|
|
char *p = tok + strlen(tok);
|
|
if (p != &yytext[len]) {
|
|
int n;
|
|
for (++p; isspace(*p); ++p)
|
|
;
|
|
switch (node_type) {
|
|
case nd_Ident: n = fetch_var_offset(p); break;
|
|
case nd_Integer: n = strtol(p, NULL, 0); break;
|
|
case nd_String: n = fetch_string_offset(p); break;
|
|
default: error("Unknown node type: %s\n", p);
|
|
}
|
|
return make_leaf(node_type, n);
|
|
}
|
|
|
|
Tree *left = load_ast();
|
|
Tree *right = load_ast();
|
|
return make_node(node_type, left, right);
|
|
}
|
|
|
|
int main(int argc, char *argv[]) {
|
|
init_in(argc > 1 ? argv[1] : "");
|
|
|
|
Tree *x = load_ast();
|
|
interp(x);
|
|
|
|
return 0;
|
|
}
|