東北大學(xué)編譯原理實驗報告二

...wd......wd......wd...編譯原理程序設(shè)計實驗報告——表達(dá)式語法分析器的設(shè)計與實現(xiàn)實驗?zāi)繕?biāo)：用兩種不同的方法設(shè)計一個表達(dá)式的語法分析器實驗內(nèi)容：①LL(1)分析法 LL〔1〕文法是一種自上而下的語法分析方法，它是從文法的識別符號出發(fā)，生成句子的最左推導(dǎo)，從左到右掃描源程序，每次向前查看1個字符，便能確定當(dāng)前應(yīng)該選擇的產(chǎn)生式。LL〔1〕分析需要用到一個分析表M和一個符號棧S，分析表M是一個矩陣，它的元素可以存放一個非終結(jié)符的產(chǎn)生式，說明當(dāng)符號棧S的棧頂元素非終結(jié)符遇到當(dāng)前輸入字符時，所應(yīng)選擇的產(chǎn)生式；M的元素還可以是存放一個出錯標(biāo)志，說明符號棧S的棧頂元素非終結(jié)符不應(yīng)該遇到當(dāng)前輸入字符〔終結(jié)符〕。重復(fù)調(diào)用LL〔1〕分析方法對每一個輸入字符進(jìn)展分析，直到輸入棧為空為止。②遞歸下降子程序遞歸下降分析法，在判斷一個表達(dá)式時首先進(jìn)入E然后調(diào)用T在調(diào)用F，判斷是否為“〔〞或字符或常數(shù)，如果不是報錯，是“〔〞的話再進(jìn)入E，是字符或常數(shù)的話跳出遞歸。然后進(jìn)入T中下一步，判斷是否為“*〞，是的話進(jìn)入T子遞歸，不是的話跳出，進(jìn)入E的下一步判斷是否為“+〞，是的話進(jìn)入E的子遞歸，不是的話跳出回到主程序。當(dāng)ch標(biāo)識符為#時完畢。源程序代碼：〔參加注釋〕LL(1)分析算法：#include<iostream>#include<malloc.h>usingnamespacestd;#defineSTACKSIZE50#defineSTACKINCREMENT10#defineOK1#defineerror0#defineoverflow-1typedefcharSElemType;typedefintStatus;typedefstruct{SElemType*base;SElemType*top;Intstacksize;}SqStack;StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACKSIZE*sizeof(SElemType));if(!S.base)exit(overflow);S.top=S.base;S.stacksize=STACKSIZE;returnOK;}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(overflow);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}(S.top)++;*(S.top)=e;returnOK;}StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnerror;e=*(S.top);S.top--;returnOK;}StatusGrammerAnalysis(SqStack&S,char*ch,charc){SElemTypee;Push(S,'#');Push(S,'E');while(!((*(S.top)=='#')&&(c=='#'))){Pop(S,e); if((e=='E')&&(((c>='0')&&(c<='9'))||(c>='a'&&c<='z')||(c=='('))){Push(S,'A');Push(S,'T');}elseif((e=='A')&&(c=='+')){Push(S,'A');Push(S,'T');ch++;c=*ch;}elseif((e=='A')&&((c==')')||(c=='#')));elseif((e=='T')&&(((c>='0')&&(c<='9'))||(c>='a'&&c<='z')||(c=='(')))Push(S,'B');Push(S,'F');}elseif((e=='B')&&(c=='*')){Push(S,'B');Push(S,'F');ch++;c=*ch;} elseif((e=='B')&&((c=='+')||(c==')')||(c=='#')));elseif((e=='F')&&((c>='0'&&c<='9')||(c>='a'&&c<='z'))){ch++;while(((c=*ch)>='0')&&(c<='9')||(c>='a'&&c<='z'))ch++;}elseif((e=='F')&&(c=='(')){Push(S,')');Push(S,'E');ch++;c=*ch;}elseif((e==')')&&(c==')')){ch++;c=*ch;}elsereturnerror;}returnOK;}intmain(){charstr[50];charc;system("color0B");SqStackS;InitStack(S);printf("|-------------------------------------------------|\n");printf("|請輸入表達(dá)式，以#鍵完畢:|\n");printf("|-------------------------------------------------|\n");scanf("%s",str);c=*str;if(GrammerAnalysis(S,str,c)){printf("語法分析通過\n");printf("表達(dá)式正確\n");}else{printf("語法分析未通過\n");printf("表達(dá)式錯誤\n");}main();return0;}遞歸下降#include<iostream>usingnamespacestd;inta=1;charch;inti=0;charstr[80];voidT(void);voidF(void);voidE(void);voidError(void);voidError()//出錯函數(shù){cout<<"語法錯誤"<<endl;}voidT(void)//子程序T{F();//進(jìn)入子程序Fif(ch=='*'){i++;ch=str[i];T();}//遞歸子程序T}voidF(void)//子程序F{if(ch=='('){i++;ch=str[i];E();//回到子程序Eif(ch==')'){i++;ch=str[i];}else{Error();a=0;}}elseif((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')){i++;ch=str[i];}else{Error();a=0;}}voidE(void){//子程序ET();if(ch=='+'){i++;ch=str[i];E();//遞歸子程序E}}intmain()//主函數(shù){system("color0B");cout<<"|-------------------------------------------------|"<<endl;cout<<"|輸入表達(dá)式以#號完畢|"<<endl;cout<<"|-------------------------------------------------|"<<endl;cin>>str;ch=str[0];while(ch!='#'){E();if(!a)break;}if((ch=='#')&&(a!=0))//遇#且a