Simple Lisp tree implementation. Adopted from http://nakkaya.com/2010/08/24/a-micro-manual-for-lisp-implemented-in-c/

lisp-tree.c

/**
 * Simple Lisp tree implementation. 
 * Adopted from http://nakkaya.com/2010/08/24/a-micro-manual-for-lisp-implemented-in-c/
 * 
 * @blackball
 */

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum Type { ATOM, CONS };

struct Obj{
    enum Type type;
};

struct Atom {
    enum Type type;
    char *name;
};

struct Cons {
    enum Type type;
    struct Obj *car;
    struct Obj *cdr;
};

/* future customization may need */
#define xmalloc  malloc
#define xrealloc realloc
#define xcalloc  calloc
#define xfree    free

#define car(x) (((struct Cons*) (x))->car)
#define cdr(x) (((struct Cons*) (x))->cdr)

#define err(msg) puts(msg)

const char*
name(struct Obj *o) {
    if (o->type != ATOM) {
	err("Only ATOM object has a name!");
	exit(1);
    }  
    return ((struct Atom *)(o))->name;
}

struct Obj*
atom(char *n) {
    /* create an atom object */
    char *name;
    struct Atom *ptr = (struct Atom *)xmalloc( sizeof(*ptr) );

    ptr->type = ATOM;
    name  = (char *)xmalloc(strlen(n) + 1);
    strcpy(name, n);
    ptr->name = name;
    return (struct Obj *)ptr;
}

struct Cons*
cons(struct Obj *first, struct Obj *second) {
    /* create cons object */
    struct Cons *ptr = (struct Cons *)xmalloc( sizeof(*ptr) );
    ptr->type = CONS;
    ptr->car = first;
    ptr->cdr = second;
    return (struct Cons *)ptr;
}

void
print(struct Obj *sexp){
    /* output Obj into console */
    if(sexp == NULL)
	return;

    if(sexp->type == CONS){
	printf ("(");
	print(car(sexp));
	sexp = cdr(sexp);
	while (sexp != NULL && sexp->type == CONS) {
	    printf (" ");
	    print(car(sexp));
	    sexp = cdr(sexp);
	}
	printf ( ")");
    }else if(sexp->type == ATOM){
	printf ("%s", name(sexp));
    } else {
	printf("Error!\n");
    }
}

struct Obj*
next_token(FILE *in) {
    /* read next token in stream */
    char buffer[128];
    int index;
    int ch = getc(in);

    while(isspace(ch)) ch = getc(in);

    if(ch == '\n')
	ch = getc(in);
    if(ch == EOF)
	exit(0);

    if(ch == ')')
	return atom(")");
    if(ch == '(')
	return atom("(");

    index = 0;
    while(!isspace(ch) && ch != ')'){
	buffer[index++] = ch;
	ch = getc (in);
    }

    buffer[index] = '\0';
    if (ch == ')') 
	ungetc (ch, in);

    return atom(buffer);
}

struct Obj*
read_tail(FILE *in) {
    struct Obj *first, *second; 
    struct Obj *token = next_token(in);

    if(strcmp(name(token),")") == 0)
	return NULL;
    else if(strcmp(name(token),"(") == 0) {
	first = read_tail(in);
	second = read_tail(in);
	return (struct Obj*)cons(first, second);
    }else{
	first = token;
	second = read_tail(in);
	return (struct Obj*)cons(first, second);
    }
}

struct Obj* 
read(FILE *in) {
    /* read expr from in */
    struct Obj *token = next_token(in);

    if(strcmp(name(token),"(") == 0)
	return read_tail(in);

    return token;
}

int main(int argc, char *argv[]) {
    FILE *in;

    if (argc > 1)
	in = fopen(argv[1], "r");
    else
	in = stdin;

    do {
	printf("> ");
	print( read(in) );
	printf("\n");
    } while (1);

    return 0;
}