編譯原理實(shí)驗(yàn)報(bào)告

1、編譯原理課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)2 :語法分析姓名1院系1軟件學(xué)院學(xué)號(hào)任課教師指導(dǎo)教師實(shí)驗(yàn)地點(diǎn)軟件學(xué)院三樓機(jī)房實(shí)驗(yàn)時(shí)間2016/10/30/ 星期日實(shí)驗(yàn)課表現(xiàn)出勤、表現(xiàn)得分實(shí)驗(yàn)報(bào)告得分實(shí)驗(yàn)總分操作結(jié)果得分一、需求分析得分要求：采用至少一種句法分析技術(shù)（LL（1）、SLR（1、LR（1）或LALR（1）對(duì)類高級(jí)語言中的基本語句進(jìn)行句法分析。闡述句法分析系統(tǒng)所要完成的功能。本語法分析器是在詞法分析器的基礎(chǔ)上實(shí)現(xiàn)對(duì)類高級(jí)語言中的基本語句進(jìn)行句法分析，基本功能 如下：（1）能識(shí)別以下幾類語句：聲明語句（包括變量聲明、數(shù)組聲明、記錄聲明和過程聲明 ）表達(dá)式及賦值語句（包括數(shù)組元素的引用和賦值）分支語句：if_t

2、hen_else循環(huán)語句：do_while過程調(diào)用語句（2） 本語法分析器采用自頂向下的分析技術(shù)，能根據(jù)導(dǎo)入的文法，自動(dòng)計(jì)算first集和follow集， 能夠生成每個(gè)產(chǎn)生式的select集，并自動(dòng)生成預(yù)測分析表。（3）本語法分析器具備語法錯(cuò)誤處理能力，可以進(jìn)行錯(cuò)誤檢測，如果檢測到在出錯(cuò)時(shí)，采用恐慌模式，能夠給出錯(cuò)誤提示信息，格式：錯(cuò)誤項(xiàng)錯(cuò)誤原因行號(hào)a）忽略輸入中的一些符號(hào)，直到輸入中出現(xiàn)選定的同步詞法單元集合中的某個(gè)詞法單元，同步集合的選取是非終結(jié)符的follow集；b）如果終結(jié)符在棧頂而不能匹配，彈出此終結(jié)符。c）輸入棧中缺少某些應(yīng)有的符號(hào)，比如只有右括號(hào)沒有左括號(hào)等，會(huì)給出相應(yīng)的提示。（

3、4）系統(tǒng)的輸入形式多樣：可以通過文件導(dǎo)入文法和測試用例，可以通過用戶界面顯示并編輯測試用例。測試用例涵蓋了第（1）條中列出的各種類型的語句，并設(shè)置了一些語法錯(cuò)誤。（5） 系統(tǒng)的輸出分為兩部分：一部分是打印輸出語法分析器的FIRST集、FOLLOW集、select集和LL（1）分析表。另一部分是打印輸出語法分析結(jié)果。（6）本系統(tǒng)還實(shí)現(xiàn)了輸出語法分析樹的功能，讓語法分析的過程更清晰。二、文法設(shè)計(jì)得分要求：給出如下語言成分的文法描述。聲明語句（包括變量聲明、數(shù)組聲明、記錄聲明和過程聲明 ）表達(dá)式及賦值語句（包括數(shù)組元素的引用和賦值）分支語句：if_then_else循環(huán)語句：do_while過程調(diào)用

4、語句本語法分析器主要針對(duì)C語言進(jìn)行文法設(shè)計(jì)，下面給出各語言成分的文法描述。程序入口：Program->PP->D P /支持連續(xù)聲明P ->S PP->£1）聲明語句：D proc id ; D S| T id;/支持過程聲明和變量聲明T t X C | record D/支持結(jié)構(gòu)體聲明X t short|int | Iong|float|double|char|string/ 支持多種基本類型的聲明C t numC | &II支持?jǐn)?shù)組的聲明2）表達(dá)式及賦值語句：S id = E ;| L = E ;E E + E | E * E | E |（E） |

