编译原理 之 代码生成【VIP专享】

编译原理实验四代码生成输入：语法树。

输出：生成P代码存入codestr[codeindex]。

样例程序已经能生成P代码。

文法：stmt_seq -->statement ; stmt_seq | statementstatement-->decl_stmt | assign_stmtdecl_stmt-->type var_listtype-->int |floatvar_list-->id , var_list | idassign_stmt--> id := expexp-->exp + term | exp - term |termterm--> term * factor | term * factor | factorfactor-->id | num | ( exp )要求掌握理解程序设计方法。

#include<stdio.h>#include<ctype.h>typedef enum{MINUS,PLUS,TIMES,OVER,LPAREN,RPAREN,SEMI,ASSIGN,NUM,ID,INT,FLOAT,COMMA,DOLLAR} tokentype;/*记号*/typedef enum {stmtk,expk} nodekind;typedef enum {ifk,assignk,declk} stmtkind;typedef enum {opk,constk,idk} expkind;typedef enum {integer,real} exptype;typedef struct treenode{ struct treenode * child[3];struct treenode * sibling;nodekind nodek;exptype dtype ;union { stmtkind stmt; expkind exp;} kind;union { tokentype op;int val;char * name; } attr;} treenode;typedef struct bucket{char * name; exptype dtype; struct bucket * next;} bucket;bucket * hashtable[211];tokentype token[]={ID,ASSIGN,NUM,PLUS,NUM,TIMES,ID,SEMI,ID,ASSIGN,NUM,DOLLAR};char tokenstring[][30]={"ab",":=","12","+","5","*","x",";","xy",":=","34","$"}; int wordindex=0; /*以上两个数组的索引*/char codestr[30][30];int codeindex=0;treenode * t;treenode * decl();treenode * factor();treenode * term();treenode * exp();treenode * assign_stmt();treenode * stmt_seq();pretraverse(treenode *);expcode(treenode *);gencode(treenode *);main(){int i;t=stmt_seq();pretraverse(t);gencode(t);for(i=0; i<codeindex;i++)printf("%s\n",codestr[i]);}treenode * stmt_seq(){treenode * t;treenode * p;if(( token[wordindex]==INT)||(token[wordindex]==FLOAT)){t=decl(); }if(token[wordindex]==ID) t=assign_stmt();p=t;while( (token[wordindex]==SEMI)&& (token[wordindex]!=DOLLAR)) {treenode * q;wordindex++;q=assign_stmt();p->sibling=q;p=q;}return t;}treenode * assign_stmt(){treenode * t=(treenode *)malloc(sizeof(treenode));if(token[wordindex]==ID){t->nodek=stmtk;t->kind.stmt=assignk;t->=tokenstring[wordindex];wordindex++;}else {printf("error");exit(1);}if(token[wordindex]==ASSIGN)wordindex++;else {printf("error");exit(1);}t->child[0]=exp();t->child[1]=NULL;t->child[2]=NULL;t->sibling=NULL;return t;}treenode * exp(){treenode * t;t=term();while((token[wordindex]==PLUS)||(token[wordindex]==MINUS)) {treenode * p=(treenode *)malloc(sizeof(treenode));p->nodek=expk;p->kind.exp=opk;p->attr.op=token[wordindex];p->child[0]=t;t=p;wordindex++;t->child[1]=term();t->child[2]=NULL;t->sibling=NULL;}return t;}treenode * term(){treenode * t=factor();while((token[wordindex]==TIMES)||(token[wordindex]==OVER)) {treenode * p=(treenode *)malloc(sizeof(treenode));p->nodek=expk;p->kind.exp=opk;p->attr.op=token[wordindex];p->child[0]=t;t=p;wordindex++;t->child[1]=factor();t->child[2]=NULL;t->sibling=NULL;}return t;}treenode * factor(){treenode * t;switch(token[wordindex]){case LPAREN :wordindex++;t=exp();if(token[wordindex]==RPAREN)wordindex++;else {printf("error");exit(1);}break;case NUM :t=(treenode *)malloc(sizeof(treenode));t->nodek=expk;t->kind.exp=constk;t->attr.val=atoi(tokenstring[wordindex]);t->child[0]=NULL;t->child[1]=NULL;t->child[2]=NULL;t->sibling=NULL;wordindex++;break;case ID :t=(treenode *)malloc(sizeof(treenode));t->nodek=expk;t->kind.exp=idk;t->=tokenstring[wordindex];wordindex++;break;default:printf("error");}return t;}pretraverse(treenode * t){if (t!=NULL){ if (t->nodek==stmtk) printf("stmt-id:%s\n",t->);if (t->nodek==expk && t->kind.exp==idk)printf("exp-id:%s\n",t->);if (t->nodek==expk && t->kind.exp==opk) printf("exp-op:%d\n",t->attr.op);if (t->nodek==expk && t->kind.exp==constk)printf("exp-val:%d\n",t->attr.val);if(t->child[0]!=NULL) pretraverse(t->child[0]);if(t->child[1]!=NULL) pretraverse(t->child[1]);if(t->child[2]!=NULL) pretraverse(t->child[2]);if(t->sibling!=NULL) pretraverse(t->sibling);}}treenode * decl(){treenode * p,* q,* t1;treenode * t=(treenode *)malloc(sizeof(treenode));t->nodek=stmtk;t->kind.stmt=declk;t->=tokenstring[wordindex];t->child[1]=NULL;t->child[2]=NULL;wordindex++;if(token[wordindex]==ID){t1=(treenode *)malloc(sizeof(treenode));t->child[0]=t1;t1->nodek= expk;t1->kind.exp=idk;t1->=tokenstring[wordindex];t1->child[0]=NULL;t1->child[1]=NULL;t1->child[2]=NULL;t1->sibling=NULL;wordindex++;p=t1;while( token[wordindex]==COMMA){ wordindex++;q=(treenode *)malloc(sizeof(treenode));q->nodek= expk;q->kind.exp=idk;q->=tokenstring[wordindex];q->child[0]=NULL;q->child[1]=NULL;q->child[2]=NULL;q->sibling=NULL;p->sibling=q;wordindex++;p=q;}return t;}}expcode(treenode * t){char * s1, * s2;if(t->child[0]!=NULL) expcode(t->child[0]);if(t->child[1]!=NULL) expcode(t->child[1]);if(t->nodek==expk && t->kind.exp==opk){if (t->attr.op==PLUS) strcpy(codestr[codeindex++],"adi"); if (t->attr.op==MINUS) strcpy(codestr[codeindex++],"sbi"); if (t->attr.op==TIMES) strcpy(codestr[codeindex++],"mpi"); if (t->attr.op==OVER) strcpy(codestr[codeindex++],"ovi");}if(t->nodek==expk && t->kind.exp==idk)strcpy(codestr[codeindex++],strcat("lod ",t->)); if(t->nodek==expk && t->kind.exp==constk){strcpy(s1,"ldc ");itoa(t->attr.val, s2,10);strcat(s1,s2);strcpy(codestr[codeindex++],s1);}}gencode(treenode * t){char * s;if(t->nodek==stmtk && t->kind.stmt==assignk){ strcpy(s,"lda ");strcat(s,t->);strcpy(codestr[codeindex++],s);expcode(t->child[0]);strcpy(s,"sto");strcpy(codestr[codeindex++],s);if(t->sibling!=NULL) gencode(t->sibling);}}_。

