Added assignment for nasm preassembler thing

9 files changed, 492 insertions, 0 deletions

diff --git a/sem1/osc/miniproject/cnasm/Makefile b/sem1/osc/miniproject/cnasm/Makefile
new file mode 100644
index 0000000..9ace547
--- /dev/null
+++ b/sem1/osc/miniproject/cnasm/Makefile
@@ -0,0 +1,30 @@
+
+LEX=flex
+YACC=bison
+LIBS=-ly -lfl -lm
+CC=gcc
+
+PROG=regn
+TRASH=lex.yy.c $(PROG).tab.c $(PROG) $(PROG).tab.h $(PROG).output
+
+$(PROG): $(PROG).tab.o lex.yy.o ast.c codegen.c
+		$(CC) -ggdb -o $@ $^ $(LIBS) 
+
+$(PROG).tab.c $(PROG).tab.h: $(PROG).y
+		$(YACC) -d -v $(PROG).y
+
+lex.yy.c: $(PROG).l
+		$(LEX) $(PROG).l
+
+%.o: %.c
+	$(CC) -ggdb -c -o $@ $^
+
+PHONY: clean run
+
+run: $(PROG)
+	./$(PROG)
+
+clean:
+	rm -f *.o
+	rm -f $(TRASH)
+
diff --git a/sem1/osc/miniproject/cnasm/ast.c b/sem1/osc/miniproject/cnasm/ast.c
new file mode 100644
index 0000000..035b75d
--- /dev/null
+++ b/sem1/osc/miniproject/cnasm/ast.c
@@ -0,0 +1,98 @@
+#include "ast.h"
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+static ast_node_t *create_empty_node() {
+	ast_node_t *n = malloc(sizeof(ast_node_t));
+	memset(n, 0, sizeof(ast_node_t));
+}
+
+ast_node_t *insert_ctrl(enum ntype t, cond_t *c, ast_node_t *iftrue, ast_node_t *iffalse) {
+	ast_node_t *n = create_empty_node();
+
+	n->t = t;
+	n->flowctrl.condition = c;
+	n->flowctrl.iftrue = iftrue;
+	n->flowctrl.iffalse = iffalse;
+
+	return n;
+}
+
+ast_node_t *insert_for(char *pre, cond_t *c, char *inc, ast_node_t *stuff) {
+	ast_node_t *n = create_empty_node();
+
+	n->t = TFOR;
+	n->forloop.condition = c;
+	n->forloop.pre = pre;
+	n->forloop.inc = inc;
+	n->forloop.stuff = stuff;
+
+	return n;
+}
+
+ast_node_t *insert_stm(ast_node_t *stm, ast_node_t *stm_list) {
+	ast_node_t *n = create_empty_node();
+
+	n->t = TSTM_LIST;
+	n->list.children[0] = stm_list;
+	n->list.children[1] = stm;
+
+	return n;
+}
+ast_node_t *insert_ident(char *ident) {
+	ast_node_t *n = create_empty_node();
+
+	n->t = TIDENT;
+	n->ident = ident;
+
+	return n;
+}
+
+cond_t *insert_cond(uint8_t cmp, char *a, char *b) {
+	cond_t *c = malloc( sizeof(cond_t));
+
+	c->cmp = cmp;
+	c->a = a;
+	c->b = b;
+}
+
+void node_print(ast_node_t *node) {
+	if( !node ){
+		printf("Nil");
+		return;
+	}
+	switch(node->t) {
+		case TSTM_LIST: 
+			printf("Stm_list(");
+			node_print(node->list.children[0]);
+			printf(",");
+			node_print(node->list.children[1]);
+			printf(")");
+			break;
+		case TIF:
+			printf("If");
+			printf("(%s %c %s) {", node->flowctrl.condition->a,
+					node->flowctrl.condition->cmp,
+					node->flowctrl.condition->b);
+			node_print(node->flowctrl.iftrue);
+			printf("}{");
+			node_print(node->flowctrl.iffalse);
+			printf("}");
+			break;
+		case TIDENT:
+			printf("%s", node->ident);
+			break;
+		case TWHILE:
+			printf("while");
+			printf("(%s %c %s) {", node->flowctrl.condition->a,
+					node->flowctrl.condition->cmp,
+					node->flowctrl.condition->b);
+			node_print(node->flowctrl.iftrue);
+			printf("}");
+			break;
+		default:
+			printf("invalid");
+	}
+}
diff --git a/sem1/osc/miniproject/cnasm/ast.h b/sem1/osc/miniproject/cnasm/ast.h
new file mode 100644
index 0000000..61a8f4f
--- /dev/null
+++ b/sem1/osc/miniproject/cnasm/ast.h
@@ -0,0 +1,53 @@
+#ifndef AST_HEADER
+#define AST_HEADER
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#define CEQ 0x10
+#define CNEQ CEQ ^ 0x80
+#define CGT 0x20
+#define CLT 0x30
+#define CLEQ CGT ^ 0x80
+#define CGEQ CLT ^ 0x80
+
+enum ntype { TSTM_LIST, TIF, TFOR, TIDENT, TWHILE};
+
+typedef struct cond {
+	uint8_t cmp;
+	char *a;
+	char *b;
+} cond_t;
+
+typedef struct ast_node {
+	enum ntype t;
+	// Dependent on type
+	union {
+		struct {
+			cond_t *condition;
+			struct ast_node *iftrue;
+			struct ast_node *iffalse;
+		} flowctrl;
+		struct {
+			cond_t *condition;
+			char *pre;
+			char *inc;
+			struct ast_node *stuff;
+		} forloop;
+		char *ident;
+		struct {
+			struct ast_node *children[2];
+		} list;
+	};
+} ast_node_t;
+
+ast_node_t *insert_ctrl(enum ntype t, cond_t *c, ast_node_t *iftrue, ast_node_t *iffalse);
+ast_node_t *insert_stm(ast_node_t *stm, ast_node_t *stm_list);
+ast_node_t *insert_ident(char *ident);
+ast_node_t *insert_for(char *pre, cond_t *c, char *inc, ast_node_t *stuff);
+
+cond_t *insert_cond(uint8_t cmp, char *a, char *b);
+
+void node_print(ast_node_t *node);
+
+#endif 
diff --git a/sem1/osc/miniproject/cnasm/codegen.c b/sem1/osc/miniproject/cnasm/codegen.c
new file mode 100644
index 0000000..c995df9
--- /dev/null
+++ b/sem1/osc/miniproject/cnasm/codegen.c
@@ -0,0 +1,132 @@
+#include "codegen.h"
+
+#include <stdio.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include "ast.h"
+
+static void gencondjmp(FILE *f, cond_t *c, bool neg) {
+	uint8_t cmp = neg ? c->cmp^0x80 : c->cmp;
+	fprintf(f, "cmp %s %s\n", c->a, c->b);
+	switch(cmp) {
+		case CEQ:
+			fprintf(f, "je ");
+			break;
+		case CNEQ:
+			fprintf(f, "jne ");
+			break;
+		case CGT:
+			fprintf(f, "jg ");
+			break;
+		case CLT:
+			fprintf(f, "jl ");
+			break;
+		case CLEQ:
+			fprintf(f, "jle ");
+			break;
+		case CGEQ:
+			fprintf(f, "jge ");
+			break;
+		default:
+			fprintf(stderr, "Invalid cmp type %x", cmp);
+			fprintf(f, "jmp ");
+	}
+}
+
+static void genif(FILE *f, struct genctx *ctx, ast_node_t *n) {
+	bool doElse = n->flowctrl.iffalse;
+	// Create conditional jump
+	gencondjmp(f, n->flowctrl.condition, true);
+	if( doElse ) {
+		fprintf(f, "else_%d\n", ctx->nested);
+	} else {
+		fprintf(f, "end_%d\n", ctx->nested);
+	}
+
+	struct genctx octx = { ctx->nested+1 };
+	// Paste code
+	gentree(f, &octx, n->flowctrl.iftrue);
+	
+	// Do else
+	if( doElse ) {
+		fprintf(f, "jmp end_%d\n", ctx->nested);
+		fprintf(f, "else_%d:\n", ctx->nested);
+		gentree(f, &octx, n->flowctrl.iffalse);
+	}
+
+	// End block
+	fprintf(f, "end_%d:\n", ctx->nested);
+}
+
+static void genwhile(FILE *f, struct genctx *ctx, ast_node_t *n) {
+	// Create loop label
+	fprintf(f, "loop_%d:\n", ctx->nested);
+
+	// Create conditional jump
+	gencondjmp(f, n->flowctrl.condition, true);
+	fprintf(f, "end_%d\n", ctx->nested);
+
+	struct genctx octx = { ctx->nested+1 };
+	// Paste code
+	gentree(f, &octx, n->flowctrl.iftrue);
+
+	// Jump to start
+	fprintf(f, "jmp loop_%d\n", ctx->nested);
+	
+	// End block
+	fprintf(f, "end_%d:\n", ctx->nested);
+}
+
+static void genfor(FILE *f, struct genctx *ctx, ast_node_t *n) {
+	// Do pre stuff
+	fprintf(f, "%s\n", n->forloop.pre);
+
+	// Create loop label
+	fprintf(f, "loop_%d:\n", ctx->nested);
+
+	// Create conditional jump
+	gencondjmp(f, n->flowctrl.condition, true);
+	fprintf(f, "end_%d\n", ctx->nested);
+
+	struct genctx octx = { ctx->nested+1 };
+	// Paste code
+	gentree(f, &octx, n->forloop.stuff);
+
+	// Do inc stuff
+	fprintf(f, "%s\n", n->forloop.inc);
+	// Jump to start
+	fprintf(f, "jmp loop_%d\n", ctx->nested);
+	
+	// End block
+	fprintf(f, "end_%d:\n", ctx->nested);
+}
+
+void gentree(FILE *f, struct genctx *ctx, ast_node_t *n) {
+	if( !n ) {
+		return;
+	}
+	if( ctx == NULL ) {
+		ctx = malloc(sizeof(struct genctx));
+		ctx->nested = 0;
+	}
+	switch(n->t) {
+		case TSTM_LIST: 
+			gentree(f, ctx, n->list.children[0]);
+			gentree(f, ctx, n->list.children[1]);
+			break;
+		case TIF:
+			genif(f, ctx, n);
+			break;
+		case TIDENT:
+			fprintf(f, "%s\n", n->ident);
+			break;
+		case TFOR:
+			genfor(f, ctx, n);
+			break;
+		case TWHILE:
+			genwhile(f, ctx, n);
+			break;
+		default:
+			return;
+	}
+}
diff --git a/sem1/osc/miniproject/cnasm/codegen.h b/sem1/osc/miniproject/cnasm/codegen.h
new file mode 100644
index 0000000..24ad6c4
--- /dev/null
+++ b/sem1/osc/miniproject/cnasm/codegen.h
@@ -0,0 +1,14 @@
+
+#ifndef CODEGEN_HEADER
+#define CODEGEN_HEADER
+
+#include <stdio.h>
+#include "ast.h"
+
+struct genctx {
+	unsigned int nested;
+};
+
+void gentree(FILE *f, struct genctx *ctx, ast_node_t *n);
+
+#endif 
diff --git a/sem1/osc/miniproject/cnasm/regn.l b/sem1/osc/miniproject/cnasm/regn.l
new file mode 100644
index 0000000..00876d6
--- /dev/null
+++ b/sem1/osc/miniproject/cnasm/regn.l
@@ -0,0 +1,39 @@
+%{
+#include <math.h>
+#include <string.h>
+#include "regn.tab.h"
+#include "ast.h"
+%}
+
+id		[a-zA-Z0-9_;]([^\n=><(){}])*
+if		if[ \t]*
+else	else[ \t]*
+for		for[ \t]*
+while	while[ \t]*
+
+%%
+
+{if} {return IFF;};
+{else} {return EELSE;};
+{for} {return FFOR;};
+{while} {return WHILE;};
+"(" {return LP;};
+")" {return RP;};
+"{" {return LCP;};
+"}" {return RCP;};
+"<" {yylval.cmp = CLT; return CMP;};
+">" {yylval.cmp = CGT; return CMP;};
+"=" {yylval.cmp = CEQ; return CMP;};
+"!=" {yylval.cmp = CNEQ; return CMP;};
+{id} {yylval.string = strdup(yytext);return ID;};
+[1-9][0-9]* {yylval.string = yytext;return NO;};
+
+
+
+[ \t\n] ;
+
+.           {return yytext[0];} 
+
+%%
+
+// TODO match normal assembler
diff --git a/sem1/osc/miniproject/cnasm/regn.y b/sem1/osc/miniproject/cnasm/regn.y
new file mode 100644
index 0000000..b72d440
--- /dev/null
+++ b/sem1/osc/miniproject/cnasm/regn.y
@@ -0,0 +1,81 @@
+%{
+#include "ast.h"
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include "codegen.h"
+
+#define CLEAN_BOTH 2
+#define CLEAN_DST 1
+
+char *strconcat(char *dst, char *src, unsigned int clean) {
+	size_t dstlen = strlen(dst) + 1;
+	size_t srclen = strlen(src) + 1;
+
+	// Create new duplicate
+	char *new = malloc(( dstlen + srclen ) * sizeof(char));
+
+	// Copy stuff
+	memcpy(new, dst, dstlen);
+	strcat(new, src);
+
+	// Free old one
+	if( clean-- ) {
+		free(dst);
+
+		if( clean ) {
+			free(src);
+		}
+	}
+	return new;
+}
+
+// Trace node
+
+%}
+
+%token IFF EELSE FFOR RP RCP RSP LP LCP LSP ID COLON CMP NO WHILE
+
+%union {
+	char				*string;
+	struct ast_node		*node;
+	struct cond			*condition;
+	uint8_t				cmp;
+}
+
+%type <string>	ID 
+%type <node>	statement stm_list 
+%type <cmp>		CMP
+%type <condition> condition
+
+%%
+
+program: stm_list 			{gentree(stdout, NULL, $1);printf("\n");};
+
+stm_list: statement				{ $$ = $1; }
+		| stm_list statement 	{ $$ = insert_stm($2, $1); };
+
+condition: ID CMP ID		{ $$ = insert_cond($2, $1, $3); }
+		 | ID				{ $$ = insert_cond(CNEQ, $1, "0");};
+
+statement: ID																{$$ = insert_ident($1);}
+		 | IFF LP condition RP LCP stm_list RCP								{$$ = insert_ctrl(TIF, $3, $6, NULL);}
+		 | IFF LP condition RP LCP stm_list RCP	EELSE LCP stm_list RCP		{$$ = insert_ctrl(TIF, $3, $6, $10);}
+		 | WHILE LP condition RP LCP stm_list RCP							{$$ = insert_ctrl(TWHILE, $3, $6, NULL);}
+		 | FFOR LP ID LP condition LP ID RP LCP stm_list RCP				{$$ = insert_for($3, $5, $7, $10);};
+
+%%
+
+
+int main() {
+
+	/*for(;;) {
+		int t = yylex();
+		printf("yylex: %d\n", t);
+	} */
+
+	yyparse(); 
+}
+
diff --git a/sem1/osc/miniproject/cnasm/test.asm b/sem1/osc/miniproject/cnasm/test.asm
new file mode 100644
index 0000000..77a3572
--- /dev/null
+++ b/sem1/osc/miniproject/cnasm/test.asm
@@ -0,0 +1,39 @@
+global _start
+
+section .data
+        align 2
+        ; String, which is just a collection of bytes, 0xA is newline
+        str:     db 'Hello, world!',0xA
+        strLen:  equ $-str
+
+section .bss
+
+section .text
+        _start:
+
+        mov     edx, strLen     ; Arg three: the length of the string
+        mov     ecx, str        ; Arg two: the address of the string
+        mov     ebx, 1          ; Arg one: file descriptor, in this case stdout
+        mov     eax, 4          ; Syscall number, in this case the 
+        int     0x80            ; Interrupt 0x80        
+
+		if ( hej = 10 ) {
+			mov     ebx, 0          ; Arg one: the status
+			mov     eax, 1          ; Syscall number:
+			if(cool) {
+				int     0x80
+			}
+		} else {
+			while( lol ) {
+				mov hej, 0
+			}
+		}
+		while( lol ) {
+			mov hej, 0
+		}
+
+		hej
+
+		for(mov a, 0( a < 100( a++ ) {
+			test
+		}
diff --git a/sem1/osc/noter.md b/sem1/osc/noter.md
index 92f875a..6e13640 100644
--- a/sem1/osc/noter.md
+++ b/sem1/osc/noter.md
@@ -9,3 +9,9 @@ Leksikal analysen: bruger regulær
 Parsing: ikke regulær.
 
 Shift-reduce parser.
+
+3 adress code bruges til mellem kode.
+
+In order: tree (venstre, top, højre)
+preorder: tree (top, venstre, højre)
+postorder: tree (venstre, højre, top)