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

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

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

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

4、sert(P,a) while stack 非空 begin 棧頂項出棧，記為(Q,a) for 對每條形如 PQ的產(chǎn)生式 do insert(P,a) end; end.2、構(gòu)造算符優(yōu)先分析表依據(jù)文法和求出的相應(yīng)FirstVT和 LastVT 集生成算符優(yōu)先分析表。算法描述如下：for 每個形如 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 中的每個元素 a do Xi < a ; if Xi為非終結(jié)符, Xi+1為終結(jié)符 then for LastVT 中的每個元素 a do a > Xi+1 ; end;3、構(gòu)造算符優(yōu)先分析和中間代碼產(chǎn)生過程。四、輸入數(shù)據(jù)和輸出數(shù)據(jù)若輸入文法： E->E+T | T T->T*F | F F-> (E) | i 將得到如下所示的 FirstVT 集和LastVT數(shù)組。輸出的優(yōu)先關(guān)系表如下：若輸入的語句是 a:=b+c*(e-a)則輸出：(-，e,a,T1)(*,c,T1,T2)(+,b,T2,T3)(:=,T3,_,a

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

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

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

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

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

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