Pascal語言編譯器的設(shè)計與實現(xiàn)

1、Pascal語言編譯器的設(shè)計與實現(xiàn)我們設(shè)計的編譯程序涉及到編譯五個階段中的三個，即詞法分析器、語法分析器和中間代碼生成器。編譯程序的輸出結(jié)果包括詞法分析后的二元式序列、變量名表、狀態(tài)棧分析過程顯示及四元式序列程序，整個編譯程序分為三部分：詞法分析部分語法分析處理及四元式生成部分輸出顯示部分.詞法分析器設(shè)計由于我們規(guī)定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯誤的檢查，而將編譯程序的重點放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號。我們規(guī)定輸出的單詞符號格式為如下的二元式：（單詞種別，單詞自身的值）#defineACC-2#definesy_if0ttdefi

2、nesy_then1ttdefinesy_else2#definesy_while3#definesy_begin4ttdefinesy_do5itdefinesy_end6ttdefinea7#definesemicolon8#definee9#definesharp10tidefineS11itdefineL121518 /E and19 /E or#definetempsy#defineEA#defineE0# defineplus34tidefinesubtract35tidefinetimes36tidefinedivide37# definebecomes38# defineop_

3、and39itdefineop_or40# defineop_not41# definerop42# defineIparent48# definerparent49# defineident56# defineintconst57函數(shù)說明1. 讀取函數(shù)readline()、readchar()詞法分析包含從源文件讀取字符的操作，但頻繁的讀文件操作會影響程序執(zhí)行效率，故實際上是從源程序文件”PAS.dat”中讀取一行到輸入緩沖區(qū)，而詞法分析過程中每次讀取一個字符時則是通過執(zhí)行readchar()從輸入緩沖區(qū)獲得的；若緩沖區(qū)已被讀空，則再執(zhí)行readline()從PAS.dat中讀取下一行至輸入

4、緩沖區(qū)。2.掃描函數(shù)scan()掃描函數(shù)scan()的功能是濾除多余空格并對主要單詞進(jìn)行分析處理，結(jié)果緩將分析得到的二元式存入二元式?jīng)_區(qū)。3.變量處理find()變量處理中首先把以字母開頭的字母數(shù)字串存到spelling1數(shù)組中，然后進(jìn)行識別。識別過程是先讓它與保留關(guān)鍵字表中的所有關(guān)鍵字進(jìn)行匹配，若獲得成功則說明它為保留關(guān)鍵字，即將其內(nèi)碼值寫入二元式結(jié)果緩沖區(qū)；否則說明其為變量，這時讓它與變量名表中的變量進(jìn)行匹配(變量匹配函數(shù)find(),如果成功，則說明該變量已存在并在二元式結(jié)果緩沖區(qū)中標(biāo)記為此變量(值填為該變量在變量名表中的位置)，否則將該變量登記到變量名表中，再將這個新變量存入二元式緩存

5、數(shù)組中。4.數(shù)字識別number()數(shù)字識別將識別出的數(shù)字填入二元式結(jié)果緩存數(shù)組。5.顯示函數(shù)顯示函數(shù)的功能在屏幕上輸出詞法分析的結(jié)果(行數(shù)統(tǒng)即二元式序列程序)，同時給出二元式個數(shù)及源程序計.O二.語法分析器設(shè)計語法分析器的核心是三張SLR分析表以及針對這三張SLR分析表進(jìn)行語義加工的語義動作。編譯程序中語法分析處理及四元式生成部分主要是以二元式作為輸入，并通過SLR分析表對語法分析處理過程進(jìn)行控制，使四元式翻譯的工作有條不紊的進(jìn)行，同時識別語法分析中的語法錯誤。在處理if和while語句時，需要進(jìn)行真值或假值的拉鏈和返填工作，以便轉(zhuǎn)移目標(biāo)的正確填入。1 .控制語句的SLR分析表1設(shè)計過程如下

6、：將擴(kuò)展文法G0)sS1) SifethenSelseS2) SwhileedoS3) SbeginLend4)Sa5)LS6) LS;L用CLOSURE方法構(gòu)造LR(0)項目規(guī)范簇為：10: sifethenSelseSwhileedoSbeginLend11: s12：ifeethenSelseS13：whileeedoS14:begin-LendsS；LifethenSelseSwhileedoSbeginLend15:16：ifeethenSelseS17：whileedoS18: beginLend19: $S*;L110: ifethenSelseSifethenSelseSwhi

