Second

7 files changed, 361 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..2434358
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,16 @@
+CC := gcc
+CFLAGS := -Wall -Wextra -std=c11 -O2 -fwrapv
+BIN := lysp
+
+.PHONY: all clean remake
+
+all: $(BIN)
+
+clean:
+	rm -rf *.o $(BIN) *.dSYM
+
+remake: clean all
+
+
+$(BIN): $(wildcard *.c *.h) Makefile
+	$(CC) $(CFLAGS) -o $@ $(filter %.c,$^)
diff --git a/ast.c b/ast.c
new file mode 100644
index 0000000..3d84d97
--- /dev/null
+++ b/ast.c
@@ -0,0 +1,96 @@
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include "ast.h"
+#include "util.h"
+
+
+void ast_free(AST *ast){
+	assert(ast);
+	switch(ast->type){
+		case AST_LIST:
+			assert(ast->l.len>=0);
+			for(int i=0;i<ast->l.len;i++){
+				assert(ast->l.nodes[i]);
+				ast_free(ast->l.nodes[i]);
+			}
+			break;
+
+		case AST_WORD:
+			assert(ast->w.word);
+			free(ast->w.word);
+			break;
+
+		case AST_NUMBER:
+		case AST_SYMBOL:
+			break;
+
+		default:
+			assert(false);
+	}
+	free(ast);
+}
+
+
+AST* ast_copy(const AST *ast){
+	assert(ast);
+	switch(ast->type){
+		case AST_LIST:{
+			assert(ast->l.len>=0);
+			assert(ast->l.nodes);
+			AST **nodes=malloc(ast->l.len,AST*);
+			for(int i=0;i<ast->l.len;i++)nodes[i]=ast_copy(ast->l.nodes[i]);
+			return ast_list(ast->l.len,nodes);
+		}
+
+		case AST_WORD:
+			assert(ast->w.word);
+			return ast_word(copystring(ast->w.word));
+
+		case AST_NUMBER:
+			return ast_number(ast->n.num);
+
+		case AST_SYMBOL:{
+			assert(ast->s.name);
+			AST *sym=ast_symbol(ast->s.name);
+			sym->s.symid=ast->s.symid;
+			return sym;
+		}
+
+		default:
+			assert(false);
+	}
+}
+
+
+AST* ast_list(int len,AST **nodes){
+	assert(len>=0);
+	assert(nodes);
+	AST *ast=malloc(1,AST);
+	ast->l.len=len;
+	ast->l.nodes=malloc(len,AST*);
+	memcpy(ast->l.nodes,nodes,len*sizeof(AST*));
+	return ast;
+}
+
+AST* ast_word(char *word){
+	assert(word);
+	AST *ast=malloc(1,AST);
+	ast->w.word=word;
+	return ast;
+}
+
+AST* ast_number(double num){
+	AST *ast=malloc(1,AST);
+	ast->n.num=num;
+	return ast;
+}
+
+AST* ast_symbol(char *name){
+	assert(name);
+	AST *ast=malloc(1,AST);
+	ast->s.name=name;
+	ast->s.symid=-1;
+	return ast;
+}
diff --git a/ast.h b/ast.h
new file mode 100644
index 0000000..46c4b49
--- /dev/null
+++ b/ast.h
@@ -0,0 +1,53 @@
+#pragma once
+
+
+typedef enum ASTtype{
+	AST_LIST,
+	AST_WORD,
+	AST_NUMBER,
+	AST_SYMBOL,
+} ASTtype;
+
+
+typedef struct AST AST;
+
+typedef struct ASTlist{
+	int len;
+	AST **nodes;
+} ASTlist;
+
+typedef struct ASTword{
+	char *word;
+} ASTword;
+
+typedef struct ASTnumber{
+	double num;
+} ASTnumber;
+
+typedef struct ASTsymbol{
+	char *name;
+	int symid;
+	//if you're not the interpreter:
+	// if you just allocated the ASTsymbol yourself, set symid to -1;
+	// else, leave symid alone.
+} ASTsymbol;
+
+struct AST{
+	ASTtype type;
+	union {
+		ASTlist l;
+		ASTword w;
+		ASTnumber n;
+		ASTsymbol s;
+	};
+};
+
+
+void ast_free(AST *ast);
+
+AST* ast_copy(const AST *ast);
+
+AST* ast_list(int len,AST **nodes); //these convenience functions DO NOT copy their arguments
+AST* ast_word(char *word);
+AST* ast_number(double num);
+AST* ast_symbol(char *name);
diff --git a/parser.c b/parser.c
new file mode 100644
index 0000000..7e7a1c2
--- /dev/null
+++ b/parser.c
@@ -0,0 +1,94 @@
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include "parser.h"
+#include "util.h"
+
+typedef struct Cursor{
+	const char *s;
+	int l;
+} Cursor;
+
+typedef enum Tokentype{
+	TT_EOF, //str=NULL, len=-1
+	TT_SYMBOL,
+	TT_WORD,
+	TT_NUMBER,
+
+	TT_ERR=-1 //str is an error description, len=-1
+} Tokentype;
+
+typedef struct Token{
+	Tokentype type;
+	const char *str; //pointer into source
+	int len;
+} Token;
+
+#define SYMBOLCHARS "()[]"
+
+
+static Token tt_make(Tokentype type,const char *str,int len){
+	Token tok={type,str,len};
+	return tok;
+}
+
+static Token tt_eof(void){
+	return tt_make(TT_EOF,NULL,-1);
+}
+
+static Token tt_err(const char *errstr){
+	return tt_make(TT_ERR,errstr,-1);
+}
+
+
+static void advance(Cursor *cursor,int n){
+	assert(cursor->l>=n);
+	cursor->s+=n;
+	cursor->l-=n;
+}
+
+static bool iswordchar(char c){
+	return strchr(SYMBOLCHARS,c)==NULL&&c>=33&&c<=126;
+}
+
+static Token nexttoken(Cursor *cursor){
+	while(cursor->l>=1&&isspace(*cursor->s))advance(cursor,1);
+	if(cursor->l==0)return tt_eof();
+
+	if(strchr(SYMBOLCHARS,*cursor->s)!=NULL){
+		advance(cursor,1);
+		return tt_make(TT_SYMBOL,cursor->s-1,1);
+	}
+
+	if(isdigit(*cursor->s)||(cursor->l>=2&&cursor->s[0]=='-'&&isdigit(cursor->s[1]))){
+		char *endp;
+		strtod(cursor->s,&endp);
+		assert(endp>cursor->s);
+		int len=endp-cursor->s;
+		advance(cursor,len);
+		return tt_make(TT_NUMBER,cursor->s-len,len);
+	}
+
+	int i;
+	for(i=0;i<cursor->l;i++){
+		if(!iswordchar(cursor->s[i]))break;
+	}
+	if(i==0){
+		return tt_err("Unrecognised character while looking for next token");
+	}
+	advance(cursor,i);
+	return tt_make(TT_WORD,cursor->s-i,i);
+}
+
+
+static ParseRet parse_(Cursor *cursor){
+	;
+}
+
+
+ParseRet parse(const char *source,int length){
+	Cursor cursor={source,length};
+	return parse_(&cursor);
+}
diff --git a/parser.h b/parser.h
new file mode 100644
index 0000000..b6e0233
--- /dev/null
+++ b/parser.h
@@ -0,0 +1,13 @@
+#pragma once
+
+#include "ast.h"
+
+
+typedef struct ParseRet{
+	// Exactly one of ast and errstr is non-NULL. The non-NULL member
+	// needs to be free'd.
+	AST *ast;
+	char *errstr;
+} ParseRet;
+
+ParseRet parse(const char *source,int length);
diff --git a/util.c b/util.c
new file mode 100644
index 0000000..d6890d6
--- /dev/null
+++ b/util.c
@@ -0,0 +1,63 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "util.h"
+
+
+char* copystring(const char *s){
+	size_t len=strlen(s);
+	char *s2=malloc(len+1,char);
+	memcpy(s2,s,len+1);
+	return s2;
+}
+
+char* copybufasstring(const char *b,int length){
+	char *s=malloc(length+1,char);
+	memcpy(s,b,length);
+	s[length]='\0';
+	return s;
+}
+
+
+__attribute__((noreturn)) void outofmem(void){
+	fprintf(stderr,"OUT OF MEMORY!\n");
+	exit(2);
+}
+
+
+void* malloccheck(size_t n){
+	void *p=mallocreal(n);
+	if(!p)outofmem();
+	return p;
+}
+
+void* calloccheck(size_t n,size_t s){
+	void *p=callocreal(n,s);
+	if(!p)outofmem();
+	return p;
+}
+
+void* realloccheck(void *p,size_t n){
+	p=reallocreal(p,n);
+	if(!p)outofmem();
+	return p;
+}
+
+
+
+#undef malloc
+#undef calloc
+#undef realloc
+
+void* mallocreal(size_t n){
+	return malloc(n);
+}
+
+void* callocreal(size_t n,size_t s){
+	return calloc(n,s);
+}
+
+void* reallocreal(void *p,size_t n){
+	return realloc(p,n);
+}
diff --git a/util.h b/util.h
new file mode 100644
index 0000000..d2f18c3
--- /dev/null
+++ b/util.h
@@ -0,0 +1,26 @@
+#pragma once
+
+#include <stdbool.h>  // this is useful
+
+
+#define malloc(n,t) ((t*)malloccheck((n)*sizeof(t)))
+#define calloc(n,t) ((t*)calloccheck((n),sizeof(t)))
+#define realloc(p,n,t) ((t*)realloccheck((p),(n)*sizeof(t)))
+
+#define mallocx(n,t) ((t*)mallocreal((n)*sizeof(t)))
+#define callocx(n,t) ((t*)callocreal((n),sizeof(t)))
+#define reallocx(p,n,t) ((t*)reallocreal((p),(n)*sizeof(t)))
+
+
+char* copystring(const char *s);
+char* copybufasstring(const char *b,int length);
+
+void outofmem(void) __attribute__((noreturn));
+
+void* malloccheck(size_t n);
+void* calloccheck(size_t n,size_t s);
+void* realloccheck(void *p,size_t n);
+
+void* mallocreal(size_t n);
+void* callocreal(size_t n,size_t s);
+void* reallocreal(void *p,size_t n);