第7章-高级设计讨论-minic编译器

第7章本章将讨论一些高级设计的话题，这包括设计流水型CPU，一些更复杂实用的接口部件，以MiniCMiniSysMiniSys5章所讲的汇编器。对于C语言，有标准C语言和方言C语言。对于标准C语言，主要是学语言是根据特定应用领域需求对ANSICC语言。C语言编写的程序转化为机器可以理解运行的机器指令程序，则需要通CC语言程序直接编译成机器指令程序，也可先编译生成汇编指令程序，后通过汇编器（5章）将所生成的汇编指令程序编译CC语言编译器编译生成汇编指令CMiniCMiniC编译器，以有效支撑MiniCMiniSYS进行系统编程和应用编程。MiniCMiniSYSANSICMini循环语句允许有while，可以用continue、gotoiteruptrer0interuptServer1MiniC decl_list/*程序由变量描述或函数描述组成（decl）*/ decl_listdecl|decl var_decl| type_specIDENT|type_specIDENTint_literal*变量包括简单变量和一维数组变量*/type_specVOID|INT/*函数返回值类型或变量类型包括整型或VOID*/ type_specIDENT(params)compound_stmt param_list|VOID/*函数参数个数可为0或多个*/param_listparam_list,param|param type_specIDENT|type_specIDENT[int_literal] stmt_liststmt|ε expr_stmt|compound_stmt|if_stmt|while_stmt|return_stmt|expr_stmtIDENTexpr|IDENTexprexpr|/*赋值语句*/while_stmtWHILE(expr)stmt/*WHILE语句*/compound_stmtlocal_declsstmt_list/*函数内部描述，包括局部变量和语句描述*/local_declslocal_declslocal_decl|ε/*函数内部变量描述*/ type_specIDENT;|type_specIDENT[int_literal]; IF(expr)stmt|IF(expr)stmtELSEstmtreturn_stmtRETURN;|RETURNexpr; exprORexpr/*逻辑或表达式，运算符为exprEQexpr|exprNEexpr/*关系表达式exprLEexpr|exprexpr|exprGEexpr|exprexpr/*关系表达式exprANDexpr*逻辑与表达式，运算符为exprexpr|exprexpr*算术表达式expr*expr|exprexpr|exprexpr/*算术表达式expr|expr|expr|$expr/*$expr为取端口地址为expr值的端口值(exprIDENT|IDENTexpr|IDENTargs)/*IDENTargs为函数调用int_literal/*数值常量 um/*数值常量是十进制整数*/ arg_list,expr|expr arg_list|ε（1）IF语句中，ELSEIF规表达式表示。如，标识符的正规表达式是：(letter)(letter|digit)*，用于表示以字母开头的

=

**

*

**

letterordigit

