編譯原理實驗報告696

編譯方法實驗報告實驗1：掃描器的設(shè)計一、實驗?zāi)康氖煜げ崿F(xiàn)一個掃描器（詞法分析程序）。二、實驗要求(1)設(shè)計掃描器的有限自動機（識別器）；(2)設(shè)計翻譯、生成Token的算法（翻譯器）；(3)編寫代碼并上機調(diào)試運行通過?！ぽ斎搿闯绦蛭募蛟闯绦蜃址弧ぽ敵觥鄳?yīng)的Token序列；關(guān)鍵字表和界符表；符號表和常數(shù)表；三、實驗步驟流程：初始化；打開用戶源程序文件；while（文件未結(jié)束）{讀入一行到w[i]，i=0;do//處理一行，每次處理一個單詞{濾空格，直到第一個非空的w[i]；i--；s=1;//處理一個單詞開始while（s!=0）//拼單詞并生成相應(yīng)Token{act(s);if（s>=11&&s<=14）break;//執(zhí)行q//一個單詞處理結(jié)束si++;//getchar()s=find(s,w[i]);}if（s==0）詞法錯誤；}while（w[i]!=換行符）；}關(guān)閉用戶源程序文件；生成Token文件；輸出關(guān)鍵字表；輸出Token序列；輸出符號表；輸出常數(shù)表；有限自動機的狀態(tài)轉(zhuǎn)換圖：eddd+|--1/+/-+①d②.③d④e⑤⑥d⑦11d--1/+/-l/d-1/+/-12-1-1l⑧--113b⑨b⑩-14--115-其中：d為數(shù)字，l為字母，b為界符，-1代表其它符號（如在狀態(tài)8處遇到了非字母或數(shù)字的其它符號，會變換到狀態(tài)12）。關(guān)鍵字表和界符表：ProgramBeginEnd;:(Var)WhileDoRepeatUntilFor,:=+-*To/IfThenElse>>===<<=四、主要數(shù)據(jù)結(jié)構(gòu)①狀態(tài)轉(zhuǎn)換矩陣：intaut[10][7]={2,0,0,0,8,9,15,2,3,5,11,0,0,11,4,0,0,0,0,0,0,4,0,5,11,0,0,11,7,0,0,6,0,0,0,7,0,0,0,0,0,0,7,0,0,11,0,0,11,8,0,0,0,8,0,12,0,0,0,0,0,10,14,0,0,0,0,0,0,13};②關(guān)鍵字表：charkeywords[30][12]={“program”,”begin”,”end”,”var”,”while”,”do”,”repeat”,”until”,”for”,”to”,”if”,”then”,”else”,“;”,”:”,”(“,”)”,”,”,”:=”,”+”,”-“,”*”,”/”,”>”,”>=”,”==”,“<”,“<=”};③符號表：charID[50][12];④常數(shù)表：floatC[20];//表中存有源程序中的標(biāo)識符⑤其它變量：structtoken{intcode;intvalue};structtokentok[100];ints;//Token結(jié)構(gòu)//Token數(shù)組//當(dāng)前狀態(tài)intn,p,m,e,t;floatnum;charw[50];inti;//尾數(shù)值，指數(shù)值，小數(shù)位數(shù)，指數(shù)符號，類型//常數(shù)值//源程序緩沖區(qū)//源程序指針,當(dāng)前字符為w[i]charstrTOKEN[12];//當(dāng)前已經(jīng)識別出的單詞五、實驗核心代碼intmain(intargc,char*argv[]){FILE*fp;ints;當(dāng)前狀態(tài)有限自*動機中的狀態(tài)//fp=fopen("exa.txt","r");while(!feof(fp)){fgets(w,50,fp);i=0;//*處理一行do{printf("%c",w[i]);測試顯示每個tok的e首n字母////*處理一個tokenwhile(w[i]=='')濾空格i++;if(w[i]>='a'&&w[i]<='z')//判定單詞類別*是字母（關(guān)鍵字或標(biāo)識符）{ptr=col2;num_map=2;}else//*是數(shù)字（常量的開頭）{if(w[i]>='0'&&w[i]<='9'ptr=col1;num_map=4;}elseif//*其他字符算為非法字符(strchr(col3[0].str,{printf("非法字符%c\n",w[i]);i++;continue;}else//界符{ptr=col3;num_map=1;}i--;向后退一個字符開始處理一個單詞s=1;while(s!=0){act(s);if(s>=11&&s<=14)判斷是否是終止?fàn)顟B(tài)是*終止?fàn)顟B(tài)，則形成一個tokenbreak;i++;讀取下一個字符s=find(s,w[i]);狀態(tài)轉(zhuǎn)換}if(s==0){strTOKEN[i_str]='\0';printf("詞法錯誤：%s\n",strTOKEN);}}while(w[i]!=10);}printf(關(guān)鍵字表：");輸出結(jié)果//for(i=0;i<30;i++)printf("%s",keywords[i]);printf("\n");printf("Token序列：");for(i=0;i<num_token;i++)printf("(%d,%d)",tok[i].code,tok[i].valueprintf("\n");printf("符號表：");for(i=0;i<num_ID;i++)printf("%s",ID[i]);printf("\n");printf("常數(shù)表：");for(i=0;i<num_C;i++)printf("%d",C[i]);printf("\n");fclose(fp);printf("HelloWorld!\n");return0;}//*狀態(tài)轉(zhuǎn)換后，達到新的狀態(tài)之后，記錄的變化voidact(ints){intcode;switch(s){case1:n=0;m=0;p=0;t=0;e=1;num=0;i_str=0;strTOKEN[i_str]='\0';其它變量初始化break;case2:n=10*n+w[i]-48;break;case3:t=1;break;case4:n=10*n+w[i]-48;m++;break;case5:t=1;break;case6:if(w[i]=='-')e=-1;break;case7:p=10*p+w[i]-48;break;case8:strTOKEN[i_str++]=w[i];將ch中的符號拼接到strTO的K尾E部N//；break;case9:strTOKEN[i_str++]=w[i];將ch中的符號拼接到strTO的K尾E部N//；break;case10:strTOKEN[i_str++]=w[i];將ch中的符號拼接到strTO的K//尾EN部；break;case11:num=n*pow(10,e*p-m);計算常數(shù)值//tok[i_token].code=2;tok[i_token+生成常數(shù)Tokennum_token++;break;case12:strTOKEN[i_str]='\0';code=Reserve(strTOKEN);查關(guān)鍵字表if(code)t{ok[i_token].code=code;}tok[i_token++]生成//關(guān)鍵字Tokenelse{tok[i_token].code=1;tok[i_token++].value=InsertID(strTOKEN)生成標(biāo)識符Tokennum_token++;break;case13:strTOKEN[i_str]='\0';code=Reserve(strTOKEN);查界符表if(code){tok[i_token].code=code;生成界tok[i_tok符Tokenelse{strTOKEN[strlen(strTOKEN)-1]=單界符i--;code=Reserve(strTOKEN);查界符表tok[i_token].code=code;生成界符Toktok[ien}num_token++;break;case14:strTOKEN[i_str]='\0';code=Reserve(strTOKEN);查界符表tok[i_token].code=code;生成界符tok[i_toTokennum_token++;break;}}//*狀態(tài)轉(zhuǎn)換intfind(ints,charch){inti,col=7;structmap*p;p=ptr;for(i=0;i<num_map;i++)if(strchr((p+i)->str,ch)){col=(p+i)->col;break;}returnaut[s][col];}//*向常量表中插入常量intInsertConst(doublenum){inti;for(i=0;i<num_C;i++)if(num==C[i])returni;C[i]=(int)num;num_C++;returni;}intReserve(char*str){inti;for(i=0;i<num_key;i++)if(!strcmp(keywords[i],str))return(i+3);return0;}//*向符號表中插入新的符號intInsertID(char*str){inti;for(i=0;i<num_ID;i++)if(!strcmp(ID[i],str))符號已經(jīng)存在，則返回地址//returni;strcpy(ID[i],str);num_ID++;returni;}六、實驗結(jié)果實驗思考題：1.掃描器的任務(wù)是什么？答：詞法分析程序又稱掃描器，任務(wù)有：(1)識別單詞——從用戶的源程序中把單詞分離出來;(2)翻譯單詞——把單詞轉(zhuǎn)換成機內(nèi)表示，便于后續(xù)處理。2.掃描器、識別器、翻譯器三者之間的關(guān)系是怎樣的？答：掃描器、識別器、翻譯器三者之間的關(guān)系是：掃描器的實現(xiàn)要通過識別器和翻譯器1.為什么說有限自動機是詞法分析的基礎(chǔ)？答：因為詞法分析的包括：識別---識別單詞的有限自動機。和翻譯---根據(jù)有限自動機所識別出的對象，完成從單詞串到單詞的TOKEN串的翻譯。我們可以看出，不論是識別還是分析，都是應(yīng)用有限自動機，所以可以說有限自動機是詞法分析的基礎(chǔ)。實驗2：中間代碼生成器的設(shè)計一、實驗?zāi)康氖煜に阈g(shù)表達式的語法分析與中間代碼生成原理。二、實驗要求(1)設(shè)計語法制導(dǎo)翻譯生成表達式的四元式的算法；(2)編寫代碼并上機調(diào)試運行通過。·輸入——算術(shù)表達式·輸出——語法分析結(jié)果相應(yīng)的四元式序列(3)本實驗已給出遞歸子程序法的四元式屬性翻譯文法的設(shè)計，鼓勵學(xué)生在此基礎(chǔ)上進行創(chuàng)新，即設(shè)計LL(1)分析法或LR(0)分析法的屬性翻譯文法，并根據(jù)這些屬性翻譯文法，使用擴展的語法分析器實現(xiàn)語法制導(dǎo)翻譯。三、設(shè)計概要(1)算術(shù)表達式文法G(E)：EEω0T|TTTω1F|FFi|(E)(2)文法變換G’(E)ET{ωT}TF{ω1F}Fi|(E)0(3)屬性翻譯文法：ET{ω“push(SYN,w)”T“QUAT”}0TF{ω“push(SYN,w)”F“QUAT”}1Fi“push(SEM,entry(w))”|(E)其中：·push(SYN,w)—當(dāng)前單詞w入算符棧SYN;·push(SEM,entry(w))—當(dāng)前·QUAT—生成四元式函數(shù)i．T=newtemp;w在符號表中的入口值壓入語義棧SEM;ii．QT[j]=(SYN[k],SEM[s-1],SEM[s],T);j++;iii．pop(SYN,_);pop(SEM,_);pop(SEM,_);push(SEM,T);(4)遞歸下降子程序：·數(shù)據(jù)結(jié)構(gòu)：SYN—算符棧；SEM—語義棧；E:T:入口入口TFnω0?nω1?yy出口push(SYN,w)出口push(SYN,w)read(w)QUATread(w)TQUATi?FF:主程序：ZE入口(?nnerrread(w)read(w)push(SEM,entry(w))EEerrn#?errn)?yy輸出四元式序列read(w)結(jié)束出口四、實驗核心代碼voidmain()//主函數(shù){t=1;cout<<"輸入表達式，以#結(jié)束:"<<endl;Z();}stringits(inta){stringd;//整形變成字符串形函數(shù)charb='0',c;inti;while(a!=0){i=a%10;a=a/10;c=(int)b+i;d=c+d;}returnd;}charF(charw){stringtheWord;//F自動機if(w>='a'&&w<='z'||w>='A'&&w<='Z'){theWord=w;//當(dāng)前字符是字母markStack.push(theWord);//則壓棧}elseif(w=='('){cin>>w;//是左括號//則讀取下一字符w=E(w);if(w!=')'){//不是右括號則輸入有誤，報錯cerr<<"輸入錯誤!"<<endl;exit(0);}}else{//否則有誤，報錯cerr<<"輸入錯誤!"<<endl;exit(0);}cin>>w;//讀取下一字符returnw;}charE(charw){stringoperate,a,b,c;//E自動機stringstate[5];w=T(w);while(w=='+'||w=='-'){operate=w;//是加或減符號cin>>w;//讀入下一字符w=T(w);b=markStack.pop();a=markStack.pop();//字符棧彈出//兩個操作字符cout<<"(\""<<operate<<"\","<<a<<","<<b<<",t"<<t<<")"<<endl;c="t"+its(t);markStack.push(c);t++;//輸出四元式//新狀態(tài)壓棧//狀態(tài)計數(shù)加一}returnw;}charT(charw){stringoperate,a,b,c;stringstate[5];w=F(w);while(w=='*'||w=='/'){operate=w;cin>>w;//讀取下一字符w=F(w);b=markStack.pop();a=markStack.pop();//符號棧彈出//兩個操作字符cout<<"(\""<<operate<<"\","<<a<<","<<b<<",t"<<t<<")"<<endl;c="t"+its(t);markStack.push(c);t++;}returnw;}boolZ(){charw;//Z自動機cin>>w;w=E(w);if(w=='#'){//遇到"#"則結(jié)束returntrue;}else{returnfalse;}}五、實驗結(jié)果實驗思考題：1.語法分析分為幾類？其關(guān)鍵技術(shù)各是什么？答：自頂向下法（推導(dǎo)法）從開始符號出發(fā)，采用推導(dǎo)運算，試圖自頂向下構(gòu)造語法樹。自底向上法（歸約法）從給定的符號串出發(fā)，采用歸約運算，試圖自底向上構(gòu)造語法樹。2.什么是遞歸下降子程序法，什么是LL(1)分析法？二者對文法各有什么要求？答：遞歸