finished lexer, preliminary work on parser

6 files changed, 254 insertions, 15 deletions

diff --git a/Makefile b/Makefile
index d98a13d..e276abd 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,8 @@
 include config.mk
 
 SRC:=lc.c\
-     lexer.c
+     lexer.c\
+     parser.c
 
 OBJ:=$(SRC:.c=.o)
 
diff --git a/examples/hello_world.ll b/examples/hello_world.ll
index 9fe2910..88c410d 100644
--- a/examples/hello_world.ll
+++ b/examples/hello_world.ll
@@ -1,5 +1,3 @@
-#include <stdio.h>
-
 i32 main() {
 	printf("Hello world!\n");
 
diff --git a/lc.c b/lc.c
index 651ed95..6518b4a 100644
--- a/lc.c
+++ b/lc.c
@@ -1,20 +1,26 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include "lexer.h"
+#include "parser.h"
 
 int main(void)
 {
-	char *src = "12.3";
+	FILE *fp = fopen("examples/hello_world.ll", "r");
+	fseek(fp, 0, SEEK_END);
+	size_t length = ftell(fp);
+	fseek(fp, 0, SEEK_SET);
+
+	char *src = malloc(length + 1);
+	fread(src, 1, length, fp);
+	src[length] = '\0';
 	token *head = lexer_parse(src);
 
 	if (!head) {
 		printf("Parsing error!\n");
 		exit(1);
 	}
-	while (head->next) {
-		head = head->next;
-		printf("%d -> %.*s\n", head->type, head->length, head->lexeme);
-		free(head->prev);
-	}
+
+	ir_parse(head);
+
 	return 0;
 }
diff --git a/lexer.c b/lexer.c
index 87e146a..8639f91 100644
--- a/lexer.c
+++ b/lexer.c
@@ -2,6 +2,97 @@
 #include <stdlib.h>
 #include <ctype.h>
 #include <stdio.h>
+#include <string.h>
+
+struct keywords_cell {
+	token_type type;
+	struct keywords_cell *next;
+	char *keyword;
+	size_t keyword_length;
+};
+
+static struct keywords_cell *keywords[TOKEN_VOLATILE - TOKEN_IF] = {0};
+
+static size_t hash_keyword(char *keyword, size_t length)
+{
+	size_t sum = 0;
+	for (size_t i=0; i < length; i++) {
+		sum += (uint8_t) keyword[i];
+	}
+
+	return sum % (TOKEN_VOLATILE - TOKEN_IF);
+}
+
+static void insert_keyword(char *keyword, size_t length, token_type type)
+{
+	struct keywords_cell *next = keywords[hash_keyword(keyword, length)];
+	if (!next) {
+		keywords[hash_keyword(keyword, length)] = calloc(1, sizeof(struct keywords_cell));
+		keywords[hash_keyword(keyword, length)]->keyword = keyword;
+		keywords[hash_keyword(keyword, length)]->keyword_length = length;
+		keywords[hash_keyword(keyword, length)]->type = type;
+		keywords[hash_keyword(keyword, length)]->next = NULL;
+		return;
+	}
+
+	while (next->next) {
+		next = next->next;
+	}
+
+	next->next = calloc(1, sizeof(struct keywords_cell));
+	next->next->keyword = keyword;
+	next->next->keyword_length = length;
+	next->next->type = type;
+	next->next->next = NULL;
+}
+
+static token_type get_keyword(char *keyword, size_t length)
+{
+	struct keywords_cell *cell = keywords[hash_keyword(keyword, length)];
+	if (!cell) return 0;
+	if (cell->next == NULL) return cell->type;
+	while (cell->next != NULL) {
+		if (cell->keyword_length != length) {
+			cell = cell->next;
+			continue;
+		}
+		if (strncmp(cell->keyword, keyword, length) == 0) {
+			return cell->type;
+		}
+		cell = cell->next;
+	}
+
+	if (strncmp(cell->keyword, keyword, length) == 0) {
+		return cell->type;
+	}
+
+	return 0;
+}
+
+static void populate_keywords(void)
+{
+	insert_keyword("if", 2, TOKEN_IF);
+	insert_keyword("else", 4, TOKEN_ELSE);
+	insert_keyword("while", 5, TOKEN_WHILE);
+	insert_keyword("for", 3, TOKEN_FOR);
+	insert_keyword("break", 5, TOKEN_BREAK);
+	insert_keyword("case", 4, TOKEN_CASE);
+	insert_keyword("const", 5, TOKEN_CONST);
+	insert_keyword("do", 2, TOKEN_DO);
+	insert_keyword("enum", 4, TOKEN_ENUM);
+	insert_keyword("extern", 6, TOKEN_EXTERN);
+	insert_keyword("goto", 4, TOKEN_GOTO);
+	insert_keyword("inline", 6, TOKEN_INLINE);
+	insert_keyword("return", 6, TOKEN_RETURN);
+	insert_keyword("signed", 6, TOKEN_SIGNED);
+	insert_keyword("unsigned", 8, TOKEN_UNSIGNED);
+	insert_keyword("static", 6, TOKEN_STATIC);
+	insert_keyword("struct", 6, TOKEN_STRUCT);
+	insert_keyword("switch", 6, TOKEN_SWITCH);
+	insert_keyword("typedef", 7, TOKEN_TYPEDEF);
+	insert_keyword("union", 5, TOKEN_UNION);
+	insert_keyword("volatile", 8, TOKEN_VOLATILE);
+}
 
 static token *token_create(char *lexeme, size_t length, token_type type)
 {
@@ -151,24 +242,34 @@ size_t check_symbol(char *src, size_t index, token **last)
 		}
 		case '{':
 			token_add(last, token_create(src+index, 1, TOKEN_LCURLY));
+			return 1;
 		case '}':
 			token_add(last, token_create(src+index, 1, TOKEN_RCURLY));
+			return 1;
 		case '(':
 			token_add(last, token_create(src+index, 1, TOKEN_LPAREN));
+			return 1;
 		case ')':
 			token_add(last, token_create(src+index, 1, TOKEN_RPAREN));
+			return 1;
 		case '[':
 			token_add(last, token_create(src+index, 1, TOKEN_LSQUARE));
+			return 1;
 		case ']':
 			token_add(last, token_create(src+index, 1, TOKEN_RSQUARE));
+			return 1;
 		case ':':
 			token_add(last, token_create(src+index, 1, TOKEN_COLON));
+			return 1;
 		case ';':
 			token_add(last, token_create(src+index, 1, TOKEN_SEMICOLON));
+			return 1;
 		case ',':
 			token_add(last, token_create(src+index, 1, TOKEN_COMMA));
+			return 1;
 		case '.':
 			token_add(last, token_create(src+index, 1, TOKEN_DOT));
+			return 1;
 
 		default:
 			return 0;
@@ -177,10 +278,18 @@ size_t check_symbol(char *src, size_t index, token **last)
 
 token *lexer_parse(char *src)
 {
+	populate_keywords();
 	size_t index = 0;
 	token *head = token_create(src, 0, TOKEN_HEAD);
 	token *last = head;
+	size_t row = 1, col = 1;
 	while (src[index] != '\0') {
+		if (src[index] == '\n') {
+			index++;
+			col++;
+			row = 1;
+			continue;
+		}
 		if (isspace(src[index])) {
 			index++;
 			continue;
@@ -194,7 +303,7 @@ token *lexer_parse(char *src)
 
 		if (src[index] == '\'') {
 			if (src[index+1] != '\\' && src[index+2] != '\'') {
-				// TODO: error
+				fprintf(stderr, "%zu:%zu: invalid character\n", row, col);
 				return NULL;
 			}
 			token_add(&last, token_create(src+index+1, 1, TOKEN_CHAR));
@@ -208,7 +317,7 @@ token *lexer_parse(char *src)
 			size_t string_length = index;
 			while (src[index++] != '\"') {
 				if (src[index] == '\0') {
-					// TODO: error
+					fprintf(stderr, "%zu:%zu: unterminated string\n", row, col);
 					return NULL;
 				}
 			}
@@ -224,7 +333,13 @@ token *lexer_parse(char *src)
 				index++;
 			}
 			identifier_length = index - identifier_length;
-			token_add(&last, token_create(identifier_start, identifier_length, TOKEN_IDENTIFIER));
+
+			token_type keyword = get_keyword(identifier_start, identifier_length);
+			if (keyword == 0) {
+				token_add(&last, token_create(identifier_start, identifier_length, TOKEN_IDENTIFIER));
+			} else {
+				token_add(&last, token_create(identifier_start, identifier_length, keyword));
+			}
 			continue;
 		}
 
@@ -233,7 +348,7 @@ token *lexer_parse(char *src)
 			size_t number_length = index;
 			uint8_t is_float = 0;
 
-			if (src[index] == '0' && !isdigit(src[index+1]) && src[index+1] != '.') {
+			if (src[index] == '0' && !isdigit(src[index+1]) && src[index+1] != '.' && (isdigit(src[index+2]) || ((src[index+2] >= 65 && src[index+2] <= 70) && (src[index+2] >= 97 && src[index+2] <= 102)))) {
 				if (src[index+1] == 'x') {
 					index += 2;
 				} else if (src[index+1] == 'o') {
@@ -241,7 +356,7 @@ token *lexer_parse(char *src)
 				} else if (src[index+1] == 'b') {
 					index += 2;
 				} else {
-					// TODO: error
+					fprintf(stderr, "%zu:%zu: invalid integer\n", row, col);
 					return NULL;
 				}
 			}
@@ -249,7 +364,7 @@ token *lexer_parse(char *src)
 			while (isdigit(src[index]) || src[index] == '.') {
 				if (src[index] == '.') {
 					if (is_float) {
-						// TODO: error
+						fprintf(stderr, "%zu:%zu: invalid float\n", row, col);
 						return NULL;
 					}
 					is_float = 1;
diff --git a/parser.c b/parser.c
new file mode 100644
index 0000000..764858d
--- /dev/null
+++ b/parser.c
@@ -0,0 +1,90 @@
+#include "parser.h"
+#include "lexer.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#define STBDS_SIZE_T_BITS           ((sizeof (size_t)) * 8)
+
+#define STBDS_ROTATE_LEFT(val, n)   (((val) << (n)) | ((val) >> (STBDS_SIZE_T_BITS - (n))))
+#define STBDS_ROTATE_RIGHT(val, n)  (((val) >> (n)) | ((val) << (STBDS_SIZE_T_BITS - (n))))
+
+#define STBDS_SIPHASH_C_ROUNDS 1
+#define STBDS_SIPHASH_D_ROUNDS 1
+
+static size_t hash_bytes(void *p, size_t len, size_t seed)
+{
+	unsigned char *d = (unsigned char *) p;
+	size_t i,j;
+	size_t v0,v1,v2,v3, data;
+
+	v0 = ((((size_t) 0x736f6d65 << 16) << 16) + 0x70736575) ^  seed;
+	v1 = ((((size_t) 0x646f7261 << 16) << 16) + 0x6e646f6d) ^ ~seed;
+	v2 = ((((size_t) 0x6c796765 << 16) << 16) + 0x6e657261) ^  seed;
+	v3 = ((((size_t) 0x74656462 << 16) << 16) + 0x79746573) ^ ~seed;
+
+#ifdef STBDS_TEST_SIPHASH_2_4
+	v0 ^= 0x0706050403020100ull ^  seed;
+	v1 ^= 0x0f0e0d0c0b0a0908ull ^ ~seed;
+	v2 ^= 0x0706050403020100ull ^  seed;
+	v3 ^= 0x0f0e0d0c0b0a0908ull ^ ~seed;
+#endif
+
+#define STBDS_SIPROUND() \
+	do {                   \
+		v0 += v1; v1 = STBDS_ROTATE_LEFT(v1, 13);  v1 ^= v0; v0 = STBDS_ROTATE_LEFT(v0,STBDS_SIZE_T_BITS/2); \
+		v2 += v3; v3 = STBDS_ROTATE_LEFT(v3, 16);  v3 ^= v2;                                                 \
+		v2 += v1; v1 = STBDS_ROTATE_LEFT(v1, 17);  v1 ^= v2; v2 = STBDS_ROTATE_LEFT(v2,STBDS_SIZE_T_BITS/2); \
+		v0 += v3; v3 = STBDS_ROTATE_LEFT(v3, 21);  v3 ^= v0;                                                 \
+	} while (0)
+
+	for (i=0; i+sizeof(size_t) <= len; i += sizeof(size_t), d += sizeof(size_t)) {
+	data = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24);
+	data |= (size_t) (d[4] | (d[5] << 8) | (d[6] << 16) | (d[7] << 24)) << 16 << 16; // discarded if size_t == 4
+
+	v3 ^= data;
+	for (j=0; j < STBDS_SIPHASH_C_ROUNDS; ++j)
+	STBDS_SIPROUND();
+	v0 ^= data;
+	}
+	data = len << (STBDS_SIZE_T_BITS-8);
+	switch (len - i) {
+		case 7: data |= ((size_t) d[6] << 24) << 24; // fall through
+		case 6: data |= ((size_t) d[5] << 20) << 20; // fall through
+		case 5: data |= ((size_t) d[4] << 16) << 16; // fall through
+		case 4: data |= (d[3] << 24); // fall through
+		case 3: data |= (d[2] << 16); // fall through
+		case 2: data |= (d[1] << 8); // fall through
+		case 1: data |= d[0]; // fall through
+		case 0: break;
+	}
+	v3 ^= data;
+	for (j=0; j < STBDS_SIPHASH_C_ROUNDS; ++j)
+	STBDS_SIPROUND();
+	v0 ^= data;
+	v2 ^= 0xff;
+	for (j=0; j < STBDS_SIPHASH_D_ROUNDS; ++j)
+	STBDS_SIPROUND();
+
+	return v1^v2^v3;
+}
+
+void add_child(node *n, node *child)
+{
+	if (n->children_length + 1 >= n->children_size) {
+		n->children_size += (n->children_size / 2) + n->children_size;
+		n->children = realloc(n->children, n->children_size * sizeof(node));
+	}
+
+	n->children[n->children_length++] = child;
+}
+
+node *ir_parse(token *tokens)
+{
+	(void)tokens;
+	node *start = calloc(1, sizeof(node));
+	start->type = NODE_START;
+	start->id = hash_bytes((void *)start, sizeof(node), 0xcafebabe);
+
+	return NULL;
+}
diff --git a/parser.h b/parser.h
new file mode 100644
index 0000000..4c750cf
--- /dev/null
+++ b/parser.h
@@ -0,0 +1,29 @@
+#ifndef PARSER_H
+#define PARSER_H
+
+#include <stdint.h>
+#include <stddef.h>
+
+typedef enum {
+	NODE_START,
+	NODE_RETURN,
+	NODE_CONST,
+} node_type;
+
+typedef struct _node {
+	union {
+		uint64_t integer;
+		double flt;
+	} data;
+
+	node_type type;
+	struct _node **children;
+	size_t children_length;
+	size_t children_size;
+	size_t id;
+} node;
+
+void add_child(node *n, node *child);
+node *ir_parse(token *tokens);
+
+#endif