7、leedoSbeginLend111: whileedoSifethenSelseSwhileedoSbeginLend112: beginLend113：S;LS;LifethenSelseSwhileedoSbeginLendSa114:$ifethenSelseS15：SwhileedoSe116: LS;L117: SifethenSelseSSifethenSelseSwhileedoSbeginLendSa118：SifethenSelseS構(gòu)造文法G中非終結(jié)符的FOLLOW集如下：FOLLOW(L)=endFOLLOW(S)=else,;,end,#在LR(O)項目規(guī)范簇中，只有

8、I9有“移進(jìn)一一歸約沖突，LS-LSLstatic int/*0*/*!*/actio n19131=因為FOLLOW(L)nFIRST(L)=/所以可以用SLR方法解決以上沖突，表如下：最后我們得到的SLR分析ACTION1GOTOIfthenelsewhilebegindoendaJesL0S2S3S4S511ACC2S63S74S2S3S4S5985R4R3R4R46S107Sil8S129R5S1310S2S3S4S51411S2S3S4S51512R3R3R3R313S2S3S4S591614S1715R2R2R2R216R617S2S3S4S51818RIRIRIRI2,T,T,3

9、,4,T,T,5,T,T,10,1,T,T,T,T,T,T,T,T,T,T,T,ACC,T,T,T,T,T,T,T,T,T,T,T,6,-1,一1,一1,-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,T,T,3,4,-1,-1,5,-1,-1,-1,9,8),1*3*1-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1),1*4*1-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1*5*1-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,

10、12,-1,-1,-1,-1,-1,-1),T,T,T,T,T,T,105,-1,13,T,T,T,T,/*6*/*7*/*8*/1*9*1/*10*/2,T,T,3,4,-1,-1,5,-1,-1,-1,14,-1,/*u*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-1,1*12*-1,-1,103,-1,-1,-1,103,1,103,-1,103,-1,1,/*13*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16,/*14*/-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1),/*15*/1*16*1-1,一1,1

11、02,-1,-1,-1,102,1,102,-1,102,-1,-1,-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1,1*17*12,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1),/*18*/-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;其中，前列為action值，表后2列為goto值；016表示17個移進(jìn)狀態(tài)(即Si)；-1表示出100-1()6對應(yīng)歸約錯；ACC示分析成功；而產(chǎn)生式：2.算術(shù)表達(dá)式的LR分析表2設(shè)計如下：0)1) E+E2) E*E3) (E)4)Ei(過程略)ACTIONGOTO

12、I+*/()#E0S3S211S4SUS5S10ACC2S3S263RIR4R4R4R4R44S3S275S3S286S4SUS5S10S97RIRIS5S10RIRI8R2R2R2R2R2R29R3R3R3R3R3R310S3S21211S3S21312R6R6R6R6R6R613R5R5S5S10R5R5staticintactionl149=1*0*13,-1,-1,-1,-1,2,-1,-1,1),/*1*/-1,4,11,5,10,-1,-1,ACC,-1),/*2*/*3*/1*4*11*5*13,-1,-1,-1,-1,2,-1,-1,6),104,104,104,104,104

13、,104,104,104,-1),3,-1,-1,-1,-1,2,-1,-1,7),(3,-1,-i,-i,-1,2,-1,-1,8),/*6*/T, 4, 11, 5, 10, -1, 9, -1, -1,/*7*/101, 101, 101, 5, 10, 101, 101, 101,-1,/*8*/102, 102, 102, 102, 102, 102, 102, 102,-1,/*9*/103, 103, 103, 103, 103, 103, 103, 103,-1,3, -1, -1, -1, -1, 2, T, T, 13,106, 106, 106, 106, 106, 10

14、6, 106, 106,-1,105, 105, 105, 5, 10, 105, 105, 105,-1;3.布爾表達(dá)式的SLR分析表3設(shè)計如下：（過程略）1)2)3)i rop i4)(B )5)NOT B6)B AND7)AB8)B ORACTIONGOTO1Rop()NOTANDOR#BA00SIS4S513781S2RIRIRIRI2S33R2R2R2R24SIS4S511785SIS4S56786R4S9S10R47SIS4S514788SIS4S515789R5R5R510R7R7R711S12S9S1012R3R3R3R313S9S10ACC14R6S9S10R615RSS9S

