算符優(yōu)先詞法分析器_編譯原理完整課程設計

1、算符優(yōu)先詞法分析器目錄一、設計目的1二、設計原理 1三、設計思想 2四、設計要求 3五、設計流程圖及程序 4六、運行結果及分析 14七、設計總結16八、參考文獻 16算符優(yōu)先詞法分析器一、設計目的算符優(yōu)先算法是自底而上分析方法的一種。所謂自底向上分析，也稱移進規(guī) 約分析，粗略地說他的實現(xiàn)思想是對輸入符號串自左向右進行掃描，并將輸入符逐 個移入一個后進先出的棧中，邊移進邊分析，一旦棧頂符號串形成某個句型的句柄 或可規(guī)約串是，就用該產(chǎn)生式的左部非終結符代替相應右部的文法符號串，這稱為 一部規(guī)約。重復這一過程直到規(guī)約到棧中只剩文法的開始符號是則為分析成功，也 就確認輸入串是文法的句子。而算符優(yōu)先分析

2、的基本思想是只規(guī)定算符之間的優(yōu)先 關系，也就是只考慮終結符之間的優(yōu)先關系。本課程設計的主要目的：1、通過本次課程設計，全面系統(tǒng)的了解編譯原理程序構造的一般原理和基本實 現(xiàn)方法，尤其是對自底向上的優(yōu)先分析方法的認識和理解；2、提高對編譯程序工作基本過程及其各階段基本任務的分析技能；3、加強對編譯程序的生成過程、構造工具及編譯程序總流程框圖的理解，鞏固 所學的課本知識。二、設計原理算符優(yōu)先分析法是一種有效的自底向上的分析方法。自底向上分析方法面臨的 主要問題是如何確定可歸約串，而算符優(yōu)先分析法根據(jù)兩個終結符號之間的優(yōu)先關 系比較，成功的解決了可歸約串的問題。算符優(yōu)先分析法是采用最左素短語進行歸 約

3、的，嚴格來講不屬于規(guī)范規(guī)約的范疇。因此，在設計以前我們必須要知道什么是素短語和最左素短語。所謂素短語就 是指句型中具有這樣性質(zhì)的短語：至少含有一個終結符，且除了自身之外，不再含 有任何更小的素短語的短語。最左素短語，是指在句型的所有素短語中，處于句型 最左邊的素短語。了解了素短語和最左素短語，那么如何構造這種算法呢？首先，根據(jù)非終結符 的FIRSTVT集和LASTVT集找出它們之間的優(yōu)先關系，構造算符優(yōu)先矩陣。然后，由 此矩陣構造相應符號串的算符優(yōu)先分析表并編寫程序。三、設計思想 在算符優(yōu)先算法中，存在定理：一個算符優(yōu)先文法G的任何句型# n i ai N2 a?M an e #（a VT,N

4、j V,i=1,2,，n, n+1,N j 可有可無）的最左素短語是滿足下列條件的最左子串：N j aj Nj+1 aj+ 1 Ni ai Ni+1其中， aj- 1 < ajaj = a j+ 1, ,ai- 1 = aiai > ai+ 1 由該定理可以看出，在算符優(yōu)先文法的句型中，任何素短語中最相近的兩個終 結符的優(yōu)先級相等，且素短語中位于最前面的終結符的優(yōu)先級高于在句型中緊臨其 前的終結符的優(yōu)先級，而素短語中處于最后面的終結符的優(yōu)先級高于在句型中緊隨 其后的終結符的優(yōu)先級。設有算符優(yōu)先文法 GS= （VN, VT, P, S ），則得出如下步驟：1 、根據(jù)GS文法構造優(yōu)先關

5、系矩陣；2、設置一個符號棧S,存放已經(jīng)歸約的或待形成最左素短語的符號串，另設一 個工作單元R,存放當前的待輸入符號；3、采用移進歸約的方法，當符號棧 S的棧頂形成可歸約串一一最左素短語時， 進行歸約。具體方法如下： 分析開始時，符號棧S中只有一個符號“ #”，工作單元R中存放輸入串的第 一個終結符； 查優(yōu)先關系矩陣，比較符號棧中最靠棧頂?shù)慕K結符號 （假設為a）與工作單元 R中的終結符（假設為b）的優(yōu)先關系；i）若a,b之間無優(yōu)先關系，則出錯并退出分析程序；ii）若a<b或a=b,則將b進棧，掃描指針后移，工作單元 R中存放下一待 輸入的終結符，重復；iii）若a>b,則表明此時棧頂

