aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--sexpr.c247
1 files changed, 247 insertions, 0 deletions
diff --git a/sexpr.c b/sexpr.c
new file mode 100644
index 0000000..fbe490b
--- /dev/null
+++ b/sexpr.c
@@ -0,0 +1,247 @@
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#define DEFAULT "(& (>> t 6) (& (* 2 t) (>> t 1)))"
+# define NUMNODE 160
+
+struct node {
+ char type;
+ char cval;
+ unsigned int ival;
+ struct node *lval;
+ struct node *rval;
+};
+
+void print_sexpr(struct node *sexpr);
+unsigned int execute(struct node *sexpr, unsigned int t);
+void play(struct node *sexpr);
+int find_split(char* s, int start, int end);
+struct node *parse(char *s, int start, int end);
+struct node *new_node(char type, char cval, unsigned int ival,
+ struct node *lval, struct node *rval);
+void test();
+
+static struct node node_table[NUMNODE];
+static int newest_node = 0;
+
+
+void main() {
+ //test();
+ play(parse(DEFAULT, 0, strlen(DEFAULT)-1));
+};
+
+void test() {
+ printf(DEFAULT);
+ printf("\n");
+ print_sexpr(parse(DEFAULT, 0, strlen(DEFAULT)-1));
+ printf("\n");
+}
+
+int digtoi(char *s, int start, int end) {
+ int num = 0;
+ for(;start<=end;start++) {
+ if (! isdigit(s[start])) {
+ fprintf(stderr, "parse: not a digit: %c", s[start]);
+ exit(-1);
+ }
+ num = num*10 + (s[start] - '0');
+ }
+ return num;
+}
+
+struct node *parse(char *s, int start, int end) {
+ struct node *lval, *rval;
+ char cval;
+ int offset, split;
+
+ // number
+ if (isdigit(s[start])) {
+ return new_node('n', '_', digtoi(s, start, end), NULL, NULL);
+ }
+ // variable
+ if ((s[start] == 't') && (end-start == 0)) {
+ return new_node('v', '_', 0, NULL, NULL);
+ }
+
+ // must be an s-exp
+ if ( !(s[start] == '(' && s[end] == ')') || (end-start < 4)) {
+ fprintf(stderr, "parse: unparsable: ");
+ for (;start<=end;start++) {
+ fprintf(stderr, "%c", s[start]);
+ }
+ fprintf(stderr, "\n");
+ exit(-1);
+ }
+
+ // unitary operator
+ if (s[start+1] == '~') {
+ rval = parse(s, start+3, end-1);
+ return new_node('u', '~', 0, NULL, rval);
+ }
+
+ // various binary operators
+ if ( strchr("*/%+-&^|<>", s[start+1]) != NULL) {
+ cval = s[start+1];
+ offset = 3;
+ if (cval == '<' && s[start+2] == '<' && s[start+3] == ' ') {
+ cval = 'l';
+ offset = 4;
+ } else if (cval == '>' && s[start+2] == '>' && s[start+3] == ' ') {
+ cval = 'r';
+ offset = 4;
+ } else if (s[start+2] != ' ') {
+ fprintf(stderr, "parse: invalid operator: %c\n", cval);
+ exit(-1);
+ }
+ split = find_split(s, start+offset, end-1);
+ lval = parse(s, start+offset, split-1);
+ rval = parse(s, split+1, end-1);
+ return new_node('b', cval, 0, lval, rval);
+ }
+
+ // should not get here
+ fprintf(stderr, "parse: feel through\n");
+ exit(-1);
+}
+
+unsigned int execute(struct node *sexpr, unsigned int t) {
+ switch (sexpr->type) {
+ // atom
+ case 'v':
+ return t;
+ case 'n':
+ return sexpr->ival;
+ // unary
+ case 'u':
+ if (sexpr->cval == '~') {
+ return (~ execute(sexpr->rval, t));
+ } else {
+ fprintf(stderr, "unexpected unary oper: %c", sexpr->cval);
+ }
+ // binary
+ case 'b':
+ switch (sexpr->cval) {
+ case '+':
+ return execute(sexpr->lval, t) + execute(sexpr->rval, t);
+ case '-':
+ return execute(sexpr->lval, t) - execute(sexpr->rval, t);
+ case '*':
+ return execute(sexpr->lval, t) * execute(sexpr->rval, t);
+ case '/':
+ return execute(sexpr->lval, t) / execute(sexpr->rval, t);
+ case '^':
+ return execute(sexpr->lval, t) ^ execute(sexpr->rval, t);
+ case '&':
+ return execute(sexpr->lval, t) & execute(sexpr->rval, t);
+ case '|':
+ return execute(sexpr->lval, t) | execute(sexpr->rval, t);
+ case 'r':
+ return execute(sexpr->lval, t) >> execute(sexpr->rval, t);
+ case 'l':
+ return execute(sexpr->lval, t) << execute(sexpr->rval, t);
+ default:
+ fprintf(stderr, "unexpected binary oper: %c", sexpr->cval);
+ exit(-1);
+ }
+ default:
+ fprintf(stderr, "execute: unknown type: %c", sexpr->type);
+ exit(-1);
+ }
+}
+
+void play(struct node *sexpr) {
+ unsigned int t = 0;
+ for (;;t++) {
+ printf("%c", (char)(0x000000FF & execute(sexpr, t)));
+ }
+ return;
+}
+
+int find_split(char *s, int start, int end) {
+ int depth = 0;
+ int i;
+ for (i=start; i <= end; i++) {
+ if ((depth == 0) && (s[i] == ' '))
+ return i;
+ if (s[i] == '(')
+ depth++;
+ if (s[i] == ')')
+ depth--;
+ if (depth < 0) {
+ fprintf(stderr, "parse: unmatched ')'\n");
+ exit(-1);
+ }
+ }
+ if (depth > 0) {
+ fprintf(stderr, "parse: unmatched '('\n");
+ exit(-1);
+ }
+ fprintf(stderr, "parse: could not find split\n");
+ exit(-1);
+}
+
+void print_sexpr(struct node *sexpr) {
+ char oper = '_';
+ char twice = 0;
+ switch (sexpr->type) {
+ // atoms
+ case 'v':
+ printf("t");
+ break;
+ case 'n':
+ printf("%d", sexpr->ival);
+ break;
+ // unary operators
+ case 'u':
+ if (sexpr->cval == '~') {
+ printf("(~ ");
+ print_sexpr(sexpr->rval);
+ printf(")");
+ } else {
+ fprintf(stderr, "unexpected unary: %c", sexpr->cval);
+ }
+ // binary operators
+ case 'b':
+ if ((sexpr->cval == 'l') || (sexpr->cval == 'r')) {
+ twice = 1;
+ oper = '<';
+ if (sexpr->cval == 'r')
+ oper = '>';
+ } else {
+ oper = sexpr->cval;
+ }
+ if (strchr("+-*/^|&<>", oper) != NULL) {
+ printf("(%c ", oper);
+ if (twice)
+ printf("%c", oper);
+ print_sexpr(sexpr->lval);
+ printf(" ");
+ print_sexpr(sexpr->rval);
+ printf(")");
+ } else {
+ fprintf(stderr, "unexpected binary: %c", sexpr->cval);
+ exit(-1);
+ }
+
+ }
+}
+
+struct node *new_node(char type, char cval, unsigned int ival,
+ struct node *lval, struct node *rval) {
+ struct node *n;
+ newest_node++;
+ if (newest_node >= NUMNODE) {
+ fprintf(stderr, "node table overrun\n");
+ exit(-1);
+ }
+ n = &node_table[newest_node];
+ n->type = type;
+ n->cval = cval;
+ n->ival = ival;
+ n->lval = lval;
+ n->rval = rval;
+ return n;
+}
+