实验五_用语法制导方式生成中间代码生成器

实验五_用语法制导方式生成中间代码生成器 实验5 用语法制导方式生成中间代码生成器 魏陈强 23020092204168 一、实验目的 掌握语法制导定义和翻译的原理和技术，在语法器的基础上，加上语义分析，构造一个中间代码生成器。 二、实验内容 在实验四生成的语法分析器基础上加入语义动作，将源程序翻译为对应的中间代码序列。 三、实验要求 1(实验中给出采用测试源代码片断，及其对应的三地址码形式(内部示形式可以自行考虑)。 例如，程序片断 对应的中间代码为: 四、实验思路 在前4次实验的基础上进行中间代码生成的编写，采用linux环境下的lex和yacc工具。首先编写goto.c函数，该函数实现符号表、回填、创建节点、定义节点属性等功能。Lex.l文件无需修改，yacc.y文件中，在每个生成式后加上语法制导翻译，主要是依据truelist和falselist来实现回填功能。编写完后，在yacc.y中以头文件的方式加入goto.c，编译即可。 五、实验代码 1、lex.l %{ %} …… letter [A-Za-z] digit [0-9] …… %option noyywrap %% if { return( IF ); } else { return( ELSE ); } …… "<"|"<="|">"|">="|"!="|"==" { op_in(&yylval, yytext); return( REL); } …… %% 2、Yacc.y %{ #include "goto.c" #define YYSTYPE node int yyerror(); int yyerror(char* msg); extern int yylex(); codelist* list; %} %token BASIC NUMBER REAL ID TRUE FALSE %token INT CHAR BOOL FLOAT %token REL %token IF ELSE WHILE DO BREAK SWITCH CASE DEFAULT %token OR AND %left OR %left AND %right '!' %left '+' '-' %left '*' '/' %right UMINUS %right INC DEC %expect 1 %% program : block { } ; block : '{' decls statementlist '}' { } ; decls : decls decl { } | { } ; decl : type ID ';' { } ; type : type '[' NUMBER ']' { } | BASIC { } ; statementlist : statementlist M statement { backpatch(list, $1.nextlist, $2.instr); $$.nextlist = $3.nextlist; } | statement { $$.nextlist = $1.nextlist; } ; statement : IF '(' boolean ')' M statement ELSE N M statement { backpatch(list, $3.truelist, $5.instr); backpatch(list, $3.falselist, $9.instr); $6.nextlist = merge($6.nextlist, $8.nextlist); $$.nextlist = merge($6.nextlist, $10.nextlist); } | IF '(' boolean ')' M statement { backpatch(list, $3.truelist, $5.instr); $$.nextlist = merge($3.falselist, $6.nextlist); } | WHILE M '(' boolean ')' M statement { backpatch(list, $7.nextlist, $2.instr); backpatch(list, $4.truelist, $6.instr); $$.nextlist = $4.falselist; gen_goto(list, $2.instr); } | DO M statement M WHILE '(' boolean ')' M ';' { backpatch(list, $3.nextlist, $4.instr); backpatch(list, $7.truelist, $9.instr); $$.nextlist = $7.falselist; gen_goto(list, $2.instr); } | BREAK ';' { } | '{' statementlist '}' { $$.nextlist = $2.nextlist; } | assignment ';' { $$.nextlist = NULL; } ; assignment : ID '=' boolean { address(&$1, $1.lexeme); gen_assignment(list, $1, $3); } ; loc : loc '[' boolean ']' { } | ID { address(&$$, $1.lexeme); } ; boolean : boolean OR M boolean { backpatch(list, $1.falselist, $3.instr); $$.truelist = merge($1.truelist, $4.truelist); $$.falselist = $4.falselist; } | boolean AND M boolean { backpatch(list, $1.truelist, $3.instr); $$.truelist = $4.truelist; $$.falselist = merge($1.falselist, $4.falselist); } | '!' boolean { $$.truelist = $1.falselist; $$.falselist = $1.truelist; } | '(' boolean ')' { $$.truelist = $1.truelist; $$.falselist = $1.falselist; } | expression REL expression { $$.truelist = new_instrlist(nextinstr(list)); $$.falselist = new_instrlist(nextinstr(list)+1); gen_if(list, $1, $2.oper, $3); gen_goto_blank(list); } | TRUE { address(&$$, "TRUE"); gen_goto_blank(list); } | FALSE { address(&$$, "FALSE"); gen_goto_blank(list); } | expression { addr_node(&$$, $1); } ; M : { $$.instr = nextinstr(list); } ; N : { $$.nextlist = new_instrlist(nextinstr(list)); gen_goto_blank(list); } ; expression : expression '+' expression { new_temp(&$$, get_temp_index(list)); gen_3addr(list, $$, $1, "+", $3); } | expression '-' expression { new_temp(&$$, get_temp_index(list)); gen_3addr(list, $$, $1, "-", $3); } | expression '*' expression { new_temp(&$$, get_temp_index(list)); gen_3addr(list, $$, $1, "*", $3); } | expression '/' expression { new_temp(&$$, get_temp_index(list)); gen_3addr(list, $$, $1, "/", $3); } | '-' expression %prec UMINUS { new_temp(&$$, get_temp_index(list)); gen_2addr(list, $$, "-", $2); } | loc { addr_node(&$$, $1); } | NUMBER { address(&$$, $1.lexeme); } | REAL { address(&$$, $1.lexeme); } ; %% #include"lex.yy.c" int yyerror(char* msg) { printf("\nERROR with message: %s\n", msg); return 0; } int main() { list = newcodelist(); yyparse(); print(list); return 0; } 2、Goto.c #ifndef GOTO_C #define GOTO_C #include #include #include typedef struct listele { int instrno; struct listele *next; }listele; listele* new_listele(int no) { listele* p = (listele*)malloc(sizeof(listele)); p->instrno = no; p->next = NULL; return p; } typedef struct instrlist { listele *first,*last; }instrlist; instrlist* new_instrlist(int instrno) { instrlist* p = (instrlist*)malloc(sizeof(instrlist)); p->first = p->last = new_listele(instrno); return p; } instrlist* merge(instrlist *list1, instrlist *list2) { instrlist *p; if (list1 == NULL) p = list2; else { if (list2!=NULL) { if (list1->last == NULL) { list1->first = list2->first; list1->last =list2->last; }else list1->last->next = list2->first; list2->first = list2->last = NULL; free(list2); } p = list1; } return p; } typedef struct node { instrlist *truelist, *falselist, *nextlist; char addr[256]; char lexeme[256]; char oper[3]; int instr; }node; int op_in(node *dst, char *src) { strcpy(dst->oper, src); return 0; } int lexeme_in(node *dst, char *yytext) { strcpy(dst->lexeme, yytext); return 0; } int address(node *dst, char *src) { strcpy(dst->addr, src); return 0; } int new_temp(node *dst, int index) { sprintf(dst->addr, "t%d", index); return 0; } int addr_node(node *dst, node src) { strcpy(dst->addr, src.addr); return 0; } typedef struct codelist { int linecnt, capacity; int temp_index; char **code; }codelist; codelist* newcodelist() { codelist* p = (codelist*)malloc(sizeof(codelist)); p->linecnt = 0; p->capacity = 1024; p->temp_index = 0; p->code = (char**)malloc(sizeof(char*)*1024); return p; } int get_temp_index(codelist* dst) { return dst->temp_index++; } int nextinstr(codelist *dst) { return dst->linecnt; } int Gen(codelist *dst, char *str) { if (dst->linecnt >= dst->capacity) { dst->capacity += 1024; dst->code = (char**)realloc(dst->code, sizeof(char*)*dst->capacity); if (dst->code == NULL) { printf("Error!\n"); return 0; } } dst->code[dst->linecnt] = (char*)malloc(strlen(str)+20); strcpy(dst->code[dst->linecnt], str); dst->linecnt++; return 0; } char tmp[1024]; int gen_goto_blank(codelist *dst) { sprintf(tmp, "goto"); Gen(dst, tmp); return 0; } int gen_goto(codelist *dst, int instrno) { sprintf(tmp, "goto L%d", instrno); Gen(dst, tmp); return 0; } int gen_if(codelist *dst, node left, char* op, node right) { sprintf(tmp, "if %s %s %s goto", left.addr, op, right.addr); Gen(dst, tmp); return 0; } int gen_1addr(codelist *dst, node left, char* op) { sprintf(tmp, "%s %s", left.addr, op); Gen(dst, tmp); return 0; } int gen_2addr(codelist *dst, node left, char* op, node right) { sprintf(tmp, "%s = %s %s", left.addr, op, right.addr); Gen(dst, tmp); return 0; } int gen_3addr(codelist *dst, node left, node op1, char* op, node op2) { sprintf(tmp, "%s = %s %s %s", left.addr, op1.addr, op, op2.addr); Gen(dst, tmp); return 0; } int gen_assignment(codelist *dst, node left, node right) { gen_2addr(dst, left, "", right); return 0; } int backpatch(codelist *dst, instrlist *list, int instrno) { if (list!=NULL) { listele *p=list->first; char tmp[20]; sprintf(tmp, " L%d", instrno); while (p!=NULL) { if (p->instrnolinecnt) strcat(dst->code[p->instrno], tmp); p=p->next; } } return 0; } int print(codelist* dst) { int i; for (i=0; i < dst->linecnt; i++) printf("L%d: %s\n", i, dst->code[i]); return 0; } #endif 六、实验结果 1、输入程序 2、输出结果 七、实验心得 本次实验要实现中间代码生成，也是本学期的最后一次实验，要在前4次实验的基础上完成，综合比较前4次实验，感觉本次实验难度挺高，首先，前4次实验的词法分析和语法分析需要有足够高的正确率，否者本次实验中会遇到一些神奇的问题，不知道错在哪里;其次，对语法制导定义和语法制导翻译要掌握好才能把握编写思路。本次实验难度较大，编写许久任进展不佳，因此参考了往年学长的代码，主要是参考了其符号表和回填方法，并且在其代码上进行了适当的优化。小学期有时间了，还得慢慢研究下本次实验。