5、 id | digit | LL idE | LEII支持?jǐn)?shù)組元素的引用和賦值3）控制流語句：S if B then Slelse S2 | while B do S1B t b | bII或語句| B && BII且語句| ! BII非語句1(B)| E relop E| true| false/使用括號(hào) /關(guān)系語句/bool 型/bool 型/關(guān)系符號(hào)relop t < | <= | = | != | > | >=4) 過程調(diào)用語句S call id (Elist)Elist Elist, EElist E下面給出整個(gè)程序的無二義性，無左遞歸的LL

6、(1)文法：Program->PP->D P|S P|emptyD->proc T id ( M ) P |T id A ;|record id P M->X id M'M'->, X id M'|emptyA->= F|empty|, id AF->digit|id|char| G |stringG->H G'G'->, H G'|emptyH->digit|charT->X CX->short|i nt|l on g|float|double|char|void|stri

7、 ng|boolea nC-> digit C|emptyS->L = E ;|if B the n S else S|while B do S|call id ( Elist ) ;|return E ;E->- E E'|( E ) E'|digit E'|L E'|string E'E'->+ E E'|* E E'|emptyL->id L'L'-> digit L'|emptyB->! B B'|( B ) B'|E relop E B&#

8、39;|true B'|false B'B'->or B B'|a nd B B'|emptyrelop_><|<=|=|!=|>|>=Elist->E Elist'Elist'->, E Elist'|empty注：此處用empty代表空要求：分為系統(tǒng)概要設(shè)計(jì)和系統(tǒng)詳細(xì)設(shè)計(jì)。(1) 系統(tǒng)概要設(shè)計(jì)：給出必要的系統(tǒng)宏觀層面設(shè)計(jì)圖，如系統(tǒng)框架圖、數(shù)據(jù)流圖、功能模塊結(jié)構(gòu) 圖等以及相應(yīng)的文字說明。1) 系統(tǒng)的數(shù)據(jù)流圖：說明蠱取下一個(gè) 詞建單元說明：本語法分析器是基于上一個(gè)實(shí)驗(yàn)詞法分析器的基礎(chǔ)

9、上，通過在界面寫或者是導(dǎo)入源程序，詞法分析器將源程序識(shí)別的詞法單元傳遞給語法分析器，語法分析器驗(yàn)證這個(gè)詞法單元組成的串是否可以由源語言的文法生成，能夠輸出語法分析的結(jié)果，文法的first集、follow集和預(yù)測分析表，當(dāng)然也可以以易于理解的方式報(bào)告語法錯(cuò)誤。2) 系統(tǒng)框架圖本系統(tǒng)框架王要是三部分,馬戶岸面電演W出百斗測仔嶄擊顯小區(qū)Ft獲來占rn豐顯示懐部分是詞法分析， 負(fù)責(zé)識(shí)別源程序的詞法單元識(shí)別，并將其存儲(chǔ)，以供語法分析時(shí)讀取；第二部分是文法分析部分，負(fù)責(zé)將導(dǎo)入的文法進(jìn)行分析，得出文 法的first集和follow集，以及自動(dòng)構(gòu)造出預(yù)測分析表，在語法分析時(shí)進(jìn)行查詢；第三部分 是用戶界面，提供

10、源程序輸入功能，以及語法分析結(jié)果的顯示，顯示語法分析樹，還有first集、follow集和預(yù)測分析表的展示。(2)系統(tǒng)詳細(xì)設(shè)計(jì)：對(duì)如下工作進(jìn)行展開描述核心數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)核心數(shù)據(jù)結(jié)構(gòu)主要有兩種：1) Tuple三元組為了存儲(chǔ)預(yù)測分析表，我使用Tuple<string,string,string>三元組的數(shù)據(jù)結(jié)構(gòu)，分別存儲(chǔ)產(chǎn)生式的頭部，產(chǎn)生式體，輸入符號(hào)。2) Stack 棧為了能夠在語法分析時(shí)根據(jù)預(yù)測分析表來進(jìn)行分析，我寫了一個(gè)CStack的類用來實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)，在進(jìn)行語法分析時(shí)，一個(gè)棧用來存儲(chǔ)文法符號(hào)，一個(gè)棧用來存儲(chǔ)輸入符號(hào)，然后 根據(jù)預(yù)測分析表進(jìn)行語法分析。主要功能函數(shù)說明 主