*Return(gettoken(),install

13*#defineIF#defineELSE#defineWHILE#defineINT#defineVOID#defineRETURN#defineRELOP#defineID#defineNUM#defineLE#defineEQ#defineGE#defineGT#defineENDintstate=0;*当前状态,初始设置为零*/charword[];/*当前单词*/struct{intcatalog;*单词所属类别structentry{/*保留字符号表表项结构定义*/charlexeme[]; int /*token码}structentry *保留字符号表*/structsymbol_table*符号表项定义*/charname[];/*项名*/[];/charcatalog[];/*项类别，如，是变量名或函数名*/charval[]; int structsymbol_table structsymbol_tableliteral_table[];/*常量（字面量）符号表*/intlast_id_table_entry=-1; {charc*当前单词中的当前字符intc_pos=0;*当前单词中的当前字符位置*/Tokentoken;/*token信息*/while(1){switch(state){case0:c=nextchar*c是下一个字符ifc==blank||c==tab||c==newline*c是空白符号*/state=0;/*0*/}elseifcstate=1;*}elseifcstate=4;*}elseif {case1:

elseif(isletter(c)){}elseif(isdigit(c)){}if(c==’=’)state=2;elsestate=3;case2:);/caseretract(1*将当前字符c返回到输入缓冲区以作为下一个单词的开始符号);/case4:if(c==’=’)state=5;elsestate=6;case);/caseretract(1*将当前字符c返回到输入缓冲区以作为下一个单词的开始符号);/case7:if(c==’=’)state=8;elsestate=9;case);/caseretract(1*将当前字符c返回到输入缓冲区以作为下一个单词的开始符号return(token*当前单词是关系运算符’>’*/case10:c=netxchar();ifisletter(c||isdigit(cstate=10;*当前字符c是字母或数字elsestate=11;caseretract(1*将当前字符c返回到输入缓冲区以作为下一个单词的开始符号(();/elsetoken.innercode=0;*当前单词是保留字*/case12:if(isdigit(c))state=12;elsestate=13;caseretract(1*将当前字符c返回到输入缓冲区以作为下一个单词的开始符号default:}}}int while [p].lexeme!=’\0’&&if(strcmp( [p].lexeme,word)==0)*当前单词出现在保留字符号表中*/elseif(endtag==1)return( [p].tokencode是保留字elsereturn(ID);}intinstall_id*判断当前单词wordintif(last_id_table_entry==-1){}elsewhile(p<=last_id_table_entry&&endtag==0)if(strcmp(id_table[p].name,word)==0)endtag=1;elsep=p+1;if(endtag==1)return(p);else{}}}intif(last_literal_table_entry==-1){}elsewhile(p<=last_literal_table_entry&&endtag==0)if(strcmp(literal_table[p].name,word)==0)endtag=1;elsep=p+1;if(endtag==1)return(p);else{}}}Lex规范描述自己的词法（单词正规式描述及相应语义动作）及辅助成分，形成Lex描的词法分析程序描述语言，如，CJava语言；用户可对所生成的词法分析程序进行Lex所给出的规范比较复杂。我们可以模仿LexLex自动机(NFA)构造程序（可包括将所有正规表达式对应的NFA合并为一个NFA化为确定有限自动机(DFA)和DFA最小化算法可参见任何一本编译原理。structedge*自动机中边的定义*/intastate;/*边的起点状态charsymbol;/*边上的符号*/intbstate/*边的终点状态*/int charsigma[];/*状态机中每条边上可以出现的字符集合，其中包括*/intstart; intendstate*终止状态集，可有一个或多个终止状态*/structedgeedges[];/*边集*/}Thompson算法(RENFA)所对应非确定有限自动机结点structnodeintlabel*状态结点标记名intacceptstatetag;*接受状态标记，0为非接受状态，1为接受状态*/struct{charsymbol*边上标记structnode*nextnode*后续状态结点}firstnode,}注：①NFANFA可转化为五元组形NFANFA。解析正规表达式(RE)NFA的方法有二：LR(1)语法制导生成法和基于正规表达式NFA，也就是语法制导生成。其过程如下：R s1=newstate*s1labels1*/s2=newstate();/*s2labels2*/s1.acceptstatetag=0;/*s1为非接受态*/(s1.firstnode).symbola’;(s1.firstnode).nextnode=s2*s1通过as2*/(s1.lastnode).nextnode=’\0’;/*s1无其他发出边*/s2.acceptstatetag=1;/*s2为接受态*/(s2.lastnode).nextnode=’\0’*s2无发出边*/R.start=s1;/*s1R的自动机的初态*/R.end=s2*s2R的自动机的接受态}aRR(1)R(2) /*R(1).startR的开始状态*/((R(1).end).firstnode).symbol’;/*R(1).end通过R(2).start*/(R(1).end).acceptstatetag=0;*R(1).end为非接受状态*/R.end=R(2).end;/*R(2).endR的接受状态*/}R2s1=newstate*s1labels1*/s2=newstate();/*s2labels2*/s1.acceptstatetag=0;/*s1为非接受态*/(s1.firstnode).symbol’;(s1.firstnode).nextnode=R(1).start*s1通过R(1).start*/(s1.lasttnode).symbol’;;/R.start=s1*s1R的开始状态*/s2.acceptstatetag=1;/*s2为接受态*/((R(1).end).firstnode).symbol’;(R(1).end).acceptstatetag=0;*R(1).end为非接受状态*/((R(2).end).firstnode).symbol’;(R(2).end).acceptstatetag=0;*R(2).end为非接受状态*/R.end=s2;/*s2R的接受状态*/}R1R2 RR(1)*s1=newstate*s1labels1*/s2=newstate();/*s2labels2*/s1.acceptstatetag=0;/*s1为非接受态*/(s1.firstnode).symbol’;(s1.firstnode).nextnode=R(1).start*s1通过R(1).start*/(s1.lasttnode).symbol’;(s1.lastnode).nextnode=s2*s1通过s2R.start=s1*s1R的开始状态*/s2.acceptstatetag=1;/*s2为接受态*/((R(1).end).firstnode).symbol’;((R(1).end).lastnode).symbol’;/*R(1).end通过s2R(1).start*/(R(1).end).acceptstatetag=0;*R(1).end为非接受状态*/R.end=s2;/*s2R的接受状态*/}R1R1R(R(1))R.end=R(1)}构造相应LR(1)R如下：运算符号’’的优先级高于选择运算符号’|’；闭包运算符号’*、连接运算符号’’和选择运算符号|’均遵循左结合规则。RLR(1)下推自动机（这里略LR(1)分 a|*()#R011273456789）’#’，LR(1)NFA的局部。当出现接收动作时，则整个NFA就已生成。voidChange(char*r1,char* {Stack inti,j; char if(ch==' else }