编译原理之中间代码⽣产、词法优化与代码⽣成
中间代码⽣成
在把⼀个源程序翻译成⽬标代码的过程中，⼀个编译器可能构造出⼀个或多个中间表⽰。

这些中间表⽰可以有多种形式。

语法树是⼀种中间表⽰形式，它们通常在语法分析和语义分析中使⽤。

在源程序的语法分析和语义分析完成之后，很多编译器⽣成⼀个明确的低级的或类机器语⾔的中间表⽰。

我们可以把这个表⽰看作是某个抽象机器的程序。

该中间表⽰应该具有两个重要的性质：它应该易于⽣成，且能够被轻松地翻译为⽬标机器上的语⾔。

代码优化
机器⽆关的代码优化步骤试图改进中间代码，以便⽣成更好的⽬标代码。

“更好”通常意味着更快，但是也可能会有其他⽬标，如更短的或能耗更低的⽬标代码
代码⽣成
代码⽣成器以源程序的中间表⽰形式作为输⼊，并把它映射到⽬标语⾔。

如果⽬标语⾔是机器代码，那么就必须为程序使⽤的每个变量选择寄存器或内存位置。

然后，中间指令被翻译成为能够完成相同任务的机器指令序列。

代码⽣成的⼀个⾄关重要的⽅⾯是合理分配寄存器以存放变量的值。

（这⾥我觉得还存疑因为书本上下下段还说了⼀句话，上⾯对代码⽣成的讨论忽略了对源程序中的标识⾏进⾏存储分配的重要问题。

