From: Bernhard Urban Date: Tue, 30 Mar 2010 10:50:49 +0000 (+0200) Subject: ag: paulchen init X-Git-Url: http://wien.tomnetworks.com/gitweb/?p=uebersetzerbau-ss10.git;a=commitdiff_plain;h=3512b27e407d7972f7ea0e17dc62b4cb9207a15a ag: paulchen init --- diff --git a/.gitignore b/.gitignore index 8adb59d..518f397 100644 --- a/.gitignore +++ b/.gitignore @@ -22,5 +22,11 @@ parser/parser.c parser/parser.h parser/scanner.c +#ag +ag/ag +ag/parser.c +ag/parser.h +ag/scanner.c + #weitere eintragen... torero/torero.log diff --git a/ag/Makefile b/ag/Makefile new file mode 100644 index 0000000..236f3ae --- /dev/null +++ b/ag/Makefile @@ -0,0 +1,38 @@ +SHELL := bash +NAME := ag +CFLAGS := -ansi -pedantic -D_GNU_SOURCE +OBJS := scanner.o parser.o symbol_table.o +TARGETS := parser.y scanner.lex + +all: $(NAME) + +$(NAME): $(OBJS) + @echo " LINK $<" + @gcc -o $@ $(OBJS) -lfl + +scanner.c: oxout.l + @echo " FLEX $<" + @flex -o$@ $< + +%.o: %.c parser.h symbol_table.h + @echo " CC $<" + @gcc -c $(CFLAGS) $< #-Wall + +parser.c: oxout.y + @echo " YACC $<" + @yacc -t -v -d $< -o $@ + +parser.h: parser.c + +oxout.y oxout.l: $(TARGETS) + @echo " OX $(TARGETS)" + @ox parser.y scanner.lex + +.PHONY: clean +clean: + rm -f $(NAME) $(OBJS) scanner.c parser.{h,c,output} oxout.{y,l} + +1test: 2test + +2test: + /usr/ftp/pub/ublu/test/$(NAME)/test 2>&1 diff --git a/ag/parser.y b/ag/parser.y new file mode 100644 index 0000000..7634069 --- /dev/null +++ b/ag/parser.y @@ -0,0 +1,204 @@ +%{ + #include + #include + #include + #include "symbol_table.h" +%} + +%start Input +%token FUNC END STRUCT VAR IF THEN ELSE WHILE DO RETURN OR NOT +%token ID NUM ASSIGN GREATER + +@autoinh symbols + +@attributes { char *name; } ID +@attributes { struct symbol_t *fields; struct symbol_t *symbols; } Program +@attributes { struct symbol_t *fields; } Ids Structdef +@attributes { struct symbol_t *pars; } Pars +@attributes { struct symbol_t *symbols; } Funcdef Stats Bool Expr Call Lexpr Field Term Plusterm Malterm Bterm Orterm Exprs +@attributes { struct symbol_t *in_symbols; struct symbol_t *out_symbols; } Stat + +@traversal @postorder t + +%% + +Input: Program + @{ @i @Program.symbols@ = @Program.fields@; @} + + ; + +Program: Funcdef ';' Program + @{ + @i @Program.fields@ = @Program.1.fields@; + @} + + | Structdef ';' Program + @{ + @i @Program.fields@ = table_merge(@Structdef.fields@, @Program.1.fields@, 1); + @i @Program.1.symbols@ = @Program.0.symbols@; + @} + + | + @{ @i @Program.fields@ = new_table(); @} + + ; + +Funcdef: FUNC ID '(' Pars ')' Stats END + @{ @i @Stats.symbols@ = table_merge(@Funcdef.symbols@, @Pars.pars@, 0); @} + + | + FUNC ID '(' ')' Stats END + @{ @i @Stats.symbols@ = table_merge(@Funcdef.symbols@, new_table(), 0); @} + + ; + +Structdef: STRUCT Ids END + @{ @i @Structdef.fields@ = @Ids.fields@; @} + + ; + +Ids: ID Ids + @{ @i @Ids.fields@ = table_add_symbol(@Ids.1.fields@, @ID.name@, SYMBOL_TYPE_FIELD, 1); @} + + | + @{ @i @Ids.fields@ = new_table(); @} + + ; + +Pars: Pars ',' ID + @{ @i @Pars.pars@ = table_add_symbol(@Pars.1.pars@, @ID.name@, SYMBOL_TYPE_VAR, 0); @} + + | ID + @{ @i @Pars.pars@ = table_add_symbol(new_table(), @ID.name@, SYMBOL_TYPE_VAR, 0); @} + + ; + +Stats: Stat ';' Stats + @{ + @i @Stat.in_symbols@ = @Stats.symbols@; + @i @Stats.1.symbols@ = @Stat.out_symbols@; + @} + + | + ; + +Stat: VAR ID ASSIGN Expr + @{ + @i @Stat.out_symbols@ = table_add_symbol(clone_table(@Stat.in_symbols@), @ID.name@, SYMBOL_TYPE_VAR, 0); + @i @Expr.symbols@ = @Stat.in_symbols@; + @} + + | Lexpr ASSIGN Expr + @{ + @i @Stat.out_symbols@ = @Stat.in_symbols@; + @i @Lexpr.symbols@ = @Stat.in_symbols@; + @i @Expr.symbols@ = @Stat.in_symbols@; + @} + + | IF Bool THEN Stats END + @{ + @i @Bool.symbols@ = @Stat.in_symbols@; + @i @Stats.symbols@ = @Stat.in_symbols@; + @i @Stat.out_symbols@ = @Stat.in_symbols@; + @} + + | IF Bool THEN Stats ELSE Stats END + @{ + @i @Bool.symbols@ = @Stat.in_symbols@; + @i @Stats.symbols@ = @Stat.in_symbols@; + @i @Stats.1.symbols@ = @Stat.in_symbols@; + @i @Stat.out_symbols@ = @Stat.in_symbols@; + @} + + | WHILE Bool DO Stats END + @{ + @i @Bool.symbols@ = @Stat.in_symbols@; + @i @Stats.symbols@ = @Stat.in_symbols@; + @i @Stat.out_symbols@ = @Stat.in_symbols@; + @} + + | Call + @{ + @i @Call.symbols@ = @Stat.in_symbols@; + @i @Stat.out_symbols@ = @Stat.in_symbols@; + @} + + | RETURN Expr + @{ + @i @Expr.symbols@ = @Stat.in_symbols@; + @i @Stat.out_symbols@ = @Stat.in_symbols@; + @} + + ; + +Lexpr: ID + @{ @t check_variable(@Lexpr.symbols@, @ID.name@); @} + + | Field + ; + +Expr: '-' Term + | Term + | Term Plusterm + | Term Malterm + ; + +Plusterm: '+' Term Plusterm + | '+' Term + ; + +Malterm: '*' Term Malterm + | '*' Term + ; + +Term: '(' Expr ')' + | ID + @{ @t check_variable(@Term.symbols@, @ID.name@); @} + + | NUM + | Call + | Field + ; + +Bool: Bterm + | Bterm Orterm + | NOT Bterm + ; + +Orterm: OR Bterm Orterm + | OR Bterm + ; + +Bterm: Term GREATER Term + | Term '=' Term + | '(' Bool ')' + ; + +Field: Term '.' ID + @{ @t check_field(@Field.symbols@, @ID.name@); @} + + ; + +Call: ID '(' Exprs ')' + | ID '(' ')' + ; + +Exprs: Expr + | Exprs ',' Expr + ; + +%% + +extern int yylex(); +extern int yylineno; + +int yyerror(char *error_text) { + fprintf(stderr,"Line %i: %s\n",yylineno, error_text); + exit(2); +} + +int main(int argc, char **argv) { + yyparse(); + return 0; +} + diff --git a/ag/scanner.lex b/ag/scanner.lex new file mode 100644 index 0000000..f66b947 --- /dev/null +++ b/ag/scanner.lex @@ -0,0 +1,67 @@ + #include + #include + #include + #include "parser.h" + +KEYWORD func|end|struct|var|if|then|else|while|do|return|or|not +IDENTIFIER [[:alpha:]_][[:alnum:]_]* +NUMBER_HEX [0-9][0-9A-Fa-f]*H +NUMBER_DEC [0-9]+ +WHITESPACE [\t\n\r ] +COMMENT_START \(\* +COMMENT_END \*\) + +%x COMMENT +%option yylineno +%% + + +{COMMENT_START} BEGIN(COMMENT); + +{COMMENT_END} BEGIN(INITIAL); + +{COMMENT_START} fprintf(stderr, "Possibly nested comment on line %i\n", yylineno); + +<> { fprintf(stderr, "Unterminated comment.\n"); exit(1); } + +{WHITESPACE} /* ignore */ + +. /* ignore everything inside comment */ + +func return(FUNC); +end return(END); +struct return(STRUCT); +var return(VAR); +if return(IF); +then return(THEN); +else return(ELSE); +while return(WHILE); +do return(DO); +return return(RETURN); +or return(OR); +not return(NOT); + +{IDENTIFIER} return(ID); @{ @ID.name@=strdup(yytext); @} + +{NUMBER_DEC} return(NUM); +{NUMBER_HEX} return(NUM); + +\:= return(ASSIGN); +>= return(GREATER); +\; 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/ag/symbol_table.c b/ag/symbol_table.c new file mode 100755 index 0000000..b28687f --- /dev/null +++ b/ag/symbol_table.c @@ -0,0 +1,152 @@ +#include +#include +#include +#include "symbol_table.h" + +struct symbol_t *new_table(void) { + return (struct symbol_t *)NULL; +} + +struct symbol_t *clone_table(struct symbol_t *table) { + struct symbol_t *element; + struct symbol_t *new_tablex; + + element=table; + new_tablex=new_table(); + while((struct symbol_t *)NULL!=element) { + /* check return value */ + new_tablex=table_add_symbol(new_tablex,element->identifier,element->type,0); + element=element->next; + } + + return new_tablex; +} + +struct symbol_t *table_add_symbol(struct symbol_t *table, char *identifier, short type, short check) { + struct symbol_t *element; + struct symbol_t *new_element; + + if(table_lookup(table,identifier)!=(struct symbol_t *)NULL) { + if(check) { + fprintf(stderr,"Duplicate field %s.\n",identifier); + exit(3); + } + + table=table_remove_symbol(table,identifier); + } + + new_element=(struct symbol_t *)malloc(sizeof(struct symbol_t)); + new_element->next=(struct symbol_t *)NULL; + new_element->identifier=strdup(identifier); + new_element->type=type; + + if((struct symbol_t *)NULL==table) { + return new_element; + } + element=table; + + while((struct symbol_t *)NULL!=element->next) { + element=element->next; + } + + element->next=new_element; + + return table; +} + +struct symbol_t *table_lookup(struct symbol_t *table, char *identifier) { + struct symbol_t *element; + + element=table; + + if((struct symbol_t *)NULL==table) { + return (struct symbol_t *)NULL; + } + + if(strcmp(element->identifier,identifier)==0) { + return element; + } + + while((struct symbol_t *)NULL!=element->next) { + element=element->next; + if(strcmp(element->identifier,identifier)==0) { + return element; + } + } + + return (struct symbol_t *)NULL; +} + +struct symbol_t *table_merge(struct symbol_t *table, struct symbol_t *to_add, short check) { + struct symbol_t *element; + struct symbol_t *new_table=clone_table(table); + + element=to_add; + while(element!=(struct symbol_t *)NULL) { + new_table=table_add_symbol(new_table,element->identifier,element->type,check); + element=element->next; + } + + return new_table; +} + +struct symbol_t *table_remove_symbol(struct symbol_t *table, char *identifier) { + struct symbol_t *element; + struct symbol_t *previous_element; + struct symbol_t *new_element; + + if((struct symbol_t *)NULL==table) { + return table; + } + + previous_element=(struct symbol_t *)NULL; + element=table; + + while((struct symbol_t *)NULL!=element) { + if(strcmp(element->identifier,identifier)==0) { + if((struct symbol_t *)NULL==previous_element) { + new_element=element->next; + } + else { + previous_element->next=element->next; + new_element=table; + } + (void)free(element->identifier); + (void)free(element); + return new_element; + } + previous_element=element; + element=element->next; + } + + return table; +} + +void check_variable(struct symbol_t *table, char *identifier) { + struct symbol_t *element=table_lookup(table,identifier); + if(element!=(struct symbol_t *)NULL) { + if(element->type!=SYMBOL_TYPE_VAR) { + fprintf(stderr,"Identifier %s not a variable.\n",identifier); + exit(3); + } + } + else { + fprintf(stderr,"Unknown identifier %s.\n",identifier); + exit(3); + } +} + +void check_field(struct symbol_t *table, char *identifier) { + struct symbol_t *element=table_lookup(table,identifier); + if(element!=(struct symbol_t *)NULL) { + if(element->type!=SYMBOL_TYPE_FIELD) { + fprintf(stderr,"Identifier %s not a variable.\n",identifier); + exit(3); + } + } + else { + fprintf(stderr,"Unknown identifier %s.\n",identifier); + exit(3); + } +} + diff --git a/ag/symbol_table.h b/ag/symbol_table.h new file mode 100755 index 0000000..e160c83 --- /dev/null +++ b/ag/symbol_table.h @@ -0,0 +1,23 @@ +#ifndef SYMBOL_TABLE_H +#define SYMBOL_TABLE_H + +#define SYMBOL_TYPE_FIELD 1 +#define SYMBOL_TYPE_VAR 2 + +struct symbol_t { + char *identifier; + struct symbol_t *next; + short type; +}; + +struct symbol_t *clone_table(struct symbol_t *table); +struct symbol_t *new_table(void); +struct symbol_t *table_add_symbol(struct symbol_t *table, char *identifier, short type, short check); +struct symbol_t *table_lookup(struct symbol_t *table, char *identifier); +struct symbol_t *table_remove_symbol(struct symbol_t *table, char *identifier); +struct symbol_t *table_merge(struct symbol_t *table, struct symbol_t *to_add, short check); +void check_variable(struct symbol_t *table, char *identifier); +void check_field(struct symbol_t *table, char *identifier); + +#endif /* SYMBOL_TABLE_H */ + diff --git a/parser/Makefile b/parser/Makefile index 057281a..372ed18 100644 --- a/parser/Makefile +++ b/parser/Makefile @@ -1,3 +1,4 @@ +SHELL := bash NAME := parser PARSER := $(NAME) SCANNER := scanner diff --git a/scanner/Makefile b/scanner/Makefile index 50a3ddd..8bcdabf 100755 --- a/scanner/Makefile +++ b/scanner/Makefile @@ -1,3 +1,4 @@ +SHELL := bash NAME := scanner all: $(NAME)