編譯原理實驗報告-語法分析

編譯原理課程實驗報告實驗2：語法分析姓名趙璐媛院系軟件學(xué)院學(xué)號1143710516任課教師陳鄞指導(dǎo)教師陳鄞實驗地點軟件學(xué)院三樓機房實驗時間10月30日78節(jié)實驗課表現(xiàn)出勤、表現(xiàn)得分實驗報告得分實驗總分操作結(jié)果得分一、需求分析得分要求：采用至少一種句法分析技術(shù)（LL(1)、SLR(1)、LR(1)或LALR(1)）對類高級語言中的基本語句進行句法分析。闡述句法分析系統(tǒng)所要完成的功能。語法分析器使用LL(1)進行語法分析（1）能識別以下幾類語句：聲明語句（包括變量聲明、數(shù)組聲明、記錄聲明和過程聲明）表達式及賦值語句（包括數(shù)組元素的引用和賦值）分支語句：if_then_else循環(huán)語句：do_while過程調(diào)用語句（2）自動計算FIRST集和FOLLOW集，并自動生成預(yù)測分析表。（3）具備語法錯誤處理能力，能準(zhǔn)確給出錯誤所在位置，并采用可行的錯誤恢復(fù)策略。輸出的錯誤提示信息格式如下：ErroratLine[行號]：[說明文字]（4）系統(tǒng)的輸入形式：要求可以通過文件導(dǎo)入文法和測試用例，可以通過用戶界面顯示并編輯測試用例。（5）系統(tǒng)的輸出分為兩部分：一部分是打印輸出語法分析器的FIRST集、FOLLOW集和LL(1)分析表。另一部分是打印輸出語法分析結(jié)果。二、文法設(shè)計得分要求：給出如下語言成分的文法描述。聲明語句（包括變量聲明、數(shù)組聲明、記錄聲明和過程聲明）表達式及賦值語句（包括數(shù)組元素的引用和賦值）分支語句：if_then_else循環(huán)語句：do_while過程調(diào)用語句P?D //參見教材p229P?S //參見教材p241 S?SS //參見教材p241/*聲明*/D?DD|procid;DS|Tid; //參見講義第7章 T→XC|recordD //參見教材p227 X→int|real //參見教材p227C→[E]C|ε //參見教材p227/*賦值語句*/S?id=E;|L=E; //參見教材p234E?E+E|E*E|-E|(E)|id|digit|L //參見教材p234L?id[E]|L[E] //參見教材p234/*控制流語句*/S?ifBthenS1 //參見教材p241|ifBthenS1elseS2 //參見教材p241 |doS1whileB //參見教材p241B→BorB //參見教材p243 |BandB //參見教材p243 |notB //參見教材p243 |(B) //參見教材p243 |EopE //參見教材p243 |true //參見教材p243 |false //參見教材p243op→<|<=|==|!=|>|>= //參見教材p240/*過程調(diào)用*/S?callid(Elist) //參見講義第6章Elist?Elist,E //參見講義第6章Elist?E //參見講義第6章消除左遞歸和二義性后文法如下：P->S'|D/*聲明*/D->Tid;D'|procid;DS'D'D'->DD'|εT->XC|recordDX->int|realC->[E]C|ε/*控制流語句*/S->L=E;|callid(Elist);|ifBthenSEL|doS'whileBEL->ε|elseSS'->SS'|εB->notBB'|(B)B'|EOPEB'|trueB'|falseB'B'->orBB'|andBB'|εOP-><|<=|==|!=|>|>=/*過程調(diào)用*/Elist->EElist'Elist'->,EElist'|ε/*賦值語句*/E->FE'E'->+FE'|εF->GF'F'->*GF'|εG->-G|(E)|digit|LL->idL'L'->[E]L'|ε三、系統(tǒng)設(shè)計得分要求：分為系統(tǒng)概要設(shè)計和系統(tǒng)詳細設(shè)計。（1）系統(tǒng)概要設(shè)計：給出必要的系統(tǒng)宏觀層面設(shè)計圖，如系統(tǒng)框架圖、數(shù)據(jù)流圖、功能模塊結(jié)構(gòu)圖等以及相應(yīng)的文字說明。（2）系統(tǒng)詳細設(shè)計：對如下工作進行展開描述核心數(shù)據(jù)結(jié)構(gòu)的設(shè)計主要功能函數(shù)說明程序核心部分的程序流程圖系統(tǒng)概要設(shè)計系統(tǒng)的設(shè)計類圖如下：（建議放大查看）在選擇了DFA文件、語法文件和代碼文件后，點擊分析按鈕，1）由DFAView生成DFA實例，由SyntaxView生成LL實例并打印fist集、follow集、預(yù)測分析表；2）調(diào)用DFA實例的doDFA方法對CodeView中的代碼進行分析；3）調(diào)用LL實例的getTree方法對2）產(chǎn)生的結(jié)果進行分析，得到語法樹和錯誤信息；4）調(diào)用語法樹的printTree方法得到字符串表示，調(diào)用OutputView的setTextLabel方法打印語法樹和錯誤信息。系統(tǒng)詳細設(shè)計系統(tǒng)的核心類是LL類，LL類中實現(xiàn)了first集、follow集、預(yù)測分析表的生成過程，以及使用預(yù)測分析表對語法進行分析的過程。first集數(shù)據(jù)結(jié)構(gòu)是Map<String,Set<String>>，map的key是終結(jié)符或語法變量，value是一個set，即first(key)。生成過程見LL.getFirst()。follow集數(shù)據(jù)結(jié)構(gòu)是Map<String,Set<String>>，map的key是終結(jié)符或語法變量，value是一個set，即follow(key)。生成過程見LL.getFollow()。預(yù)測分析表數(shù)據(jù)結(jié)構(gòu)是Map<String,Map<String,String[]>>，舉例說明，若table(X,a)為X->Y1Y2，則table.get(X).get(a)為String[]類型，記做temp，則temp[0]=Y1temp[1]=Y2。生成過程見LL.getTable()。分析過程分析過程見下圖，其中P是語法樹根，同時也是棧中最初的元素。四、系統(tǒng)實現(xiàn)及結(jié)果分析得分要求：對如下內(nèi)容展開描述。系統(tǒng)實現(xiàn)過程中遇到的問題；輸出該句法分析器的分析表；針對一測試程序輸出其句法分析結(jié)果；輸出針對此測試程序?qū)?yīng)的語法錯誤報告；對實驗結(jié)果進行分析。注：其中的測試樣例需先用已編寫的詞法分析程序進行處理。遇到問題：指導(dǎo)書中給出的文法有二義性和左遞歸，直接使用預(yù)測分析法進行分析會導(dǎo)致程序無限循環(huán)或不能正確分析。解決方法：改寫文法，消除其中的二義性和左遞歸。程序打印預(yù)測分析表如下：為方便查看，導(dǎo)入到excel中如下所示：（建議放大查看）測試程序：分析結(jié)果：錯誤報告：結(jié)果分析：源程序第1-4行是不同種類的聲明語句，從分析結(jié)果圖一可看到最終都規(guī)約為語法變量D。源程序第5-7行是不同種類的賦值語句，從圖二可