） 不过总之，运⾏时刻的存储组织⽅法依赖于被编译的语⾔。

编译器在中间代码⽣成或代码⽣成阶段做出有关存储分配的决定。

编译原理与代码生成在计算机科学领域中，编译原理是一门研究编程语言如何被转换成可执行代码的学科。

它涉及到编译器的设计和开发，其中一个关键环节就是代码生成。

代码生成是编译过程中的最后一步，它将中间表示形式（如抽象语法树或中间代码）转化为机器代码或目标代码，以便计算机能够直接执行。

代码生成是编译过程中至关重要的一环，其质量直接影响到最终生成的可执行程序的效率和性能。

一个好的代码生成器应该能够生成高效、优化的机器代码，并且具备可移植性。

为了实现这一目标，代码生成器通常需要考虑以下几个方面：1. 寄存器分配：寄存器是现代计算机体系结构中重要的资源之一。

在代码生成阶段，寄存器的分配是一个关键问题。

代码生成器需要决定哪些变量应该存储在寄存器中，哪些应该存储在内存中，并生成相应的指令来进行寄存器的分配和管理。

2. 内存分配：除了寄存器分配外，代码生成器还需要考虑如何进行内存分配。

它需要决定哪些变量应该存储在堆栈上，哪些应该存储在静态数据区，以及如何有效地进行内存的分配和释放。

3. 代码优化：代码生成器还需要考虑一系列的代码优化技术，以提高生成代码的质量和效率。

这些技术包括常见的优化方法，如常量折叠、公共子表达式消除、死代码删除等。

通过应用这些优化技术，代码生成器可以生成更紧凑、更高效的机器代码。

4. 目标代码生成：最后，代码生成器需要将中间表示形式翻译成目标机器能够执行的机器代码。

这一过程中，代码生成器需要根据目标机器的指令集架构和特性来生成相应的机器代码。

同时，为了保证生成的代码的可移植性，代码生成器还需要考虑各种编译器选项和标准。

综上所述，编译原理中的代码生成是编译过程中不可或缺的一部分。

通过合理的寄存器分配、内存分配、代码优化和目标代码生成，代码生成器可以生成高质量、高效率的机器代码。

这对于计算机科学学习者和编译器开发者来说，都是一个重要的课题。

只有深入理解编译原理和代码生成的原理和技术，才能够设计和实现出优秀的编译器和程序。

第十二章代码生成课前索引【课前思考】在第2章PL/0语言编译程序的实现中，产生的目标代码是一种与机器无关的假想栈式计算机器汇编语言类PCODE,它的执行需要用具体机器配置的语言编写一个解释程序。

本章将介绍的代码生成是把某种高级程序设计语言经过语法语义分析或优化后的中间代码作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器，因此，代码生成器的构造与输入的中间代码形式和输出的目标代码的机器结构密切相关。

本章将主要介绍生成具体机器汇编语言为目标代码时需要考虑的一些共同问题和中间语言的选择考虑。

建议学员考虑如何把PL/0语言编译程序的目标代码类PCODE翻译成你所熟悉的具体机器的汇编语言,作为学习代码生成的预习思考。

【学习目标】本章将介绍以具体计算机指令作为目标代码的代码生成器的设计，以一个计算机模型为例介绍一个简单的代码生成器需要考虑的问题，在代码生成时要考虑充分利用寄存器，以减少对内存的存取次数以提高目标程序运行速度，为此，本章将给出寄存器分配的原则，并使用待用信息链表法的代码生成算法，最后给出中间语言的选择需要考虑的问题。

【学习指南】由于代码生成的目标代码与具体计算机的结构有关，如指令格式、字长及寄存器的个数和种类，并与指令的语义和所用操作系统等都密切相关，因此实现非常困难。

通过本章学习，仅为学员初步了解一个高级程序设计语言编译程序目标代码生成需要考虑的问题和解决这些问题的基本原则和方法，为今后应用打下初步基础。

要想真正掌握代码生成技术的细节，最好的方法是实现一个代码生成器，建议学员学习本章后，用第2章PL/0语言的中间代码类PCODE为输入，选择一个自己熟悉的汇编语言为输出，编写一个代码生成器。

【难重点】重点：衡量目标代码的质量主要从占用空间和执行效率两方面考虑，而寄存器的合理分配对解决这两方面的问题起着重要的作用，因此要求学员了解寄存器的分配原则很重要，一个要求执行效率高的编译器对寄存器的分配可能要进行优化。