else{

else charw=Peek(R);Precedence(w)Precedence('*')=3,//Precedence('|')=1,//Pop(R);w=Peek(R);}}else}}while{}Pop(R);//弹出'#'r2[j++]='\0'r2}可规定闭包运算符号’*’的优先级高于连接运算符号’’，而连接运算符号’’的优先级高于选择运算符号’|’；闭包运算符号’*、连接运算符号’’和选择运算符号’|’均遵循左结根据正规表达式后缀形式r2生成相应r2r2中当前符号若r2中当前符号是’或’|’,则弹出当前操作数栈栈顶两项，并生成r2中当前符号是*’NFAR，NFARr2结束。Stack int char if(isletter(ch)) s1=newstate*s1labels1*/s2=newstate();/*s2labels2*/s1.acceptstatetag=0;/*s1为非接受态*/(s1.firstnode).nextnode=s2*s1通过as2*/(s1.lastnode).nextnode=’\0’;/*s1无其他发出边*/s2.acceptstatetag=1;/*s2为接受态*/(s2.lastnode).nextnode=’\0’*s2无发出边*/aR.start=s1;/*s1R的自动机的初态*/R.end=s2*s2RaPush(S,RRS }else R2=Pop(SSR2,R2NFAR1=Pop(SSR1R1NFA//R1R2NFA,NFAR1R2NFA((R1.end).firstnode).symbol=’’;(R1.end).acceptstatetag=0*R1.end为非接受状态*/R.start=R1.start;/*R1.startR的开始状态*/R.end=R2.end;/*R2.endR的接受状态*/R1R1R1R1R2}elseNFAR,

{ R2=Pop(S);SR2R2NFAR1=Pop(SSR1R1NFA//R1R2NFANFAR1R2NFARs1=newstate();/*s1labels1*/s2=newstate();/*s2labels2*/s1.acceptstatetag=0;/*s1为非接受态*/(s1.firstnode).nextnode=R1.start*s1通过R1.start*/(s1.lasttnode).symbol’;(s1.lastnode).nextnode=R2.start*s1通过R2.start*/s2.acceptstatetag=1;/*s2为接受态*/((R1.end).firstnode).symbol’;(R1.end).acceptstatetag=0;*置R1.end为非接受状态*/((R2.end).firstnode).symbol’;/*R2.end通过(R2.end).acceptstatetag=0;*R2.end为非接受状态*/R.start=s1;/*s1R的开始状态*/R.end=s2*s2R的接受状态R1R2 }

elses1=newstate*s1labels1*/s2=newstate();/*s2labels2*/s1.acceptstatetag=0;/*s1为非接受态*/(s1.firstnode).symbol’;(s1.firstnode).nextnode=R1.start*s1通过R1.start*/(s1.lasttnode).symbol’;(s1.lastnode).nextnode=s2*s1通过s2s2.acceptstatetag=1;/*s2为接受态*/((R1.end).firstnode).symbol’;((R1.end).lastnode).symbol’;/*R1.end通过s2R1.start/R.start=s1*s1R的开始状态*/R.end=s2;/*s2R的接受状态*/R1}else}}RENFA。LL(1)预测LR(1)语法分析法。中，有一个产生式，产生式用于定义语言的成分，如程序，其它产生式用于定MiniC语法对语句(stmt)的定义，描述如何构造基于递归下降分析法的语stmtexpr_stmt|compound_stmt|if_stmt|while_stmtexpr_stmtIDENTexpr|IDENTexprexpr|/*赋值语句*/while_stmtWHILE(expr)stmt/*WHILE语句*/compound_stmtlocal_declsstmt_list}/*函数内部描述，包括局部变量和语句描述*/local_declslocal_declslocal_decl|ε/*函数内部变量描述*/local_decltype_specIDENT;|type_specIDENT[];if_stmtIF(expr)stmt|IF(expr)stmtELSEstmtreturn_stmtRETURN;|RETURNexpr;if_stmtIF(expr)stmtif_stmtIF(expr)stmt1elsestmt2{Tokenvoidstmt*{if(lookahead.catalog==ID)//当前单词是标识符();//elseiflookahead.catalog==IF当前单词是保留字IFif_stmt();//IF语句处理子程序elseiflookahead.catalog==WHILE当前单词是保留字IFwhile_stmt();//IF语句处理子程序 }void{match(ID);//ID，并读入下一个单词()//elseifmatch(ASSIGN确认当前单词类型是赋值符号,并读入下一个单词expr();//调用表达式处理子程序分析赋值符号右部的表达式}else}void{intmatch(IF);//确认当前单词是’if’,并读入下一个单词match(LEFTP确认当前单词是’(’,并读入下一个单词expr();//条件表达式处理match(RIGHTP);//确认当前单词是’)’,并读入下一个单词out1=newlabel();//产生一个标号,用于指示条件表达式为出口stmt();//处理条件为真时应该执行的语句if(lookahead.innercode==ELSE)//ELSE{out2=newlabel();//产生一个标号,if语句的出口emit(GO,out2goto语句,gotoif语句的出口//else//}else//if语句无else}voidmatch(int{if(lookahead.catalog==t)//tlookahead=nexttoken读入并分析下一个单词else}voidemit(intt,int{switch(t)caseLVALUE:caseGOFALSE:printf(“jmp%d\n”,tval);caseprintf(“jmp%d\n”,tval);printf(“token%d,tokenval}此表以一定的方式进行，以便于LR(1)语法分析总控程序使用。②手工构造

LR(1)LALR(1)分析表的构造，但一般可以不压缩。structlr_rowintstate;//状态stringaction动作intgoto[];//gotostructlr_rowlr[];action和gototokens和nontermtokens是一个常量数组，作用是用于存放可识别单词(也就是可以出现nontermstringnonterm[]={“E”,“T”,tokensm个元素，nonterm数组有nLR(1)分析表的每一1+m+n个元素：状态,action[0],…,action[n-1],goto[0],…,goto[n-1]。LR(1)语法分析总控程序使用。LR(1)分析表文件中每行信息可按如下结构存放，每个元间用’,’隔开，若一将LR(1)分析表文件读入内存的基本过程如下：FILE*fp;structlr_rowintfp=fopen(“lr1.txtr假设LR(1)lr1.txtif(fp!=‘\0’) while(！feof(fp)){i=i+1;//准备读下一行}}else在LR(1)语法分析总控程序中可如下根据当前状态和LR(1)分析表查找决定下inti,tempcatalog,endtag;intactionindex,currentstate;stringaction;//iftempcatalogRELOP||tempcatalog==ARIOP当前单词是运算符tempcatalog=lookahead.innercode;//运算符类别码用其内码表示whilei<n&&endtag==0tempcatalog寻找对应动作的actionif(tempcatalog==tokens[i])endtag=1;elsei=i+1;ifi<nactionindex=i获得对应动作的action数组下标,以查找actionelseactionindex=-if(actionindex>=0)elseerror();由上可以得出，基于LR(1)分析法的语法分析程序编写的和是由语言文LR(1)分析表。该构造过程非常繁琐，且当语言文法稍微调整时，LR(1)LR(1)分析表，进一步自动生成基于LR(1)分析的语法分析程序。这就需要语法分析程序MiniC语法，就需要通过一个语法分析程序生成MiniC语法分析程序，而不必只要语法修改则)YACC描述文件--.yYACC程序生成与.y文Java语言YACCYACC思路写自己的语法分析要求用户写出语言语法成分定义的产生式规则、语法成分正确识别后应采（（LALR(1)（LR(1)LR(1)下推自动机构造相应LR(1)LR(1)LALR(1)语法分析表的程序LALR(1)语法分析表。LALR(1)语法分析表进行语法分LALR(1)语法分析总控程序的程序。我们编写自己的语法分析程序生成工具的关键是如何编写由语言语法(文法)产生式构造L()L()(1)下推自动机构造L(1)语法分析表、由L(1分析表通过合并相容状态生成LAL1)法分析的算可参任何本编译。structLr1Item{//LR(1)项目定义;//stringright[];//项目右部,对应某一非终结符产生式的右部，由多个符号组成 }structLr1PDAStateLR(1)下推自动机的状态定义intname;//状态标识名，用整数表示Lr1Itemitems[];//状态所拥有的项目（可有多个）intitemsnum;//状态拥有项目数}structLr1PDAedgeLR(1)下推自动机的边定义intstartname;//边的起点状态标识}structLr1PDALR(1)下推自动机定义Lr1PDAStatestates[];//状态集定义intNumOfStates;int}structLr1PDAstructLr1PDAStateinitState,s1;structLr1Items2;Enqueue(StateQueue,InitState);//将初始状态入队intnumStates=0;intwhile(StateQueue不为空){s1=Delqueue(StateQueue);//StateQueues1if(s1StateSet中){//s1放入集合ExtendedStateSet){//(//s1LR(1)项目右部点之后是非终结符，需要展开}while(ItemQueue不为空s2=Delqueue(ItemQueueItemQueues2if(s2ExtendedItemSet中){//扩展新项目//s2放入集合ExtendedItemSet,ifs是非终结符structLr1Itemtempitem;//定义用于扩展项目的tempitemstringtemps;//s2形如：(AB,a)temps为astrcpy(temps,s2.right[s2.dotpos+1]);intwhilej<=nnsCopy(tempitem.right,sj个产生式右部);//将当前形成的与当前产生式相关的LR(1)项目tempitem作为s1iftempitem.right[dotpos]是非终结符)}}}}structLr1Itemtempitem1;inttempnum=1;//tempnum用于s1状态中项目右部点之后不同符号structstringsym;intitemno[];int}//genitem[i]用于记录s1状态中项目右部点之后为符号genitem[i].sym的所有项目编int//s1genitem[0]while(endtag==0&&mm<s1.itemsnum)//s1.items[mm]是可移进项目,也就是可以有后续状态}elseifendtag==1s1inttempcount=1;//tempcounts1strings=if(s1.items[tempcount].dotpos<s1.items[tempcount].rightnum){intk=0,endtag1=0;while(endtag1==0&&k<tempnum){if(strcmp(s,genitem[k].sym)==0){//若s是已出现的符号，则记录s的当前项目编号入相应genitem[k]}else}if(endtag1==0)//sgenitem[tempnum]}}}//以上代码用于根据s1中所有项目点之后的符号进行归类，tempnum是分类intm=0;stringwhile(m<tempnum){structLr1PDAStatetempstate;if(genitem[m].numitem>0){intkk=0;while(kk<genitem[m].numitem){structLr1Itemtempitem2;//s作为项目右部点后符号的当前项目令为if(tempitem2.dotpos<tempitem.rightnum){}}//tempstate放入状态队列，以对tempstate//s1tempstate之间形成一条边}//}}}}}造LR(1)分析表的是如何定义LR(1)分析表的数据结构，具体可参见本节“基LR(1)语法分析法”的语法分析程序编写部分。件中指明的算符优先级及结合规则或else悬挂等消除规则进行消除。设当前状态为m,后继状态为n,mn连接的边上标记为终结符c,即在m中存m中又有可归约项目(Bc.,c)(为空或一个非终结符,也就是项目的核前读头下终结符c，根据移进项目(A.c,a)要求移进；根据可归约项目(Bc.,c为空或一个非终结符)要求先归约)c的结合规则进行序列编号)；否则保留移进动作，也就是置action(m,c)Sn(nmc连接的项目的部分的最后一个终结符为d)，则同样出现了对同一个符号c的移进—项目(Cd.,c为空或一个非终结符)要求先归约)d与c的优先级进行消除(若d的优先级高于c的优先级，则保留归约动作,也就是置action(m,c)Sn(nm通过边c连接的后续状态)言文则进行语法分析的同时，利用相应语言文则的语义规则进行目标代码生成，也为了便于目标代码生成，我们可先通过语言文则的语义规则生成以三地址码形式表该标识符所处的环境也一无所知，词法分析时所构造的符号表很不成熟，推语法分析及并分配相应空间（以相对地址表示。对于全局变量说明，经过翻译后放在全局变量符 type_specIDENT;量} type_specIDENT[int_literal];量}type_specint } type_specIDENT(params)compound_stmt} }

param_list1param_list2,param}param_listparam } type_specIDENT量} type_