C語言語法分析器

鄭州輕工業(yè)學院編譯原理課程設計總結(jié)報告設計題目：詞法分析器（語法分析器）學生姓名：系別：專業(yè)：班級：學號：指導教師：20013年6月2日目錄設計題目………3運行環(huán)境（軟、硬件環(huán)境）……3算法設計的思想………………3算法流程圖……………………5算法設計分析…………………5六、源代碼…………6七、運行結(jié)果……………………11八、收獲及體會……………………12（一）設計題目詞法分析器（二）運行環(huán)境VisualC++.6.0(三)算法設計的思想源程序源程序詞法分析器Token串各種單詞符號對應的種別碼:單詞符號種別碼單詞符號種別碼begin1:17if2:=18then3<20while4<>21do5<=22end6>23letter(letter|digit)*10>=24digitdigit*11=25+13(26-14)27*15;28/16#0算法的基本任務是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據(jù)掃描到單詞符號的第一個字符的種類，拼出相應的單詞符號。主程序示意圖：主程序示意圖如下；其中初值包括如下兩個方面：關鍵字表的初值。關鍵字作為特殊標示符處理，把它們預先安排到一張表格中（稱為關鍵字表），當掃描程序識別出標識符時，查關鍵字表。如果能查到匹配的單詞，則該單詞為關鍵字，否則為一般的標識符。關鍵字表為一個字符串數(shù)組，其描述如下：Char*rwtab[6]={“begin”,”if”,”then”,”while”,”do”,”end”};置初值調(diào)用掃描子程序調(diào)用掃描子程序輸出單詞二元組輸出單詞二元組輸入串結(jié)束？否輸入串結(jié)束？是結(jié)束結(jié)束(2)程序需要用到的主要變量為syn,token和sum。2．掃描子程序的算法思想首先設置3個變量：（1）token用來存放構成單詞符號的字符串；（2）sum用來存放整型單詞（3）syn用來存放單詞符號的種別碼。main（四）算法的流程圖main變量初始化變量初始化忽略空格忽略空格結(jié)束文件結(jié)束否結(jié)束文件結(jié)束否否拼字符串 其它字符拼字符串對不同符號給出相應的syn值是否是關鍵字 數(shù)字對不同符號給出相應的syn值是否是關鍵字報錯拼數(shù)報錯拼數(shù)syn為對應單詞的種別碼syn=10syn=11syn為對應單詞的種別碼syn=10syn=11結(jié)束 結(jié)束（五）算法設計分析算法的基本任務是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據(jù)掃描到單詞符號的第一個字符的種類，拼出相應的單詞符號。其中初值包括如下兩個方面：（一）關鍵字表的初值。關鍵字作為特殊標示符處理，把它們預先安排到一張表格中（稱為關鍵字表），當掃描程序識別出標識符時，查關鍵字表。如果能查到匹配的單詞，則該單詞為關鍵字，否則為一般的標識符。關鍵字表為一個字符串數(shù)組，其描述如下：Char*rwtab[6]={“begin”,”if”,”then”,”while”,”do”,”end”};(2)程序需要用到的主要變量為syn,token和sum。2．掃描子程序的算法思想首先設置3個變量：（1）token用來存放構成單詞符號的字符串；（2）sum用來存放整型單詞（3）syn用來存放單詞符號的種別碼。（六）源代碼#include<stdio.h>#include<iostream.h>#include<string.h>#defineMAX150//詞法分析表的最大容量#defineMAXBUF255//緩沖區(qū)的最大緩沖量charprog[MAXBUF],token[MAX];charch;intsyn,p,m,n,sum;char*rwtab[6]={"begin","if","then","while","do","end"};/////////////////////////////////////////////////詞法分析程序///////////////////////////////////////////////voidscaner(){ for(m=0;m<MAX;m++) token[m]=NULL; m=0;sum=0; ch=prog[p++]; while(ch=='') ch=prog[p++];//讀取下一個字符; if(ch>=65&&ch<=122/*是字母字符*/) { while(ch>=65&&ch<=122||ch>=48&&ch<=57)/*為字母字符或數(shù)字字符*/ { token[m++]=ch; ch=prog[p++];//讀取下一個字符； } token[m++]='\0'; p=p-1; syn=10; for(n=0;n<6;n++) if(strcmp(token,rwtab[n])==0) { syn=n+1;//給出syn值; break; } } elseif(ch>=48&&ch<=57/*ch為數(shù)字字符*/) { while(ch>=48&&ch<=57/*ch為數(shù)字字符*/) { sum=sum*10+ch-'0'; ch=prog[p++];//讀取下一個字符； } p=p-1;//回退一個字符； syn=11; } elseswitch(ch) {case'<':m=0;token[m++]=ch; ch=prog[p++];//讀取下一個字符； if(ch=='>') { syn=21; token[m++]=ch; } elseif(ch=='=') { syn=22; token[m++]=ch; } else { syn=20; p=p-1;//回退一個字符； } break; case'>':token[m++]=ch;; ch=prog[p++];//讀取下一個字符； if(ch=='=') { syn=24;//將>=的中別碼=>syn; token[m++]=ch;; } else { syn=23; p=p-1;//回退一個字符； } break; case':':token[m++]=ch;; ch=prog[p++];//讀取下一個字符； if(ch=='=') { syn=18; token[m++]=ch;; } else { syn=17; p=p-1;//回退一個字符； } break; case'+':syn=13;token[0]=ch; break; case'-':syn=14;token[0]=ch; break; case'*':syn=15;token[0]=ch; break; case'/':syn=16;token[0]=ch; break; case'=':syn=25;token[0]=ch; break; case';':syn=26;token[0]=ch; break; case'(':syn=27;token[0]=ch; break; case')':syn=28;token[0]=ch; break; case'#':syn=0;token[0]=ch; break; default:syn=-1; break; }}/////////////////////////////////////////////主函數(shù)///////////////////////////////////////////voidmain(){ charA; cout<<"*****************************************"<<endl; loop: p=0; cout<<"*****************************************"<<endl;printf("pleaseinputstring(以#結(jié)束):\n"); do { scanf("%c",&ch); prog[p++]=ch;//輸入源程序字符串，送到緩沖區(qū)prog[p++]中； } while(ch!='#'); p=0; do { scaner(); switch(syn) { case11:cout<<"("<<syn<<","<<sum<<")"<<endl;//輸出（數(shù)的二元組）； break; case-1:cout<<"error"<<endl; break; default:cout<<"("<<syn<<","<<token<<")"<<endl;//輸出(其他單詞二元組); } }while(syn!=0); cout<<"*****************************************"<<endl; cout<<"請確定是否繼續(xù)使用程序:S為繼續(xù)；其它為退出；"<<endl; cout<<"是否繼續(xù):"; cin>>A; switch(A) { case'S':gotoloop; default:cout<<"*****************************************"<<endl; cout<<"Thankyou!ByeBye!"<<endl; cout<<"*****************************************"<<endl; break; }}（七）運行結(jié)果分析（八）收獲及體會為期一周的編譯原理課程設計結(jié)束了，我們這次的任務是做一個編譯器。這次課程設計我做的是用C++編寫詞法分析器，編譯程序是在單詞的級別上來分析和翻譯源程序的，因此詞法分析是編譯的基礎。通過此次實驗，我基本上了解了詞法分析器的工作原理和功能以及實現(xiàn)方法。進一步學習了C語言的知識。此次實驗，遇到的最大的一個問題就是用了C++語言里的cin輸入字符串，結(jié)果空格符號直接給預處理掉了，導致開始的關鍵字與字母連接時會不識別，最后通過查閱，終于找到了這個問題的所在，最后通過C語言里的Scanf函數(shù)來輸入，就解決了這個問題?？偠灾境绦?qū)崿F(xiàn)了所要求的全部功能。美中不足的是程序中沒有運用文件，對文件的掌握不是很到位，相信經(jīng)過以后的程序訓練，會熟練的運用文件來編程。目錄一、設計題目………14二、運行環(huán)境（軟、硬件環(huán)境）…………………14三、算法設計的思想………………14四、算法流程圖……………………15五、算法設計分析…………………16六、源代碼…………17七、運行結(jié)果……………………26八、收獲及體會……………………27（一）設計題目語法分析器（二）運行環(huán)境VisualC++.6.0(三)算法設計的思想利用C語言編制遞歸下降分析程序，并對簡單語言進行語法分析。待分析的簡單語言得語法：EE+T|E-T|TTT*F|T/F|F

