From df3e7a4206850f0fd9b618e7f886df9716b6a25a Mon Sep 17 00:00:00 2001 From: Bernhard Urban Date: Sat, 29 May 2010 20:07:07 +0200 Subject: [PATCH] codeb: init von codea --- .gitignore | 7 + codeb/Makefile | 48 +++++ codeb/chelper.c | 72 ++++++++ codeb/chelper.h | 9 + codeb/code.bfe | 267 +++++++++++++++++++++++++++ codeb/parser.y | 448 ++++++++++++++++++++++++++++++++++++++++++++++ codeb/scanner.lex | 67 +++++++ codeb/symtable.c | 146 +++++++++++++++ codeb/symtable.h | 26 +++ codeb/tree.c | 118 ++++++++++++ codeb/tree.h | 53 ++++++ 11 files changed, 1261 insertions(+) create mode 100644 codeb/Makefile create mode 100644 codeb/chelper.c create mode 100644 codeb/chelper.h create mode 100644 codeb/code.bfe create mode 100644 codeb/parser.y create mode 100644 codeb/scanner.lex create mode 100644 codeb/symtable.c create mode 100644 codeb/symtable.h create mode 100644 codeb/tree.c create mode 100644 codeb/tree.h diff --git a/.gitignore b/.gitignore index 300bf9d..369abdb 100644 --- a/.gitignore +++ b/.gitignore @@ -35,5 +35,12 @@ codea/parser.h codea/scanner.c codea/code.c +#codeb +codeb/codeb +codeb/parser.c +codeb/parser.h +codeb/scanner.c +codeb/code.c + #weitere eintragen... torero/torero.log diff --git a/codeb/Makefile b/codeb/Makefile new file mode 100644 index 0000000..a1dfc64 --- /dev/null +++ b/codeb/Makefile @@ -0,0 +1,48 @@ +SHELL := bash +NAME := codeb +CFLAGS := -ansi -pedantic -D_GNU_SOURCE -g +OBJS := scanner.o parser.o symtable.o code.o chelper.o tree.o + +all: $(NAME) + +$(NAME): $(OBJS) + @echo " LINK $@" + @gcc -o $@ $(OBJS) -lfl + +scanner.c: oxout.l + @echo " FLEX $<" + @flex -o$@ $< + +#dirty deps ;) +%.o: %.c parser.h symtable.h chelper.h tree.h + @echo " CC $<" + @cp $< tmp.c + @gcc -c $(CFLAGS) $< #-Wall + @rm tmp.c + +parser.c: oxout.y chelper.h tree.h + @echo " YACC $<" + @yacc -t -v -d $< -o $@ + +parser.h: parser.c + +oxout.y oxout.l: parser.y scanner.lex + @echo " OX $^" + @ox $^ + +%.c: %.bfe chelper.h tree.h + @echo " IBURG $<" + @bfe < $< | iburg > $@ + +.PHONY: clean +clean: + rm -f $(NAME) $(OBJS) scanner.c parser.{h,c,output} oxout.{y,l,h} code.c + +1test: + ~/test/scripts/modlvatest_codeb.sh 2>&1 + +lvatest: + /usr/ftp/pub/ublu/test/$(NAME)/test 2>&1 + +bench: + ~/test/scripts/bench.sh $(NAME) diff --git a/codeb/chelper.c b/codeb/chelper.c new file mode 100644 index 0000000..015e7a3 --- /dev/null +++ b/codeb/chelper.c @@ -0,0 +1,72 @@ +#include +#include +#include +#include "chelper.h" +#include "tree.h" + +#if 0 +#define DDCHELP +#endif + +#define REGLEN 4 +static char *regs64[] = {"rax", "r10", "r11", "r9"}; +static char *regs8l[] = {"al", "r10b", "r11b", "r9b"}; + +void func_header(char *s) +{ + printf("\t.globl %1$s\n\t.type %1$s, @function\n%1$s:\n", s); +} + +void func_footer(void) +{ + printf("\tret\n"); +} + +void move(char *src, char *dst) +{ + if(strcmp(src,dst) != 0) { + printf("\tmovq %%%s, %%%s\n", src, dst); + } +} + +void moveimm(long imm, char *dst) +{ + char buf[100]; + sprintf(buf, "$%d", imm); + printf("\tmovq %s, %%%s\n", buf, dst); +} + +char *next_reg(char *s, int params) +{ + int i = 0; + if (s != (char*) NULL) { + while(strcmp(s, regs64[i]) != 0) { + i = (i+1) % REGLEN; + } + i = (i+1) % REGLEN; + } +#ifdef DDCHELP + fprintf(stderr, "next_reg(): %s (bei %i parameter)\n", regs64[i], params); +#endif + return regs64[i]; +} + +char *reg_64to8l(char *s) +{ + int i = 0; + if (s != (char*) NULL) { + while(strcmp(s, regs64[i]) != 0) { + i = (i+1) % REGLEN; + } + return regs8l[i]; + } + fprintf(stderr, "reg_64to8l(): sollte nicht passieren\n"); + exit(4); +} + +char *param_reg(int num) +{ + char *regs[] = {"rdi", "rsi", "rdx", "rcx", "r8", "r9"}; + return regs[num]; +} + diff --git a/codeb/chelper.h b/codeb/chelper.h new file mode 100644 index 0000000..d857db0 --- /dev/null +++ b/codeb/chelper.h @@ -0,0 +1,9 @@ +#ifndef __CHELPER_H +#define __CHELPER_H +void func_header(char *s); +void func_footer(void); +char *next_reg(char *s, int params); +char *reg_64to8l(char *s); +char *param_reg(int num); +void move(char *src, char *dest); +#endif diff --git a/codeb/code.bfe b/codeb/code.bfe new file mode 100644 index 0000000..7150830 --- /dev/null +++ b/codeb/code.bfe @@ -0,0 +1,267 @@ +%{ +#define BFEHAX + +/* macros zum registerzugriff bei kinder */ +#define KID_REG(A) bnode->kids[A]->reg +#define KIDKID_REG(A,B) bnode->kids[A]->kids[B]->reg +#define KIDKIDKID_REG(A,B,C) bnode->kids[A]->kids[B]->kids[C]->reg + +/* macros zum wertezugriff bei kindern */ +#define KID_VAL(A) bnode->kids[A]->val +#define KIDKID_VAL(A,B) bnode->kids[A]->kids[B]->val +#define KIDKIDKID_VAL(A,B,C) bnode->kids[A]->kids[B]->kids[C]->val + +/* macros zum zugriff des aktuellen knotens */ +#define BN_REG bnode->reg +#define BN_VAL bnode->val + +/* wenn sich ein parameter auf der "leseseite" (also links bei at&t syntax) + * befindet, dann soll dieses register verwendet werden */ +#define KIDREG2PARM(A) if(bnode->kids[A]->param_index > -1) { bnode->kids[A]->reg = param_reg(bnode->kids[A]->param_index); } +#define KIDKIDREG2PARM(A,B) if(bnode->kids[A]->kids[B]->param_index > -1) { bnode->kids[A]->kids[B]->reg = param_reg(bnode->kids[A]->kids[B]->param_index); } +#define KIDKIDKIDREG2PARM(A,B,C) if(bnode->kids[A]->kids[B]->kids[C]->param_index > -1) { bnode->kids[A]->kids[B]->kids[C]->reg = param_reg(bnode->kids[A]->kids[B]->kids[C]->param_index); } + +/* wenn sich ein parameter auf der "schreibeseite" befindet (also rechts bei + * at&t syntax), dann muss es vorher in ein temporaeres register gemovt werden */ +#define KIDREG2ID(A) if(bnode->kids[A]->op == O_ID && bnode->kids[A]->param_index > -1) move(param_reg(bnode->kids[A]->param_index), bnode->kids[A]->reg); + +#include +#include +#include +#include "tree.h" +#include "chelper.h" + +void gen_e_eno(struct treenode *bnode, char *instr) +{ + printf("\t//gen_e_eno(%s)\n", instr); + KIDREG2ID(0); + KIDREG2PARM(1); + printf("\t%s %%%s, %%%s\n", instr, KID_REG(1), KID_REG(0)); +} + +void gen_id_eno(struct treenode *bnode) +{ + printf("\t//gen_id_eno\n"); + KIDKIDREG2PARM(1,0); + printf("\taddq %%%s, %%%s\n", KIDKID_REG(1,0), KIDKID_REG(1,1)); + printf("\tsubq %%%s, %%%s\n", KIDKID_REG(1,1), BN_REG); +} + +void gen_e_field(struct treenode *bnode, char *instr) +{ + printf("\t//gen_e_field(%s)\n", instr); + KIDREG2ID(0); + KIDKIDREG2PARM(1,0); + printf("\t%s %d(%%%s), %%%s\n", instr, bnode->kids[1]->soffset * 8, KIDKID_REG(1,0), KID_REG(0)); +} + +void gen_field_imm(struct treenode *bnode) +{ + printf("\t//gen_field_imm\n"); + KIDKIDREG2PARM(0,0); + KIDREG2ID(1); + printf("\timulq $%d, %d(%%%s), %%%s\n", KID_VAL(1), bnode->kids[0]->soffset * 8, KIDKID_REG(0, 0), BN_REG); +} + +void gen_e_imm(struct treenode *bnode, char *instr) +{ + printf("\t//gen_e_imm(%s)\n", instr); + KIDREG2PARM(0); + KIDREG2ID(1); + /* man kann sich ein move der konstante bei der multiplikation ersparen */ + if(strcmp(instr, "imulq") == 0) { + if(KID_VAL(1) == 1 && strcmp(KID_REG(0), BN_REG) == 0) { + printf("\t//multiplikation mit 1 wegoptimiert\n"); + } else { + printf("\timulq $%d, %%%s, %%%s\n", KID_VAL(1), KID_REG(0), BN_REG); + } + } else { + if(strcmp(instr, "subq") == 0 && KID_VAL(1) == 0) { + printf("\t//subtraktion mit 0 wegoptimiert\n"); + move(KID_REG(0), BN_REG); + } else { + move(KID_REG(0), BN_REG); + printf("\t%s $%d, %%%s\n", instr, KID_VAL(1), BN_REG); + } + } +} + +void gen_imm_field(struct treenode *bnode) +{ + printf("\t//gen_imm_field\n"); + KIDREG2ID(0); + KIDKIDREG2PARM(1, 0); + + moveimm(KID_VAL(0), BN_REG); + printf("\tsubq %d(%%%s), %%%s\n", bnode->kids[1]->soffset * 8, KIDKID_REG(1, 0), BN_REG); +} + +void gen_imm_eno(struct treenode *bnode, char *instr) +{ + printf("\t//gen_imm_eno(%s)\n", instr); + KIDREG2ID(0); + KIDREG2PARM(1); + /* man kann sich ein move der konstante bei der multiplikation ersparen */ + if(strcmp(instr, "imulq") == 0) { + if(KID_VAL(0) == 1 && strcmp(KID_REG(1), BN_REG) == 0) { + printf("\t//multiplikation mit 1 wegoptimiert\n"); + } else { + printf("\timulq $%d, %%%s, %%%s\n", KID_VAL(0), KID_REG(1), BN_REG); + } + } else { /* addq */ + printf("\taddq $%d, %%%s\n", KID_VAL(0), BN_REG); + } +} + +void gen_eqless(struct treenode *bnode, char *op, short e0, short e1, short deep) +{ + printf("\t//gen_eqless_%i%i @ %i\n", e0, e1, deep); + if(e0) { KIDREG2PARM(0); } else { KIDREG2ID(0); } + if(e1) { KIDREG2PARM(1); } else { KIDREG2ID(1); } + + if(e0 && e1) { + if(deep) { + KIDKIDREG2PARM(1,0); + printf("\tcmp %d(%%%s), %%%s\n", bnode->kids[1]->soffset *8, KIDKID_REG(1,0), KID_REG(0)); + } else { + printf("\tcmp %%%s, %%%s\n", KID_REG(1), KID_REG(0)); + } + } else if(e0 && !e1) { + if (deep == 0) { + printf("\tcmp $%d, %%%s\n", KID_VAL(1), KID_REG(0)); + } else if (deep == 1) { + KIDKIDREG2PARM(0,0); + printf("\tcmp $%d, %%%s\n", KID_VAL(1), KIDKID_REG(0,0)); + } else if (deep == 2) { + KIDKIDKIDREG2PARM(0,0,0); + printf("\tcmp $%d, %%%s\n", KID_VAL(1), KIDKIDKID_REG(0,0,0)); + } + } else if(!e0 && e1) { + printf("\tcmp $%d, %%%s\n", KID_VAL(0), KID_REG(1)); + } + printf("\tset%s %%%s\n", op, reg_64to8l(BN_REG)); + printf("\tand $1, %%%s\n", BN_REG); +} + +void gen_lea(struct treenode *bnode, short e) +{ + printf("\t//gen_lea(e: %i)\n", e); + KIDREG2PARM(0); + if(e) { + KIDKIDREG2PARM(1,0); + printf("\tlea (%%%s,%%%s,%d), %%%s\n", KID_REG(0), KIDKID_REG(1,0), -1 * KIDKID_VAL(1,1), BN_REG); + } else { + KIDKIDREG2PARM(1,1); + printf("\tlea (%%%s,%%%s,%d), %%%s\n", KID_REG(0), KIDKID_REG(1,1), -1 * KIDKID_VAL(1,0), BN_REG); + } +} + +void gen_subspecial(struct treenode *bnode, short e) +{ + /* tritt z.b. bei snafu_05.0 auf */ + printf("\t//gen_subspecial(%i)\n", e); + KIDREG2ID(0); + KIDKIDREG2PARM(1,0); + + if(e) { + printf("\tsubq $%d, %%%s\n", KIDKID_VAL(1,0), BN_REG); + } else { + printf("\tsubq %%%s, %%%s\n", KIDKID_REG(1,0), BN_REG); + } + if(e) KIDKIDREG2PARM(1,1); + printf("\taddq %%%s, %%%s\n", KIDKID_REG(1,1), BN_REG); +} + +%} + +%start begin +%term O_RET=1 O_NULL=2 O_SUB=3 O_MUL=4 O_OR=5 O_LESS=6 O_EQ=7 O_ID=8 O_ADD=9 O_NUM=10 O_FIELD=11 O_MTWO=12 O_MFOUR=13 O_MEIGHT=14 O_MONE=15 + +%% + +begin: ret # 0 # printf("\n"); +ret: O_RET(retexpr) # 2 # printf("\t//o_ret(expr)\n"); move(BN_REG, "rax"); func_footer(); + +retexpr: O_ID # 1 # printf("\t//retexpr\n"); if(bnode->param_index > -1) move(param_reg(bnode->param_index), BN_REG); +retexpr: expr + +expr: O_ID # 0 # +expr: imm # 1 # moveimm(BN_VAL, BN_REG); + + +expr: O_SUB(expr,expr) # 2 # gen_e_eno(bnode, "subq"); +expr: O_SUB(expr,O_FIELD(expr)) # 2 # gen_e_field(bnode, "subq"); +expr: O_SUB(expr,imm) # 1 # gen_e_imm(bnode, "subq"); + +expr: O_SUB(expr,O_SUB(O_ID,expr)) # 2 # gen_subspecial(bnode, 0); +expr: O_SUB(expr,O_SUB(imm,expr)) # 2 # gen_subspecial(bnode, 1); + +expr: O_SUB(expr, O_ADD(O_ID,expr)) # 1 # gen_id_eno(bnode); + +expr: O_SUB(expr,O_MUL(O_MONE,expr)) # 1 # gen_lea(bnode,0); +expr: O_SUB(expr,O_MUL(O_MTWO,expr)) # 1 # gen_lea(bnode,0); +expr: O_SUB(expr,O_MUL(O_MFOUR,expr)) # 1 # gen_lea(bnode,0); +expr: O_SUB(expr,O_MUL(O_MEIGHT,expr)) # 1 # gen_lea(bnode,0); + +expr: O_SUB(expr,O_MUL(expr,O_MONE)) # 1 # gen_lea(bnode,1); +expr: O_SUB(expr,O_MUL(expr,O_MTWO)) # 1 # gen_lea(bnode,1); +expr: O_SUB(expr,O_MUL(expr,O_MFOUR)) # 1 # gen_lea(bnode,1); +expr: O_SUB(expr,O_MUL(expr,O_MEIGHT)) # 1 # gen_lea(bnode,1); + + +expr: O_ADD(expr,expr) # 1 # gen_e_eno(bnode, "addq"); +expr: O_ADD(expr,imm) # 2 # gen_e_imm(bnode, "addq"); +expr: O_ADD(imm,expr) # 1 # gen_imm_eno(bnode, "addq"); + +expr: O_ADD(expr,O_FIELD(expr)) # 2 # gen_e_field(bnode, "addq"); + + +expr: O_MUL(expr,expr) # 1 # gen_e_eno(bnode, "imulq"); +expr: O_MUL(expr,imm) # 1 # gen_e_imm(bnode, "imulq"); +expr: O_MUL(imm,expr) # 1 # gen_imm_eno(bnode, "imulq"); + +expr: O_MUL(expr,O_FIELD(expr)) # 1 # gen_e_field(bnode, "imulq"); +expr: O_MUL(O_FIELD(expr),imm) # 1 # gen_field_imm(bnode); + +expr: O_OR(expr,expr) # 1 # gen_e_eno(bnode, "orq"); +expr: O_OR(expr,imm) # 2 # gen_e_imm(bnode, "orq"); +expr: O_OR(expr,O_FIELD(expr)) # 2 # gen_e_field(bnode, "orq"); + + +expr: O_LESS(expr,expr) # 3 # gen_eqless(bnode, "l", 1, 1, 0); +expr: O_LESS(expr,O_FIELD(expr)) # 3 # gen_eqless(bnode, "l", 1, 1, 1); +expr: O_LESS(expr,imm) # 3 # gen_eqless(bnode, "l", 1, 0, 0); +expr: O_LESS(imm,expr) # 3 # gen_eqless(bnode, "g", 0, 1, 0); + + +expr: O_EQ(expr,expr) # 3 # gen_eqless(bnode, "e", 1, 1, 0); +expr: O_EQ(expr,O_FIELD(expr)) # 3 # gen_eqless(bnode, "e", 1, 1, 1); +expr: O_EQ(expr,imm) # 3 # gen_eqless(bnode, "e", 1, 0, 0); +expr: O_EQ(imm,expr) # 3 # gen_eqless(bnode, "e", 0, 1, 0); +expr: O_EQ(expr,O_NULL) # 3 # gen_eqless(bnode, "e", 1, 0, 0); + +expr: O_EQ(O_EQ(expr,O_NULL),O_NULL) # 3 # gen_eqless(bnode, "ne", 1, 0, 1); +expr: O_EQ(O_EQ(O_EQ(expr,O_NULL),O_NULL),O_NULL) # 3 # gen_eqless(bnode, "e", 1, 0, 2); + + +expr: O_FIELD(expr) # 1 # printf("\t//field(expr)\n"); KIDREG2PARM(0); printf("\tmovq %d(%%%s), %%%s\n", bnode->soffset * 8, KID_REG(0), BN_REG); +expr: O_FIELD(imm) # 1 # printf("\t//field(imm)\n"); printf("\tmovq %d, %%%s\n", KID_VAL(0) + (bnode->soffset * 8), BN_REG); + + +imm: O_ADD(imm,imm) # 0 # BN_VAL = KID_VAL(0) + KID_VAL(1); +imm: O_SUB(imm,imm) # 0 # BN_VAL = KID_VAL(0) - KID_VAL(1); +imm: O_MUL(imm,imm) # 0 # BN_VAL = KID_VAL(0) * KID_VAL(1); +imm: O_LESS(imm,imm) # 0 # BN_VAL = KID_VAL(0) < KID_VAL(1) ? 1 : 0; +imm: O_EQ(imm,imm) # 0 # BN_VAL = KID_VAL(0) == KID_VAL(1) ? 1 : 0; +imm: O_OR(imm,imm) # 0 # BN_VAL = KID_VAL(0) | KID_VAL(1); +imm: O_NUM # 0 # +imm: O_MONE # 0 # +imm: O_MTWO # 0 # +imm: O_MFOUR # 0 # +imm: O_MEIGHT # 0 # +imm: O_NULL # 0 # + +%% + +/* vim: filetype=c + */ diff --git a/codeb/parser.y b/codeb/parser.y new file mode 100644 index 0000000..9a08dcc --- /dev/null +++ b/codeb/parser.y @@ -0,0 +1,448 @@ +%{ + #include + #include + #include + #include "symtable.h" + #include "chelper.h" + #include "tree.h" + + #define MAX(A,B) (A > B ? A : B) +%} + +%start Input +%token STRUCT END METHOD VAR IF THEN ELSE WHILE DO RETURN NOT OR THIS IDENT NUM ASSIGN + +@macro xxputsin(xx,) + @i xx = @Statement.sin@; +@end + +@macro statinout() + @i @Statement.sout@ = @Statement.sin@; + /* das + *> xxputsin(@Statement.sout@,) + * geht nicht, weil verschachtelte macros deaktiviert sind */ +@end + +/* beschreibung der attribute + * s: symboltabelle + * f: symboltabelle fuer quirks mit structur und parameter + * gparamges: anzahl der parameter in einer methode + * parms: parametercounter + * node: baum fuer iburg + * sin: symboltabelle fuer statement ("eingabe") + * sout: symboltabelle die aus einem statement wieder rauskommt ("ausgabe") + */ +@autoinh s gparamges +@autosyn node imm + +@attributes { char *name; } IDENT +@attributes { long val; } NUM +@attributes { struct symbol *f; int paramges; int parms; } Parms +@attributes { struct symbol *f; } Program Structdef; +@attributes { struct symbol *f; int offsetcount; } FeldID +@attributes { struct symbol *s; } Methoddef +@attributes { struct symbol *s; int gparamges; } Statseq Exprs +@attributes { struct symbol *s; int gparamges; struct treenode *node; short imm; } Expr Minusterm Multerm Orterm Feld Term +@attributes { struct symbol *s; int gparamges; struct treenode *node; } Lexpr +@attributes { struct symbol *sin; int gparamges; struct symbol *sout; struct treenode *node; } Statement + +@traversal @postorder c +@traversal @preorder reg +@traversal @preorder gen + +%% +Input: + Program + @{ + @i @Program.f@ = tab_new(); + @gen printf("\t.text\n"); + @} + ; + +Program: + Methoddef ';' Program + @{ + @i @Methoddef.s@ = @Program.0.f@; + @i @Program.1.f@ = @Program.0.f@; + @} + + | Structdef ';' Program + @{ + @i @Program.1.f@ = tab_merge(@Program.0.f@, @Structdef.f@, 1); + @} + | + ; + +Methoddef: + METHOD IDENT '(' Parms ')' Statseq END + @{ + @i @Parms.parms@ = 1; + @i @Statseq.s@ = tab_merge(@Methoddef.s@, @Parms.f@, 0); + @i @Statseq.gparamges@ = @Parms.paramges@; + @gen func_header(@IDENT.name@); + @} + ; + +Structdef: + STRUCT FeldID END + @{ + @i @Structdef.f@ = @FeldID.f@; + @i @FeldID.offsetcount@ = 0; + @} + ; + +Parms: + /* lokale Vars werden in Statement in die tabelle eingefuegt */ + IDENT Parms + @{ + @i @Parms.1.parms@ = @Parms.0.parms@ + 1; + @i @Parms.0.paramges@ = @Parms.1.paramges@; + @i @Parms.0.f@ = tab_add_symbol(@Parms.1.f@, @IDENT.name@, S_PARM, 1, @Parms.parms@, -1); + @} + + | + @{ + @i @Parms.f@ = tab_new(); + @i @Parms.paramges@ = @Parms.parms@; + @} + ; + +FeldID: + IDENT FeldID + @{ + @i @FeldID.1.offsetcount@ = @FeldID.0.offsetcount@ + 1; + @i @FeldID.0.f@ = tab_add_symbol(@FeldID.1.f@, @IDENT.name@, S_FIELD, 1, -1, @FeldID.0.offsetcount@); + @} + + | + @{ + @i @FeldID.f@ = tab_new(); + @} + ; + +Statseq: + Statement ';' Statseq + @{ + @i @Statement.sin@ = @Statseq.0.s@; + @i @Statseq.1.s@ = @Statement.sout@; + @gen write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1); + @} + + | + ; + +Statement: + Lexpr ASSIGN Expr + @{ + statinout() + xxputsin(@Lexpr.s@,) + xxputsin(@Expr.s@,) + @i @Statement.node@ = TREENULL; + @} + + | VAR IDENT ASSIGN Expr + @{ + /* tab_clone ist hier noetig, vgl. folgendes statement + * > var x := x - 1; */ + @i @Statement.sout@ = tab_add_symbol(tab_clone(@Statement.sin@), @IDENT.name@, S_VAR, 1, -1, -1); + xxputsin(@Expr.s@,) + @i @Statement.node@ = TREENULL; + @} + + | Expr + @{ + statinout() + xxputsin(@Expr.s@,) + @i @Statement.node@ = TREENULL; + @} + + | IF Expr THEN Statseq END + @{ + statinout() + xxputsin(@Expr.s@,) + xxputsin(@Statseq.s@,) + @i @Statement.node@ = TREENULL; + @} + + | IF Expr THEN Statseq ELSE Statseq END + @{ + statinout() + xxputsin(@Expr.s@,) + xxputsin(@Statseq.0.s@,) + xxputsin(@Statseq.1.s@,) + @i @Statement.node@ = TREENULL; + @} + + | WHILE Expr DO Statseq END + @{ + statinout() + xxputsin(@Expr.s@,) + xxputsin(@Statseq.s@,) + @i @Statement.node@ = TREENULL; + @} + + | RETURN Expr + @{ + statinout() + xxputsin(@Expr.s@,) + @i @Statement.node@ = new_node(O_RET, @Expr.node@, TREENULL); + @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@); + @} + ; + +Lexpr: + IDENT + @{ + @i @Lexpr.node@ = TREENULL; + @c check(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM); + /* this.feldname */ + /* TODO fuer zuweisungen ... (codeb?) */ + @} + + | Feld + ; + +Feld: Term '.' IDENT + @{ + @c check(@Feld.s@, @IDENT.name@, S_FIELD); + @i @Feld.node@ = new_field(@IDENT.name@, @Term.node@, TREENULL, tab_lookup(@Feld.s@, @IDENT.name@, S_FIELD) == SYMNULL ? -1 : tab_lookup(@Feld.s@, @IDENT.name@, S_FIELD)->soffset); + + @reg @Term.node@->reg = @Feld.node@->reg; + @} + ; + +Expr: + Term + @{ + @reg @Term.node@->reg = @Expr.node@->reg; + @} + + | NOT Term + @{ + @i @Expr.node@ = new_node(O_EQ, @Term.node@, new_node(O_NULL, TREENULL, TREENULL)); + + @reg @Term.node@->reg = @Expr.node@->reg; + @} + + | Term Minusterm + @{ + @i @Expr.node@ = new_node(O_SUB, @Term.node@, @Minusterm.node@); + @i @Expr.imm@ = @Term.imm@ && @Minusterm.imm@; + + @reg { + if(!(@Expr.node@->kids[0] == TREENULL && @Expr.node@->kids[1] == TREENULL)) { + @Term.node@->reg = @Expr.node@->reg; + if(@Minusterm.imm@) { + @Minusterm.node@->reg = @Expr.node@->reg; + } else { + @Minusterm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@); + } + } + } + @} + + | Term Multerm + @{ + @i @Expr.node@ = new_node(O_MUL, @Term.node@, @Multerm.node@); + @i @Expr.imm@ = @Term.imm@ && @Multerm.imm@; + + @reg { + @Term.node@->reg = @Expr.node@->reg; + if(@Term.imm@) { + @Multerm.node@->reg = @Expr.node@->reg; + } else { + @Multerm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@); + } + } + @} + + | Term Orterm + @{ + @i @Expr.node@ = new_node(O_OR, @Term.node@, @Orterm.node@); + @i @Expr.imm@ = @Term.imm@ && @Orterm.imm@; + + @reg { + @Term.node@->reg = @Expr.node@->reg; + @Orterm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@); + } + @} + + | Term '<' Term + @{ + @i @Expr.node@ = new_node(O_LESS, @Term.0.node@, @Term.1.node@); + @i @Expr.imm@ = @Term.0.imm@ && @Term.0.imm@; + + @reg { + @Term.0.node@->reg = @Expr.node@->reg; + @Term.1.node@->reg = next_reg(@Term.0.node@->reg, @Expr.gparamges@); + } + @} + + | Term '=' Term + @{ + @i @Expr.node@ = new_node(O_EQ, @Term.0.node@, @Term.1.node@); + @i @Expr.imm@ = @Term.0.imm@ && @Term.0.imm@; + + @reg { + @Term.0.node@->reg = @Expr.node@->reg; + @Term.1.node@->reg = next_reg(@Term.0.node@->reg, @Expr.gparamges@); + } + @} + ; + +Minusterm: + '-' Term Minusterm + @{ + @i @Minusterm.node@ = new_node(O_ADD, @Minusterm.1.node@, @Term.node@); + @i @Minusterm.0.imm@ = @Term.imm@ && @Minusterm.1.imm@; + + @reg { + @Minusterm.1.node@->reg = @Minusterm.node@->reg; + if(@Minusterm.1.imm@) { + @Term.node@->reg = @Minusterm.node@->reg; + } else { + @Term.node@->reg = next_reg(@Minusterm.1.node@->reg, @Minusterm.gparamges@); + } + } + @} + + | '-' Term + @{ + @reg @Term.node@->reg = @Minusterm.node@->reg; + @} + ; + +Multerm: + '*' Term Multerm + @{ + @i @Multerm.node@ = new_node(O_MUL, @Multerm.1.node@, @Term.node@); + @i @Multerm.0.imm@ = @Term.imm@ && @Multerm.1.imm@; + + @reg { + @Multerm.1.node@->reg = @Multerm.node@->reg; + if(@Multerm.1.imm@) { + @Term.node@->reg = @Multerm.node@->reg; + } else { + @Term.node@->reg = next_reg(@Multerm.1.node@->reg, @Multerm.gparamges@); + } + } + @} + + | '*' Term + @{ + @reg @Term.node@->reg = @Multerm.node@->reg; + @} + ; + +Orterm: + OR Term Orterm + @{ + @i @Orterm.node@ = new_node(O_OR, @Orterm.1.node@, @Term.node@); + @i @Orterm.0.imm@ = @Term.imm@ && @Orterm.1.imm@; + + @reg { + @Orterm.1.node@->reg = @Orterm.node@->reg; + if(@Orterm.1.imm@) { + @Term.node@->reg = @Orterm.node@->reg; + } else { + @Term.node@->reg = next_reg(@Orterm.1.node@->reg, @Orterm.gparamges@); + } + } + @} + | OR Term + @{ + @reg @Term.node@->reg = @Orterm.node@->reg; + @} + + ; + +Term: + '(' Expr ')' + @{ + @i @Term.node@ = @Expr.node@; + @} + + | NUM + @{ + @i @Term.node@ = new_number(@NUM.val@); + @i @Term.imm@ = 1; + @} + + | '-' NUM + @{ + @i @Term.node@ = new_number(-1 * (@NUM.val@)); + @i @Term.imm@ = 1; + @} + + | THIS + @{ + @i @Term.node@ = new_param(O_ID, strdup("this"), TREENULL, TREENULL, 0); + @i @Term.imm@ = 0; + @} + + | IDENT + @{ + @c check(@Term.s@, @IDENT.name@, S_VAR|S_PARM); + + @i @Term.imm@ = 0; + @i { + @Term.node@ = TREENULL; + if(tab_lookup(@Term.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) { + /* es handelt sich um ein feldzugriff auf this */ + @Term.node@ = new_field(@IDENT.name@, new_param(O_ID, strdup("this"), TREENULL, TREENULL, 0), TREENULL, tab_lookup(@Term.s@, @IDENT.name@, S_FIELD) == SYMNULL ? -1 : tab_lookup(@Term.s@, @IDENT.name@, S_FIELD)->soffset); + } else { /* param oder var */ + @Term.node@ = new_param(O_ID, @IDENT.name@, TREENULL, TREENULL, tab_lookup(@Term.s@, @IDENT.name@, S_PARM) == SYMNULL ? -1 : tab_lookup(@Term.s@, @IDENT.name@, S_PARM)->param_index); + } + } + + @reg if(tab_lookup(@Term.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) { + /* TODO: kein schoener hack? */ + @Term.node@->kids[0]->reg = @Term.node@->reg; + } + @} + + | Feld + @{ + @i @Term.node@ = @Feld.node@; + @i @Term.imm@ = 0; + @} + + | IDENT '(' Exprs ')' + @{ + @i @Term.node@ = TREENULL; + @i @Term.imm@ = 0; + @} + + | Term '.' IDENT '(' Exprs ')' + @{ + @i @Term.node@ = TREENULL; + @i @Term.imm@ = 0; + @} + + ; + +Exprs: + Expr ',' Exprs + | Expr + | + ; +%% + +extern int yylex(); +extern int yylineno; + +int yyerror(char *error_text) +{ + fprintf(stderr,"Zeile %i: %s\n", yylineno, error_text); + exit(2); +} + +int main(int argc, char **argv) +{ + #if 0 + yydebug=1; + #endif + yyparse(); + return 0; +} + diff --git a/codeb/scanner.lex b/codeb/scanner.lex new file mode 100644 index 0000000..92f6df7 --- /dev/null +++ b/codeb/scanner.lex @@ -0,0 +1,67 @@ + #include + #include + #include + #include "parser.h" + +KEYWORD struct|end|method|var|if|then|else|while|do|return|not|or|this +IDENTIFIER [a-zA-Z_][0-9a-zA-Z_]* +NUMBER_HEX 0x[0-9A-Fa-f]+ +NUMBER_DEC [0-9]+ +WHITESPACE [\t\n\r ] +COMMENT_START \/\* +COMMENT_END \*\/ + +%x COMMENT +%option yylineno +%% + +{COMMENT_START} BEGIN(COMMENT); + +{COMMENT_END} BEGIN(INITIAL); + +<> { + fprintf(stderr, "Kommentar nicht geschlossen\n"); + exit(1); +} + +(.|\n) /* alles im kommentar wird ignoriert */ + +struct return(STRUCT); +end return(END); +method return(METHOD); +var return(VAR); +if return(IF); +then return(THEN); +else return(ELSE); +while return(WHILE); +do return(DO); +return return(RETURN); +not return(NOT); +or return(OR); +this return(THIS); + +{IDENTIFIER} return(IDENT); @{ @IDENT.name@ = strdup(yytext); @} + +{NUMBER_DEC} return(NUM); @{ @NUM.val@ = strtol(yytext, (char **)NULL, 10); @} +{NUMBER_HEX} return(NUM); @{ @NUM.val@ = strtol(yytext, (char **)NULL, 16); @} + +\:= return(ASSIGN); +\; return(';'); +\( return('('); +\) return(')'); +\. return('.'); +\- return('-'); +\* return('*'); +\< return('<'); +\= return('='); +\, return(','); + +{WHITESPACE} /* ignore */ + +. { + fprintf(stderr, "Lexical error on line %i\n", yylineno); + exit(1); +} + +%% + diff --git a/codeb/symtable.c b/codeb/symtable.c new file mode 100644 index 0000000..4776240 --- /dev/null +++ b/codeb/symtable.c @@ -0,0 +1,146 @@ +#include +#include +#include +#include "symtable.h" + +#if 0 +#define DD +#endif + +struct symbol *tab_new(void) +{ + return SYMNULL; +} + +struct symbol *tab_clone(struct symbol *tab) +{ + struct symbol *elm = tab; + struct symbol *ntab = tab_new(); +#ifdef DD + fprintf(stderr, "tab_clone: tab(%08X)\n", tab); +#endif + + while(elm != SYMNULL) { + ntab = tab_add_symbol(ntab, elm->ident, elm->type, 0, elm->param_index, elm->soffset); + elm = elm->next; + } + return ntab; +} + +struct symbol *tab_add_symbol(struct symbol *tab, char *ident, short type, short check, int param_index, int soffset) +{ + struct symbol *elm = tab; + struct symbol *new_elm; +#ifdef DD + fprintf(stderr, "tab_add_symbol: tab(%08X), ident(%s), type(%i), check(%i), param_index(%i), soffset(%i)\n", tab, ident, type, check, param_index, soffset); +#endif + + if(param_index >= 6) { + fprintf(stderr, "eine methode hat zu viele parameter (max. 6 inkl. this erlaubt)\n"); + exit(4); + } + + if(tab_lookup(tab, ident, type) != SYMNULL || (type == S_VAR && tab_lookup(tab, ident, S_PARM) != SYMNULL)) { + if(check) { + fprintf(stderr, "Identifier doppelt vorhanden: \"%s\"\n", ident); + exit(3); + } else { + tab = tab_remove_symbol(tab, ident, type); + } + } + + new_elm = (struct symbol *) malloc(sizeof(struct symbol)); + new_elm->next = SYMNULL; + new_elm->ident = strdup(ident); + new_elm->type = type; + new_elm->param_index = param_index; + new_elm->soffset = soffset; + + if(tab == SYMNULL) return new_elm; + + while(elm->next != SYMNULL) { + elm = elm->next; + } + elm->next = new_elm; + + return tab; +} + +struct symbol *tab_lookup(struct symbol *tab, char *ident, short type) +{ + struct symbol *elm = tab; + + if(tab == SYMNULL) return SYMNULL; + + do { + if((elm->type & type) && (strcmp(elm->ident, ident) == 0)) { + return elm; + } + elm = elm->next; + } while(elm != SYMNULL); + + return SYMNULL; +} + +struct symbol *tab_merge(struct symbol *tab, struct symbol *to_add, short check) +{ + struct symbol *elm = to_add; + struct symbol *ntab = tab_clone(tab); +#ifdef DD + fprintf(stderr, "tab_merge: tab(%08X), to_add(%08X), check(%i), ntab(%08X)\n", tab, to_add, check, ntab); +#endif + + while(elm != SYMNULL) { + ntab = tab_add_symbol(ntab, elm->ident, elm->type, check, elm->param_index, elm->soffset); + elm = elm->next; + } + + return ntab; +} + +struct symbol *tab_remove_symbol(struct symbol *tab, char *ident, short type) +{ + struct symbol *elm = tab; + struct symbol *previous_elm = SYMNULL; + + while(elm != SYMNULL) { + if((elm->type == type) && (strcmp(elm->ident, ident) == 0)) { + if(previous_elm == SYMNULL) { + tab = elm->next; + } else { + previous_elm->next = elm->next; + } + (void)free(elm->ident); + (void)free(elm); + break; + } + previous_elm = elm; + elm = elm->next; + } + + return tab; +} + +void check(struct symbol *tab, char *ident, short type) +{ + struct symbol *elm; +#ifdef DD + fprintf(stderr, "check: tab(%08X), ident(%s), type(%i), elm(%08X)\n", tab, ident, type, elm); +#endif + + if(type & (S_VAR | S_PARM)) { + elm = tab_lookup(tab, ident, type); + if(elm != SYMNULL) { + return; + } + } + + /* keine passende variable gefunden? + * => vllt gibt es ja ein passenden feldnamen */ + elm = tab_lookup(tab, ident, S_FIELD); + if(elm == SYMNULL) { + fprintf(stderr, "Unbekannter Identifier: \"%s\"\n", ident); + exit(3); + } +} + diff --git a/codeb/symtable.h b/codeb/symtable.h new file mode 100644 index 0000000..9892899 --- /dev/null +++ b/codeb/symtable.h @@ -0,0 +1,26 @@ +#ifndef SYMTABLE_H +#define SYMTABLE_H + +#define S_FIELD (1<<0) +#define S_VAR (1<<1) +#define S_PARM (1<<2) + +#define SYMNULL (struct symbol *)NULL + +struct symbol { + char *ident; + struct symbol *next; + short type; + int param_index; + int soffset; +}; + +struct symbol *tab_clone(struct symbol *tab); +struct symbol *tab_new(void); +struct symbol *tab_add_symbol(struct symbol *tab, char *ident, short type, short check, int param_index, int soffset); +struct symbol *tab_lookup(struct symbol *tab, char *ident, short type); +struct symbol *tab_remove_symbol(struct symbol *tab, char *ident, short type); +struct symbol *tab_merge(struct symbol *tab, struct symbol *to_add, short check); +void check(struct symbol *tab, char *ident, short type); + +#endif diff --git a/codeb/tree.c b/codeb/tree.c new file mode 100644 index 0000000..593709c --- /dev/null +++ b/codeb/tree.c @@ -0,0 +1,118 @@ +#include +#include +#include +#include "tree.h" + +#if 0 +#define DDTREE +#endif + +static struct treenode *_new_plain(int op) +{ + struct treenode *new = (TREECAST) malloc(TREESIZE); + new->op = op; + new->kids[0] = new->kids[1] = TREENULL; + new->parent = TREENULL; + new->label = NULL; + new->name = new->reg = (char *)NULL; + new->val = 0; + new->param_index = -1; + return new; +} + +struct treenode *new_node(int op, struct treenode *l, struct treenode *r) +{ + struct treenode *new = TREENULL; + +#ifdef DDTREE + fprintf(stderr, "new_node: %i (%s)\n", op, o_names[op]); +#endif + if(op == O_SUB && l != TREENULL && r != TREENULL && l->op == O_NUM && r->op == O_NUM) { + new = new_number(l->val - r->val); + free(l); free(r); + } else { + new = _new_plain(op); + new->kids[0] = l; + new->kids[1] = r; + } + new->name = (char *)NULL; + return new; +} + +struct treenode *new_param(int op, char *name, struct treenode *l, struct treenode *r, int param_index) +{ + struct treenode *new = new_node(op, l, r); + +#ifdef DDTREE + fprintf(stderr, "new_param: %i (index)\n", param_index); +#endif + new->param_index = param_index; + new->name = name; + return new; +} + +struct treenode *new_field(char *name, struct treenode *l, struct treenode *r, int soffset) +{ + struct treenode *new = new_node(O_FIELD, l, r); + +#ifdef DDTREE + fprintf(stderr, "new_field: %i (soffset)\n", soffset); +#endif + new->soffset = soffset; + new->name = name; + return new; +} + +struct treenode *new_number(long val) +{ + struct treenode *new; + /* TODO: maximal groesse? */ +#define BUFMAX 40 + char *t = (char*) malloc(BUFMAX); + + if (val == 0) { + new = _new_plain(O_NULL); + } else if(val == -1) { + new = _new_plain(O_MONE); + } else if(val == -2) { + new = _new_plain(O_MTWO); + } else if(val == -4) { + new = _new_plain(O_MFOUR); + } else if(val == -8) { + new = _new_plain(O_MEIGHT); + } else { + new = _new_plain(O_NUM); + } + +#ifdef DDTREE + fprintf(stderr, "new_number: %i\n", val); +#endif + new->val = val; + memset(t, 0, BUFMAX); + sprintf(t, "%li", val); + new->name = t; + + return new; +} + +static void write_indent(int i) +{ + int a; + for(a = 0; a < i; a++) { + fprintf(stderr, "| "); + } +} + +void write_tree(struct treenode *node, int indent) +{ + if(node == TREENULL) return; + write_indent(indent); + fprintf(stderr, "%s @ %%%s. \"%s\"\n", o_names[node->op], node->reg, node->name == (char*) NULL ? "" : node->name); + if(node->kids[0] != TREENULL) { + write_tree(node->kids[0], indent+1); + } + if(node->kids[1] != TREENULL) { + write_tree(node->kids[1], indent+1); + } +} + diff --git a/codeb/tree.h b/codeb/tree.h new file mode 100644 index 0000000..24f1a3a --- /dev/null +++ b/codeb/tree.h @@ -0,0 +1,53 @@ +#ifndef __TREE_H +#define __TREE_H + +#define TREENULL (struct treenode *)NULL +#define TREESIZE (sizeof(struct treenode)) +#define TREECAST struct treenode * + +#ifndef BFEHAX +typedef struct burm_state *STATEPTR_TYPE; +#endif + +enum { + O_RET=1, O_NULL, O_SUB, O_MUL, + O_OR=5, O_LESS, O_EQ, O_ID, O_ADD, + O_NUM=10, O_FIELD, O_MTWO, O_MFOUR, O_MEIGHT, + O_MONE=15 +}; + +static char *o_names[] = { + "", "O_RET", "O_NULL", "O_SUB", "O_MUL", + "O_OR", "O_LESS", "O_EQ", "O_ID", "O_ADD", + "O_NUM", "O_FIELD", "O_MTWO", "O_MFOUR", "O_MEIGHT", + "O_MONE" +}; + +struct treenode { + int op; + struct treenode *kids[2]; + STATEPTR_TYPE label; + char *name; + long val; + char *reg; + struct treenode *parent; + int param_index; + int soffset; +}; + +typedef struct treenode *treenodep; + +#define NODEPTR_TYPE treenodep +#define OP_LABEL(p) ((p)->op) +#define LEFT_CHILD(p) ((p)->kids[0]) +#define RIGHT_CHILD(p) ((p)->kids[1]) +#define STATE_LABEL(p) ((p)->label) +#define PANIC printf + +struct treenode *new_node(int op, struct treenode *l, struct treenode *r); +struct treenode *new_number(long val); +struct treenode *new_param(int op, char *name, struct treenode *l, struct treenode *r, int param_index); +struct treenode *new_field(char *name, struct treenode *l, struct treenode *r, int soffset); +void write_tree(struct treenode *node, int ident); + +#endif -- 2.25.1