6、已經(jīng)形成最左素短語，轉； 從符號棧中最靠棧頂?shù)慕K結符 Xn開始，依次向前（向棧底方向）與最近的終結符比較,若X-1=X,則繼續(xù)比較Xn-2和X-1如此反復，直至Xi-1 < Xi （i=1,2,n,設 Xo = #）為止，于是最左素短語的左界也確定，此時最左素短語為從N開始（N為在X之前緊臨X的非終結符，若為“空”，則從X開始）一直到棧頂?shù)姆柎篘i Xi Ni+1 Xi+1 Nn Xn Nn+1 在文法GS的產(chǎn)生式中，選擇其右部具有 N X N+1 Xn+1Nn Xn Nn+1形式的規(guī) 則進行規(guī)約（注意：此時非終結符號不必完全相同） ：彈出符號棧棧頂?shù)淖钭笏囟陶Z， 相應規(guī)則的左部非終

7、結符進棧。若此時分析棧中只有 #和文法的一個非終結符，且待 分析符號串只剩下# （即工作單元R中符號為#），則表明分析成功，所分析的輸入串（源程序）是文法GS的句子，退出分析程序；否則，重復。有了以上的思路， 我們首先對已經(jīng)給定的文法按其產(chǎn)生式構造算符優(yōu)先關系表， 有了算符優(yōu)先關系表并滿足算符優(yōu)先文法時，我們就可以對任意給定的符號串進行 歸約分析，形成句柄時就歸約，最后判定輸入串是否為該文法的句子。在分析過程 中可以設置一個符號棧S,用以寄存歸約或待形成最左素短語的符號串，用一個工作 單元a存放當前讀入的終結符號，歸約成功的標志是當讀到句子結束時，S棧中只剩 #N，即只剩句子最左括號 #

8、9;和一非終結符N。四、設計要求使用算符優(yōu)先分析算法分析下面的文法：E ' #E#E E+T | TT T*F | FF PAF | PP （E） | i- 4 -算符優(yōu)先詞法分析器其中i可以看作是一個終結符，無需作詞法分析。具體要求如下：1、如果輸入符號串為正確句子，顯示分析步驟，包括分析棧中的內(nèi)容、優(yōu)先關系、輸入符號串的變化情況；2、如果輸入符號串不是正確句子，則顯示出錯。五、設計流程圖及程序1、分析文法為：(O)E'#E#(1)EE+TETTT*FTFFPAFFPP(E)(8)Pi根據(jù)算符優(yōu)先文法的分析規(guī)則求得終結符優(yōu)先矩陣+*Ai()#+><<<

9、<>>*>><<<>>A>><<<>>i>>>>>(<<<<<=)>>>>>#<<<<<=圖1算符優(yōu)先算法流程圖-7 -算符優(yōu)先詞法分析器3、程序：#include<stdlib.h> #include<stdio.h> #include<dos.h> #include<stdio.h> #include<string.h

10、> #include<ctype.h> #include<iostream.h> #define SIZE 128char youxian77;/算符優(yōu)先關系數(shù)組char lexbufSIZE;/存放輸入的要進行分析的句子char lexSIZE;/存放剩余串char fenxizhanSIZE;/void fenxi();int panduanyou(char x); void shengyuchuan();int k;void zengjia();void main() / 將算符優(yōu)先關系存放在算符優(yōu)先關系數(shù)組里youxian00='>'

11、youxian01='<'youxian02='<'youxian03='<'youxian04='<'youxian05='>'youxian06='>'/youxian10='>'youxian11='>'youxian12='<'youxian13='<'youxian14='<'youxian15='>'youxian16=&

12、#39;>'/youxian20='>'youxian21='>'youxian22='<'youxian23='<'youxian24='<'youxian25='>'youxian26='>'/youxian30='>'youxian31='>'youxian32='>'youxian33='$'/ 無優(yōu)先關系的用 $表示youxian34=&

13、#39;$'youxian35='>'youxian36='>'/youxian40='<'youxian41='<'youxian42='<'- 9 -算符優(yōu)先詞法分析器youxian43='<'youxian44='<'youxian45='='youxian46='$'/youxian50='>'youxian51='>'youxian52='&

14、gt;'youxian53='$'youxian54='$'youxian55='>'youxian56='>' / youxian60='<'youxian61='<'youxian62='<'youxian63='<'youxian64='<'youxian65='$'youxian66='=' /n");printf（" 將要進行算符優(yōu)先分析，請

15、做好準備printf("f*n");printf（" 請輸入要進行分析的句子 n"）;cin.get(lexbuf,SIZE); /將輸入的字符串存到數(shù)組- 10 -算符優(yōu)先詞法分析器printf(" 步驟 棧 優(yōu)先關系 當前符號 剩余輸入串 移進或歸約 n"); k=0; fenxizhank='#'fenxizhank+1='0'int lenth,i1; / 初始化 剩余串數(shù)組為輸入串 lenth=strlen(lexbuf);for(i1=0;i1<lenth;i1+) lexi1=lex