11、要功能函數(shù)：1) IDContent 類：功能：充當(dāng)符號(hào)表的角色，主要是用來保存關(guān)鍵字，運(yùn)算符，界符，轉(zhuǎn)義字符等各類單詞。主要函數(shù)：bool isConstChstring str)/判斷是否轉(zhuǎn)義字符bool isLetter_(char c)判斷是否字母或下劃線bool isDigit(char c) 判斷是否數(shù)字bool isBlank(char c)判斷是否是空格、制表符、換行、回車bool isKeyWord(string str)/ 判斷是否關(guān)鍵字bool isBoundary(char c)/判斷是否是邊界符號(hào)bool isOperator(stri ng ch)/ 判斷是否運(yùn)算符

12、2) Identifier 類功能：識(shí)別單詞的核心類主要函數(shù)：string isID(string str, ref int i)/是否是標(biāo)識(shí)符string isSixteen(string str, ref int i,out bool right)/ 是否 16 進(jìn)制數(shù)string isEighttring str,ref int i,out bool right)/ 是否 8 進(jìn)制數(shù)string isNumber(string str, ref int i, out bool right)/ 是否是常數(shù)string isOperator(string str, ref int i, ou

13、t bool right)/ 是否是運(yùn)算符string isNote(string str, ref int i, out bool right)/ 是否注釋string isBoundary(string str, ref int i,out bool right)/ 是否界符string isChartring str, ref int i, out bool right)/ 是否字符常數(shù)3) FirstAndFollow 類功能：得到first集、follow集、select集、預(yù)測分析表public void getFirstCollection()/ 得到 first 集合publi

14、c void getFollowCollection()/ 得到 follow 集合public void getSelectCollection()/ 得到預(yù)測分析表public void getAnalysisTable(string str1, string str2, string str3)/ 得到預(yù)測分析表public void errorHandle()加入同步詞法單元4) CStack 類功能：棧結(jié)構(gòu)public bool isEmpty()判斷棧是否為空public void push(object item)/ 往棧中加入一個(gè)元素public object pop()從棧中

15、彈岀一個(gè)元素public object peek() 返回棧頂對(duì)象5) Form 類public void analysis(string str)/ 詞法單元識(shí)另Vpublic void parse()語法單元識(shí)別private void 導(dǎo)入文法 ToolStripMenultem_Click(object sender. EventArgse)/ 導(dǎo)入文法private void 顯示語法分析樹 ToolStripMenultem_Click(object sender, EventArgs e)/輸岀語法分析樹private void addListview1ltem() 輸岀 fir

16、st 集和 follow 集private void addListview3ltem() 輸岀預(yù)測分析表程序核心部分的程序流程圖語法分析核心部分流程圖：輸出語法分析樹開始將文法開始符號(hào)壓入文法棧中從輸入棧中讀取詞法單元空從文法棧中取出頂?shù)姆?hào)報(bào)錯(cuò)彈出文法棧棧頂對(duì)掃描預(yù)測分析表象彈出文法棧棧頂對(duì) 象和輸入棧棧頂對(duì)象結(jié)束否是同步詞曰 法單是將產(chǎn)生式的右部替 換文法棧中產(chǎn)生的左部a棧頂是否為、和輸入棧的輸否入字符是否匹否配彈出文法棧頂對(duì)彈出輸入棧棧頂對(duì)象四、系統(tǒng)實(shí)現(xiàn)及結(jié)果分析得分要求：對(duì)如下內(nèi)容展開描述。（1）系統(tǒng)實(shí)現(xiàn)過程中遇到的問題；實(shí)現(xiàn)過程中主要遇到的問題有：1）如何修改文法使其時(shí) LL（ 1

17、）文法通過對(duì)文法的修改，主要是對(duì)文法消除左遞歸，消除二義性，以及提取公因式等，最終對(duì)于相同左部的產(chǎn)生式他們的select集不相交，得到了 LL（ 1）文法。2） 如何得到文法符號(hào)的first集對(duì)于終結(jié)符，其first集就是本身，但是對(duì)非終結(jié)符，在遍歷的時(shí)候依賴于其他的非終結(jié) 符，于是我采用循環(huán)遍歷的方法，如果當(dāng)前某個(gè)非終結(jié)符的first集依賴于其他非終結(jié)符，且其他非終結(jié)符的first集還沒有求出來，則跳過當(dāng)前的非終結(jié)符求下一個(gè)非終結(jié)符的first集，直到其依賴的非終結(jié)符的first集求出來后再求解。直到所有的非終結(jié)符的first集求出來后，循環(huán)結(jié)束，就得到了所有文法符號(hào)的first集合。3）

