<tt id="iwmsi"></tt>
  • <xmp id="iwmsi">
  • 編譯原理課程設計指導書(含參考選題)(2016版) - 下載本文

    《 編 譯 原 理 》

    課 程 設 計 指 導 書

    李宏芒 編 寫

    適用專業:計算機科學與技術

    合肥工業大學計算機與信息學院

    2016年 6月

    第1頁

    《編譯原理》是計算機專業的一門重要的專業課程,其中包含大量軟件設計

    思想。大家通過課程設計,實現一些重要的算法,或設計一個完整的編譯程序模型,能夠進一步加深理解和掌握所學知識,對提高自己的軟件設計水平具有十分重要的意義。課程設計的內容主要包括:

    ? 詞法分析。利用狀態轉換圖設計詞法分析器。從正規式構造非確定有限自動

    機(NFA)。用子集法把非確定有限自動機(NFA)確定化為確定有限自動機(DFA)。確定有限自動機(DFA)狀態最少化。

    ? 語法分析。自上而下分析。遞歸子程序分析和預測分析。自下而上分析。算

    符優先分析法和LR分析程序。

    ? 語義分析和中間代碼產生。基于一遍掃描的語法制導翻譯方法。算術表達式、

    賦值語句、布爾表達式、控制語句等語法單位的翻譯模式。

    大家在進行課程設計時,可以選擇本指導書提供給大家的一些參考選題,或者可以從上述課程設計的內容中選擇某個主題,抽象成一個模型,以確定自己的設計題目,上機完成軟件開發。軟件開發可選擇C++、C#、Java等語言(也可以是你熟悉的任何語言)。

    最后每位同學都要認真撰寫課程設計報告,格式要規范,內容要詳盡,

    主要包括:

    ? 設計題目(封面含姓名、學號等), ? 設計目的及設計要求

    ? 設計內容(問題的描述及解決的方法)、主要算法描述(流程圖), ? 設計的輸入和輸出形式

    ? 程序運行(測試、模擬)的結果(屏幕拷貝、生成結果的打印輸出), ? 總結(體會)

    ? 源程序清單(部分核心代碼)作為報告的附件。

    希望每個同學盡可能不要都選擇完全一樣的題目(原則上同一個班學生不重復選題)。大家可以自主選題,或選擇本指導書提供的題目,也可以把幾個題目合起來做以增加工作量或難度(如開發一個小的編譯器等)。鼓勵選擇有一定技術難度、有一定工作量、綜合性較強的題目,在評定成績時將會給予好的成績。

    第2頁

    編譯原理課程設計部分參考選題: 1. 題目: FORTRAN語言實型常數識別程序設計

    設計內容及要求: 將教材P.41的圖3.2(d)識別FORTRAN實型常數的狀態

    轉換圖用程序實現。程序能夠從用戶輸入的任意一個字符串中識別出FORTRAN實型常數,顯示輸出。

    2. 題目: 簡化的FORTRAN語言詞法分析程序設計

    設計內容及要求:將教材P.42上的表3.1的詞法分析器構造出來,限制

    條件如教材所述。保留字的識別按標識符一樣識別,通過查找保留字表區分是保留字還是標識符。程序能夠從用戶輸入的源程序中,識別出的單詞符號,并用二元式表示,顯示輸出或輸出到文件中。

    3. 題目: ε-CLOSURE(I)構造算法的程序實現

    設計內容及要求:將ε-CLOSURE(I)構造算法用程序實現。要求:對任意

    給定的一個NFA M(其狀態轉換矩陣及初態、終態信息保存在指定文件中)的某一個狀態子集I,顯示輸出構造出的ε-CLOSURE(I)。

    4. 題目: 從右線性文法構造與之等價的有限自動機的程序實現

    設計內容及要求:構造一轉換程序,實現將用戶任意給定的右線性文法,

    轉換為與之等價的有限自動機FA M,輸出其狀態轉換矩陣(顯示輸出或輸出到文件中)。

    5. 題目: 從有限自動機構造與之等價的右線性文法的程序實現

    設計內容及要求:構造一轉換程序,實現將用戶任意給定的有限自動機FA

    M,轉換為與之等價的右線性文法,顯示輸出或輸出到文件中。 6. 題目: 有限自動機的狀態轉換圖顯示程序的實現

    設計內容及要求:構造一程序,實現:將任一給定的有限自動機M(其狀態

    轉換矩陣及初態、終態信息保存在指定文件中),在屏幕上顯示輸出M的狀態轉換圖。程序應具有通用性,狀態節點在屏幕上的分布應合理、美觀。 7. 題目: 從NFA構造與之等價的正規式r的程序實現

    設計內容及要求:對給定的任意NFA M(其狀態轉換矩陣及初態、終態信息

    分別保存在指定文件中)。構造一程序,從NFA構造與之等價的正規式r,并顯示輸出。

    8. 題目: 構造正規式r1|r2(或運算)的NFA的程序實現

    設計內容及要求:對給定的正規式r1、r2,已知它們的NFA分別為M1、

    M2(其狀態轉換矩陣及初態、終態信息分別保存在指定文件中)。構造一程序,由

    第3頁

    此程序構造正規式r1|r2(或運算)的NFA(將其狀態轉換矩陣及初態、終態信息保存在指定文件中)。

    9. 題目: 構造正規式r1r2(連接運算)的NFA的程序實現

    設計內容及要求:對給定的正規式r1、r2,已知它們的NFA分別為M1、

    M2(其狀態轉換矩陣及初態、終態信息分別保存在指定文件中)。構造一程序,由此程序構造正規式r1r2(連接運算)的NFA(將其狀態轉換矩陣及初態、終態信息保存在指定文件中)。 10.

    題目: 構造正規式r*(閉包運算)的NFA的程序實現

    設計內容及要求:對給定的正規式r,已知其NFA為M(其狀態轉換矩陣及

    初態、終態信息保存在指定文件中)。構造一程序,由此程序構造正規式r*(閉包運算)的NFA(將其狀態轉換矩陣及初態、終態信息保存在指定文件中)。 11.

    題目: 基于語法制導構造正規式的NFA

    設計內容及要求:首先構造一個語法分析程序,實現對任意正規式的語法

    分析。語法分析方法采用自下而上的分析方法(如算符優先分析,或LR分析)。在此語法分析器的基礎上,按照語法制導的思想,增加構造NFA的功能。生成的NFA將其狀態轉換矩陣及初態、終態信息保存在指定文件中。進一步實現把NFA確定化為DFA 的算法(其狀態轉換矩陣及初態、終態信息保存在指定文件中)。 12.

    題目: DFA M狀態最少化的程序實現

    設計內容及要求:構造一程序,實現:將給定的DFA M(其狀態轉換矩陣及

    初態、終態信息保存在指定文件中)的有限狀態集S劃分成若干互不相交的子集,使得:任何不同的兩個子集中的狀態都是可區別的,而同一子集中的任何兩個狀態都是等價的(要利用Ia函數,但并不需要構造ε-CLOSURE函數,因這是DFA)。輸出化簡后的DFA M’(其狀態轉換矩陣及初態、終態信息保存在指定文件中)。 13.

    題目: 把NFA確定化為DFA 的算法實現

    設計內容及要求:構造一程序,實現:將給定的NFA M(其狀態轉換矩陣及

    初態、終態信息保存在指定文件中),確定化為DFA M’。(要先實現ε-CLOSURE函數和Ia函數)。輸出DFA M’(其狀態轉換矩陣及初態、終態信息保存在指定文件中)。 14.

    題目: 基于貪心算法的DFA 的程序實現

    設計內容及要求:采用貪心算法實現教材P.62表3.5的DFA,要求從輸入

    串中匹配最長的子串。輸出所有識別出的符號串及其詞形。 15.

    題目: 根據句型的推導構造其語法分析樹的程序實現

    第4頁

    設計內容及要求:構造一程序,實現:接受用戶任意輸入的一個句型的推

    導序列,生成該句型的語法分析樹并顯示輸出。程序應具有通用性,語法分析樹的節點在屏幕上的分布要合理、美觀。 16.

    題目: 從語法分析樹構造句型所有的推導的程序實現

    設計內容及要求:構造一程序,實現:接受用戶任意輸入的一個句型的語

    法分析樹(其表示存于指定文件中),生成該語法分析樹中包含的該句型的所有推導(顯示輸出)。 17.

    題目: 遞歸下降分析程序的實現 設計內容及要求:

    對文法 G: E→E+T|T 構造出G的遞歸下降分析程序。程序顯示輸出

    T→T*F|F 匹配過程(即自上而下生成語法分析樹的步驟,

    F→(E)|i 輸出各匹配產生式序號即可)。

    18.

    題目: 集合FIRST(X)構造算法的程序實現

    設計內容及要求:構造一程序,實現教材P.78的FIRST(X)集合的構造算

    法。對任一給定的文法G,程序輸出所有非終結符P的FIRST(P)。 19.

    題目: 集合FOLLOW(A)構造算法的程序實現

    設計內容及要求:首先,構造一程序,實現教材P.78的FIRST(X)集合的

    構造算法。對任一給定的文法G,程序輸出所有非終結符P的FIRST(P)。在此基礎上,構造一程序,實現教材P.79的FOLLOW(A)集合的構造算法。對任一給定的文法G,程序輸出所有非終結符A的FOLLOW (A)。 20.

    題目: 預測分析表構造算法的程序實現

    設計內容及要求:對于給定的一個LL(1)文法,假定所有非終結符號P的

    集合FIRST(P)和集合FOLLOW(P)都已知,構造其預測分析表(實現教材P.79給出的預測分析表構造算法)。對教材P.79給出的例4.7構造出預測分析表。程序顯示輸出預測分析表或輸出到指定文件中。 21.

    題目: 預測分析表自動構造程序的實現

    設計內容及要求:對于任意輸入的一個LL(1)文法,構造其預測分析表。

    要求:首先實現集合FIRST(X)構造算法和集合FOLLOW(A)構造算法,再實現教材P.79給出的預測分析表構造算法。程序顯示輸出預測分析表或輸出到指定文件中。 22.

    題目: 預測分析程序的實現 設計內容及要求:

    對文法 G: E→E+T|T 按教材P.76表4.1構造出G的預測分析程序,

    第5頁





    白小姐结果开奖结果小说