中间代码生成器
一、实验目的
掌握中间代码生成器的构造原理和编程方法。
二、实验内容
用自顶向下方法或Yacc进行语法分析的基础上，编写一个中间代码生成程序。（见教材附录A.1，p394）
program →block
block→ {declsstmts}
decls→decls decl| e
decl→typeid;
type→type[num]//数组可以不做
|basic//四种基本数据类型int | float | char | bool
stmts →stmts stmt |e
stmt →id=expr;
|if(bool)stmt
|if(bool)stmtelsestmt
|while(bool)stmt
|dostmtwhile(bool) ;
|break ;//break可以不做
|block
bool →bool||join|join
join→join&&equality|equality
equality→ equality == rel | equality != rel | rel
rel→expr<expr
|expr<=expr
| expr>expr
| expr>=expr
| expr
expr →expr+term
| expr-term
| term
term →term*unary
| term/unary
| unary
unary→ !unary| -unary|factor
factor→(expr)|id|num
。
三、实验要求
１．个人完成，提交实验报告。
２．实验的结果为：生成中间代码 （三地址码）
{
a=10;
x = b - c;
y = a * x;
z = x * d;
abcd = a + x +y;
if(a>10)
a=a+1;
a=a+2;
}
实验结果生成的代码片段
0: a = 10
1: t0 = b - c
2: x = t0
3: t1 = a * x
4: y = t1
5: t2 = x * d
6: z = t2
7: t3 = a + x
8: t4 = t3 + y
9: abcd = t4
10: if a > 10 goto 12
11: goto 14
12: t5 = a + 1
13: a = t5
14: t6 = a + 2
15: a = t6
个人对于本次中间代码生成器-编译实验的心得：
View Code
#define YYSTYPE node：定义符号栈属性结点类型typedef struct node{instrlist *truelist, *falselist, *nextlist;//相当于有一个 正确链表与 错误链表 每个链表结点都有个值char addr[256];// 地址字段 存放具体结点的内容比如 a 8 10 等char lexeme[256];//字符串指端char oper[3];//操作符字段 具体存放操作符对应的字符串int instr; //是否要回填指示具体内容是行号}node;int main(){list = newcodelist();//申请一个内存空间给list// int linecnt, capacity; 行数 与 最大行数// int temp_index; // char **code; 总代码freopen("test.in", "rt+", stdin);freopen("test.out", "wt+", stdout);//打开文件yyparse();print(list);fclose(stdin);//关闭文件fclose(stdout);//关闭文件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); //将tmp的内容存放到 总字符串list的code字段当中return 0;} int Gen(codelist *dst, char *str) //输入 第一个参数为 list 第二个参数是 总字符串 tmp[1024]{ //目标是 将tmp的内容存放到 总字符串 list的code字段当中if (dst->linecnt >= dst->capacity){dst->capacity += 1024;dst->code = (char**)realloc(dst->code, sizeof(char*)*dst->capacity);if (dst->code == NULL){printf("short of memeory\n");return 0;}}dst->code[dst->linecnt] = (char*)malloc(strlen(str)+20);//申请一个内存空间存放中间字符串strcpy(dst->code[dst->linecnt], str);//字符串复制dst->linecnt++; //行号加1return 0;}int backpatch(codelist *dst, instrlist *list, int instrno)//总代码 dst 错误列表list 错误的指向行数{if (list!=NULL) //如果错误的列表不为空{listele *p=list->first;char tmp[20];sprintf(tmp, " %d", instrno); 取出一个while (p!=NULL){if (p->instrno<dst->linecnt)strcat(dst->code[p->instrno], tmp); //错误列表：1 2 3 4 假设都指向instrno=6 那么将6转化为字符串tmp//再添加到每个字符串的末尾p=p->next;}}return 0;}// int linecnt, capacity; 行数 与 最大行数// int temp_index; // char **code;
重点是对课上的回填技术，还有
栈中的可能属性类别也就是node结点的属性种类，还有的是全局变量list使用的结点除了行号，最大行号，还有就是三地址码存放的chor **类型的code。
jia.l
View Code
%{#include "jia.tab.h"%}delim [ \t\n\r]ws {delim}+letter [A-Za-z]digit [0-9]id {letter}({letter}|{digit})*integer {digit}+exponent E[+-]?{integer}number {integer}{exponent}?real integer(\.integer)?{exponent}?%option noyywrap%%if { return( IF ); }else{ return( ELSE ); }while { return( WHILE ); }do { return( DO ); }for { return( FOR ); }switch { return( SWITCH ); }case { return( CASE ); }default { return( DEFAULT ); }break { return( BREAK ); }true { return( TRUE ); }false { return( FALSE ); }int { return( INT ); }long { return( LONG ); }char { return( CHAR ); }bool { return( BOOL ); }float { return( FLOAT ); }double { return( DOUBLE ); }"&&" { return( AND ); }"||" { return( OR ); }"!" { return( '!'); }"<"|"<="|">"|">="|"!="|"==" { filloperator(&yylval, yytext); return( REL); }"++" { return( INC ); }"--" { return( DEC ); }"+" { return( '+' ); }"-" { return( '-' ); }"*" { return( '*' ); }"/" { return( '/' ); }"=" { return( '=' ); }"{" { return( '{' ); }"}" { return( '}' ); }"[" { return( '[' ); }"]" { return( ']' ); }"(" { return( '(' ); }")" { return( ')' ); }";" { return( ';' ); }{ws} { }{id} { filllexeme(&yylval, yytext); return( ID ); }{number} { filllexeme(&yylval, yytext); return( NUMBER ); }{real} { filllexeme(&yylval, yytext); return( REAL ); }%%
jia.y
View Code
%{#include "xu.h"#define YYSTYPE node#include "jia.tab.h"int yyerror();int yyerror(char* msg);extern int yylex();codelist* list;%}%token BASIC NUMBER REAL ID TRUE FALSE%token INT LONG CHAR BOOL FLOAT DOUBLE%token REL%token IF ELSE WHILE DO BREAK FOR SWITCH CASE DEFAULT %token OR AND%left OR%left AND%right '!'%left '+' '-'%left '*' '/'%right UMINUS%right INC DEC%%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); }| FOR '(' assignment ';' M boolean ';' M assignment ')' N M statement { backpatch(list, $6.truelist, $12.instr);backpatch(list, $11.nextlist, $5.instr);backpatch(list, $13.nextlist, $8.instr);$$.nextlist = $6.falselist;gen_goto(list, $8.instr); }| BREAK ';'{ }| '{' statementlist '}'{ $$.nextlist = $2.nextlist; } | assignment ';' { $$.nextlist = NULL; };assignment : ID '=' boolean{ copyaddr(&$1, $1.lexeme); gen_assignment(list, $1, $3); };loc : loc '[' boolean ']' { }| ID { copyaddr(&$$, $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 { copyaddr(&$$, "TRUE");gen_goto_blank(list); }| FALSE{ copyaddr(&$$, "FALSE");gen_goto_blank(list); }| expression { copyaddr_fromnode(&$$, $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 { copyaddr_fromnode(&$$, $1); }| NUMBER { copyaddr(&$$, $1.lexeme); }| REAL { copyaddr(&$$, $1.lexeme); };%%int yyerror(char* msg){printf("\nERROR with message: %s\n", msg);return 0;}int main(){list = newcodelist();//申请一个内存空间给list // int linecnt, capacity;// int temp_index;// char **code;freopen("test.in", "rt+", stdin);freopen("test.out", "wt+", stdout);//打开文件 yyparse();print(list);fclose(stdin);//关闭文件 fclose(stdout);//关闭文件return 0;}
xu.h
View Code
#ifndef CP_H#define CP_H#include <stdio.h>#include <string.h>#include <malloc.h>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 filloperator(node *dst, char *src){strcpy(dst->oper, src);return 0;} int filllexeme(node *dst, char *yytext){strcpy(dst->lexeme, yytext);return 0;}int copyaddr(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 copyaddr_fromnode(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("short of memeory\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 %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, " %d", instrno);while (p!=NULL){if (p->instrno<dst->linecnt)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("%5d: %s\n", i, dst->code[i]);return 0;}#endif
test.in
View Code
{a=10;x = b - c;y = a * x;z = x * d;abcd = a + x +y;if(a>10)a=a+1;a=a+2;while(a>0)a=a-1;b=b+1;}
最终老师给的代码暂未公开
课件
