實(shí)驗(yàn)二 遞歸下降法語法分析.docVIP

實(shí)驗(yàn)二 遞歸下降語法分析目的：理解自定向下語法分析的基本模式，熟悉遞歸下降分析程序的構(gòu)造。內(nèi)容：采用遞歸下降法對賦值語句、算術(shù)表達(dá)式運(yùn)算、while循環(huán)語句、if分支語句及其分類體系進(jìn)行分析。步驟：1、重構(gòu)單詞內(nèi)碼表在實(shí)驗(yàn)一的基礎(chǔ)上，要求考慮while語句、if語句。以下為一參考實(shí)現(xiàn)： 保留字 內(nèi)部編碼 運(yùn)算符號 內(nèi)部編碼 其他 內(nèi)部編碼 if 1 + 51 ( 81 else 2 - 52) 82 while 3 * 53 ; 83 int 4 / 54 84float 5 * 55 85 char 6 = 56 = 86 byte7 58 = 60 數(shù)字100 61 標(biāo)識符1102、定義語言文法（1）定義所需的非終結(jié)符選取高級語言的部分語句，先定義其中所涉及的非終結(jié)符：符號定義符號定義符號定義程序定義語句集可執(zhí)行語句集定義語句變量列表關(guān)系運(yùn)算符可執(zhí)行語句while語句If語句賦值語句過程調(diào)用語句類型聲明關(guān)系表達(dá)式算術(shù)運(yùn)算符1算術(shù)運(yùn)算符2表達(dá)式文法引入的幾個符號依然使用。 （2）用文法表達(dá)其語法規(guī)范。 | ; ,|int | float | char | byte;|while ( ) if ( ) else =;|=|=|!=|(E)|+|-*|/ 說明： 大寫字母構(gòu)成的單詞（也用尖括號括起）表非終結(jié)符，小寫單詞表終結(jié)符。由于在詞法分析階段已經(jīng)識別了數(shù)字和標(biāo)識符，故邏輯上在此作為終結(jié)符對待；但另一方面又由于其概括性，又用尖括號括起。 本文法設(shè)計(jì)對高級語言子集也作了較大的簡化，如不考慮過程定義及調(diào)用；不考慮輸入輸出；不考慮主程序；不考慮for循環(huán)；不考慮switch case語句；不考慮字符串常量；變量定義只能在文件開頭等等。3、編碼（1）遞歸下降子程序的基本模式（請注意規(guī)則和下面的顏色對應(yīng)關(guān)系）： 文法中的每個非終結(jié)符對應(yīng)一個過程（函數(shù)）。 若某個非終結(jié)符有多個產(chǎn)生式候選，或者某個分支路徑有多個候選。則根據(jù)該候選的Select集是否包含輸入符進(jìn)行選擇。每個候選對應(yīng)一個if分支。 選擇好候選之后，對產(chǎn)生式候選的右部的符號由左到右依次處理。（a）若為終結(jié)符。則判別是否與輸入符號相等。若相等，繼續(xù)。否則轉(zhuǎn)（b）若為非終結(jié)符，則調(diào)用該非終結(jié)符所對應(yīng)的過程。（c）若當(dāng)前掃描的符號為當(dāng)前候選的第一個符號，且當(dāng)前候選同層次有候選項(xiàng).則不作出錯處理。否則均出錯處理。例1：S(S)|achar str; /待檢查的串int ip; /掃描指針void S() /只有一個非終結(jié)符S if(strip=() /處理S(S)候選ip+; S();if(strip=) ip+;else error(); else if(strip=a) /處理Sa候選 ip+; else /對應(yīng)第1符號 error(); /但無候選項(xiàng)，必須出錯。例2：S(S)|char str; /待檢查的串int ip; /掃描指針void S() /只有一個非終結(jié)符S if(strip=() ip+; S();if(strip=) ip+;else error(); /不與第1個符號，出錯。 /最外層if不構(gòu)造出錯處理分支。（2）本實(shí)驗(yàn)中需要考慮的具體問題 上例比較的是字符。而本實(shí)驗(yàn)中用的是符號（單詞）編碼，是經(jīng)過詞法分析后的編碼。依據(jù)字符串的排列和內(nèi)碼排列構(gòu)成的兩套系統(tǒng)是同構(gòu)的。不影響語法分析的結(jié)果。希望大家能理解“同構(gòu)”的含義。也就是后面定義的token數(shù)組相當(dāng)于本例的str。這點(diǎn)變通能力希望大家有。 對于多個候選依據(jù)Select集來判定，具體實(shí)現(xiàn)時(shí)可定義一個函數(shù)：boolean inSelect(x,),判別 xSELECT()是否成立。數(shù)據(jù)結(jié)構(gòu)可采用二維表格的方式，在inSelect內(nèi)部查表。 雖然處理的是內(nèi)碼，但可用宏定義，則程序可讀性好：/* 終結(jié)符定義 */#define $if1/*if*/#define $else2/*else*/#define $while3/*while*/ 關(guān)于上面規(guī)則的具體運(yùn)用，可看模板代碼。實(shí)現(xiàn)了兩個非終結(jié)符，其余的需要同學(xué)們自己去實(shí)現(xiàn)，注意利用詞法分析程序的成果。4、測試構(gòu)造正反測試用例，如：正確實(shí)例：whil