diff options
| -rw-r--r-- | sem1/osc/miniproject/cnasm/Makefile | 30 | ||||
| -rw-r--r-- | sem1/osc/miniproject/cnasm/ast.c | 98 | ||||
| -rw-r--r-- | sem1/osc/miniproject/cnasm/ast.h | 53 | ||||
| -rw-r--r-- | sem1/osc/miniproject/cnasm/codegen.c | 132 | ||||
| -rw-r--r-- | sem1/osc/miniproject/cnasm/codegen.h | 14 | ||||
| -rw-r--r-- | sem1/osc/miniproject/cnasm/regn.l | 39 | ||||
| -rw-r--r-- | sem1/osc/miniproject/cnasm/regn.y | 81 | ||||
| -rw-r--r-- | sem1/osc/miniproject/cnasm/test.asm | 39 | ||||
| -rw-r--r-- | sem1/osc/noter.md | 6 |
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) |