18、如何得到非終結(jié)符的follow集為了使思路清晰，我采用兩遍遍歷的方式來求非終結(jié)符的follow集。第一遍之后，所有非終結(jié)符都將得到一個(gè)暫時(shí)的follow集（不是最終的follow集），第二遍的目標(biāo)就是發(fā)現(xiàn)其中是否有非終結(jié)符的follow集發(fā)生了改變，如果改變，則繼續(xù)遍歷整個(gè)文法，直到?jīng)]有新的符號(hào)加入follow集中。求follow集的具體思想就是：不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符可以被加入到任何FOLLOW集合中為止將$放入FOLLOW（ S ）中，其中S是開始符號(hào)，$是輸入右端的結(jié)束標(biāo)記如果存在一個(gè)產(chǎn)生式 Aa B0那么FIRST（份中除&之外的所有符號(hào)都在 FOLLO% B ）

19、 中如果存在一個(gè)產(chǎn)生式AaB,或存在產(chǎn)生式Aa BB且FIRST （ 3 ）包含 &那么FOLLOW A ）中的所有符號(hào)都在 FOLLOW（ B ）中4）如何根據(jù)預(yù)測分析表進(jìn)行語法分析這里主要依賴于棧的結(jié)構(gòu)，將經(jīng)過詞法分析得到的詞法單元壓入輸入棧，將文法起始符 號(hào)壓入文法棧，然后根據(jù)預(yù)測分析表得到各個(gè)產(chǎn)生式進(jìn)行語法分析。（2）輸出該句法分析器的分析表；文法符號(hào)$procshortProgramFrogr«n->PFrogram->FFrograin->PFP->enptyP->D PP->D PDMD->pr ocD->T id

20、 A ； M->X id MK*AFGGHTT-X CXX->shortCSEsytchsynchsynchintFrogr«m->P P->D P D->T id A ； M->X id Mlong Program-?P->D P D->7 id A ； M->X id Zfloat Frogrwn->FP->D P5->T id A M->X id M*doubleFrogram->FP->D P D->T id A . M->X idM*T->X CT-X CT->

21、X CT-X CX->intX->lon$X->£loatX-doublesynchsynchsynchsynchLzB b' relcp Elist Elist'charProgram->FP-D PD-)T id A :M-X idvoidFrogrtm->?P->D P TT id A : M->X id Itstring Progran->PP->D P D->T id A : M->X il MrecordPro5ram->PP->D P D->recorLcharG->

22、;H Gf>stringK-char r->x C X->charT-X C X")voidT-X CX">strin.synchsynchsynch f->stringsynchB->E rel.synchEli st：E.idifwtilecallProgram-?Program->PFrogrtm">?Progra»->PP->S PP->S PP->S PP->S PsynchsynchsynchsynchHidsynch synch C*>enpty S->

23、;1 = E :E->L E'E ->empty L->id L' L ->empty rel.S->i£ BS->whil«.S->cd. 1synchEli st">E.re turn1/)(Ir->s PP>e«ptysjnclsynchzynehK* > enp tykr>, id XA->- FA_>etiptysyrchF-)diei tF-> G tynohC-Jenptyd X CG->X GsynokSYIkdlX->d

24、igitsynch C> dig.5>r«tuz.synah5ynchsynch5 yr chE>di g t EsynchE > c»ptyF > onp tyE > emptyE JcrrptysynchsynclsyxvcksyxxhsrxichL' >e«pt/L' ->enptyl/>enpty L -mptyL*-> E synchf->E rel .V > an; tysyncksynchIlisf>I.(list -).(*J<<=!=K-&g

25、t;- E IzE-X E ) Iz%yxv?hcyn-?xsynohsynchsyn?hsyn?hF-” E £re 丁1* ->cnptyF->c«ptyT ->cnptyI? ->cnytyt >onptysyxwX、ynohsynsklynd>ynckl/_>e»p：yl/_>en?ty1/-Xnpty1/ ->«npty1/ >efiptyL/_>«nptyL/_>«nptyB->E reL.B->< B ) Hsynck«y

