算符優(yōu)先分析法設(shè)計(jì)與實(shí)現(xiàn)

1、 算符優(yōu)先分析法設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康募由顚?duì)語(yǔ)法分析器工作過(guò)程的理解；加強(qiáng)對(duì)算符優(yōu)先分析法實(shí)現(xiàn)語(yǔ)法分析程序的掌握；能夠采用一種編程語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的語(yǔ)法分析程序；能夠使用自己編寫的分析程序?qū)?jiǎn)單的程序段進(jìn)行語(yǔ)法翻譯。二、實(shí)驗(yàn)內(nèi)容在實(shí)驗(yàn)1的基礎(chǔ)上，用算符優(yōu)先分析法編制語(yǔ)法分析程序，語(yǔ)法分析程序的實(shí)現(xiàn)可以采用任何一種編程語(yǔ)言和工具。三、實(shí)驗(yàn)要求：1. 對(duì)語(yǔ)法規(guī)則有明確的定義；2. 編寫的分析程序能夠?qū)?shí)驗(yàn)一的結(jié)果進(jìn)行正確的語(yǔ)法分析；3. 對(duì)于遇到的語(yǔ)法錯(cuò)誤，能夠做出簡(jiǎn)單的錯(cuò)誤處理，給出簡(jiǎn)單的錯(cuò)誤提示，保證順利完成語(yǔ)法分析過(guò)程；四、實(shí)驗(yàn)步驟1. 定義目標(biāo)語(yǔ)言的語(yǔ)法規(guī)則；2. 求解預(yù)測(cè)分析方法需要的符號(hào)集

2、和分析表；3. 依次讀入實(shí)驗(yàn)一的分析結(jié)果，根據(jù)預(yù)測(cè)分析的方法進(jìn)行語(yǔ)法分析，直到源程序結(jié)束；4. 對(duì)遇到的語(yǔ)法錯(cuò)誤做出錯(cuò)誤處理。五、實(shí)驗(yàn)報(bào)告要求詳細(xì)說(shuō)明你的程序的設(shè)計(jì)思路和實(shí)現(xiàn)過(guò)程。實(shí)驗(yàn)報(bào)告要求用文法的形式對(duì)語(yǔ)法定義做出詳細(xì)說(shuō)明，說(shuō)明語(yǔ)法分析程序的工作過(guò)程，說(shuō)明錯(cuò)誤處理的實(shí)現(xiàn)。算符優(yōu)先分析器（綜合性實(shí)驗(yàn)）一、實(shí)驗(yàn)?zāi)康恼莆?FirstVT和 LastVT集的算法，算符優(yōu)先分析表的構(gòu)造算法及其分析過(guò)程，并掌握中間代碼產(chǎn)生過(guò)程。二、實(shí)驗(yàn)內(nèi)容算術(shù)表達(dá)式和賦值語(yǔ)句的文法可以是（可以根據(jù)需要適當(dāng)改變）： Si=EEE+TEE-TETTT*F TT/F TFF(E)Fi 根據(jù)算符優(yōu)先分析法，將賦值語(yǔ)句進(jìn)行語(yǔ)法