15、10RS9)OBstatic int actio n216_ L11Z =1*0*1 /*1*/ /*2*/ 1*3*11*4*11, T, 4, T, 5, -1, -1, -1, 13, 7, 8),T,2,T, 101,-1, 101, 101, 101,-1,-1,-1),102,-1,102,102,102,-1,-1,-1),1,T,4,-1,5,-1,-1,-1,11,7,8),1*5*1/*6*/*7*/*8*/1*9*1/*口*/1*12求 1/*14*/1,T,4,T,5,T,T,T,6,7,8,-11,T,104,1,9,10,104,-1,-1,-1）,1,-1,4,-

16、1,5,-1,-1,-1,14,7,8,1,-1,4,-1,5,-1,-1,-1,15,7,8,105,-1,105,T,105,-1,-1,105,-1,-1,-1,107,-1,107,-1,107,-1,-1,107,-1,-1,-1）,-1,一1,T,12,-1,9,10,-1,-1,-1,-1）,T,103,-1,103,-1,103,103,103,T,T,T,-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1）,T,T,-1,106,T,9,10,106,-1,-1,-1,-1,一1,一1,108,T,9,10,108,T,T,T;LR分析表控制語義加工的實現(xiàn)：當(dāng)掃

17、描LR分析表的當(dāng)前狀態(tài)為歸約狀態(tài)時，則在調(diào)用與該狀態(tài)對應(yīng)的產(chǎn)生式進(jìn)行歸約的同時，調(diào)用相應(yīng)的語義子程序進(jìn)行有關(guān)的翻譯工作?，F(xiàn)在對LR分析器的分析棧加以擴(kuò)充，使得每個文法符號之后都跟著它的語義值。為了清晰起見，我們把這個棧的每一項看成由三部分組成：狀態(tài)state,文法符號syl和語義值val。編譯程序?qū)崿F(xiàn)算術(shù)表達(dá)式、布爾表達(dá)式及程序語句的語義加工時，都是按這種狀態(tài)棧加工方式進(jìn)行的。例如：（5+3）*6的分析過程序號STATEValsylinput10#(5+3)*6#202以5+3)*6#3023#(5+3)*6#4026一5#(E+3)*6#502645-#(E+3)*6#6026435#(E+

18、3)*6#702647-5-3似E+E)*6#80268#(E)*6#90269-8-做E)*6#1001-8#E*6#11015-8-8E*6#120153-8#E*6130158-8-6#E*E1401-48#E15ACC在分析過程中，第（3）步操作后的狀態(tài)棧為023,根據(jù)棧頂狀態(tài)“3”和現(xiàn)行輸入符號“+”（input欄字符串的第一個字符）查分析表ACTION3,+=R4,即按第（4）個產(chǎn)生式En來進(jìn)行歸約；由于產(chǎn)生式右部僅含一項，故去掉狀態(tài)棧棧頂“3”；此時2變?yōu)樾碌臈ｍ敔顟B(tài)，再查（2,E）的下一狀態(tài)GOTO2,E=6,即將狀態(tài)6和文法符號E壓棧，最后得到第（4）步的狀態(tài)。第（7）步操作

19、后也是如此,當(dāng)前狀態(tài)棧為02647,根據(jù)棧頂狀態(tài)7和現(xiàn)行輸入符號“）”查分析表ACTION7,）=R1,即按第（1）個產(chǎn)生式EE1+E2進(jìn)行歸約；由于產(chǎn)生式右部有三項，故去掉狀態(tài)棧棧頂?shù)?47三項；此時2變?yōu)樾碌臈ｍ敔顟B(tài)，再查（2,E）的下一狀態(tài)s=GOTO2,E=6,即將狀態(tài)6和文法符號E壓棧，最后得到第（8）步的狀態(tài)。三.中間代碼生成器設(shè)計:1 .布爾表達(dá)式布爾表達(dá)式在程序語言中有兩個基本作用：一是用作控制語句女0if-else或while語句）的條（&、（件式；二是用于邏輯演算，計算邏輯值。布爾表達(dá)式是由布爾算符I、?。┳饔糜诓紶栕兞浚ɑ駿2,其中常數(shù)）或關(guān)系表達(dá)式而形成的。關(guān)系表達(dá)式的