16、bufi1;lexi1='0'fenxi();void fenxi()int i,j,f,z,z1,n,n1,z4,n4;int flag=0;/ 操作的步驟數(shù) char a; / 存放正在分析的字符 char p6,Q,p1,p4;f=strlen(lexbuf); / 測出數(shù)組的長度 for(i=0;i<f;i+)a=lexbufi;if(fen xizha n k='+'|fe nxizha n k='*'|fe nxizha nk='A'|fe nxiz hank='i'|fenxizhank=

17、9;('|fenxizhank=')'|fenxizhank='#') j=k;elsej=k-1;z=panduanyou(fenxizhanj);/ 從優(yōu)先關系表中查出 sj 和 a 的優(yōu)先關系if(a='+'|a='*'|a='A'|a='i'|a='('|a=')'|a=#)- 11 -算符優(yōu)先詞法分析器n=panduanyou(a);else / 如果句子含有不是終結符集合里的其它字符，不合法printf("error! 不合法的句子 &q

18、uot;);break;p6=youxianzn;if(p6='>')loop: Q=fenxizhanj;if(fen xizha nj-1='+'|fe nxizha nj-1='*'|fe nxizha nj-1=s' |fenxizhanj-1='i'|fenxizhanj-1='('|fenxizhanj-1=')'|fenx izhanj-1='#')j=j-1;elsej=j-2;z1=panduanyou(fenxizhanj);n1=panduanyo

19、u(Q);p1=youxianz1n1;if(p1='v')/fenxizhanj+1fenxizhank 歸約為 Nk=j+1;shengyuchuan();flag+;%cprintf("(%d)%s%c%s歸約 n",flag,fenxizhan,p6,a,lex);if(fenxizhank='i') fenxizhank='P'i-;- 12 -算符優(yōu)先詞法分析器else if(fenxizhank+1='*') fenxizhank='T'else if(fenxizhank+1=&

20、#39;+') fenxizhank='E'int hou,hou1;hou=strlen(fenxizhan);for(hou1=k+1;hou1<hou;hou1+)fenxizhanhou1='0' / 多個字符歸約，把棧頂后面的舍棄 zengjia(); / 歸約剩余串沒變化elsegoto loop;elseif(p6='<') / 移進有一個問題就是如果上一步是不歸約，剩余的字符 串減少一個shengyuchuan();lexbuff='0'flag=flag+1;printf("(%d)

21、 %s %c %c%s 移進 n",flag,fenxizhan,p6,a,lex);k=k+1;fenxizhank=a;elseif(p6='=')z4=panduanyou(fenxizhanj);n4=panduanyou('#');p4=youxianz4n4;if(p4='=')shengyuchuan();flag+;%c%cprintf("(%d) %s %s 接受 n",flag,fenxizhan,p6,a,lex); printf(" 合法的句子 "); break;else

22、k=k+1;fenxizhank=a;elseprintf(" 出錯 "); break;int panduanyou(char x) int m;if(x='+')m=0;if(x='*')m=1;if(x=s')m=2;if(x='i')m=3;if(x='(')m=4;if(x=')')m=5;if(x='#')m=6;return m;void shengyuchuan()int i4,i5;i4=strlen(lex);for(i5=0;i5<i4;i5+

23、) lexi5=lexi5+1;lexi4-1='0'- 15 -算符優(yōu)先詞法分析器void zen gjia()int h1,h2;h仁strle n(lex);for(h2=0;h2<h1;h2+)Iexh1-h2=lexh1-h2-1;lex0='$'/存入一字符個特殊六、運行結果及分析1 、對輸入串進行舉例，并得出如下運行結果：<1>俞入串為i+i*i#，運行結果為""C - Wseir eyiuLDeskt oplDebug123_ eare*現(xiàn)在就要迸訂專符優(yōu)先分析*請做奸準番NX MiKMiWKiaaiEKiW

24、MiiMaiEiOEKlgMi HitK :MKJf>t：WiMK：MM：>OtME>E>EiWMi MEJtaM請輸入要進行分析的句子i+i*iu步疆 棧優(yōu)先壬系當前符號剩除輸入<1>tt<i+i*ifl<2>Hl>*1*1«<3>HP<*i*iil(4)HP*<i*ill<5>NP«1>*IN<6>HP+P<*ill<7>IIP*P*<1«HP*P»i>tt<?>flP*P*P>4C10>ttP+T>tt<11 >ttE=Jt丨口蠶 Mllasgg啓