-------------精選文檔------------------------------精選文檔-----------------可編輯可編輯-------------精選文檔-----------------可編輯太原科技大學(xué)計算機學(xué)科學(xué)與技術(shù)院計算機08200班李永峰實驗五LR分析太原科技大學(xué)計算機學(xué)科學(xué)與技術(shù)院計算機08200班李永峰1．實驗?zāi)康呐c任務(wù)設(shè)計一個LR分析器，實現(xiàn)對表達式語言的分析，加深對LR語法分析方法的基本思想的理解，掌握LR分析器設(shè)計與實現(xiàn)的基本方法。2．實驗要求建立文法及其LR分析表表示的數(shù)據(jù)結(jié)構(gòu)，設(shè)計并實現(xiàn)一個LALR(1)的分析器，對源程序經(jīng)詞法分析后生成的二元式代碼流進行分析，如果輸入串是文法定義的句子則輸出“是”，否則輸出“否”。3．實驗內(nèi)容（1）文法描述及其LALR(1)分析表描述表達式語言的文法G如下：S→EE→E+TE→TT→T*FT→FF→(E)F→ID該文法的LALR(1)分析表如下：分析表狀態(tài)動作Action表（Yy_action）轉(zhuǎn)移Goto表（Yy_goto）#ID+*()SETF0-S1--S2--3451R6-R6R6-R6----2-S1--S2--6453A-S7-------4R2-R2S8-R2----5R4-R4R4-R4----6--S7--S9----7-S1--S2---1058-S1--S2----119R5-R5R5-R5----10R1-R1S8-R1----11R3-R3R3-R3----SN=移進并轉(zhuǎn)移到狀態(tài)NA=accept接受RN=按第N條產(chǎn)生式進行規(guī)約-=error轉(zhuǎn)移（2）LR分析器總控程序框架如下：push(0);advance();while(Action[tos][sym]!=accept)if(Action[tos][sym]==’-’)error();elseif(Action[tos][sym]==SN){push(N);advance();}elseif（Action[tos][sym]==RN{act(N);pop(產(chǎn)生式N的右部的符號個數(shù));push(Goto[新tos][產(chǎn)生式N的左部符號])；}accept();上述算法中的有關(guān)函數(shù)與符號的意義如下：accept()：返回成功狀態(tài)，LR分析器停止工作；act(N)：執(zhí)行利用產(chǎn)生式N的歸約的動作，通常為產(chǎn)生代碼；advance()：叢輸入流讀下一單詞到sym；error()：出錯處理；pop(N)：從棧頂彈出N個符號（狀態(tài)）；push(N)：把狀態(tài)N壓入狀態(tài)棧；sym：當(dāng)前輸入的單詞符號；tos：棧頂狀態(tài)號。（3）存放LR分析表的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)方法一：用一個二維整數(shù)數(shù)組表示數(shù)組元素為表示動作的整數(shù)。數(shù)組的行下標(biāo)為狀態(tài)號，列下標(biāo)用來表示終結(jié)符與非終結(jié)符的整數(shù)表示。數(shù)組元素可作如下約定：正整數(shù)：表示移進動作，如S6用數(shù)6表示；負(fù)整數(shù)：表示歸約動作，如R5用數(shù)-5表示；0：表示接受，通常為按產(chǎn)生式0歸約；狀態(tài)號也用整數(shù)表示；用不可能是狀態(tài)號的較大的整數(shù)表示錯誤轉(zhuǎn)移。請將上述LALR(1)分析表用這種表示方法，完成LR分析器的程序設(shè)計，并添加輸出狀態(tài)棧內(nèi)容的功能。用上述表達式文法G的一個句子作為輸入，進行測試。實現(xiàn)方法二：采用壓縮表示法動作Action表的每一行用一個數(shù)組表示，數(shù)組的第一個元素是本數(shù)組中存放的數(shù)偶個數(shù)，第二個元素到最后一個元素都以[終結(jié)符，動作]的數(shù)偶的形式存放。再用一個以狀態(tài)號為下標(biāo)的下標(biāo)數(shù)組，每個元素含一個指向數(shù)偶數(shù)組的指針。若數(shù)組元素的值為NULL，則表示從此狀態(tài)無轉(zhuǎn)移弧發(fā)出。若分析表有幾行相同，則只需保存一行，其它元素則都指向存放這一行表的數(shù)組即可。轉(zhuǎn)移Goto表也按同樣方式組織，只是這個行數(shù)組的數(shù)偶為[非終結(jié)符，下一狀態(tài)號]。每個行數(shù)組Yyan表示動作表Yy_action的一行，每個行數(shù)組Yygn表示轉(zhuǎn)移表Yy_goto的一行。假定上述表達式文法G中終結(jié)符及非終結(jié)符的整數(shù)值為：終結(jié)符：#ID+*()非終結(jié)符：SETF整數(shù)值：012345整數(shù)值：0123Yy_action數(shù)組是以狀態(tài)號為下標(biāo)的下標(biāo)數(shù)組，每個元素含有指向數(shù)組Yyan的指針；下標(biāo)數(shù)組Yy_goto的每個元素含有指向數(shù)組Yygn的指針。表達式文法G的LALR(1)分析表的具體壓縮表示如下：Yy_action.024,21,1Yya000.145,-63,-62,-60,-6Yya001.2.320,02,7Yya003.445,-22,-20,-23,8Yya004.545,-43,-42,-40,-4Yya005.625,92,7Yya006.7.8.945,-53,-52,-50,-5Yya009.1045,-12,-10,-13,8Yya010.1145,-35,-32,-30,-3Yya011Yyg000.033,52,41,3Yyg000NULL1.233,52,41,6Yyg002NULL3NULL4NULL5NULL6.723,52,10Yyg007.813,11Yyg008NULL9NULL10NULL11以上分析表用C語言程序描述如下：/**Yy_action表*/intYya000[]={2,4,2,1,1};intYya001[]={4,5,-6,3,-6,2,-6,0,-6};intYya003[]={2,0,0,2,7};intYya004[]={4,5,-2,2,-2,0,-2,3,8};intYya005[]={4,5,-4,3,-4,2,-4,0,-4};intYya006[]={2,5,9,2,7};intYya009[]={4,5,-53,-5,2,-5,0,-5};intYya010[]={4,5,-1,2,-1,0,-1,3,8};intYya011[]={4,5,-3,3,-3,2,-3,0,-3};intYy_action[]={Yya000,Yya001,Yya000,Yya003,Yya004,Yya005,Yya006,Yya000,Yya000,Yya009,Yya010,Yya011};/**Yy_goto表*/intYyg000[]={3,3,5,2,4,1,3};intYyg002[]={3,3,5,2,4,1,6};intYyg007[]={2,3,5,2,10};intYyg008[]={1,3,11};intYy_goto[]={Yyg000,NULL,Yyg002,NULL,NULL,NULL,NULL,Yyg007,Yyg008,NULL,NULL,NULL};/**為了進行歸約，使用一個Yy_lhs[]數(shù)組，其值為代表產(chǎn)生式左部符號的*整數(shù)，數(shù)組的下標(biāo)為產(chǎn)生式號*/intYy_lhs[7]={/*0*/0,/*1*/1,/*2*/1,/*3*/2,/*4*/2,/*5*/3,/*6*/3};/**Yy_reduce[]數(shù)組元素的值為產(chǎn)生式右部符號的個數(shù)，*以產(chǎn)生式號為數(shù)組的下標(biāo)索引*/intYy_reduce[]={/*0*/1,/*1*/3,/*2*/1,/*3*/3,/*4*/1,/*5*/3,/*6*/1};根據(jù)以上數(shù)組結(jié)構(gòu)，構(gòu)造函數(shù)Yy_next()，其功能是在給定狀態(tài)和輸入符號下，求出應(yīng)采取的動作或轉(zhuǎn)向的下一狀態(tài)。intYy_next(table,cur_state,symbol)int**table;/*要查的表*/intcur_state;/*行號*/intsymbol;/*列號*/{int*p=table[cur_state];inti;if(p)for(i=(int)*p++;--i>0;p+=2)if(symbol==p[0])return(p[1]);returnYYF;/*出錯指示*/};指針p指向Yyan數(shù)組或Yygn數(shù)組，由參數(shù)table的值而定。如果table指向Yy_action，則p指向Yyan數(shù)組；若table指向Yy_goto，則p指向Yygn數(shù)組據(jù)。根據(jù)上述LALR(1)分析表壓縮表示方法，完成LR分析器的程序設(shè)計，并添加輸出狀態(tài)棧內(nèi)容的功能。用上述表達式文法G的一個句子作為輸入，進行測試。4.程序源代碼和運行結(jié)果：#include<iostream>#include<string>#include<iomanip>usingnamespacestd;char*cp;/*指向給定的要分析的表達式語言*/inti=1;//從第一步開始執(zhí)行structsta_stack{intstas[50];inttop1;};//狀態(tài)棧的數(shù)據(jù)結(jié)構(gòu)sta_stackstack1;//定義一個狀態(tài)棧structstr_stack{stringstrs[50];inttop2;};//符號棧的數(shù)據(jù)結(jié)構(gòu)str_stackstack2;//定義一個符號棧/*終結(jié)符用相應(yīng)的整數(shù)代替*/stringsymbol1[6]={"#","ID","+","*","(",")"};/*非終結(jié)符也用相應(yīng)的整數(shù)代替*/stringsymbol2[4]={"S","E","T","F"};/*Yy_action表*/intYya000[]={2,4,2,1,1};intYya001[]={4,5,-6,3,-6,2,-6,0,-6};intYya003[]={2,0,0,2,7};intYya004[]={4,5,-2,2,-2,0,-2,3,8};intYya005[]={4,5,-4,3,-4,2,-4,0,-4};intYya006[]={2,5,9,2,7};intYya009[]={4,5,-5,3,-5,2,-5,0,-5};intYya010[]={4,5,-1,2,-1,0,-1,3,8};intYya011[]={4,5,-3,3,-3,2,-3,0,-3};int*Yy_action[]={ Yya000,Yya001,Yya000,Yya003,Yya004,Yya005, Yya006,Yya000,Yya000,Yya009,Yya010,Yya011};/*Yy_goto表*/intYyg000[]={3,3,5,2,4,1,3};intYyg002[]={3,3,5,2,4,1,6};intYyg007[]={2,3,5,2,10};intYyg008[]={1,3,11};int*Yy_goto[]={ Yyg000,NULL,Yyg002,NULL,NULL,NULL, NULL,Yyg007,Yyg008,NULL,NULL,NULL};/*為了進行歸約，使用一個Yy_lhs[]數(shù)組，其值為代表產(chǎn)生式左部符號的整數(shù)，數(shù)組的下標(biāo)為產(chǎn)生式號*/intYy_lhs[7]={0,1,1,2,2,3,3};/*Yy_reduce[]數(shù)組元素的值為產(chǎn)生式右部符號的個數(shù)，以產(chǎn)生式號為數(shù)組的下標(biāo)索引*/intYy_reduce[7]={1,3,1,3,1,3,1};/*根據(jù)以上數(shù)組結(jié)構(gòu)，構(gòu)造函數(shù)Yy_next()，其功能是在給定狀態(tài)和輸入符號下，求出應(yīng)采取的動作或轉(zhuǎn)向的下一狀態(tài)。*/intYy_next(int**table,intcur_state,intsymbol){ int*p=table[cur_state]; inti; if(p) for(i=(int)*p++;i-->0;p+=2) if(symbol==p[0]) return(p[1]); return8000;/*出錯指示*/}/*將相應(yīng)的狀態(tài)和符號進行壓棧*/voidpush(intsta,stringstr){stack1.top1++;stack1.stas[stack1.top1]=sta;stack2.top2++;stack2.strs[stack2.top2]=str;}/*從輸入流讀下一單詞到sym*/stringadvance(){stringsym;if(*cp=='I'&&*(cp+1)=='D'){sym="ID";/*cp=cp+2;*/}else{sym=*cp;/*cp=cp+1;*/}returnsym;}/*進行歸約動作*/intact(intYN){inttYN=-YN;returnYy_lhs[tYN];}/*彈棧*/voidpop(intn){stack1.top1-=n;stack2.top2-=n;}voidoutput()//輸出狀態(tài)棧、符號棧以及未分析輸入串{intsumstrlen=0,i6;intstasum=0,i7;cout<<setw(3)<<setiosflags(ios::right)<<i<<"";for(inti2=0;i2<=stack1.top1;i2++){cout<</*setw(8)<<setiosflags(ios::left)<<*/stack1.stas[i2];if(stack1.stas[i2]==10||stack1.stas[i2]==11)i7=2;elsei7=1;stasum=stasum+i7;}cout<<setw(12-stasum)<<setiosflags(ios::left)<<"";for(inti3=0;i3<=stack2.top2;i3++){cout<<stack2.strs[i3];if(stack2.strs[i3]=="ID")i6=2;elsei6=1;sumstrlen=sumstrlen+i6;} cout<<setw(12-sumstrlen)<<setiosflags(ios::left)<<"";//cout<<"";cout<<setw(8)<<setiosflags(ios::right)<<cp<<"";}intmain(){stack1.top1=stack2.top2=-1;charas[50];cp=as;intYN=0;cout<<"請輸入要分析的語句：";cin>>as;cout<<""<<"對輸入串"<<as<<"的分析過程如下"<<endl;cout<<"步驟"<<"狀態(tài)棧";cout<<"符號棧"<<"輸入串";cout<<"ACTION"<<"GOTO"<<endl;push(0,"#");output();stringsym;while(1){ sym=advance(); inti1=0; while(sym!=symbol1[i1]) i1++; YN=Yy_next(Yy_action,YN,i1); if(YN>0&&YN<8000) {cout<<""<<"S"<<YN<<""<<endl;//進行移進動作 push(YN,sym); i++; if(sym=="ID") cp+=2; elsecp+=