【正文】 第一篇：合肥工業(yè)大學編譯原理課程設計關(guān)于《編譯原理》課程設計的有關(guān)說明《編譯原理》是計算機專業(yè)的一門重要的專業(yè)課程，其中包含大量軟件設計思想。大家通過課程設計，實現(xiàn)一些重要的算法，或設計一個完整的編譯程序模型，能夠進一步加深理解和掌握所學知識，對提高自己的軟件設計水平具有十分重要的意義。大家在進行課程設計時，可從所學內(nèi)容中選擇某個主題，抽象成一個模型，可適當進行簡化。也可按提供給大家的一些參考選題進行設計。軟件開發(fā)選擇C/C++語言（也可以是你熟悉的任何語言）。最后每位同學都要認真撰寫設計報告，格式要規(guī)范，內(nèi)容要詳盡，包括：設計題目，設計目的，設計內(nèi)容，設計要求，問題的描述及解決的方法、原理、思想、算法（流程圖），設計的輸入和輸出形式，測試、模擬的結(jié)果（屏幕拷貝、生成結(jié)果的打印輸出），總結(jié)（體會），源程序清單，等等。大家應把該門課的課程設計當成對自己學習效果的一次檢驗，當成是為在大四能夠順利完成畢業(yè)設計的一次基本功訓練。希望每個同學盡可能不要都選擇完全一樣的題目。大家可以自主選題，或選擇我提供的題目，也可以把幾個題目合起來做（如開發(fā)一個小的編譯器）。鼓勵選擇有一定技術(shù)難度、有一定工作量、綜合性較強的題目，在評定成績時將會給予好的成績。編譯原理課程設計部分參考選題： 1． 題目： FORTRAN語言實型常數(shù)識別程序設計設計內(nèi)容及要求： (d)識別FORTRAN實型常數(shù)的狀態(tài)轉(zhuǎn)換圖用程序?qū)崿F(xiàn)。程序能夠從用戶輸入的任意一個字符串中識別出FORTRAN實型常數(shù)，顯示輸出。2． 題目： 簡化的FORTRAN語言詞法分析程序設計設計內(nèi)容及要求：，限制條件如教材所述。保留字的識別按標識符一樣識別，通過查找保留字表區(qū)分是保留字還是標識符。程序能夠從用戶輸入的源程序中，識別出的單詞符號，并用二元式表示，顯示輸出或輸出到文件中。3． 題目： εCLOSURE(I)構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：將εCLOSURE(I)構(gòu)造算法用程序?qū)崿F(xiàn)。要求：對任意第1頁 給定的一個NFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)的某一個狀態(tài)子集I，顯示輸出構(gòu)造出的εCLOSURE(I)。4． 題目： 從右線性文法構(gòu)造與之等價的有限自動機的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一轉(zhuǎn)換程序，實現(xiàn)將用戶任意給定的右線性文法，轉(zhuǎn)換為與之等價的有限自動機FA M，輸出其狀態(tài)轉(zhuǎn)換矩陣（顯示輸出或輸出到文件中）。5． 題目： 從有限自動機構(gòu)造與之等價的右線性文法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一轉(zhuǎn)換程序，實現(xiàn)將用戶任意給定的有限自動機FA M，轉(zhuǎn)換為與之等價的右線性文法，顯示輸出或輸出到文件中。6． 題目： 有限自動機的狀態(tài)轉(zhuǎn)換圖顯示程序的實現(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)：將任一給定的有限自動機M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)，在屏幕上顯示輸出M的狀態(tài)轉(zhuǎn)換圖。程序應具有通用性，狀態(tài)節(jié)點在屏幕上的分布應合理、美觀。7． 題目： 從NFA構(gòu)造與之等價的正規(guī)式r的程序?qū)崿F(xiàn)設計內(nèi)容及要求：對給定的任意NFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息分別保存在指定文件中)。構(gòu)造一程序，從NFA構(gòu)造與之等價的正規(guī)式r，并顯示輸出。8． 題目： 構(gòu)造正規(guī)式r1|r2（或運算）的NFA的程序?qū)崿F(xiàn)設計內(nèi)容及要求：對給定的正規(guī)式rr2，已知它們的NFA分別為MM2(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息分別保存在指定文件中)。構(gòu)造一程序，由此程序構(gòu)造正規(guī)式r1|r2（或運算）的NFA(將其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。9． 題目： 構(gòu)造正規(guī)式r1r2（連接運算）的NFA的程序?qū)崿F(xiàn)設計內(nèi)容及要求：對給定的正規(guī)式rr2，已知它們的NFA分別為MM2(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息分別保存在指定文件中)。構(gòu)造一程序，由此程序構(gòu)造正規(guī)式r1r2（連接運算）的NFA(將其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。10． 題目： 構(gòu)造正規(guī)式r*（閉包運算）的NFA的程序?qū)崿F(xiàn)設計內(nèi)容及要求：對給定的正規(guī)式r，已知其NFA為M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。構(gòu)造一程序，由此程序構(gòu)造正規(guī)式r*（閉包運算）的NFA(將其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。11．題目： 基于語法制導構(gòu)造正規(guī)式的NFA第2頁 設計內(nèi)容及要求：首先構(gòu)造一個語法分析程序，實現(xiàn)對任意正規(guī)式的語法分析。語法分析方法采用自下而上的分析方法（如算符優(yōu)先分析，或LR分析）。在此語法分析器的基礎(chǔ)上，按照語法制導的思想，增加構(gòu)造NFA的功能。生成的NFA將其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中。進一步實現(xiàn)把NFA確定化為DFA 的算法(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。12． 題目： DFA M狀態(tài)最少化的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)：將給定的DFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)的有限狀態(tài)集S劃分成若干互不相交的子集，使得：任何不同的兩個子集中的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的（要利用Ia函數(shù)，但并不需要構(gòu)造εCLOSURE函數(shù)，因這是DFA）。輸出化簡后的DFA M’(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。13． 題目： 把NFA確定化為DFA 的算法實現(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)：將給定的NFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)，確定化為DFA M’。（要先實現(xiàn)εCLOSURE函數(shù)和Ia函數(shù)）。輸出DFA M’(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。14． 題目： 基于貪心算法的DFA 的程序?qū)崿F(xiàn)設計內(nèi)容及要求：，要求從輸入串中匹配最長的子串。輸出所有識別出的符號串及其詞形。15． 題目： 根據(jù)句型的推導構(gòu)造其語法分析樹的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)：接受用戶任意輸入的一個句型的推導序列，生成該句型的語法分析樹并顯示輸出。程序應具有通用性，語法分析樹的節(jié)點在屏幕上的分布要合理、美觀。16． 題目： 從語法分析樹構(gòu)造句型所有的推導的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)：接受用戶任意輸入的一個句型的語法分析樹（其表示存于指定文件中），生成該語法分析樹中包含的該句型的所有推導（顯示輸出）。17． 題目： 遞歸下降分析程序的實現(xiàn) 設計內(nèi)容及要求：對文法 G: E→E+T|T 構(gòu)造出G的遞歸下降分析程序。程序顯示輸出T→T*F|F 匹配過程（即自上而下生成語法分析樹的步驟，F(xiàn)→（E）|i 輸出各匹配產(chǎn)生式序號即可）。18．題目： 集合FIRST(X)構(gòu)造算法的程序?qū)崿F(xiàn)第3頁 設計內(nèi)容及要求：構(gòu)造一程序，(X)集合的構(gòu)造算法。對任一給定的文法G，程序輸出所有非終結(jié)符P的FIRST(P)。19． 題目： 集合FOLLOW(A)構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：首先，構(gòu)造一程序，(X)集合的構(gòu)造算法。對任一給定的文法G，程序輸出所有非終結(jié)符P的FIRST(P)。在此基礎(chǔ)上，構(gòu)造一程序，(A)集合的構(gòu)造算法。對任一給定的文法G，程序輸出所有非終結(jié)符A的FOLLOW(A)。20． 題目： 預測分析表構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：對于給定的一個LL(1)文法，假定所有非終結(jié)符號P的集合FIRST(P)和集合FOLLOW(P)都已知，構(gòu)造其預測分析表（）。程序顯示輸出預測分析表或輸出到指定文件中。21． 題目： 預測分析表自動構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：對于任意輸入的一個LL(1)文法，構(gòu)造其預測分析表。要求：首先實現(xiàn)集合FIRST(X)構(gòu)造算法和集合FOLLOW(A)構(gòu)造算法。程序顯示輸出預測分析表或輸出到指定文件中。22． 題目： 預測分析程序的實現(xiàn) 設計內(nèi)容及要求：對文法 G: E→E+T|T ，T→T*F|F 。F→（E）|i 23． 題目： 集合FIRSTVT(P)構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，(P)集合的構(gòu)造算法。對任一給定的算符文法G，程序輸出所有非終結(jié)符P的FIRSTVT(P)。24． 題目： 集合LASTVT(P)構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，(P)集合的構(gòu)造算法。對任一給定的算符文法G，程序輸出所有非終結(jié)符P的LASTVT(P)。25． 題目： 算符優(yōu)先分析算法的程序?qū)崿F(xiàn) 設計內(nèi)容及要求：對文法 G: E→E+T|T ，T→T*F|F 分析算法。程序顯示輸出“移進歸約”的步驟。F→P↑F|P第4頁 P→（E）|i 26． 題目： 帶出錯處理的算符優(yōu)先分析算法的程序?qū)崿F(xiàn) 設計內(nèi)容及要求：對文法 G: E→E+T|T ，T→T*F|F 分析算法。程序顯示輸出“移進歸約”的步驟。F→(E)|i 要編制各出錯處理子程序。27． 題目： 優(yōu)先表構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求： 。對任一給定的算符優(yōu)先文法G，假定所有非終結(jié)符P的FIRSTVT(P)、LASTVT(P)均已知。28． 題目： 優(yōu)先表自動構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：對任一給定的算符優(yōu)先文法G，構(gòu)造其優(yōu)先表。要求：首先實現(xiàn)對于非終結(jié)符P的FIRSTVT(P)構(gòu)造算法和LASTVT(P)構(gòu)造算法。29． 題目： 優(yōu)先函數(shù)構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)：根據(jù)優(yōu)先關(guān)系表構(gòu)造優(yōu)先函數(shù)。輸入的優(yōu)先表假定保存在指定文件中，構(gòu)造出的優(yōu)先函數(shù)可顯示輸出，或輸出到指定文件中。30． 題目： 消除左遞歸算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序。對于用戶任意輸入的文法G，輸出一個無左遞歸的等價文法，可顯示輸出，或輸出到指定文件中。31． 題目： 消除回溯算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)：消除文法每一條產(chǎn)生式候選式的公共左因子。對于用戶任意輸入的文法G，輸出一個無回溯的等價文法，可顯示輸出，或輸出到指定文件中。32． 題目： LR分析器總控程序的實現(xiàn)設計內(nèi)容及要求：。，對于輸入串i*i+i，輸出LR分析器的工作過程。33． 題目： 識別文法活前綴的NFA構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，對任意給定的文法G：①構(gòu)造并輸出G的所有LR(0)項目；②用這些LR(0)項目構(gòu)造并輸出識別文法活前綴的NFA(輸出其第5頁 狀態(tài)轉(zhuǎn)換矩陣)。34． 題目： LR(0)項目集規(guī)范族構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，對任意給定的文法G，構(gòu)造識別文法活前綴的DFA，輸出DFA的狀態(tài)轉(zhuǎn)化矩陣及LR(0)項目集規(guī)范族。(G’)構(gòu)造，要實現(xiàn)CLOSURE(I)、GO(I,X)函數(shù)。，可輸出到指定文件中。35． 題目： LR(0)分析表構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求： 構(gòu)造一程序，實現(xiàn)LR(0)分析表構(gòu)造算法。，(0)分析表，可輸出到指定文件中。36． 題目： LR(0)分析器自動構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：對任意給定的文法G，構(gòu)造識別文法活前綴的DFA，輸出DFA的狀態(tài)轉(zhuǎn)化矩陣及LR(0)項目集規(guī)范族；實現(xiàn)LR(0)分析表構(gòu)造算法；實現(xiàn)LR分析器總控程序。程序輸出一個完整的LR(0)分析器源程序，可輸出到指定文件中。37． 題目： SLR(1)分析表構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)SLR(1)分析表構(gòu)造算法(假定所給文法識別文法活前綴的DFA、LR(0)項目集族、所有非終結(jié)符FOLLOW集合均已構(gòu)造出來了)。，構(gòu)造其SLR(1)分析表。38． 題目： LR(1)項目集規(guī)范族構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，對任意給定的文法G構(gòu)造LR(1)項目集規(guī)范族（，要實現(xiàn)CLOSURE(I)、GO(I,X)，）。39． 題目： LR(1)分析表構(gòu)造算法的程序?qū)崿F(xiàn)設計內(nèi)容及要求：構(gòu)造一程序，實現(xiàn)LR(1)分析表構(gòu)造算法(假定所給文法識別文法活前綴的DFA、LR(1)項目集族已構(gòu)造出來了)。(1)項目集族和GO函數(shù)為輸入，構(gòu)造并輸出其LR(1)。40． 題目： LR(1)分析表自動構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：對任意給定的文法G構(gòu)造LR(1)項目集規(guī)范族（，要求實現(xiàn)CLOSURE(I)、GO(I,X)、FIRST（）；然后實現(xiàn)LR(1)分析表構(gòu)造算法。，構(gòu)造并輸出其LR(1)。第6頁 41． 題目： LALR(1)項目集規(guī)范族構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：假設對于給定文法，識別文法活前綴的DFA、LR(1)項目集族已構(gòu)造出來了。構(gòu)造一程序，檢查兩個LR(1)項目集是否為同心集（可任意輸入），若是，則輸出合并后的同心集，并檢查合并后的集合是否含有沖突項目（指出存在何種沖突），輸出合并同心集后的識別文法活前綴的DFA，及LALR(1)項目集規(guī)范族。42． 題目： LALR(1)分析表自動構(gòu)造程序的實現(xiàn)設計內(nèi)容及要求：對任意給定的文法G構(gòu)造LR(1)項目集規(guī)范族（，要求實現(xiàn)CLOSURE(I)、GO(I,X)、FIRST（）；然后構(gòu)造LALR(1)項目集規(guī)范族；再實現(xiàn)LALR(1)分析表構(gòu)造算法。，構(gòu)造并輸出其LALR(1)。43． 題目： 帶出錯處理的LR分析器總控程序的實現(xiàn)設計內(nèi)容及要求：，輸出語法分析過程（），要構(gòu)造各出錯處理子程序。44． 題目： 算術(shù)表達式從中綴式翻譯成后綴式的程序?qū)崿F(xiàn)設計內(nèi)容及要求：設計一個語法制導翻譯器，將算術(shù)表達式從中綴式翻譯成后綴式。要求：先確定一個定義算術(shù)表達式的文法，為其設計一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導翻譯方法，實現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達式，程序?qū)⑵滢D(zhuǎn)換成后綴式輸出。45． 題目：將算術(shù)表達式轉(zhuǎn)換成抽象語法樹的程序?qū)崿F(xiàn)設計內(nèi)容及要求：設計一個語法制導翻譯器，將算術(shù)表達式轉(zhuǎn)換成抽象語法樹。要求：先確定一個定義算術(shù)表達式的文法，為其設計一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導翻譯方法，實現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達式，程序?qū)⑵滢D(zhuǎn)換成抽象語法樹輸出(可按一定格式輸出到指定文件中)。46． 題目：將算術(shù)表達式轉(zhuǎn)換成DAG的程序?qū)崿F(xiàn)設計內(nèi)容及要求：設計一個語法制導翻譯器，將算術(shù)表達式轉(zhuǎn)換成DAG。要求：先確定一個定義算術(shù)表達式的文法，為其設計一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導翻譯方法，實現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達式，程序?qū)⑵滢D(zhuǎn)換成D