20、形式是Elroprop是關(guān)系符（如V、m豐、或），E1和E2是算術(shù)式。在這里，我們只考慮前面給定文法所產(chǎn)生的布爾表達(dá)式:B7B&BIBIIBI!BI(B)IiropiIi遵照我們的約定，布爾算符的優(yōu)先順序（合規(guī)貝K耐系鈴的優(yōu)翔級都劇颯胡和雌左結(jié)而且高表達(dá)式的真、假出口的確定：考慮表達(dá)式于任何布爾算符，低于任何算術(shù)算符，關(guān)系算符不的真出口也就是整個B的真出口。若BlIIB2,若B1為真,則立即知道B也為真;因此,B1B1?為假，則B2必須被計值，B2的第一個四元式就是B1的假出口。當(dāng)然，B2的真、假出口也就是整個B的真、假出口。類似的考慮適用于對B1&B2的翻譯，我們將BlIIB2和Bl&B2的

21、翻譯用下圖表示，閩r出【I一一“fl”冉II31粉在自下而上的分析過程中，一個布爾式的真假出口往往不能在產(chǎn)生四元式的同時就填上。我們只好把這種未完成的四元式的地址（編號）作為B的語義值暫存起來，待到整個表達(dá)式的四兀式產(chǎn)生完畢之后再來回填這個未填入的轉(zhuǎn)移目標(biāo)。2 .條件語句對條件語句ifeSIelseS2中的布爾表達(dá)式e,其作用僅在于控制對S1和S2的選擇。因此，作為轉(zhuǎn)移條件的布爾式e,我們可以賦予它兩種“出口：一是“真”丁口，出向S1;一是“假”出口，出向S2。于是，e的代碼F條件語句可以翻譯成如圖的一般形式。SCI）的代石非終結(jié)符e具有兩項語義值eC和e_FC,它們分別指出了尚待回填真、S2

22、的代碼假出口的四元式串。e的“真”出口只有在往回掃描到if時才能知道，而它圖3-2條件語句的代碼結(jié)構(gòu)的“假”出口則需到處理過S1并且到達(dá)else才能明確。這就是說，必須把e_FC的值傳下去，以便到達(dá)相應(yīng)的else時才進(jìn)行回填。另外，當(dāng)S1語句執(zhí)行完時意味著整個if-else語句也已執(zhí)行完畢；因此，在S1的編碼之后應(yīng)產(chǎn)生一條無條件轉(zhuǎn)移指令。這條轉(zhuǎn)移指令將導(dǎo)致程序控制離開整個if-else語句。但是，在完成S2的翻譯之前，這條無條件轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)是不知道的。甚至，在翻譯完S2之后，這條轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)仍無法確定。這種情形是由于語句的嵌套性所引起的。例如下面的語句：ifelife2SIelse

23、S2elseS3在SI的代碼之后的那條無條件轉(zhuǎn)移指令不僅應(yīng)跨越S2而且應(yīng)跨越S3o這也就是說，轉(zhuǎn)移目標(biāo)的確定和語句所處的環(huán)境密切相關(guān)。3 .條件循環(huán)語句條件循環(huán)語句whileeS通常被翻譯成圖的代碼結(jié)構(gòu)。布爾式e的“真”出口出向S代碼段的第一個四元式。緊接的無條S代碼段之后應(yīng)產(chǎn)生一條轉(zhuǎn)向測試件轉(zhuǎn)移指令。e的“假”出口將導(dǎo)致程序控制離開整個使在整個while語句。e的“假”出口目標(biāo)即while語句翻譯完之后也未必明確。例如：的嵌套性引起的。騰elwhilee2SIelseS2這種情況仍是由于語句以，我們只好把它作為語句的語義值句時再伺機(jī)回填。SCHAIN暫留下來，以便在處理外層語語法翻譯實現(xiàn)方法

24、將上述語法翻譯付諸實現(xiàn)過程中，我們僅保留了算術(shù)表達(dá)式和布爾表達(dá)式翻譯的文法和語義動作；面對程序語句的翻譯，由于改造后含有較多的非終結(jié)符且語義動作又相對簡單，故仍恢復(fù)為改造之前的程序語句文法。由于總體上構(gòu)造一個SLR分析表來實現(xiàn)語法分析及語義加工將使得所構(gòu)造的SLR分析表過大，所以將其分為下面三部分處理：（1）對算術(shù)表達(dá)式單獨處理，即為算術(shù)表達(dá)式構(gòu)造一個SLR分析表，并將賦值語句A二E與算術(shù)表達(dá)式歸為一類處理，處理之后的賦值語句僅看作為程序語句文法中的一個終結(jié)符a對布爾表達(dá)式也單獨處理，并為其構(gòu)造一個SLR分析表，經(jīng)SLR分析表處理后的布爾表達(dá)式看作為程序語句文法中的一個終結(jié)符程序語句文法此時變