F(E)|i輸入單詞串，以“#”結(jié)束，如果是文法正確的句子，則輸出成功信息，打印“Accept!RightExpression!”，否則輸出“Error!!!”。（四）算法的流程圖（五）算法設計分析語法分析：a)∵E=>E+T=>E+T*F=>E+T*(E)即有E=>E+T*(E)存在左遞歸。用直接改寫法消除左遞歸，得到如下：ETE’E’+TE’|?TE’|εTFT’T’*FT’|/FT’|εF(E)|ib)對于以上改進的方法?？傻茫簩τ贓’:

FIRST(E’)=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，?，ε}對于T’: FIRST(T’)=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε}而且： FIRST(E)=FIRST(T)=FIRST(F)=FIRST((E))∪FIRST(i)={(，i}由此我們?nèi)菀椎贸龈鞣墙K結(jié)符的FOLLOW集合如下：FOLLOW(E)={)，#}FOLLOW(E’)=FOLLOW(E)={)，#}FOLLOW(T)=FIRST(E’)\ε∪FOLLOW(E’)={+，?，)，#}FOLLOW(T’)=FOLLOW(T)={+，?，)，#}FOLLOW(F)=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，?，)，#}由以上FOLLOW集可以我們可以得出SELECT集如下：對E SELECT（ETE’）=FIRST(TE’)=FIRST(T)={(，i}對E’ SELECT（E’+TE’）={+}

