第一篇:編譯原理課程設(shè)計(jì)任務(wù)
編譯原理課程設(shè)計(jì)任務(wù)
1設(shè)計(jì)報(bào)告的規(guī)范和要求
設(shè)計(jì)任務(wù)完成后寫出實(shí)踐報(bào)告。實(shí)踐報(bào)告包括程序設(shè)計(jì)時(shí)考慮的算法和方法;調(diào)試過程中出現(xiàn)的問題和解決的措施;打印出程序清單和調(diào)試時(shí)所用的源程序。
2題目
詞法分析器;語法分析器;
詞法分析器的輸出作為語法分析器的輸入。
3算法
算法:選擇最有代表性的語法分析方法,如算符優(yōu)先法、遞歸子程序法和LR分析法;選擇對(duì)各種常見程序語言都用的語法結(jié)構(gòu),如賦值語句,特別是表達(dá)式,作為分析對(duì)象,并且與所選語法分析方法要比較貼切。
語言:選用 C/C++ 語言的一個(gè)子集。
輸出:對(duì)于所輸入的算術(shù)表達(dá)式,不論對(duì)錯(cuò),都應(yīng)有明確的信息告訴外界。算術(shù)表達(dá)式中變量名可以是一般標(biāo)識(shí)符,還可含一般常數(shù)、數(shù)組元素、函數(shù)調(diào)用等等。除算術(shù)表達(dá)式外,還可擴(kuò)充分析布爾、字符、位等不同類型的各種表達(dá)式。加強(qiáng)語法檢查,盡量多和確切地指出各種錯(cuò)誤。
更詳細(xì)的內(nèi)容可參考《編譯原理》實(shí)驗(yàn)指導(dǎo)。
第二篇:編譯原理課程設(shè)計(jì)
課 程 設(shè) 計(jì) 報(bào) 告
設(shè)計(jì)題目:一個(gè)簡(jiǎn)單文法的編譯器前端的設(shè)計(jì)與實(shí)現(xiàn)
班
級(jí): 計(jì)算機(jī)1206 組長(zhǎng)學(xué)號(hào):201239 組長(zhǎng)姓名:閆智宣 指導(dǎo)教師:李曉華 設(shè)計(jì)時(shí)間:2014年12月
[在此處鍵入]
設(shè)計(jì)分工
組長(zhǎng)學(xué)號(hào)及姓名: 20123974
閆智宣
分工:
語法分析,四元式生成,目標(biāo)代碼優(yōu)化及生成 組員1學(xué)號(hào)及姓名:20123977
廖峭 分工:
詞法分析,錯(cuò)誤處理 組員2學(xué)號(hào)及姓名:20123959
郭天龍
分工:
符號(hào)表生成,語義動(dòng)作插入,操作界面[在此處鍵入]
摘要
編譯原理課程設(shè)計(jì)是通過C語言編譯器相關(guān)子系統(tǒng)的設(shè)計(jì),進(jìn)一步加深對(duì)編譯器構(gòu)造的理解;第一部分詞法分析,設(shè)計(jì)各單詞的狀態(tài)轉(zhuǎn)換圖,并為不同的單詞設(shè)計(jì)種別碼,制作掃描器識(shí)別一個(gè)個(gè)單詞,返回值為識(shí)別碼的序號(hào),返回Token序列。將詞法分析器設(shè)計(jì)成供語法分析器調(diào)用的子程序。詞法分析器具備預(yù)處理功能。將不翻譯的注釋等符號(hào)先濾掉,只保留要翻譯的符號(hào)串,即要求設(shè)計(jì)一個(gè)供詞法分析調(diào)用的預(yù)處理子程序;第二部分,語法分析,用遞歸下降法,實(shí)現(xiàn)對(duì)表達(dá)式、各種說明語句、控制語句進(jìn)行語法分析。若語法正確,則用語法制導(dǎo)翻譯法進(jìn)行語義翻譯;生成并打印出語法樹;若語法錯(cuò)誤,要求指出出錯(cuò)性質(zhì)和出錯(cuò)位置(行號(hào))。
我們還做了附加功能,即編譯后端,有中間代碼優(yōu)化,生成目標(biāo)代碼匯編語言。通過此次課程設(shè)計(jì),提高了我們的獨(dú)立分析問題、解決問題的能力,以及系統(tǒng)軟件設(shè)計(jì)的能力; 提高程序設(shè)計(jì)能力、程序調(diào)試能力,團(tuán)結(jié)協(xié)作能力
關(guān)鍵詞:詞法分析,語法分析,四元式生成,錯(cuò)誤處理,符號(hào)表生成,語義動(dòng)作插入,中間代碼優(yōu)化,生成目標(biāo)代碼 [在此處鍵入]
目錄
摘要
1.概述
2.課程設(shè)計(jì)任務(wù)及要求
2.1 設(shè)計(jì)任務(wù)
2.2 設(shè)計(jì)要求
3.算法及數(shù)據(jù)結(jié)構(gòu)
3.1算法的總體思想(流程)
3.2 詞法分析模塊
3.2.1 功能
3.2.2 數(shù)據(jù)結(jié)構(gòu)
3.2.3 算法
3.3 語法分析模塊
3.3.1功能
3.3.2 數(shù)據(jù)結(jié)構(gòu)
3.3.3算法
3.4 符號(hào)表模塊
3.4.1功能
3.4.2 數(shù)據(jù)結(jié)構(gòu)
3.4.3算法
3.5 四元式模塊
3.5.1功能
[在此處鍵入]
3.5.2 數(shù)據(jù)結(jié)構(gòu)
3.5.3算法
3.6 語義動(dòng)作分析模塊
3.6.1功能 3.6.2 數(shù)據(jù)結(jié)構(gòu)
3.6.3算法
3.7 錯(cuò)誤處理模塊
3.7.1功能
3.7.2 數(shù)據(jù)結(jié)構(gòu)
3.7.3算法
3.8 目標(biāo)代碼模塊
3.8.1功能
3.8.2 數(shù)據(jù)結(jié)構(gòu)
3.8.3算法
4.程序設(shè)計(jì)與實(shí)現(xiàn)
4.1 程序流程圖
4.2 程序說明
4.3 實(shí)驗(yàn)結(jié)果
5.結(jié)論 6.參考文獻(xiàn)。7.收獲、體會(huì)和建議。
[在此處鍵入]
1.概述
編譯器是將C語言翻譯為匯編語言代碼的計(jì)算機(jī)程序。編譯器將源程序(source language)編寫的程序作為輸入,翻譯產(chǎn)生目標(biāo)語言(target language)機(jī)器代碼的等價(jià)程序。通常地,源程序?yàn)楦呒?jí)語言(high-level language),C語言程序,而目標(biāo)則是 機(jī)器語言的目標(biāo)代碼(object code),也就是可以在計(jì)算機(jī)硬件中運(yùn)行的機(jī)器代碼軟件程序。這一過程可以表示為:
源程序→編譯器 →目標(biāo)機(jī)器代碼程序
2.課程設(shè)計(jì)任務(wù)及要求
2.1設(shè)計(jì)任務(wù)
學(xué)生在學(xué)習(xí)《編譯原理》課程過程中,結(jié)合各章節(jié)的構(gòu)造編譯程序的基本理論,要求用C#語言描述及上機(jī)調(diào)試,實(shí)現(xiàn)一個(gè) C編譯程序(包括詞法分析,語法分析等重要子程序),使學(xué)生將理論與實(shí)際應(yīng)用結(jié)合起來,受到軟件設(shè)計(jì)等開發(fā)過程的全面訓(xùn)練,從而提高學(xué)生軟件開發(fā)的能力。
2.2設(shè)計(jì)要求 要求:
(1)設(shè)計(jì)詞法分析器
設(shè)計(jì)各單詞的狀態(tài)轉(zhuǎn)換圖,并為不同的單詞設(shè)計(jì)種別碼。將詞法分析器設(shè)計(jì)成供語法分析器調(diào)用的子程序。功能包括:
a.具備預(yù)處理功能。將不翻譯的注釋等符號(hào)先濾掉,只保留要翻譯的符號(hào)串,即要求設(shè)計(jì)一個(gè)供詞法分析調(diào)用的預(yù)處理子程序;
b.能夠拼出語言中的各個(gè)單詞; [在此處鍵入]
c.返回(種別碼,屬性值,行號(hào))。
(2)語法分析
要求用學(xué)習(xí)過的自底向上或自頂向下的分析方法等,實(shí)現(xiàn)對(duì)表達(dá)式、各種說明語句、控制語句進(jìn)行語法分析。若語法正確,則用語法制導(dǎo)翻譯法進(jìn)行語義翻譯;生成并打印出語法樹;若語法錯(cuò)誤,要求指出出錯(cuò)性質(zhì)和出錯(cuò)位置(行號(hào))。
3.算法及數(shù)據(jù)結(jié)構(gòu)
3.1算法的總體思想(流程)
本節(jié)主要分析程序的代碼結(jié)構(gòu)和代碼工程文件的劃分。(程序由幾個(gè)類組成: Token類和Variable類SymbolTable類ObjectCode類Lexical類Grammar類Four_Yuan類Action類ErrorItem類,分別為詞法分析和語法分析類。工程分為幾個(gè)文件:Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs分別對(duì)應(yīng)Token類和Variable類SymbolTable類ObjectCode類Lexical類Grammar類Four_Yuan類Action類ErrorItem類的聲明和實(shí)現(xiàn)文件)。本程序采用C#語言以面向?qū)ο蟮乃枷刖帉懀绦蚍譃閹撞糠郑涸~法分析(Lexical),語法分析(Grammer),目標(biāo)代碼生成(ObjectCode)。Lexical類主要的工作是詞法分析獲取Token。Grammer類的主要工作是根據(jù)Lexical類詞法分析之后的Token進(jìn)行語法分析,生成語法樹,最后并輸出語法樹。在處理過程中,Token類的對(duì)象作為L(zhǎng)exical類的一個(gè)成員變量,配合Grammer類進(jìn)行語法分析。
工程文件總體上是按照九個(gè)類的格局分為十個(gè)文件,分別是九個(gè)類的聲明文件和實(shí)現(xiàn)文件。十個(gè)文件為Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs,他們分別是Lexical類聲明文件、Lexical類實(shí)現(xiàn)文件、Grammer類聲明文件、Grammer類實(shí)現(xiàn)文件。[在此處鍵入]
程序流程
在程序中,Lexical類的對(duì)象(Token)作為Grammer類中的一個(gè)成員變量,配合Grammer類進(jìn)行語法分析。它們的關(guān)系是這樣的:Grammer類的一個(gè)成員變量temp首先對(duì)源程序刪除注釋,然后進(jìn)行詞法分析獲取所有Token,并將獲取的Token存儲(chǔ)在Token對(duì)象的tokenList(List類型)中。然后Grammer類的語法分析程序就根據(jù)tokenList中的Token進(jìn)行語法分析,生成語法樹,最后打印語法樹。同時(shí),這也是程序的流程。[在此處鍵入]
3.2 詞法分析模塊 3.2.1功能
Lexical類主要的工作是詞法分析獲取Token序列。
3.2.2數(shù)據(jù)結(jié)構(gòu)
詞法分析階段的代碼被封裝成一個(gè)類——Lexical,Token中主要是Lexical類的聲明代碼,Lexical.cs中主要是Lexical類的實(shí)現(xiàn)代碼。Lexical類對(duì)外提供的函數(shù)主要有:
static public int RecogId(string str, int i),static public int RecogDig(string str,int i),static public int RecogOperator(string str, int i),static public int RecogBound(string str, int i),以上幾個(gè)函數(shù)構(gòu)成了詞法分析的骨架,在Lexical類中還有其他成員變量和函數(shù),主要作為這三個(gè)函數(shù)處理過程的中間步驟,為這三個(gè)函數(shù)服務(wù)。Lexical類的代碼結(jié)構(gòu)和主要的成員變量和函數(shù)及其含義如下圖所示:
3.2.3算法
算法的基本任務(wù)是從字符串表示的源程序中識(shí)別出具有獨(dú)立意義的單詞符號(hào),其基本思想是[在此處鍵入]
根據(jù)掃描到單詞符號(hào)的第一個(gè)字符的種類,拼出相應(yīng)的單詞符號(hào)。
主程序示意圖:
主程序示意圖如圖3-1所示。
⑴ 關(guān)鍵字表的初值。
關(guān)鍵字作為特殊標(biāo)識(shí)符處理,把它們預(yù)先安排在一張表格中(稱為關(guān)鍵字表),當(dāng)掃描程序識(shí)別出標(biāo)識(shí)符時(shí),查關(guān)鍵字表。如能查到匹配的單詞,則該單詞為關(guān)鍵字,否則為一般標(biāo)識(shí)符。
(2)程序中需要用到的主要變量為type和number 掃描子程序的算法思想:
首先設(shè)置3個(gè)變量: [在此處鍵入]
①token用來存放構(gòu)成單詞符號(hào)的字符串; ②number用來整型單詞;
③type用來存放單詞符號(hào)的種別碼。
Token定義
Token定義:
Token類型(TokenType):
3.3 語法分析模塊
3.3.1功能
語法分析是編譯過程的一個(gè)邏輯階段。語法分析的功能是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語法短語,如“程序”,“語句”,“表達(dá)式”等等.語法分析程序判斷源程序在結(jié)構(gòu)上是否正確.源程序的結(jié)構(gòu)由上下文無關(guān)文法描述.3.3.2 數(shù)據(jù)結(jié)構(gòu)
下圖為實(shí)現(xiàn)語法分析的類Grammar,屬性與方法的作用都已說明 在此處鍵入]
3.3.3算法
1.文法
下面終結(jié)符與非終結(jié)符意義
B程序開始
Z 數(shù)據(jù)類型,如int,char,float等
V 標(biāo)識(shí)符
S 語句
P 語句塊
E 加減算術(shù)表達(dá)式
D 逗號(hào)表達(dá)式
T 乘除算術(shù)表達(dá)式
C 關(guān)系表達(dá)式
L 邏輯表達(dá)式
Q 標(biāo)識(shí)符或圓括號(hào)
e 表示空
i 表示標(biāo)識(shí)符 a)函數(shù)文法
B----ZV()S
[
[在此處鍵入]
b)語句塊文法
P----SP|e
S----{P} c)語句文法
表達(dá)式語句文法
S----V=E
goto語句文法
S----i:S
S----goto i
if語句文法
S----if(E)S[else S]
while語句文法
S----while(E)S
聲明語句文法
S----ZVD
D----,VD|=ED|e d)表達(dá)式文法
E----T|E+T|E-T
T----F|T*F|T/F
C----C|C
L----Q|L&&Q|L||Q
Q----i|(E)|!Q
2.遞歸下降程序流程圖
對(duì)應(yīng)于每個(gè)文法編寫如下遞歸下降子程序
主程序(B)[在此處鍵入] [在此處鍵入]
3.4 符號(hào)表模塊
3.4.1功能
進(jìn)行符號(hào)表的儲(chǔ)存,添加,更新,查找,保存標(biāo)識(shí)符活躍信息以及輸出。3.4.2 數(shù)據(jù)結(jié)構(gòu)
在此處鍵入]
3.4.3算法
3.5 四元式模塊
3.5.1功能
四元式為中間代碼,編譯程序進(jìn)行完語義分析后,先生成中間代碼作為過渡,此時(shí)中間代碼與目標(biāo)代碼已經(jīng)比較相似
3.5.2 數(shù)據(jù)結(jié)構(gòu)
[ 在此處鍵入]
3.5.3算法
3.6語義動(dòng)作分析模塊
3.6.1功能
在語法分析中嵌入相應(yīng)的語義動(dòng)作,生成四元式 3.6.2 數(shù)據(jù)結(jié)構(gòu)
[
[在此處鍵入]
3.6.3算法 GEQ(+)(-)(*)(/)
(+,i1,i2,t)PUSH(i)ASSI(=)
(=,t,_,POP)LABER(i)
(lb,_,_,i)GOTO(i)
(gt,_,_,i)IF(if)
(if,a,_,_)EL(el)
(el,_,_,_)IE(ie)
(ie,_,_,_)WH()
(wh,_,_,_)DO()
(do,a,_,_)WE(we)
(we,_,_,_)
3.7 錯(cuò)誤處理模塊
3.7.1功能 保存運(yùn)行時(shí)發(fā)現(xiàn)的錯(cuò)誤,儲(chǔ)存行號(hào)已經(jīng)詳細(xì)信息并輸出。
3.7.2 數(shù)據(jù)結(jié)構(gòu)
3.7.3算法 [在此處鍵入]
public static void AddErrorMessage(int lineno,string content)函數(shù)用作在發(fā)現(xiàn)錯(cuò)誤時(shí)保存錯(cuò)誤信息以及行號(hào)。
public static string PrintErrorList()把所有發(fā)現(xiàn)的錯(cuò)誤格式化后統(tǒng)一輸出。
錯(cuò)誤信息在語法分析,語義分析,符號(hào)表檢錯(cuò)中添加。3.8 目標(biāo)代碼模塊
3.8.1功能
目標(biāo)代碼生成把優(yōu)化后的中間代碼變換成目標(biāo)代碼,此處的目標(biāo)代碼為匯編代碼,采用單寄存器生成目標(biāo)代碼 3.8.2 數(shù)據(jù)結(jié)構(gòu)[在此處鍵入]
3.8.3算法
對(duì)于一個(gè)基本塊有如下流程圖
W:操作符,B:第一操作數(shù),C:第二操作數(shù),R:寄存器
5.結(jié)論
網(wǎng)上找一段話抄上 [在此處鍵入]
6.測(cè)試
測(cè)試打開文件
測(cè)試保存文件
如果沒打開文件,直接敲代碼,點(diǎn)保存時(shí)會(huì)彈出另存為窗口[在此處鍵入]
測(cè)試錯(cuò)誤檢測(cè),程序缺少main函數(shù)的類型,錯(cuò)誤列表中顯示第一行函數(shù)缺少錯(cuò)誤類型。
測(cè)試錯(cuò)誤檢測(cè),程序缺少分號(hào),錯(cuò)誤列表中顯示該行缺少語句結(jié)束標(biāo)志';' 單擊錯(cuò)誤列表,會(huì)自動(dòng)選定錯(cuò)誤行
編譯成功,生成并顯示token串、符號(hào)表、四元式與目標(biāo)代碼 [在此處鍵入]
測(cè)試if與while語句,而且while嵌套在if當(dāng)中
測(cè)試goto語句,結(jié)果正確。[在此處鍵入]
測(cè)試優(yōu)化,輸入課件中的代碼,結(jié)果與課件一樣
6.參考文獻(xiàn)。
1、陳火旺.《程序設(shè)計(jì)語言編譯原理》(第3版).北京:國(guó)防工業(yè)出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著.李建中,姜守旭譯.《編譯原理》.24 [在此處鍵入]
北京:機(jī)械工業(yè)出版社.2003.3、美 Kenneth C.Louden著.馮博琴等譯.《編譯原理及實(shí)踐》.北京:機(jī)械工業(yè)出版社.2002.4、金成植著.《編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù)》.北京:高等教育出版社.2002.7.收獲、體會(huì)和建議。
直接拷貝好歹也檢查一下錯(cuò)誤
對(duì)于編譯原理的這次課程設(shè)計(jì),自己經(jīng)歷了從剛開始的不懂?明白任務(wù)的要求和內(nèi)容?理論知識(shí)的了解?開始著手寫代碼?完成基本功能?根據(jù)DFA及自頂向下等理論修改完善代碼等這些過程。
自己著手寫詞法分析的時(shí)候還不清楚詞法分析的任務(wù)內(nèi)容,還不知道詞法分析的結(jié)果是什么,詞法分析出錯(cuò)的情況和類型有哪些,也總是將詞法分析和語法分析混在一起,不明白哪些錯(cuò)誤在詞法分析中報(bào),哪些錯(cuò)誤在語法分析中判斷,后來經(jīng)過查書、網(wǎng)上資料、請(qǐng)教同學(xué)等途徑逐步清晰了詞法分析的工作內(nèi)容是從源代碼文件中獲取出Token,供語法分析使用。在充分了解了語法分析需要哪些信息時(shí),我才真正了解了詞法分析的工作內(nèi)容和目標(biāo),才知道詞法分析需要完成哪些任務(wù)獲取到哪些信息。充分了解了詞法分析的任務(wù)之后,就開始理論知識(shí)的學(xué)習(xí)。經(jīng)過揣摩書上的例子,自己理解和掌握了怎么設(shè)計(jì)過濾注釋和分析程序中Token的DFA,于是開始根據(jù)設(shè)計(jì)好的DFA進(jìn)行編碼,最后經(jīng)過調(diào)試已經(jīng)可以正確地完成詞法階段的任務(wù)了。這只是詞法分析的原始代碼,在之后還進(jìn)行了兩次徹底的改動(dòng)。雖然之前寫的詞法分析的代碼已經(jīng)完成了詞法分析的需求,也是根據(jù)DFA的原理編寫的,但是在代碼結(jié)構(gòu)上卻難以體現(xiàn),在對(duì)書上的根據(jù)已知DFA寫代碼的例子進(jìn)行了詳細(xì)的研究之后,發(fā)現(xiàn)自己的代碼并沒有像書上那樣完全按照所依據(jù)的DFA各狀態(tài)轉(zhuǎn)移的關(guān)系進(jìn)行編寫,所以對(duì)代碼進(jìn)行了重寫,像書上一樣嚴(yán)格按照狀態(tài)之間轉(zhuǎn)移的方式進(jìn)行編寫,將狀態(tài)劃分成11個(gè)狀態(tài),狀態(tài)分別按1~11進(jìn)行標(biāo)注,程序也按照DFA來編寫,也實(shí)現(xiàn)了詞法分析的功能。再后來寫報(bào)告的時(shí)候,發(fā)現(xiàn)分析出Token的那個(gè)DFA并不是最簡(jiǎn)的,有很多多余的狀態(tài),完全可以用一個(gè)flag標(biāo)志來標(biāo)識(shí),從而簡(jiǎn)化代碼結(jié)構(gòu),于是又重寫了一次詞法分析函數(shù)scan()的代碼,將狀態(tài)縮減為5個(gè),且不再用1-5來表示,而是像書上那樣分別取了名字(START、INNUM、INID、INDBSYM、DONE),同時(shí)為了簡(jiǎn)化代碼將輸出Token到文件的部分從scan()中剝離開來,而在Lexical類中加了一個(gè)printToken()的函數(shù),使scan()函數(shù)邏輯更加清晰,使讀者能夠容易地將代碼與DFA進(jìn)行查看比照。
在寫語法分析的時(shí)候,已經(jīng)對(duì)編譯器的語法分析的內(nèi)容有了一定的了解,所以直接進(jìn)行了理論的學(xué)習(xí)。首先自己對(duì)遞歸向下分析法進(jìn)行了學(xué)習(xí),將書上的幾個(gè)遞歸向下分析的偽代碼看過之后,自己對(duì)遞歸向下的分析方法的原理有了初步的認(rèn)識(shí),大概知道了根據(jù)文法怎么分析,但是對(duì)于如何編寫代碼卻還在此處鍵入]
是難以下手,于是就對(duì)照TINY語言的文法看了幾遍書后面的TINY語言的遞歸向下分析的語法分析程序,這樣就基本知道了C-語言的語法分析程序怎么寫。由于C-語言給出的文法有左遞歸存在,于是自己將存在左遞歸的文法改寫成EBNF的形式,并據(jù)此進(jìn)行代碼編寫。由于在編寫代碼的過程中需要確定分析是否正確或選擇多個(gè)文法中的某一個(gè)文法進(jìn)行分析,有時(shí)必須探測(cè)需要的或下一個(gè)Token的類型,在這種情況下需要求First集合,在推導(dǎo)中若存在empty,又需要求Follow集合,所以這樣又需要我了解First集合和Follow集合,自己在程序中也根據(jù)求出的First集合和Follow集合進(jìn)行判斷,以確定程序的走向。在編寫過程中,還有一類問題,就是存在公共左因子,如文法expression→ var = expression | simple-expression,左因子為ID,在分析過程中,由于已經(jīng)取出了一個(gè)ID的Token,且生成了一個(gè)IdK的節(jié)點(diǎn),但是在當(dāng)前狀態(tài)無法確定是哪一個(gè)推導(dǎo),然而IdK節(jié)點(diǎn)已經(jīng)生成,又無法回退,并且是使用自頂向下的分析方法,已經(jīng)生成的IdK在程序上方無法使用,自己通過查閱資料等途徑的學(xué)習(xí)確定了在這種情形下的處理方式:將已經(jīng)生成的IdK節(jié)點(diǎn)傳到下方的處理程序,所以TreeNode * simple_expression(TreeNode * k)、TreeNode * additive_expression(TreeNode * k)等函數(shù)都被設(shè)計(jì)成有節(jié)點(diǎn)類型參數(shù)的函數(shù),目的就是將已經(jīng)生成的節(jié)點(diǎn)傳到下面的分析函數(shù)中去。
通過這次的編譯原理課程的學(xué)習(xí)和實(shí)踐,自己獲益良多。首先最基本的成果是完成了課程設(shè)計(jì)的任務(wù),實(shí)現(xiàn)了編譯器的詞法分析和語法分析階段的功能,詞法分析主要能過濾注釋、分析出語法分析階段需要的Token并滿足語法階段的所有要求,能夠判別詞法分析階段是否出錯(cuò)和出錯(cuò)類型和位置。語法分析主要能根據(jù)遞歸向下的分析思想和C-文法對(duì)詞法分析獲取的Token進(jìn)行語法分析,能夠構(gòu)造出語法樹,能夠判別語法分析過程中是否出錯(cuò)以及出錯(cuò)位置和錯(cuò)誤類型。
由于在編寫程序過程中,涉及到了正則表達(dá)式、DFA、提取公共左因子、消除左遞歸、EBNF、求First集合和Follow集合、遞歸向下分析方法以及編程語言方面的知識(shí),所以,通過本次的課程設(shè)計(jì)的實(shí)踐,使得自己對(duì)編譯原理這門課的許多知識(shí)點(diǎn)有了更加深刻和具體的理解,而不再只限制于做題。此外,對(duì)以前那些已掌握的知識(shí)有了溫習(xí)和動(dòng)手鍛煉的機(jī)會(huì)。如:以前在編譯原理課上雖然知道First集合和Follow集合怎么求的,卻不知道First集合和Follow集合到底是干什么的,通過編寫程序自己明白了他們的實(shí)際作用,使得自己不僅知其然還知其所以然,從而使得自己加深了對(duì)知識(shí)點(diǎn)的理解和掌握。由于以前編寫代碼都是使用JAVA語言,所以C/C++很多內(nèi)容都忘記了,通過本次的實(shí)踐,自己又重新拾起了以前的知識(shí)。此外,由于在做報(bào)告的時(shí)候,需要描繪DFA和程序流程圖,使得自己初步掌握了使用visio和word畫圖的能力。此外,對(duì)于文檔的編寫和美化自己也獲得了許多有用的經(jīng)驗(yàn)。[
第三篇:編譯原理課程設(shè)計(jì)簡(jiǎn)介
編譯原理實(shí)踐課程
編譯原理課程是計(jì)算機(jī)專業(yè)必修的一門重要的專業(yè)基礎(chǔ)課程,也是計(jì)算機(jī)系統(tǒng)軟件中非常重要的一個(gè)分支,經(jīng)過多年建設(shè)取得了豐碩的教學(xué)成果:2003年被評(píng)為“吉林大學(xué)百門精品課程”之一,2004年被評(píng)為吉林省精品課程,2006年被評(píng)為教育部—微軟精品課程。編譯原理實(shí)踐課程建設(shè)作為新世紀(jì)教學(xué)改革重點(diǎn)項(xiàng)目和編譯原理精品課程建設(shè)的一個(gè)重要組成部分,在教材建設(shè)、教學(xué)內(nèi)容和教學(xué)方法的改革等方面也取得了較突出的成績(jī),并發(fā)表了多篇學(xué)術(shù)論文。
一、實(shí)驗(yàn)課程目的
編譯原理課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生的專業(yè)骨干課之一。通過學(xué)習(xí)這門課程,使學(xué)生掌握編譯程序的基本原理、方法和實(shí)現(xiàn)技術(shù),使學(xué)生更好的理解程序語言的內(nèi)部機(jī)制,培養(yǎng)學(xué)生初步掌握設(shè)計(jì)大型系統(tǒng)軟件的方法、技術(shù)以及設(shè)計(jì)大型軟件的能力。
編譯原理實(shí)踐性教學(xué)的設(shè)計(jì)思想是使學(xué)生透徹的理解編譯程序的原理和思想,系統(tǒng)全面的掌握編譯技術(shù),使學(xué)生通過課堂學(xué)習(xí),理解編譯原理的同時(shí),注重學(xué)生實(shí)踐能力的培養(yǎng),進(jìn)一步鞏固對(duì)知識(shí)的理解,通過實(shí)際的鍛煉,掌握編譯技術(shù),進(jìn)而能夠獨(dú)立的進(jìn)行編譯器的設(shè)計(jì)。
二、實(shí)驗(yàn)內(nèi)容及要求
編譯程序不同于一般的應(yīng)用程序,是一個(gè)十分龐大和復(fù)雜的系統(tǒng)軟件。一般的應(yīng)用程序是以數(shù)據(jù)作為操作對(duì)象,而編譯程序則是以程序作為操作對(duì)象,是一個(gè)元級(jí)處理程序,它所包含的算法和思想比較特殊,理論性較強(qiáng),抽象度也較高,因而編譯原理課程一直以來都是計(jì)算機(jī)專業(yè)學(xué)生比較難于理解和掌握的一門課程。為此我們開設(shè)編譯原理實(shí)踐課程。編譯原理實(shí)踐課程的主要實(shí)踐題目有:
實(shí)驗(yàn)一: 詞法分析程序開發(fā)
實(shí)驗(yàn)要求: 1.掌握詞法分析程序自動(dòng)生成工具LEX的使用。
2.掌握各類單詞的形式描述。
3.學(xué)會(huì)用數(shù)據(jù)中心法實(shí)現(xiàn)有限自動(dòng)機(jī)。4.學(xué)會(huì)用直接轉(zhuǎn)向法實(shí)現(xiàn)有限自動(dòng)機(jī)。5.獨(dú)立完成SNL語言的詞法分析器。
實(shí)驗(yàn)二: 遞歸下降語法分析
實(shí)驗(yàn)要求: 1.理解遞歸下降語法分析方法的主要原理。
2.理解遞歸下降分析法對(duì)文法的要求。
3.熟練掌握Predict集合的求法。
4.熟練掌握文法變換算法(消除左遞歸和消除公共前綴)。實(shí)驗(yàn)三: LL(1)語法分析
實(shí)驗(yàn)要求: 1.理解LL(1)分析法的主要原理。
2.理解LL(1)分析法對(duì)文法的要求。
3.熟練掌握Predict集合的求法。
4.通過編程熟練掌握LL(1)分析法的工作過程。實(shí)驗(yàn)四: 符號(hào)表管理
實(shí)驗(yàn)要求: 1.了解符號(hào)表在編譯過程中的重要作用。
2.掌握符號(hào)表應(yīng)包含的符號(hào)的屬性信息。3.了解符號(hào)表的組織原則。4.掌握符號(hào)表的操作。
5.掌握符號(hào)表的可見性問題。
實(shí)驗(yàn)五: 語義檢查
實(shí)驗(yàn)要求: 1.了解語義檢查是語義分析的一個(gè)重要內(nèi)容。
2.掌握語義檢查的一般內(nèi)容。
3.學(xué)會(huì)在語法分析的同時(shí)進(jìn)行語義檢查。4.學(xué)會(huì)將語義分析作為一遍獨(dú)立的掃描。
實(shí)驗(yàn)六: 中間代碼生成
實(shí)驗(yàn)要求: 1.了解中間代碼生成是為優(yōu)化和移植而進(jìn)行的。
2.了解幾種常見中間代碼表示形式掌握符號(hào)表應(yīng)包含的符號(hào)的屬性信息。
3.會(huì)用簡(jiǎn)單的程序?qū)崿F(xiàn)中綴式到后綴式的轉(zhuǎn)換。4.會(huì)用棧實(shí)現(xiàn)復(fù)雜表達(dá)式的求值。
5.掌握常見程序結(jié)構(gòu)的中間代碼結(jié)構(gòu)。
6.掌握由語法樹到四元式中間代碼的轉(zhuǎn)換方法。
實(shí)驗(yàn)七: 中間代碼優(yōu)化
實(shí)驗(yàn)要求: 1.能夠?qū)χ虚g代碼正確劃分基本塊。
2.理解常量表達(dá)式局部?jī)?yōu)化算法。
3.理解公共表達(dá)式局部?jī)?yōu)化算法。
4.理解循環(huán)不變式外提優(yōu)化算法。實(shí)驗(yàn)八: 目標(biāo)程序生成
實(shí)驗(yàn)要求: 1.熟練掌握虛擬機(jī)的指令系統(tǒng)。
2.理解并掌握指令選擇的方法。
3.理解多寄存器分配的原則和方法。
4.熟練掌握基本語句從四元式中間代碼形式到目標(biāo)代碼的翻譯原理和方法。
5.獨(dú)立完成目標(biāo)代碼生成程序。
三、實(shí)驗(yàn)教學(xué)過程及教學(xué)手段
教學(xué)過程:
經(jīng)過近三年的研究、探索與實(shí)踐,我們?cè)诰幾g原理實(shí)踐課程的建設(shè)方面取得了一定成效。在吉林大學(xué)計(jì)算機(jī)學(xué)院首次開設(shè)了編譯原理實(shí)踐課程,該課程以學(xué)生實(shí)際上機(jī)實(shí)習(xí)為主,教師指導(dǎo)為輔,強(qiáng)調(diào)啟發(fā)式教學(xué),注重學(xué)生自學(xué)能力的培養(yǎng)。學(xué)生在實(shí)踐課程中,通過實(shí)際動(dòng)手編程,將抽象的編譯理論知識(shí)具體化和形象化,加深了對(duì)基本概念和方法的理解和運(yùn)用,從而全面系統(tǒng)地掌握了編譯器的構(gòu)造過程。
該課程采用教研室自編實(shí)踐教材《編譯程序設(shè)計(jì)與實(shí)現(xiàn)》(高等教育出版社)作為輔導(dǎo)教材,通過對(duì)教材中提供的編譯實(shí)例的透徹解析,加深了學(xué)生對(duì)編譯程序的直觀認(rèn)識(shí),提高了學(xué)生對(duì)源程序的分析和設(shè)計(jì)能力。同時(shí),對(duì)學(xué)生學(xué)習(xí)、理解和掌握編譯原理理論課程也有很大的促進(jìn)作用。在課程中,學(xué)生通過親自動(dòng)手實(shí)踐,把原理性的抽象理論知識(shí)具體化和形象化,消化了課堂上、書本中難于理解的概念和方法,全面系統(tǒng)的掌握了編譯器的構(gòu)造過程,激發(fā)了學(xué)生的學(xué)習(xí)興趣,培養(yǎng)了學(xué)生進(jìn)行更深入學(xué)習(xí)的主動(dòng)性。在教學(xué)方法上,結(jié)合多媒體課件,強(qiáng)調(diào)啟發(fā)式教學(xué),培養(yǎng)學(xué)生的創(chuàng)新能力和動(dòng)手實(shí)踐能力。實(shí)踐證明,這些教學(xué)方式的嘗試在實(shí)際教學(xué)中取得了良好的教學(xué)效果。
教學(xué)環(huán)境:
擁有良好的實(shí)踐教學(xué)環(huán)境,已建成3個(gè)大型網(wǎng)絡(luò)化、多媒體微機(jī)實(shí)驗(yàn)室,共有800臺(tái)奔IV微機(jī),32臺(tái)服務(wù)器,實(shí)驗(yàn)室面積為2040平方米,完全能夠滿足教學(xué)實(shí)踐要求,通過開放式的實(shí)踐教學(xué),收到了良好的教學(xué)效果。除實(shí)踐課程中規(guī)定的實(shí)驗(yàn)之外,還設(shè)計(jì)了一些難度較大的選作實(shí)驗(yàn)題目,激發(fā)學(xué)生的能動(dòng)性,提高學(xué)生分析問題、解決問題的能力。教學(xué)手段:
1.多媒體輔助教學(xué)軟件-PCMCAI(Principle of Compile Multimedia CAI)在教學(xué)過程中,我們發(fā)現(xiàn)由于編譯原理理論性強(qiáng),抽象度高,學(xué)生不易于理解。針對(duì)這一情況,我們研制了編譯原理多媒體輔助教學(xué)軟件-PCMCAI(Principle of Compile Multimedia CAI),該軟件以多媒體動(dòng)畫的形式生動(dòng)形象地描述了編譯器的各個(gè)階段的工作過程。借助現(xiàn)代化的教學(xué)手段和工具,將抽象的知識(shí)具體化,便于學(xué)生理解復(fù)雜的原理,極大地調(diào)動(dòng)了學(xué)生的學(xué)習(xí)積極性,學(xué)習(xí)效果有了明顯的提高;
2.編譯實(shí)例庫(kù)
我們完成了編譯實(shí)例庫(kù)的構(gòu)建,建立實(shí)例庫(kù)的目的是使學(xué)生通過編譯實(shí)例庫(kù),可以了解和掌握不同類型語言的編譯原理和構(gòu)造技術(shù),培養(yǎng)學(xué)生的主動(dòng)參與、自主思考和創(chuàng)新能力,擴(kuò)大學(xué)生的知識(shí)面。通過實(shí)踐課程,我們總結(jié)和綜合了學(xué)生中優(yōu)秀的設(shè)計(jì)實(shí)例,同時(shí),廣泛的收集當(dāng)前國(guó)內(nèi)外最新的素材資料,對(duì)編譯實(shí)例庫(kù)不斷地進(jìn)行完善。目前,實(shí)例庫(kù)已經(jīng)初具規(guī)模并投入使用,為學(xué)生提供了廣泛的實(shí)踐素材和范例,在教學(xué)過程中作為一種輔助教學(xué)手段,效果良好。
3.網(wǎng)絡(luò)教學(xué)平臺(tái):http://softlab.jlu.edu.cn 針對(duì)目前學(xué)生人數(shù)增多,教學(xué)資源不足,學(xué)生質(zhì)量參差不齊,教學(xué)質(zhì)量和效率得不到保證的情況,我們充分利用Internet,建立和實(shí)施網(wǎng)絡(luò)課程體系,利用Internet在信息制造、貯存和遞送方面的優(yōu)勢(shì),克服資源不足的缺點(diǎn),同時(shí)也為學(xué)生提供了完全個(gè)性化的學(xué)習(xí)環(huán)境,發(fā)揮網(wǎng)絡(luò)教學(xué)優(yōu)勢(shì)。目前我們已經(jīng)開始了這方面的建設(shè),完成了編譯原理實(shí)例庫(kù)、課件、習(xí)題庫(kù)等方面的建設(shè),構(gòu)建了網(wǎng)絡(luò)課程的框架體系,目前正著手網(wǎng)絡(luò)課程的進(jìn)一步完善工作。
四、教材及課件
教材建設(shè):
1.校內(nèi)教材:《一個(gè)教學(xué)語言TINY的編譯程序教學(xué)實(shí)例分析教材》(2001年6月)。2.校內(nèi)教材:《編譯程序構(gòu)造原理與實(shí)例分析》(2003年2月)。3.編譯原理實(shí)踐教材:《編譯程序的設(shè)計(jì)與實(shí)現(xiàn)》(高等教育出版社,2004年7月)。
教學(xué)軟件:
1.多媒體輔助教學(xué)軟件-PCMCAI(Principle of Compile Multimedia CAI)。2.SNL(Small Nested Language)語言實(shí)例設(shè)計(jì)及其編譯器構(gòu)造。3.編譯原理實(shí)例庫(kù)(C語言版本)。4.編譯原理實(shí)例庫(kù)(Java語言版本)。
五、相關(guān)成果
發(fā)表論文:
1.《編譯原理實(shí)踐課程設(shè)計(jì)的探索》,劉磊等,吉林大學(xué)新世紀(jì)教學(xué)改革項(xiàng)目研究成果----創(chuàng)新、改革與實(shí)踐 第一集 吉林大學(xué)出版社。2.《用遞歸下降方法實(shí)現(xiàn)自底向上的分析》,劉磊等,吉林大學(xué)學(xué)報(bào)(信息科學(xué)版),2004(3)。
3.《編譯原理多媒體輔助教學(xué)軟件的設(shè)計(jì)與實(shí)現(xiàn)》,劉磊等,吉林大學(xué)自然科學(xué)學(xué)報(bào),2002(2)。
4.《測(cè)試語言ATLAS的實(shí)現(xiàn)技術(shù)》,劉磊等,儀器儀表學(xué)報(bào),2004(4)。5.《ATLAS_MPS的設(shè)計(jì)與實(shí)現(xiàn)》,劉磊等,吉林大學(xué)學(xué)報(bào),2004(4)。6.《編譯原理實(shí)踐課程教學(xué)方法研究》,張晶等,全國(guó)首屆計(jì)算機(jī)程序設(shè)計(jì)類課程教學(xué)研討會(huì),2005(9)。7.《“編譯原理”課程建設(shè)研究》,劉磊等,計(jì)算機(jī)教育,2006(6)。獲得獎(jiǎng)勵(lì):
1.2004年,《編譯原理實(shí)踐課程建設(shè)》,吉林大學(xué)教學(xué)成果二等獎(jiǎng)。2.2006年,《編譯程序的設(shè)計(jì)與實(shí)現(xiàn)》一書獲吉林大學(xué)本科優(yōu)秀教材。3.2002年,編譯原理CAI課件-PCMCAI獲被吉林省教育廳評(píng)為二等獎(jiǎng),并在第六屆全國(guó)多媒體教育軟件大獎(jiǎng)賽上獲得優(yōu)秀獎(jiǎng)。
4.《編譯原理》課程先后被評(píng)為吉林大學(xué)精品課程、吉林省精品課程及教育部-微軟精品課程。
總之,經(jīng)過多年的研究、探索與實(shí)踐,我們?cè)诰幾g原理實(shí)踐課程的建設(shè)方面取得了一定成效。在吉林大學(xué)計(jì)算機(jī)學(xué)院首次開設(shè)了編譯原理實(shí)踐課程,該課程以學(xué)生實(shí)際上機(jī)實(shí)習(xí)為主,教師指導(dǎo)為輔,強(qiáng)調(diào)啟發(fā)式教學(xué),注重學(xué)生自學(xué)能力的培養(yǎng)。學(xué)生在實(shí)踐課程中,通過實(shí)際動(dòng)手編程,將抽象的編譯理論知識(shí)具體化和形象化,加深了對(duì)基本概念和方法的理解和運(yùn)用,從而全面系統(tǒng)地掌握了編譯器的構(gòu)造過程。該課程采用我們自編實(shí)踐教材《編譯程序設(shè)計(jì)與實(shí)現(xiàn)》作為輔導(dǎo)教材,通過對(duì)教材中提供的編譯實(shí)例的透徹解析,加深了學(xué)生對(duì)編譯程序的直觀認(rèn)識(shí),提高了學(xué)生對(duì)源程序的分析和設(shè)計(jì)能力。同時(shí),對(duì)學(xué)生學(xué)習(xí)、理解和掌握編譯原理理論課程也有很大的促進(jìn)作用。在教學(xué)方法上,結(jié)合多媒體課件,強(qiáng)調(diào)啟發(fā)式教學(xué),培養(yǎng)學(xué)生的創(chuàng)新能力和動(dòng)手實(shí)踐能力。實(shí)踐證明,這些教學(xué)方式的嘗試在實(shí)際教學(xué)中取得了良好的教學(xué)效果。
附件(獲得獎(jiǎng)勵(lì)證書)
第四篇:《編譯原理課程設(shè)計(jì)》教學(xué)大綱
《編譯原理課程設(shè)計(jì)》教學(xué)大綱
課程名稱: 課程編號(hào): 適用專業(yè): 總 學(xué) 分: 總 周 時(shí): 主 撰 人: 撰寫日期:
一、目的與任務(wù)
通過程序設(shè)計(jì)上機(jī)調(diào)試程序?qū)崿F(xiàn)算法,學(xué)習(xí)編譯程序調(diào)試技巧和設(shè)計(jì)編譯程序的一般原則,加深對(duì)詞法分析、語法分析、語義分析和中間代碼生成等編譯階段及實(shí)用編譯系統(tǒng)的認(rèn)識(shí),初步掌握編譯程序構(gòu)造的基本原理與技術(shù), 從形式語言理論的角度, 進(jìn)一步認(rèn)識(shí)與理解程序設(shè)計(jì)語言。通過編譯程序的編寫和調(diào)試能力的訓(xùn)練,激發(fā)學(xué)生進(jìn)一步思考問題,培養(yǎng)學(xué)生的學(xué)習(xí)興趣和創(chuàng)新能力。并進(jìn)一步培養(yǎng)學(xué)生的抽象思維能力,進(jìn)一步鞏固《編譯原理》課程所學(xué)知識(shí)。
本次課程設(shè)計(jì)的時(shí)間為2周,目的是通過實(shí)際的題目如:詞法分析、語法分析、代碼優(yōu)化等,使學(xué)生了解和掌握編譯程序的工作原理,同時(shí)培養(yǎng)學(xué)生用相關(guān)的程序設(shè)計(jì)語言進(jìn)行程序設(shè)計(jì),實(shí)現(xiàn)編譯的功能,從而提高學(xué)生的綜合能力。
二、教學(xué)基本要求
1.設(shè)計(jì)和調(diào)試過程要規(guī)范化
需求分析:將題目中要求的功能進(jìn)行敘述分析,并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu),(有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的,按照指定的設(shè)計(jì)),設(shè)計(jì)或敘述解決此問題的算法,描述算法可以使用自然語言、偽代碼、或函數(shù)的方式。
給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)(測(cè)試文法),程序調(diào)試后,將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來。
如果程序不能正常運(yùn)行或運(yùn)行過程中出現(xiàn)了不滿足算法思想的情況,寫出出現(xiàn)這一情況的原因或改進(jìn)行的方法。
源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰,重點(diǎn)函數(shù)的重點(diǎn)變量,重點(diǎn)功能部分要加上清晰的程序注釋。
程序能夠運(yùn)行,要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。2.課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書寫格式
編譯原理 436105 軟件工程 2W 2012.6
審 核 人:
① 設(shè)計(jì)題目
②運(yùn)行環(huán)境(軟、硬件環(huán)境)③算法設(shè)計(jì)的思想 ④算法設(shè)計(jì)分析 ⑤主要函數(shù) ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3.實(shí)施方式
本次課程設(shè)計(jì)分成9個(gè)題目,都有一定的工作量,涵蓋本課程內(nèi)容和實(shí)際應(yīng)用相關(guān)的主要技術(shù),學(xué)生可以自由組隊(duì)選擇其中一個(gè)實(shí)現(xiàn)。課程設(shè)計(jì)題目見“主要內(nèi)容”。
根據(jù)老師給定的9個(gè)題目進(jìn)行分析設(shè)計(jì),本次課程設(shè)計(jì)采取分組的辦法進(jìn)行,3-4人為一組,要求每組學(xué)生在規(guī)定時(shí)間內(nèi)獨(dú)立完成。4.答辯:課題的論述、測(cè)試及問題回答
三、課程設(shè)計(jì)內(nèi)容
1、詞法分析器的構(gòu)造:
人們理解一個(gè)程序,起碼是在單詞級(jí)別上來思考。同樣,在編繹一個(gè)程序時(shí),也是在單詞級(jí)別上來分析和翻譯源程序。詞法分析是編繹的基礎(chǔ),執(zhí)行詞法分析的程序即為詞法分析器,它的任務(wù)是對(duì)輸入或給定的源程序,從左至右逐個(gè)字符進(jìn)行掃描,產(chǎn)生一個(gè)個(gè)單詞符號(hào),把作為字符串的源程序改造成單詞符號(hào)串的中間程序。設(shè)計(jì)目的與任務(wù):
通過本課程設(shè)計(jì)教學(xué)所要求達(dá)到的目的是:對(duì)詞法分析工作流程進(jìn)行總體設(shè)計(jì)和詳細(xì)設(shè)計(jì),最終用C語言來設(shè)計(jì)一個(gè)簡(jiǎn)單詞法分析器,實(shí)現(xiàn)對(duì)源程序的詞法分析功能,對(duì)輸入程序去除注釋,并以二元式形式輸出程序中所有單詞。
2、正則表達(dá)式到NFA 在編譯系統(tǒng)中,詞法分析階段是整個(gè)編譯系統(tǒng)的基礎(chǔ)。對(duì)于單詞的識(shí)別,有限自動(dòng)機(jī)FA是一種十分有效的工具。有限自動(dòng)機(jī)由其映射f是否為單值而分為確定的有限自動(dòng)機(jī)DFA和非確定的有限自動(dòng)機(jī)NFA。在非確定的有限自動(dòng)機(jī)NFA中,由于某些狀態(tài)的轉(zhuǎn)移需從若干個(gè)可能的后續(xù)狀態(tài)中進(jìn)行選擇,故一個(gè)NFA對(duì)符號(hào)串的識(shí)別就必然是一個(gè)試探的過程。這種不確定性給識(shí)別過程帶來的反復(fù),無疑會(huì)影響到FA的工作效率。而DFA引擎在任意時(shí)刻必定處于某個(gè)確定的狀態(tài),它搜索是無需象NFA一樣必須記錄所有的可能路徑(trace multiple possible routes through the NFA),這也是DFA運(yùn)行效率高于NFA的原因。而已經(jīng)證明DFA是NFA的一個(gè)特例,即對(duì)于每一個(gè)NFA M存在一個(gè)DFA M’’,使得L(M)=L(M’’)。
設(shè)計(jì)目的與任務(wù)
通過本課程設(shè)計(jì)教學(xué)所要求達(dá)到的目的是:充分理解和掌握NFA,DFA以及NFA確定化過程的相關(guān)概念和知識(shí),編程實(shí)現(xiàn)對(duì)輸入的任意正規(guī)式轉(zhuǎn)換成NFA的形式輸出。
3、NFA的確定化
有限自動(dòng)機(jī)理論是描述詞法規(guī)則的基本理論。一條詞法規(guī)則表示一個(gè)正規(guī)表達(dá)式(又叫正規(guī)式),而一個(gè)正規(guī)式又可化為一個(gè)DFA(確定有窮自動(dòng)機(jī)),這個(gè)有限自動(dòng)機(jī)可用來識(shí)別詞法規(guī)則所定義的所有單詞符號(hào)。把程序設(shè)計(jì)語言的所有詞法規(guī)則都構(gòu)造出相應(yīng)的有限自動(dòng)機(jī),就得到一個(gè)詞法分析器。然后,再轉(zhuǎn)換為計(jì)算機(jī)可識(shí)別的程序就能自動(dòng)實(shí)現(xiàn)詞法的分析和檢查。在實(shí)際應(yīng)用中,用NFA(不確定有窮自動(dòng)機(jī))識(shí)別詞法存在不確定和狀態(tài)的冗余,因而,就要將NFA(不確定有窮自動(dòng)機(jī))轉(zhuǎn)換為DFA(確定有窮自動(dòng)機(jī)),消除了不可到達(dá)和不確定。設(shè)計(jì)目的與任務(wù)
通過本課程設(shè)計(jì)教學(xué)所要求達(dá)到的目的是:掌握從NFA到DFA的轉(zhuǎn)換,以及用子集法把NFA轉(zhuǎn)換成DFA理論,編程實(shí)現(xiàn)將NFA(不確定有窮自動(dòng)機(jī))轉(zhuǎn)換為DFA(確定有窮自動(dòng)機(jī))。
4、DFA的最小化
確定性有限自動(dòng)機(jī)(DFA ,Deterministic Finite Automata)的最小化仍是有限自動(dòng)機(jī)應(yīng)用及實(shí)現(xiàn)方面的重要問題之一。DFA的最小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系,便于其存儲(chǔ)實(shí)現(xiàn),便于建立用DFA描述的任務(wù)模型,一些理論問題也與最小化思想有關(guān)。DFA的最小化是指,構(gòu)造一個(gè)與之等價(jià)且狀態(tài)數(shù)最小的DFA,即等價(jià)最小DFA。許多文獻(xiàn)給出了一個(gè)最小化算法,算法的思想是,構(gòu)造狀態(tài)集的一個(gè)劃分,再將這個(gè)劃分中的每個(gè)子集作為新的狀態(tài),從而得到等價(jià)最小DFA。
DFA的最小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系,便于其存儲(chǔ)實(shí)現(xiàn),便于建立用DFA描述的任務(wù)模型,一些理論問題也與最小化思想有關(guān)。
5、語法分析之LL(1)文法
通過該課程設(shè)計(jì)了解了程序語言的自上而下的語法分析過程,提高了編程能力,能使我們了解編程語言更多的細(xì)節(jié) 設(shè)計(jì)目的與任務(wù)(1)讀入文法(2)求出first(), follow()(3)判斷是否為L(zhǎng)L(1)文法
(4)若是,構(gòu)造分析表;
(5)輸入一個(gè)字符串看是否是文法的一個(gè)句子。
6、算符優(yōu)先文法
一個(gè)文法,如果它的任一產(chǎn)生式的右邊都不含有兩個(gè)相繼(并列)的非終結(jié)符,即不 含有如下形式的產(chǎn)生式的右部:
?QR?
則我們稱該文法為算符文法。
假設(shè)文法中的任意兩個(gè)終結(jié)符之間最多只有一個(gè)優(yōu)先關(guān)系,則該文法稱為算符優(yōu)先文法。
該課程設(shè)計(jì)按照求,(P),(P)各兩條規(guī)則,求出各非終結(jié)符的集。然后按照算符優(yōu)先算法求出各終結(jié)符的算符優(yōu)先關(guān)系,填寫算符優(yōu)先表,并將其輸出。
7、LR(0)分析表的構(gòu)造
LR分析技術(shù)是一種有效的自下而上分析技術(shù),是一種規(guī)范歸約,其中L表示從左到右掃描輸入串,R表示構(gòu)造一個(gè)最右推導(dǎo)的逆過程。這種方法可以適用于很大一類上下無關(guān)文法的語法分析。LR方法的基本思想是:在規(guī)范歸約過程中,一方面記住已經(jīng)移進(jìn)和歸約出的整個(gè)符號(hào)串,即記住“歷史”;另一方面根據(jù)所用的產(chǎn)生式推測(cè)未來可能碰到的輸入符號(hào),即對(duì)未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號(hào)串呈現(xiàn)于分析棧的頂端時(shí),我們希望能夠根據(jù)所記載的“歷史”和“展望”以及“現(xiàn)實(shí)”的輸入符號(hào)等三方面的材料,來確定棧頂?shù)姆?hào)傳是否構(gòu)成相對(duì)某一產(chǎn)生式的句柄。
LR分析器的核心部分是一張分析表。這張分析表包括兩部分,一是“動(dòng)作”(ACTION)表,另一是“狀態(tài)轉(zhuǎn)換”(GOTO)表。對(duì)于一個(gè)文法,如果能用一個(gè)每步頂多向前檢查K個(gè)輸入符號(hào)的LR分析器進(jìn)行分析,則這個(gè)文法就稱為L(zhǎng)R(K)文法。本文研究的LR(0)文法即K=0時(shí)的文法。
設(shè)計(jì)目的與任務(wù)
本課程設(shè)計(jì)所設(shè)計(jì)目的與任務(wù)是:通過C語言程序?qū)崿F(xiàn)LR(0)分析表的構(gòu)造,熟練掌握LR(0)分析表的構(gòu)造方法,即利用拓廣文法和構(gòu)造項(xiàng)目集規(guī)范族的方法。了解LR(0)分析器的工作原理,并能利用LR(0)分析表對(duì)輸入串進(jìn)行分析。
8、逆波蘭表達(dá)式生成算法
雖然源程序可以直接翻譯為目標(biāo)語言代碼,但許多編譯程序采用了獨(dú)立于機(jī)器的、復(fù)雜性介于源語言和機(jī)器翻譯語言之間的中間語言:后綴式(逆波蘭表達(dá)式)等。這樣做的好處是:
(1)便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化工作;(2)使編譯程序改變目標(biāo)機(jī)更容易;
(3)使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確。以中間語言為界面,編譯前端和后端的接口更清晰。設(shè)計(jì)目的與任務(wù)
將非后綴式用來表示的算術(shù)表達(dá)式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達(dá)式,并能運(yùn)行查看結(jié)果。
9、表達(dá)式的中間代碼生成
源程序可以直接翻譯為目標(biāo)語言代碼,但是許多編譯程序卻采用了獨(dú)立于機(jī)器的、復(fù)雜性介于源語言和機(jī)器語言之間的中間語言。這樣我們可以做下面工作:
(1):便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化工作;(2):使編譯程序以改變目標(biāo)機(jī)更容易;(3):使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確;
而以中間語言為界面,編譯前端和后端的接口更清晰,表達(dá)式可以用四個(gè)域分別稱為OP、ORG1、ORG2及RESULT來表示。
四、時(shí)間安排
《編譯原理課程設(shè)計(jì)》安排在第三學(xué)期進(jìn)行,時(shí)間2周(17-18周)。
五、組織管理
1.由院、系指派經(jīng)驗(yàn)豐富的專業(yè)教師擔(dān)任指導(dǎo)教師。
2.課程設(shè)計(jì)實(shí)行指導(dǎo)教師負(fù)責(zé)制,由指導(dǎo)教師全面負(fù)責(zé)課程設(shè)計(jì)的指導(dǎo)與管理工作。
六、成績(jī)考核與評(píng)定
學(xué)生課程設(shè)計(jì)結(jié)束后寫出總結(jié)報(bào)告,對(duì)設(shè)計(jì)的內(nèi)容和效果進(jìn)行總結(jié),按照學(xué)生在設(shè)計(jì)期間的表現(xiàn),指導(dǎo)老師對(duì)每位學(xué)生寫出評(píng)語和鑒定,系課程設(shè)計(jì)領(lǐng)導(dǎo)小組組織答辯,最后確定每位學(xué)生課程設(shè)計(jì)成績(jī),課程設(shè)計(jì)成績(jī)分為優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。課程設(shè)計(jì)成績(jī)?yōu)槠綍r(shí)表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%。評(píng)分標(biāo)準(zhǔn):
① 優(yōu)秀:目的明確,態(tài)度端正,模范遵守學(xué)校的各項(xiàng)紀(jì)律。工作認(rèn)真,積極 主動(dòng),吃苦耐勞,能出色的完成設(shè)計(jì)任務(wù)。撰寫了高質(zhì)量的總結(jié)報(bào)告。答辯準(zhǔn)確流利。
② 良好:目的明確,態(tài)度端正,能遵守學(xué)校的各項(xiàng)紀(jì)律,工作比較積極主動(dòng)。能較好地完成設(shè)計(jì)任務(wù),成績(jī)較突出,表現(xiàn)良好;撰寫了質(zhì)量比較高的實(shí)習(xí)報(bào)告。答辯較準(zhǔn)確流利。
③ 及格:目的明確,態(tài)度基本端正,能遵守學(xué)校紀(jì)律,在督促下能開展工作 并完成一定的設(shè)計(jì)任務(wù),無大的違紀(jì)違規(guī)現(xiàn)象;撰寫了實(shí)習(xí)報(bào)告。通過了答辯。
④ 不及格:實(shí)習(xí)態(tài)度端正,不能遵守實(shí)習(xí)單位的紀(jì)律,不服從領(lǐng)導(dǎo),自由散漫,工作消極被動(dòng),不能完成實(shí)習(xí)任務(wù),實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過失。或無實(shí)習(xí)報(bào)告,沒有通過答辯。
2.成績(jī)?cè)u(píng)定
依據(jù)上述考核內(nèi)容,最后采用優(yōu)(>90分)、良(80~89分)、中(70~79分)及格(60~69分)、不及格(<60分)五級(jí)記分制評(píng)定學(xué)生課程設(shè)計(jì)成績(jī)。
七、主要參考資料
教材:
《編譯原理及實(shí)踐》馮博琴等譯,機(jī)械工業(yè)出版社 教學(xué)參考書
1、《程序設(shè)計(jì)語言與編譯》龔天富、侯文永編,電子工業(yè)出版社。
2、《編譯原理》呂映芝、張素琴、蔣維杜主編,清華大學(xué)出版社,1998年
3、《編譯原理》胡倫駿、徐蘭芳、劉建農(nóng)編,電子工業(yè)出版社2002年
4、《編譯原理》(第二版)蔣立源、康慕寧主編,西北工業(yè)大學(xué)出版社,2002年
5、《編譯原理習(xí)題精選》陳意云、張昱著,中國(guó)科技大學(xué)出版社,2002年
6、《編譯原理習(xí)題與解析》 伍春香著,清華大學(xué)出版社,2001年
7、《編譯原理實(shí)驗(yàn)指導(dǎo)書》自編
第五篇:合肥工業(yè)大學(xué)編譯原理課程設(shè)計(jì)
關(guān)于《編譯原理》課程設(shè)計(jì)的有關(guān)說明
《編譯原理》是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)課程,其中包含大量軟件設(shè)計(jì)思想。大家通過課程設(shè)計(jì),實(shí)現(xiàn)一些重要的算法,或設(shè)計(jì)一個(gè)完整的編譯程序模型,能夠進(jìn)一步加深理解和掌握所學(xué)知識(shí),對(duì)提高自己的軟件設(shè)計(jì)水平具有十分重要的意義。大家在進(jìn)行課程設(shè)計(jì)時(shí),可從所學(xué)內(nèi)容中選擇某個(gè)主題,抽象成一個(gè)模型,可適當(dāng)進(jìn)行簡(jiǎn)化。也可按提供給大家的一些參考選題進(jìn)行設(shè)計(jì)。軟件開發(fā)選擇C/C++語言(也可以是你熟悉的任何語言)。最后每位同學(xué)都要認(rèn)真撰寫設(shè)計(jì)報(bào)告,格式要規(guī)范,內(nèi)容要詳盡,包括:設(shè)計(jì)題目,設(shè)計(jì)目的,設(shè)計(jì)內(nèi)容,設(shè)計(jì)要求,問題的描述及解決的方法、原理、思想、算法(流程圖),設(shè)計(jì)的輸入和輸出形式,測(cè)試、模擬的結(jié)果(屏幕拷貝、生成結(jié)果的打印輸出),總結(jié)(體會(huì)),源程序清單,等等。
大家應(yīng)把該門課的課程設(shè)計(jì)當(dāng)成對(duì)自己學(xué)習(xí)效果的一次檢驗(yàn),當(dāng)成是為在大四能夠順利完成畢業(yè)設(shè)計(jì)的一次基本功訓(xùn)練。希望每個(gè)同學(xué)盡可能不要都選擇完全一樣的題目。大家可以自主選題,或選擇我提供的題目,也可以把幾個(gè)題目合起來做(如開發(fā)一個(gè)小的編譯器)。鼓勵(lì)選擇有一定技術(shù)難度、有一定工作量、綜合性較強(qiáng)的題目,在評(píng)定成績(jī)時(shí)將會(huì)給予好的成績(jī)。
編譯原理課程設(shè)計(jì)部分參考選題: 1. 題目: FORTRAN語言實(shí)型常數(shù)識(shí)別程序設(shè)計(jì)
設(shè)計(jì)內(nèi)容及要求: 將教材P.41的圖3.2(d)識(shí)別FORTRAN實(shí)型常數(shù)的狀態(tài)轉(zhuǎn)換圖用程序?qū)崿F(xiàn)。程序能夠從用戶輸入的任意一個(gè)字符串中識(shí)別出FORTRAN實(shí)型常數(shù),顯示輸出。
2. 題目: 簡(jiǎn)化的FORTRAN語言詞法分析程序設(shè)計(jì)
設(shè)計(jì)內(nèi)容及要求:將教材P.42上的表3.1的詞法分析器構(gòu)造出來,限制條件如教材所述。保留字的識(shí)別按標(biāo)識(shí)符一樣識(shí)別,通過查找保留字表區(qū)分是保留字還是標(biāo)識(shí)符。程序能夠從用戶輸入的源程序中,識(shí)別出的單詞符號(hào),并用二元式表示,顯示輸出或輸出到文件中。
3. 題目: ε-CLOSURE(I)構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:將ε-CLOSURE(I)構(gòu)造算法用程序?qū)崿F(xiàn)。要求:對(duì)任意
第1頁 給定的一個(gè)NFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)的某一個(gè)狀態(tài)子集I,顯示輸出構(gòu)造出的ε-CLOSURE(I)。
4. 題目: 從右線性文法構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一轉(zhuǎn)換程序,實(shí)現(xiàn)將用戶任意給定的右線性文法,轉(zhuǎn)換為與之等價(jià)的有限自動(dòng)機(jī)FA M,輸出其狀態(tài)轉(zhuǎn)換矩陣(顯示輸出或輸出到文件中)。
5. 題目: 從有限自動(dòng)機(jī)構(gòu)造與之等價(jià)的右線性文法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一轉(zhuǎn)換程序,實(shí)現(xiàn)將用戶任意給定的有限自動(dòng)機(jī)FA M,轉(zhuǎn)換為與之等價(jià)的右線性文法,顯示輸出或輸出到文件中。6. 題目: 有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖顯示程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn):將任一給定的有限自動(dòng)機(jī)M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中),在屏幕上顯示輸出M的狀態(tài)轉(zhuǎn)換圖。程序應(yīng)具有通用性,狀態(tài)節(jié)點(diǎn)在屏幕上的分布應(yīng)合理、美觀。7. 題目: 從NFA構(gòu)造與之等價(jià)的正規(guī)式r的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)給定的任意NFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息分別保存在指定文件中)。構(gòu)造一程序,從NFA構(gòu)造與之等價(jià)的正規(guī)式r,并顯示輸出。
8. 題目: 構(gòu)造正規(guī)式r1|r2(或運(yùn)算)的NFA的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)給定的正規(guī)式r1、r2,已知它們的NFA分別為M1、M2(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息分別保存在指定文件中)。構(gòu)造一程序,由此程序構(gòu)造正規(guī)式r1|r2(或運(yùn)算)的NFA(將其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。
9. 題目: 構(gòu)造正規(guī)式r1r2(連接運(yùn)算)的NFA的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)給定的正規(guī)式r1、r2,已知它們的NFA分別為M1、M2(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息分別保存在指定文件中)。構(gòu)造一程序,由此程序構(gòu)造正規(guī)式r1r2(連接運(yùn)算)的NFA(將其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。10. 題目: 構(gòu)造正規(guī)式r*(閉包運(yùn)算)的NFA的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)給定的正規(guī)式r,已知其NFA為M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。構(gòu)造一程序,由此程序構(gòu)造正規(guī)式r*(閉包運(yùn)算)的NFA(將其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。11.
題目: 基于語法制導(dǎo)構(gòu)造正規(guī)式的NFA
第2頁 設(shè)計(jì)內(nèi)容及要求:首先構(gòu)造一個(gè)語法分析程序,實(shí)現(xiàn)對(duì)任意正規(guī)式的語法分析。語法分析方法采用自下而上的分析方法(如算符優(yōu)先分析,或LR分析)。在此語法分析器的基礎(chǔ)上,按照語法制導(dǎo)的思想,增加構(gòu)造NFA的功能。生成的NFA將其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中。進(jìn)一步實(shí)現(xiàn)把NFA確定化為DFA 的算法(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。12. 題目: DFA M狀態(tài)最少化的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn):將給定的DFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)的有限狀態(tài)集S劃分成若干互不相交的子集,使得:任何不同的兩個(gè)子集中的狀態(tài)都是可區(qū)別的,而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的(要利用Ia函數(shù),但并不需要構(gòu)造ε-CLOSURE函數(shù),因這是DFA)。輸出化簡(jiǎn)后的DFA M’(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。13. 題目: 把NFA確定化為DFA 的算法實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn):將給定的NFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中),確定化為DFA M’。(要先實(shí)現(xiàn)ε-CLOSURE函數(shù)和Ia函數(shù))。輸出DFA M’(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息保存在指定文件中)。14. 題目: 基于貪心算法的DFA 的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:采用貪心算法實(shí)現(xiàn)教材P.62表3.5的DFA,要求從輸入串中匹配最長(zhǎng)的子串。輸出所有識(shí)別出的符號(hào)串及其詞形。15. 題目: 根據(jù)句型的推導(dǎo)構(gòu)造其語法分析樹的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn):接受用戶任意輸入的一個(gè)句型的推導(dǎo)序列,生成該句型的語法分析樹并顯示輸出。程序應(yīng)具有通用性,語法分析樹的節(jié)點(diǎn)在屏幕上的分布要合理、美觀。16. 題目: 從語法分析樹構(gòu)造句型所有的推導(dǎo)的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn):接受用戶任意輸入的一個(gè)句型的語法分析樹(其表示存于指定文件中),生成該語法分析樹中包含的該句型的所有推導(dǎo)(顯示輸出)。17. 題目: 遞歸下降分析程序的實(shí)現(xiàn) 設(shè)計(jì)內(nèi)容及要求:
對(duì)文法 G: E→E+T|T 構(gòu)造出G的遞歸下降分析程序。程序顯示輸出
T→T*F|F 匹配過程(即自上而下生成語法分析樹的步驟,F(xiàn)→(E)|i 輸出各匹配產(chǎn)生式序號(hào)即可)。
18.題目: 集合FIRST(X)構(gòu)造算法的程序?qū)崿F(xiàn)
第3頁 設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn)教材P.78的FIRST(X)集合的構(gòu)造算法。對(duì)任一給定的文法G,程序輸出所有非終結(jié)符P的FIRST(P)。19. 題目: 集合FOLLOW(A)構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:首先,構(gòu)造一程序,實(shí)現(xiàn)教材P.78的FIRST(X)集合的構(gòu)造算法。對(duì)任一給定的文法G,程序輸出所有非終結(jié)符P的FIRST(P)。在此基礎(chǔ)上,構(gòu)造一程序,實(shí)現(xiàn)教材P.79的FOLLOW(A)集合的構(gòu)造算法。對(duì)任一給定的文法G,程序輸出所有非終結(jié)符A的FOLLOW(A)。20. 題目: 預(yù)測(cè)分析表構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)于給定的一個(gè)LL(1)文法,假定所有非終結(jié)符號(hào)P的集合FIRST(P)和集合FOLLOW(P)都已知,構(gòu)造其預(yù)測(cè)分析表(實(shí)現(xiàn)教材P.79給出的預(yù)測(cè)分析表構(gòu)造算法)。對(duì)教材P.79給出的例4.7構(gòu)造出預(yù)測(cè)分析表。程序顯示輸出預(yù)測(cè)分析表或輸出到指定文件中。21. 題目: 預(yù)測(cè)分析表自動(dòng)構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)于任意輸入的一個(gè)LL(1)文法,構(gòu)造其預(yù)測(cè)分析表。要求:首先實(shí)現(xiàn)集合FIRST(X)構(gòu)造算法和集合FOLLOW(A)構(gòu)造算法,再實(shí)現(xiàn)教材P.79給出的預(yù)測(cè)分析表構(gòu)造算法。程序顯示輸出預(yù)測(cè)分析表或輸出到指定文件中。22. 題目: 預(yù)測(cè)分析程序的實(shí)現(xiàn) 設(shè)計(jì)內(nèi)容及要求:
對(duì)文法 G: E→E+T|T 按教材P.76表4.1構(gòu)造出G的預(yù)測(cè)分析程序,T→T*F|F 程序顯示輸出如P.78那樣的匹配過程。
F→(E)|i 23. 題目: 集合FIRSTVT(P)構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn)教材P.91的FIRSTVT(P)集合的構(gòu)造算法。對(duì)任一給定的算符文法G,程序輸出所有非終結(jié)符P的FIRSTVT(P)。24. 題目: 集合LASTVT(P)構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn)教材P.91的LASTVT(P)集合的構(gòu)造算法。對(duì)任一給定的算符文法G,程序輸出所有非終結(jié)符P的LASTVT(P)。25. 題目: 算符優(yōu)先分析算法的程序?qū)崿F(xiàn) 設(shè)計(jì)內(nèi)容及要求:
對(duì)文法 G: E→E+T|T 采用教材P.90表5.1,實(shí)現(xiàn)P.93描述的算符優(yōu)先
T→T*F|F 分析算法。程序顯示輸出“移進(jìn)-歸約”的步驟。F→P↑F|P
第4頁 P→(E)|i 26. 題目: 帶出錯(cuò)處理的算符優(yōu)先分析算法的程序?qū)崿F(xiàn) 設(shè)計(jì)內(nèi)容及要求:
對(duì)文法 G: E→E+T|T 采用教材P.98表5.3,實(shí)現(xiàn)P.93描述的算符優(yōu)先
T→T*F|F 分析算法。程序顯示輸出“移進(jìn)-歸約”的步驟。
F→(E)|i 要編制各出錯(cuò)處理子程序。
27. 題目: 優(yōu)先表構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求: 實(shí)現(xiàn)教材P.92優(yōu)先表構(gòu)造算法。對(duì)任一給定的算符優(yōu)先文法G,假定所有非終結(jié)符P的FIRSTVT(P)、LASTVT(P)均已知。以教材P.90例5.4文法為例,程序生成表5.1優(yōu)先表。28. 題目: 優(yōu)先表自動(dòng)構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)任一給定的算符優(yōu)先文法G,構(gòu)造其優(yōu)先表。要求:首先實(shí)現(xiàn)對(duì)于非終結(jié)符P的FIRSTVT(P)構(gòu)造算法和LASTVT(P)構(gòu)造算法,再實(shí)現(xiàn)教材P.92給出的優(yōu)先表構(gòu)造算法。以教材P.90例5.4文法為例,程序生成表5.1優(yōu)先表。29. 題目: 優(yōu)先函數(shù)構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn):根據(jù)優(yōu)先關(guān)系表構(gòu)造優(yōu)先函數(shù)。輸入的優(yōu)先表假定保存在指定文件中,構(gòu)造出的優(yōu)先函數(shù)可顯示輸出,或輸出到指定文件中。30. 題目: 消除左遞歸算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn)教材P.70消除左遞歸算法。對(duì)于用戶任意輸入的文法G,輸出一個(gè)無左遞歸的等價(jià)文法,可顯示輸出,或輸出到指定文件中。31. 題目: 消除回溯算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn):消除文法每一條產(chǎn)生式候選式的公共左因子。對(duì)于用戶任意輸入的文法G,輸出一個(gè)無回溯的等價(jià)文法,可顯示輸出,或輸出到指定文件中。32. 題目: LR分析器總控程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)P.101中的文法,按圖5.5LR分析表構(gòu)造LR分析器。要求程序按P.102例5.7那樣,對(duì)于輸入串i*i+i,輸出LR分析器的工作過程。33. 題目: 識(shí)別文法活前綴的NFA構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,對(duì)任意給定的文法G:①構(gòu)造并輸出G的所有LR(0)項(xiàng)目;②用這些LR(0)項(xiàng)目構(gòu)造并輸出識(shí)別文法活前綴的NFA(輸出其
第5頁 狀態(tài)轉(zhuǎn)換矩陣)。34. 題目: LR(0)項(xiàng)目集規(guī)范族構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,對(duì)任意給定的文法G,構(gòu)造識(shí)別文法活前綴的DFA,輸出DFA的狀態(tài)轉(zhuǎn)化矩陣及LR(0)項(xiàng)目集規(guī)范族。要求按教材P.107所給的ITEMSETS(G’)構(gòu)造,要實(shí)現(xiàn)CLOSURE(I)、GO(I,X)函數(shù)。按P.105例5.8給出測(cè)試結(jié)果,可輸出到指定文件中。35. 題目: LR(0)分析表構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求: 構(gòu)造一程序,實(shí)現(xiàn)LR(0)分析表構(gòu)造算法。根據(jù)教材P.106圖5.7的識(shí)別文法活前綴的DFA,輸出如P.109表5.4的LR(0)分析表,可輸出到指定文件中。36. 題目: LR(0)分析器自動(dòng)構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)任意給定的文法G,構(gòu)造識(shí)別文法活前綴的DFA,輸出DFA的狀態(tài)轉(zhuǎn)化矩陣及LR(0)項(xiàng)目集規(guī)范族;實(shí)現(xiàn)LR(0)分析表構(gòu)造算法;實(shí)現(xiàn)LR分析器總控程序。程序輸出一個(gè)完整的LR(0)分析器源程序,可輸出到指定文件中。37. 題目: SLR(1)分析表構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn)SLR(1)分析表構(gòu)造算法(假定所給文法識(shí)別文法活前綴的DFA、LR(0)項(xiàng)目集族、所有非終結(jié)符FOLLOW集合均已構(gòu)造出來了)。根據(jù)教材P.111例5.11文法為輸入,構(gòu)造其SLR(1)分析表。38. 題目: LR(1)項(xiàng)目集規(guī)范族構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,對(duì)任意給定的文法G構(gòu)造LR(1)項(xiàng)目集規(guī)范族(按教材P.115所述方法構(gòu)造,要實(shí)現(xiàn)CLOSURE(I)、GO(I,X),集合FIRST的構(gòu)造方法參見教材P.78)。39. 題目: LR(1)分析表構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:構(gòu)造一程序,實(shí)現(xiàn)LR(1)分析表構(gòu)造算法(假定所給文法識(shí)別文法活前綴的DFA、LR(1)項(xiàng)目集族已構(gòu)造出來了)。根據(jù)教材P.116圖5.10的LR(1)項(xiàng)目集族和GO函數(shù)為輸入,構(gòu)造并輸出其LR(1)分析表5.5。40. 題目: LR(1)分析表自動(dòng)構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)任意給定的文法G構(gòu)造LR(1)項(xiàng)目集規(guī)范族(按教材P.115所述方法構(gòu)造,要求實(shí)現(xiàn)CLOSURE(I)、GO(I,X)、FIRST(集合FIRST的構(gòu)造方法參見教材P.78);然后實(shí)現(xiàn)LR(1)分析表構(gòu)造算法。以教材P.115例5.13為輸入,構(gòu)造并輸出其LR(1)分析表5.5。
第6頁 41. 題目: LALR(1)項(xiàng)目集規(guī)范族構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:假設(shè)對(duì)于給定文法,識(shí)別文法活前綴的DFA、LR(1)項(xiàng)目集族已構(gòu)造出來了。構(gòu)造一程序,檢查兩個(gè)LR(1)項(xiàng)目集是否為同心集(可任意輸入),若是,則輸出合并后的同心集,并檢查合并后的集合是否含有沖突項(xiàng)目(指出存在何種沖突),輸出合并同心集后的識(shí)別文法活前綴的DFA,及LALR(1)項(xiàng)目集規(guī)范族。42. 題目: LALR(1)分析表自動(dòng)構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:對(duì)任意給定的文法G構(gòu)造LR(1)項(xiàng)目集規(guī)范族(按教材P.115所述方法構(gòu)造,要求實(shí)現(xiàn)CLOSURE(I)、GO(I,X)、FIRST(集合FIRST的構(gòu)造方法參見教材P.78);然后構(gòu)造LALR(1)項(xiàng)目集規(guī)范族;再實(shí)現(xiàn)LALR(1)分析表構(gòu)造算法。以教材P.115例5.13為輸入,構(gòu)造并輸出其LALR(1)分析表5.6。43. 題目: 帶出錯(cuò)處理的LR分析器總控程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:按教材P.127表5.9分析表構(gòu)造一LR分析器,輸出語法分析過程(如P.128所述),要構(gòu)造各出錯(cuò)處理子程序。44. 題目: 算術(shù)表達(dá)式從中綴式翻譯成后綴式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將算術(shù)表達(dá)式從中綴式翻譯成后綴式。要求:先確定一個(gè)定義算術(shù)表達(dá)式的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的算術(shù)表達(dá)式,程序?qū)⑵滢D(zhuǎn)換成后綴式輸出。45. 題目:將算術(shù)表達(dá)式轉(zhuǎn)換成抽象語法樹的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將算術(shù)表達(dá)式轉(zhuǎn)換成抽象語法樹。要求:先確定一個(gè)定義算術(shù)表達(dá)式的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的算術(shù)表達(dá)式,程序?qū)⑵滢D(zhuǎn)換成抽象語法樹輸出(可按一定格式輸出到指定文件中)。46. 題目:將算術(shù)表達(dá)式轉(zhuǎn)換成DAG的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將算術(shù)表達(dá)式轉(zhuǎn)換成DAG。要求:先確定一個(gè)定義算術(shù)表達(dá)式的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的算術(shù)表達(dá)式,程序?qū)⑵滢D(zhuǎn)換成DAG輸出(可按一定格式輸出到指定文件中)。
第7頁 47. 題目:將算術(shù)表達(dá)式轉(zhuǎn)換成三元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將算術(shù)表達(dá)式翻譯成三元式。要求:先確定一個(gè)定義算術(shù)表達(dá)式的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的算術(shù)表達(dá)式,程序?qū)⑵滢D(zhuǎn)換成三元式輸出(可按一定格式輸出到指定文件中)。48. 題目:將算術(shù)表達(dá)式轉(zhuǎn)換成間接三元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將算術(shù)表達(dá)式翻譯成間接三元式。要求:先確定一個(gè)定義算術(shù)表達(dá)式的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的算術(shù)表達(dá)式,程序?qū)⑵滢D(zhuǎn)換成間接三元式輸出(可按一定格式輸出到指定文件中)。49. 題目:將算術(shù)表達(dá)式轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將算術(shù)表達(dá)式翻譯成四元式。要求:先確定一個(gè)定義算術(shù)表達(dá)式的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的算術(shù)表達(dá)式,程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。50. 題目:將布爾表達(dá)式轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將布爾表達(dá)式翻譯成四元式。要求:先確定一個(gè)定義布爾表達(dá)式的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的布爾表達(dá)式,程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。51. 題目:將條件語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將條件語句翻譯成四元式。要求:先確定一個(gè)定義條件語句的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的條件語句,程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。52. 題目:將WHILE語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將WHILE語句翻譯成四元式。
第8頁 要求:先確定一個(gè)定義WHILE語句的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的WHILE語句,程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。53. 題目:將FOR語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將FOR語句翻譯成四元式。要求:先確定一個(gè)定義FOR語句的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的FOR語句,程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。54. 題目:將SWITCH語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將SWITCH語句翻譯成四元式。要求:先確定一個(gè)定義SWITCH語句的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的SWITCH語句,程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。55. 題目:將包含數(shù)組引用的賦值語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,將包含數(shù)組引用的賦值語句翻譯成四元式。要求:先確定一個(gè)定義包含數(shù)組引用的賦值語句的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一個(gè)正確的包含數(shù)組引用的賦值語句,程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。56. 題目:嵌套過程中的說明語句翻譯的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:設(shè)計(jì)一個(gè)語法制導(dǎo)翻譯器,完成對(duì)說明語句的翻譯,即構(gòu)造每個(gè)過程的符號(hào)表,填寫所有名字在符號(hào)表中的有關(guān)信息。要求:先確定一個(gè)定義允許嵌套過程的說明語句的文法,為其設(shè)計(jì)一個(gè)語法分析程序,為每條產(chǎn)生式配備一個(gè)語義子程序,按照一遍掃描的語法制導(dǎo)翻譯方法,實(shí)現(xiàn)翻譯程序。對(duì)用戶輸入的任意一組正確的說明語句,程序?qū)⑤敵鱿鄳?yīng)的符號(hào)表(可按一定格式輸出到指定文件中)。57. 題目:基本塊劃分算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:根據(jù)基本塊劃分算法,構(gòu)造一個(gè)基本塊劃分程序,實(shí)現(xiàn):對(duì)于任意輸入的一個(gè)四元式程序,將其劃分為基本塊,輸出各基本塊,并輸出程
第9頁 序流圖。以P.279例10.1為輸入,輸出P.281圖10.8.58. 題目:將基本塊轉(zhuǎn)換成DAG的算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:根據(jù)將基本塊轉(zhuǎn)換成DAG的算法,實(shí)現(xiàn):對(duì)于任意輸入的一個(gè)基本塊(四元式程序),將其轉(zhuǎn)換成DAG并輸出(可按一定格式輸出到指定文件中)。以P.283例10.4為輸入,輸出P.284圖10.10構(gòu)造過程。59. 題目:由DAG重構(gòu)基本塊的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求:按照DAG節(jié)點(diǎn)構(gòu)造順序,重構(gòu)基本塊四元式代碼。輸入的DAG按一定格式存于指定文件中,輸出的基本塊四元式代碼按一定格式輸出到指定文件中。以P.284圖10.10為輸入,輸出基本塊四元式代碼。60. 題目:局部?jī)?yōu)化程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求:根據(jù)將基本塊轉(zhuǎn)換成DAG的算法,實(shí)現(xiàn):對(duì)于任意輸入的一個(gè)基本塊(四元式程序),將其轉(zhuǎn)換成DAG;然后按照DAG節(jié)點(diǎn)構(gòu)造順序,重構(gòu)基本塊四元式代碼。以P.283例10.4為輸入,完成并輸出局部?jī)?yōu)化。
(待續(xù))
。。。(大家也可以自行設(shè)計(jì)一個(gè)設(shè)計(jì)題目)
第10頁