3、語(yǔ)義分析，翻譯成等價(jià)的一組基本操作，每一基本操作用四元式表示。三、實(shí)驗(yàn)過(guò)程和指導(dǎo)1、構(gòu)造FirstVT和LastVT集合給定一個(gè)上下文無(wú)關(guān)文法，根據(jù)算法設(shè)計(jì)一個(gè)程序，求文法中每個(gè)非終結(jié)符的 FirstVT 集和LastVT 集。算符描述如下：/*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF not FP,a then begin fp,a = true; (P,a)進(jìn)棧 end; Procedure FirstVT; Begin for 對(duì)每個(gè)非終結(jié)符 P和終結(jié)符 a do FP,a = false for 對(duì)每個(gè)形如 Pa或 PQa的產(chǎn)生式 do In

4、sert(P,a) while stack 非空 begin 棧頂項(xiàng)出棧，記為(Q,a) for 對(duì)每條形如 PQ的產(chǎn)生式 do insert(P,a) end; end.2、構(gòu)造算符優(yōu)先分析表依據(jù)文法和求出的相應(yīng)FirstVT和 LastVT 集生成算符優(yōu)先分析表。算法描述如下：for 每個(gè)形如 P->X1X2Xn的產(chǎn)生式 do for i =1 to n-1 do begin if Xi和 Xi+1都是終結(jié)符 then Xi = Xi+1 if i<= n-2, Xi和 Xi+2 是終結(jié)符, 但 Xi+1 為非終結(jié)符 then Xi = Xi+2 if Xi為終結(jié)符, Xi+1

5、為非終結(jié)符 then for FirstVT 中的每個(gè)元素 a do Xi < a ; if Xi為非終結(jié)符, Xi+1為終結(jié)符 then for LastVT 中的每個(gè)元素 a do a > Xi+1 ; end;3、構(gòu)造算符優(yōu)先分析和中間代碼產(chǎn)生過(guò)程。四、輸入數(shù)據(jù)和輸出數(shù)據(jù)若輸入文法： E->E+T | T T->T*F | F F-> (E) | i 將得到如下所示的 FirstVT 集和LastVT數(shù)組。輸出的優(yōu)先關(guān)系表如下：若輸入的語(yǔ)句是 a:=b+c*(e-a)則輸出：(-，e,a,T1)(*,c,T1,T2)(+,b,T2,T3)(:=,T3,_,a

6、)算符優(yōu)先文法處理 一、實(shí)驗(yàn)?zāi)康恼莆账惴麅?yōu)先分析法的原理，利用算符優(yōu)先分析法將賦值語(yǔ)句進(jìn)行語(yǔ)法分析，翻譯成等價(jià)的四元式表示。二、實(shí)驗(yàn)內(nèi)容： 1.算術(shù)表達(dá)式的文法可以是（你可以根據(jù)需要適當(dāng)改變）：  EE+E|E-E|E*E|E/E|（E）|i 2.根據(jù)算符優(yōu)先分析法，將表達(dá)式進(jìn)行語(yǔ)法分析，判斷一個(gè)表達(dá)式是否正確。 3.將賦值語(yǔ)句進(jìn)行語(yǔ)法分析，翻譯成等價(jià)的一組基本操作，每一基本操作用四元式表示。 三、實(shí)驗(yàn)預(yù)習(xí)提示 1.實(shí)驗(yàn)原理  我們要分析的表達(dá)式滿足下面的算符優(yōu)先矩陣 21 +  -  *  /  ( 

7、)   +  >  >  <  <  <  >  > -  > >  <  <  <  > >  *  >  >  >  >  <  >  >  /  >  >  >  >

8、;  <  >  >  (  <  <  <  <  <  =  )  >  >  >  >  >  >   <  <  <  <  <  =為實(shí)現(xiàn)算符優(yōu)先算法，可以使用兩個(gè)工作棧。一個(gè)叫做OPTR，用以寄存運(yùn)算符，一個(gè)叫OPND,用以寄存操作數(shù)

9、或結(jié)果。算法描述如下：  1首先置操作數(shù)棧為空棧，將表達(dá)式起始符;作為運(yùn)算符棧的棧底元素。 2依次讀入表達(dá)式中每個(gè)單詞，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則轉(zhuǎn)3。  3將此運(yùn)算符1與OPTR棧頂元素2進(jìn)行比較，即查上表，若 12，則：1進(jìn)棧，轉(zhuǎn)2 若 12 ,如1為；，則分析成功，否則OPTR棧頂元素出棧，并轉(zhuǎn)2 若 1<2,則出棧OPND棧頂元素至b，又出棧其棧頂元素至a，出棧OPTR棧頂元素至t，進(jìn)行運(yùn)算r=a t b(t 為運(yùn)算符)，并將結(jié)果r存入棧OPND后轉(zhuǎn)3。 若1和2之間無(wú)

10、優(yōu)先關(guān)系，則報(bào)錯(cuò)。  四、實(shí)驗(yàn)步驟（一)準(zhǔn)備： 1. 閱讀課本有關(guān)章節(jié)，花一周時(shí)間確定算術(shù)表達(dá)式的文法，設(shè)計(jì)出算符優(yōu)先關(guān)系表； 2.考慮好設(shè)計(jì)方案； 3. 設(shè)計(jì)出模塊結(jié)構(gòu)、測(cè)試數(shù)據(jù)，初步編制好程序。 (二)上課上機(jī)：上機(jī)調(diào)試，發(fā)現(xiàn)錯(cuò)誤，分析錯(cuò)誤，再修改完善。教師根據(jù)學(xué)生的設(shè)計(jì)方案與學(xué)生進(jìn)行探討，以修改方案和代碼。(三）程序要求： 程序思路（僅供參考）： 1.借用實(shí)驗(yàn)一的結(jié)果，可將其中的取字符函數(shù)幾乎原封不動(dòng)地移植過(guò)來(lái)，其中的分割和分析單詞的方法可借用過(guò)來(lái)分割現(xiàn)在這個(gè)實(shí)驗(yàn)的運(yùn)算符、常量和變量。2.模塊結(jié)構(gòu)：（1）初始化：設(shè)立算符優(yōu)先關(guān)系表（或優(yōu)先函數(shù)）、初

11、始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時(shí)變量等）；（2）控制部分：將一個(gè)表達(dá)式從文件中讀出；（3）詞法分析：將表達(dá)式分割成單詞序列；（4）利用算符優(yōu)先文法進(jìn)行表達(dá)式處理：根據(jù)算符優(yōu)先關(guān)系表（或優(yōu)先函數(shù)）對(duì)表達(dá)式單詞序列進(jìn)行堆棧（或其他）操作，得到并保存四元組，如果遇到錯(cuò)誤則顯示錯(cuò)誤信息；（5）輸出四元組。 3.程序輸入/輸出示例： 如參考C語(yǔ)言的運(yùn)算符。輸入如下表達(dá)式（以分號(hào)為結(jié)束）和輸出結(jié)果： （1）10; 輸出：正確 （2）1+2; 輸出：正確 （3）(1+2)/3+4-(5+6/7); 輸出：正確（4）(1-2)/3+4 輸出：錯(cuò)誤 （5）1+2-3+(*4/5) 輸出：錯(cuò)誤 注意：1.為降低難度，表達(dá)式