25、為：SifethenSelseSwhileedoSbeginLenda;LSLIS此時為程序語句構(gòu)造相應(yīng)的SLR分析表就簡單多了。前面的程序語句文法中所添加的非終結(jié)符是為了能及時回填有關(guān)四元式轉(zhuǎn)移目標(biāo)而引入的，在取消了這些非終結(jié)符后又如何解決及時回填轉(zhuǎn)移目標(biāo)的問題呢？我們采取的解決方法是增加兩個數(shù)組labehnark和labeltemp來分別記錄語句嵌套中每一層布爾表達(dá)式（如果有的話）e的首地址以及每一層else（如果有的話）之前的四元式地址（即無條件轉(zhuǎn)出此層if語句的四元式）。也即，對程序語句的翻譯來說：在處理完布爾表達(dá)式e后，回填if或while語句的真值鏈；在歸約完每一個語句S之后檢查符

26、號棧，看在S之前的文法符號是否if或while,若是則回填假值鏈（假值入口為語句S所對應(yīng)的四元式序列之后；對if語句，此時已在該序列之后加入了一條無條件轉(zhuǎn)移的四元式）；在if語句中，else前面要加入一個無條件轉(zhuǎn)移的四元式轉(zhuǎn)向要有一個無條件轉(zhuǎn)移四元式轉(zhuǎn)向while語句開頭。if語句末尾；在while語句尾四.數(shù)據(jù)結(jié)構(gòu)說明編譯程序中涉及到的數(shù)據(jù)結(jié)構(gòu)說明如下:IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII*/charch=,0J;/*當(dāng)前字符*/intstaticcount=0;charspelling;/*存放識別的字*/staticcharline;/*一行

27、字符緩沖區(qū)水/char*pline;/*字符緩沖區(qū)指針*/staticcharntabl10010;structntabinttc;intfc;ntab2200;intlabel=0;/*存放臨時變量的表的定義*/structrwordscharsp10;int;/*存放文件sy:的結(jié)構(gòu)*/structrwordsreswords10=if,sy_if),do，sy_do,(else”,sy_else,“while”,sy_while,“then”,sy_then,“begin”,sy_begin,end，sy_end,and，op_and,or，op_or,not，op_not;struct

28、aaintsyl;intpos;buf1000,/*詞法分析結(jié)果緩沖區(qū)*/g_nCurChar,/*當(dāng)前字符*/g_nExpCurChar,/*當(dāng)前表達(dá)式中的字符*/E,/*非終結(jié)符*/sstack100,/*符號棧*/ibuf100,stack1000;structaaoth;structfourexp(charop10;structaaargl;structaaarg2;intresult;fexp200;/*四元式的結(jié)構(gòu)*/intssp=0;/*指I可sstack100*/structaa*pbuf=buf;/*指向詞法分析緩沖區(qū)*/nlength=0;intlnum=0;/*源程序長度

29、*/intintttl=O;FILE*cfile;/7P7,7,7,7P7,7,7,7P7,7,7,7P7,7,7,7P7,7,7,7P7,7,7,7,7P7,4*fit4、“、4、“、4、4、“、4、”、4、“、4、4、“、4、”、4、“、4、4、“、4、”、4、“、4、4、“、4、”、4、“、4、4、“、4、”、4、“、4、4、“、4、”、4、“、4、4、“、4、firiiivaji/*臨時變量*/intnxq=100;/*nxq指向下一個形成的四元式的地址*/intlr;intIrl;intsp=O;/*狀態(tài)棧定義*/intstackl100;intspl=0;/*狀態(tài)棧1的定義*/in

30、tnum=0;struct11intnxql;inttel;intfcl;labelmark10;intlabeltemp10;intpointmark=T,pointtemp=T;intsign=0;/*sign=1,表達(dá)式為賦值語句；sign=2,表達(dá)式為布爾表達(dá)式。*/五.編譯程序運行測試測試PAS.dat得源程序如下：while(ab)dobeginifm=nthena:=a+lelsewhilek=hdox:=x+2;m:=n-x/(m+y);p:=x/2-2end#經(jīng)編譯程序運行后得到的輸出結(jié)果如下:詞法分析結(jié)果48continue*34856423561490504000562425615603805603405712030564Pressanykeyto4256550566380566345780562380563350566370563456495638563757355710程序總10共行，產(chǎn)生了51個二元式!*變量表*狀態(tài)棧變化過程及規(guī)約Mistack0=0n二3lr=3stack1=3n=9lr=7stack2=7n=5lr=llstack3=lln=4lr