diff options
| -rw-r--r-- | sexpr.c | 247 |
1 files changed, 247 insertions, 0 deletions
@@ -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; +} + |