26、rw*hralop-Xr«lop-><=yolopr«lop->!=EL： st>Z. ELi st->z.因?yàn)轭A(yù)測分析表實(shí)在是過于龐大，因此本處分段截取預(yù)測分析表，下面的表是接在上面表的 右側(cè)。(3) 針對(duì)一測試程序輸出其句法分析結(jié)果；測試程序：百的語法分析結(jié)果:int霊嚴(yán)變量聲明ckar c -string 3 -int 3a0 = 1:/« 狂(a>l) /*分爲(wèi)律吐：廬字符串聲明不«=X聲哺«對(duì)蛆査量的施用吋tken a *3 : |s Ise聊hil匕(忒1)戶嵌套的循環(huán)語句*/do a=a+2;c

27、all addSun (1, 2).戶過程聲明，聲明一策兩羊童 pioc int addSu>(int a, int b) int c, d：c=M變量 之間的賦值盯d = b;letvurn c+d;/*支持返回值以表達(dá)式的形式縊/”記錄聲明榔record mint 3：char c：語法分析結(jié)杲DT (4)X (4) int (4)C(4)digit： 3 id: c (4)A (4)=F (4)G (4)Hdigit： 1 (4),(4)Hdigit： 2 G' (4)、Hdigit: 3 )(4):(4)PS (5)Lid： a L' (5)E (5)digit:

28、 0 (5) =E digit: 1 : PS if B( BELid: a xelop E digit： 1 )(6)then (7)S (7) L (7) id： a (7) 二 EL id： a *E (7) digit: 3 (7) ; else (8)S (9) while (9) B(9)B (9)E (9) Lid： a (9) relop (9) E (9) digit: 1 )(9) do (10) S (10)L (10)id： a (10)=(10)E (10)L (10)id： a (10)E (10)十(10)E (10)digit: 2 (10) :(10)p (1

29、1)s (11)call (11) id： addSum (11) (IDElist (11)E (11)digit： 1 (11)ElistJ (11),(11)E (11)digit: 2 (11)(11):(11)P (13)D (13)pioc (13)T (13)X (13)int (13)id: addSuA (13)(13)M (13)X (13)int (13)id： a (13)(13),(13)X (13)int (13)id: b (13)s (17)letum C17 jE (1?)L (1?)id: u (17)(17)十UT)E C17) L C17) id: d

30、(17):(17)1 ( P (20)C (20) record (20) id： m (20) (20)F (21) r (21)T (21 K (21)int (21) id: a (21) :(21)F (22)D (22) T (22)X (22) char (.22) id; c C22) ;(22)語法分析樹:語法"析樹0-FGEg|曰hE di gi t13 (jSH| 0 digii_2自G曰H曰I * ?s E0E -a u L * E - UL L & r,.s- n LS-= E&-曰-二 - - ：白digi taj- else& Sw

31、hile.Bk(S-B(=|-Ei白l m i jI0-reloph <E) E Q digi t 1；-),do;L< ! E0 L白-id&EL-2自F曰$? call自；d- addSum日.EList（白E digit Ll B-ElisfBE曰F:-proc子T白X5- i ntE) i daddS-umnt 1 i dX iiA.Q PB-Si ©lSidB-E.B* Le-icL aBP.白S 白L日E白LH id列，F(xiàn)白Si- re turn.e e (5 Li ! ©idIJ-Pe sreturn白£白LS idBl III曰-EEJ- L,"L(1reor直idi- mntTs-id日-ij: 1:Q(4) 輸出針對(duì)此測試程序?qū)?yīng)的語法錯(cuò)誤報(bào)告; 帶錯(cuò)誤的測試程序：(5)101112131415161713中圉萬歲戶非法字著X iirt a化/哆了個(gè)乘方憶一 char c = 1 a ;戶字符未封閉可 int 3 G = 1,2,3;頭;嚴(yán)完全錯(cuò)謖的一行啜一. ini d - 0x0 d - if (a>l then /*少 1 a = 09/錯(cuò)誤嗣 else vhile(a<l) do * + 2.0E-:/*錯(cuò)誤郞 call addStm Cl,