SELECT（E’?TE’）={?}

SELECT（E’ε）={ε，)，#}對T SELECT（TFT’）={(，i}對T’ SELECT（T’*FT’）={*}SELECT（T’∕FT’）={∕}SELECT（T’ε）={ε，+，?，)，#}對F SELECT（F(E)）={(}SELECT（Fi）={i}∴ SELECT(E’+TE’)∩SELECT（E’?TE’）∩SELECT（E’ε）=SELECT(T’*FT’)∩SELECT（T’∕FT’）∩SELECT（T’ε）=SELECT（F(E)）∩SELECT（Fi）=由上可知，有相同左部產(chǎn)生式的SELECT集合的交集為空，所以文法是LL（1）文法。因此，轉(zhuǎn)化后的文法可以用遞歸下降分析法作語法分析。（六）源代碼#include<stdio.h>#include<dos.h>#include<stdlib.h>#include<string.h>chara[50],b[50],d[200],e[10];charch;intn1,i1=0,flag=1,n=5;inttotal=0;intE();intE1();intT();intG();intS();intF();voidinput();voidinput1();voidoutput();voidmain()/*遞歸分析*/{intf,p,j=0;charx;d[0]='E';d[1]='=';d[2]='>';d[3]='T';d[4]='G';d[5]='#';printf("Pleaseinputcharacterstring(length<50,endof'#'):\n");do{scanf("%c",&ch);a[j]=ch;j++;}while(ch!='#');n1=j;ch=b[0]=a[0];printf("步驟\t文法\t分析串\t\t分析字符\t剩余串\n");f=E1();if(f==0)return;if(ch=='#'){printf("\nAccept!RightExpression!\n\n");p=0;x=d[p];while(x!='#'){printf("%c",x);p=p+1;x=d[p];/*輸出推導式*/}}else{printf("\nError!!!\n");printf("回車返回\n");getchar();getchar();return;}printf("\n");printf("回車返回\n");getchar();getchar();}intE1(){intf,t;printf("%d\tE-->TG\t",total);total++;flag=1;input();input1();f=T();if(f==0)return(0);t=G();if(t==0)return(0);elsereturn(1);}intE(){intf,t;printf("%d\tE-->TG\t",total);total++;e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5]='#';output();flag=1;input();input1();f=T();if(f==0)return(0);t=G();if(t==0)return(0);elsereturn(1);intT(){intf,t;printf("%d\tT-->FS\t",total);total++;e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#';output();flag=1;input();input1();f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}intG(){intf;if(ch=='+'){b[i1]=ch;printf("%d\tG-->+TG\t",total);total++;e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=T();if(f==0)return(0);G();return(1);}printf("%d\tG-->^\t",total);total++;e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';output();flag=1;input();input1();return(1);}intS(){intf,t;if(ch=='*'){b[i1]=ch;printf("%d\tS-->*FS\t",total);total++;e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}printf("%d\tS-->^\t",total);total++;e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#';output();flag=1;a[i1]=ch;input();input1();return(1);}intF(){intf;if(ch=='('){b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=E();if(f==0)return(0);if(ch==')'){b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;flag=0;input();input1();ch=a[++i1];}else{printf("\nError!!!\n");return(0);}}elseif(ch=='i'){b[i1]=ch;printf("%d\tF-->i\t",total);total++;e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';output();flag=0;input();input1();ch=a[++i1];}else{printf("\nError!!!\n");return(0);}return(1);}voidinput(){intj=0;