语法分析报告

《编译原理》课程实验报告2009年5月题目语法分析专业班级学号姓名申请成绩指导教师实验2：语法分析一、实验目的1．巩固对语法分析的基本功能和原理的认识。2．通过对语法分析表的自动生成加深语法分析表的认识。3．理解并处理语法分析中的异常和错误。二、实验内容要求：对如下工作进行展开描述(1)掌握语法分析程序的总体框架，并将其实现。通过相应的文法构造LL(1)预测分析表，输入词法分析的token序列和符号表，逐一读入符号判断相应的产生式并输出。此处要用到栈结构，将判断出的产生式先进行压栈操作，再循环读入下一符号进行相同操作，直到栈和符号表同时为空时程序结束。(2)在手工构造的文法的基础上实现LL(1)(算符优先文法，LR(1))分析，给出其语法分析表的生成程序(对应不同的语法分析方法产生不同的分析表)及其数据结构和查找算法。LL(1)文法分析表的生成程序：classDataTable{public:staticconstintALIGN_LEFT,ALIGN_RIGHT,ALIGN_CENTER,WITH_TITLE;DataTable(){init();}voidaddRow(constchar*str){if(hasRow(str))return;StringData_tmp=newstringData();_tmp-data=newchar[strlen(str)+1];sprintf(_tmp-data,str);_tmp-rowLast=rowTail;_tmp-rowNext=rowTail-rowNext;rowTail-rowNext=_tmp;rowTail=rowTail-rowNext;_tmp=rowTail;for(inti=0;icolSize;i++){_tmp-colNext=newstringData();_tmp-colNext-rowLast=_tmp-rowLast-colNext;_tmp-colNext-rowNext=_tmp-rowLast-colNext-rowNext;_tmp-colNext-rowNext-rowLast=_tmp-colNext;_tmp-rowLast-colNext-rowNext=_tmp-colNext;_tmp-colNext-colNext=rowTail;rowTail-colLast=_tmp-colNext;_tmp-colNext-colLast=_tmp;_tmp=_tmp-colNext;}rowSize++;}voidaddCol(charac){char*tmp=newchar[2];tmp[0]=ac;tmp[1]='\0';addCol(tmp);}voidaddRow(charac){char*tmp=newchar[2];tmp[0]=ac;tmp[1]='\0';addRow(tmp);}voidaddCol(constchar*str){if(hasCol(str))return;StringData_tmp=newstringData();_tmp-data=newchar[strlen(str)+1];sprintf(_tmp-data,str);_tmp-colLast=colTail;_tmp-colNext=colTail-colNext;colTail-colNext=_tmp;colTail=colTail-colNext;_tmp=colTail;for(inti=0;irowSize;i++){_tmp-rowNext=newstringData();_tmp-rowNext-colLast=_tmp-colLast-rowNext;_tmp-rowNext-colNext=_tmp-colLast-rowNext-colNext;_tmp-rowNext-colNext-colLast=_tmp-rowNext;_tmp-colLast-rowNext-colNext=_tmp-rowNext;_tmp-rowNext-rowNext=colTail;colTail-rowLast=_tmp-rowNext;_tmp-rowNext-rowLast=_tmp;_tmp=_tmp-rowNext;}colSize++;}数据结构：typedefstructelem{elem(){data=NULL;next=NULL;width=NULL;col=0;align=0;}intalign;char*data;elem*next;intStack*width;intcol;}*Elem;typedefstructsn{sn(){data=first=NULL;next=NULL;}char*data,*first;sn*next;}*Snake;typedefstructsten{sten(){first=follow=NULL;next=NULL;result=NULL;firstVt=;lastVt=;}charword;CStringfirstVt,lastVt;char*first,*follow;Snakeresult;sten*next;}*Sten;typedefstructintStack{intStack(){value=0;next=NULL;last=NULL;}intStack*next,*last;intvalue;}*IntStack;typedefstructelem{elem(){data=NULL;next=NULL;width=NULL;col=0;align=0;}intalign;char*data;elem*next;intStack*width;intcol;}*Elem;typedefstructmlink{mlink(){link=NULL;next=NULL;row=0;length=0;}introw,length;elem*link;mlink*next;}*Mlink;查找：voidgetFollow(){CStringstr=,_tmp;Stenp=head;head-follow=newchar[2];head-follow[0]='#';head-follow[1]='\0';boolincrease=true;while(increase){p=head;increase=false;while(p!=NULL){Snaketp=p-result;while(tp!=NULL){CString_shr=tp-data;for(inti=1;i_shr.GetLength();i++){if(IsNsign(_shr[i])){CString_fol=__getFollow(_shr[i]);if(i_shr.GetLength()-1){_tmp=__getFirst(_shr.Right(_shr.GetLength()-i-1));if(_tmp.Find(OMG)!=-1){_tmp.Delete(_tmp.Find(OMG));if(__delSame(_fol,__getFollow(p-word)))increase=true;}if(__delSame(_fol,_tmp))increase=true;}else{if(__delSame(_fol,__getFollow(p-word)))increase=true;}setFollow(_shr[i],_fol);}}tp=tp-next;}p=p-next;}}}CStringgetFirst(charac){Stenp=getPos(ac);if(p!=NULL){returnp-first;}return;}p=head;while(p!=NULL){Snaketp=p-result;while(tp!=NULL){if((tp-data[0]=BEGIN&&tp-data[0]=END)||(tp-data[0]64&&tp-data[0]91)){delete[]tp-first;str=;CString_shr=tp-data;CString_tmp=getFirst(_shr[0]);while(_tmp.Find(OMG)!=-1){_tmp.Delete(_tmp.Find(OMG));__delSame(str,_tmp);_shr.Delete(0);if(_shr.GetLength()==0)break;if(!IsNsign(_shr[0])){__delSame(str,CString(_shr[0]));break;}_tmp=getFirst(_shr[0]);}if(_shr.GetLength()!=0){if(IsNsign(_shr[0]))__delSame(str,_tmp);}else__delSame(str,CString(OMG));tp-first=newchar[str.GetLength()+1];sprintf(tp-first,str);}else{delete[]tp-first;tp-first=newchar[2];tp-first[0]=tp-data[0];tp-first[1]='\0';}tp=tp-next;}p=p-next;}}for(inti=0;ip-length;i++){_tmp=_sk-value+(_sk-value%2==0?0:1);_tmp/=2;for(intj=0;j_tmp;j++){putchar(mat[0][2]);putchar(mat[0][3]);}if(i==p-length-1){if(p-next-length==p-length&&p-row!=row){putchar(mat[1][6]);putchar(mat[1][7]);}elseif(p-next-lengthp-length||p==tail){putchar(mat[3][6]);putchar(mat[3][7]);}elseif(p-next-lengthp-length){putchar(mat[1][4]);putchar(mat[1][5]);IntStack_sk1=_sk;for(intk=i+1;kp-next-length;k++){_sk1=_sk1-next;int_tit=_sk1-value+(_sk1-value%2==0?0:1);_tit/=2;for(_tmp=0;_tmp_tit;_tmp++){putchar(mat[0][2]);putchar(mat[0][3]);}if(k==p-next-length-1){putchar(mat[0][6]);putchar(mat[0][7]);}else{putchar(mat[0][4]);putchar(mat[0][5]);}}}}elseif(i=p-next-length||p==tail){putchar(mat[3][4]);putchar(mat[3][5]);}elseif(p-row==row||p-next-length==0){putchar(mat[3][4]);putchar(mat[3][5]);}else{putchar(mat[1][4]);putchar(mat[1][5]);}_sk=_sk-next;}Mlink_ww=p;while(_ww!=tail-next){if(_ww-next-length!=0){_ww=_ww-next;break;}putchar(10);_w