第一篇：編譯原理課程設(shè)計(jì)2011級
2011級《編譯原理課程設(shè)計(jì)》任務(wù)書
一、課程設(shè)計(jì)的性質(zhì)和目的編譯原理課程設(shè)計(jì)是計(jì)算機(jī)專業(yè)課程，通過課程設(shè)計(jì)使學(xué)生進(jìn)一步鞏固課堂所學(xué)知識，全面熟悉、掌握編譯程序編寫的基本設(shè)計(jì)方法和技巧，進(jìn)一步提高分析問題、解決問題及上機(jī)操作能力，為將來從事高層次的計(jì)算機(jī)軟件開發(fā)工作打下一定的專業(yè)基礎(chǔ)。
二、設(shè)計(jì)課題
課題一：應(yīng)用編譯原理的方法實(shí)現(xiàn)帶括號的四則混合運(yùn)算
給定條件：
1、詞法符號定義如下：
INTC ? D+
FLOATC ?(D+.D+)|(D+.)|(.D+)
FLOATC ?((D+.D+)|(D+.)|(.D+)|(D+))(E | e)(+ | ? | λ)D+
OPADD ? +
OPSUB ? ?
OPMUL ? *
OPDIV ? /
LPAREN ? ‘(’
RPAREN ? ‘)’
LINE ? ‘n’
ASSIGN ? =
2、表達(dá)式文法定義如下：
01.S ? E
02.E ? T
03.E ? EOPADDT
04.E ? EOPSUBT
05.T ? P
06.T ? TOPMULP
07.T ? TOPDIVP
08.P ? INTC
09.P ? FLOATC
10.P ? LPARENERPAREN
基本要求：
1、以ASSIGN作為文法結(jié)束符號；
2、應(yīng)用詞法分析技術(shù)識別單詞；
3、應(yīng)用SLR(1)分析技術(shù)判別表達(dá)式的合法性；
4、應(yīng)用尾動作文法技術(shù)計(jì)算表達(dá)式的類型與值；
5、要求表達(dá)式的類型與值嚴(yán)格一致。
課題二：Micro語言詞法語法分析
給定條件：
1、詞法符號定義如下：
ID ? L(L|D)*
INTC ? D+
REALC ? D+ ? D+
PLUS ? +
MULT ? *
LPAREN ?（RPAREN ?)
COLON ? ：
ASSIGN ? ：＝
SEMI ? ；
LINE ? ’n’
STOP ? ?
FEOF ? EOF2、表達(dá)式文法定義如下：
01.PROG ? BEGINDECLBODYENDSTOP
02.DECL ? DECLVARIDCOLONTYPESEMI
03.DECL ? VARIDCOLONTYPESEMI
04.TYPE ? REAL
05.TYPE ? INTEGER
06.BODY ? BODYSEMISTM
07.BODY ? STM
08.STM ? IDASSIGNEXP
09.STM ? WRITELPARENEXPRPAREN
10.STM ? READLPARENIDRPAREN
11.EXP ? EXPPLUSFACT
12.EXP ? FACT
13.FACT ? FACTMULTPRIM
14.FACT ? PRIM
15.PRIM ? ID
16.PRIM ? INTC
17.PRIM ? REALC
18.PRIM ? LPARENEXPRPAREN
基本要求：
1、以FEOF作為文法結(jié)束符號；
2、應(yīng)用詞法分析技術(shù)識別單詞；
3、應(yīng)用SLR(1)分析方法進(jìn)行語法分析；
4、報(bào)錯要指明所在行。
三、課程設(shè)計(jì)報(bào)告要求
1、課程設(shè)計(jì)報(bào)告必須按本系規(guī)定的格式要求打印成冊；
2、課程設(shè)計(jì)報(bào)告每人一份，正文必須包含如下幾個方面的內(nèi)容：
1)基本設(shè)計(jì)思想；
2)主要數(shù)據(jù)結(jié)構(gòu)；
3)總結(jié)與體會。
3、課程設(shè)計(jì)報(bào)告裝訂順序：封面、任務(wù)書、目錄、正文、源程序清單。
四、選題及考核辦法
1、一人一組，學(xué)號為奇數(shù)者做課題一，學(xué)號為偶數(shù)者做課題二。
2、成績考核按個人課題完成情況、設(shè)計(jì)報(bào)告質(zhì)量及對課程設(shè)計(jì)的態(tài)度等綜合評定。
五、設(shè)計(jì)進(jìn)度安排
1、講課時間安排：
待定
2、上機(jī)調(diào)試時間安排：
待定
3、答辯時間安排：
待定
4、其余時間：查閱資料，確定方案，設(shè)計(jì)課題相關(guān)程序。
第二篇：編譯原理課程設(shè)計(jì)
課 程 設(shè) 計(jì) 報(bào) 告
設(shè)計(jì)題目：一個簡單文法的編譯器前端的設(shè)計(jì)與實(shí)現(xiàn)
班
級： 計(jì)算機(jī)1206 組長學(xué)號：201239 組長姓名：閆智宣 指導(dǎo)教師：李曉華 設(shè)計(jì)時間：2014年12月
[在此處鍵入]
設(shè)計(jì)分工
組長學(xué)號及姓名： 20123974
閆智宣
分工：
語法分析，四元式生成，目標(biāo)代碼優(yōu)化及生成 組員1學(xué)號及姓名：20123977
廖峭 分工：
詞法分析，錯誤處理 組員2學(xué)號及姓名：20123959
郭天龍
分工：
符號表生成，語義動作插入，操作界面[在此處鍵入]
摘要
編譯原理課程設(shè)計(jì)是通過C語言編譯器相關(guān)子系統(tǒng)的設(shè)計(jì)，進(jìn)一步加深對編譯器構(gòu)造的理解；第一部分詞法分析，設(shè)計(jì)各單詞的狀態(tài)轉(zhuǎn)換圖，并為不同的單詞設(shè)計(jì)種別碼，制作掃描器識別一個個單詞，返回值為識別碼的序號，返回Token序列。將詞法分析器設(shè)計(jì)成供語法分析器調(diào)用的子程序。詞法分析器具備預(yù)處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設(shè)計(jì)一個供詞法分析調(diào)用的預(yù)處理子程序；第二部分，語法分析，用遞歸下降法，實(shí)現(xiàn)對表達(dá)式、各種說明語句、控制語句進(jìn)行語法分析。若語法正確，則用語法制導(dǎo)翻譯法進(jìn)行語義翻譯；生成并打印出語法樹；若語法錯誤，要求指出出錯性質(zhì)和出錯位置（行號）。
我們還做了附加功能，即編譯后端，有中間代碼優(yōu)化，生成目標(biāo)代碼匯編語言。通過此次課程設(shè)計(jì)，提高了我們的獨(dú)立分析問題、解決問題的能力，以及系統(tǒng)軟件設(shè)計(jì)的能力； 提高程序設(shè)計(jì)能力、程序調(diào)試能力，團(tuán)結(jié)協(xié)作能力
關(guān)鍵詞：詞法分析，語法分析，四元式生成，錯誤處理，符號表生成，語義動作插入，中間代碼優(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 符號表模塊
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 語義動作分析模塊
3.6.1功能 3.6.2 數(shù)據(jù)結(jié)構(gòu)
3.6.3算法
3.7 錯誤處理模塊
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.收獲、體會和建議。
[在此處鍵入]
1.概述
編譯器是將C語言翻譯為匯編語言代碼的計(jì)算機(jī)程序。編譯器將源程序（source language）編寫的程序作為輸入，翻譯產(chǎn)生目標(biāo)語言（target language）機(jī)器代碼的等價程序。通常地，源程序?yàn)楦呒壵Z言（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)一個 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ù)處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設(shè)計(jì)一個供詞法分析調(diào)用的預(yù)處理子程序；
b.能夠拼出語言中的各個單詞； [在此處鍵入]
c.返回（種別碼，屬性值，行號）。
（2）語法分析
要求用學(xué)習(xí)過的自底向上或自頂向下的分析方法等，實(shí)現(xiàn)對表達(dá)式、各種說明語句、控制語句進(jìn)行語法分析。若語法正確，則用語法制導(dǎo)翻譯法進(jìn)行語義翻譯；生成并打印出語法樹；若語法錯誤，要求指出出錯性質(zhì)和出錯位置（行號）。
3.算法及數(shù)據(jù)結(jié)構(gòu)
3.1算法的總體思想（流程）
本節(jié)主要分析程序的代碼結(jié)構(gòu)和代碼工程文件的劃分。（程序由幾個類組成: Token類和Variable類SymbolTable類ObjectCode類Lexical類Grammar類Four_Yuan類Action類ErrorItem類，分別為詞法分析和語法分析類。工程分為幾個文件：Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs分別對應(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類的對象作為Lexical類的一個成員變量，配合Grammer類進(jìn)行語法分析。
工程文件總體上是按照九個類的格局分為十個文件，分別是九個類的聲明文件和實(shí)現(xiàn)文件。十個文件為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類的對象(Token)作為Grammer類中的一個成員變量，配合Grammer類進(jìn)行語法分析。它們的關(guān)系是這樣的：Grammer類的一個成員變量temp首先對源程序刪除注釋，然后進(jìn)行詞法分析獲取所有Token，并將獲取的Token存儲在Token對象的tokenList（List類型）中。然后Grammer類的語法分析程序就根據(jù)tokenList中的Token進(jìn)行語法分析，生成語法樹，最后打印語法樹。同時，這也是程序的流程。[在此處鍵入]
3.2 詞法分析模塊 3.2.1功能
Lexical類主要的工作是詞法分析獲取Token序列。
3.2.2數(shù)據(jù)結(jié)構(gòu)
詞法分析階段的代碼被封裝成一個類——Lexical，Token中主要是Lexical類的聲明代碼，Lexical.cs中主要是Lexical類的實(shí)現(xiàn)代碼。Lexical類對外提供的函數(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)，以上幾個函數(shù)構(gòu)成了詞法分析的骨架，在Lexical類中還有其他成員變量和函數(shù)，主要作為這三個函數(shù)處理過程的中間步驟，為這三個函數(shù)服務(wù)。Lexical類的代碼結(jié)構(gòu)和主要的成員變量和函數(shù)及其含義如下圖所示：
3.2.3算法
算法的基本任務(wù)是從字符串表示的源程序中識別出具有獨(dú)立意義的單詞符號，其基本思想是[在此處鍵入]
根據(jù)掃描到單詞符號的第一個字符的種類，拼出相應(yīng)的單詞符號。
主程序示意圖：
主程序示意圖如圖3-1所示。
⑴ 關(guān)鍵字表的初值。
關(guān)鍵字作為特殊標(biāo)識符處理，把它們預(yù)先安排在一張表格中（稱為關(guān)鍵字表），當(dāng)掃描程序識別出標(biāo)識符時，查關(guān)鍵字表。如能查到匹配的單詞，則該單詞為關(guān)鍵字，否則為一般標(biāo)識符。
（2）程序中需要用到的主要變量為type和number 掃描子程序的算法思想：
首先設(shè)置3個變量： [在此處鍵入]
①token用來存放構(gòu)成單詞符號的字符串； ②number用來整型單詞；
③type用來存放單詞符號的種別碼。
Token定義
Token定義:
Token類型（TokenType）:
3.3 語法分析模塊
3.3.1功能
語法分析是編譯過程的一個邏輯階段。語法分析的功能是在詞法分析的基礎(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)識符
S 語句
P 語句塊
E 加減算術(shù)表達(dá)式
D 逗號表達(dá)式
T 乘除算術(shù)表達(dá)式
C 關(guān)系表達(dá)式
L 邏輯表達(dá)式
Q 標(biāo)識符或圓括號
e 表示空
i 表示標(biāo)識符 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.遞歸下降程序流程圖
對應(yīng)于每個文法編寫如下遞歸下降子程序
主程序（B）[在此處鍵入] [在此處鍵入]
3.4 符號表模塊
3.4.1功能
進(jìn)行符號表的儲存，添加，更新，查找，保存標(biāo)識符活躍信息以及輸出。3.4.2 數(shù)據(jù)結(jié)構(gòu)
在此處鍵入]
3.4.3算法
3.5 四元式模塊
3.5.1功能
四元式為中間代碼，編譯程序進(jìn)行完語義分析后，先生成中間代碼作為過渡，此時中間代碼與目標(biāo)代碼已經(jīng)比較相似
3.5.2 數(shù)據(jù)結(jié)構(gòu)
[ 在此處鍵入]
3.5.3算法
3.6語義動作分析模塊
3.6.1功能
在語法分析中嵌入相應(yī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 錯誤處理模塊
3.7.1功能 保存運(yùn)行時發(fā)現(xiàn)的錯誤，儲存行號已經(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)錯誤時保存錯誤信息以及行號。
public static string PrintErrorList()把所有發(fā)現(xiàn)的錯誤格式化后統(tǒng)一輸出。
錯誤信息在語法分析，語義分析，符號表檢錯中添加。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算法
對于一個基本塊有如下流程圖
W：操作符，B：第一操作數(shù)，C：第二操作數(shù)，R：寄存器
5.結(jié)論
網(wǎng)上找一段話抄上 [在此處鍵入]
6.測試
測試打開文件
測試保存文件
如果沒打開文件，直接敲代碼，點(diǎn)保存時會彈出另存為窗口[在此處鍵入]
測試錯誤檢測，程序缺少main函數(shù)的類型，錯誤列表中顯示第一行函數(shù)缺少錯誤類型。
測試錯誤檢測，程序缺少分號，錯誤列表中顯示該行缺少語句結(jié)束標(biāo)志';' 單擊錯誤列表，會自動選定錯誤行
編譯成功，生成并顯示token串、符號表、四元式與目標(biāo)代碼 [在此處鍵入]
測試if與while語句，而且while嵌套在if當(dāng)中
測試goto語句，結(jié)果正確。[在此處鍵入]
測試優(yōu)化，輸入課件中的代碼，結(jié)果與課件一樣
6.參考文獻(xiàn)。
1、陳火旺.《程序設(shè)計(jì)語言編譯原理》（第3版）.北京：國防工業(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.收獲、體會和建議。
直接拷貝好歹也檢查一下錯誤
對于編譯原理的這次課程設(shè)計(jì)，自己經(jīng)歷了從剛開始的不懂?明白任務(wù)的要求和內(nèi)容?理論知識的了解?開始著手寫代碼?完成基本功能?根據(jù)DFA及自頂向下等理論修改完善代碼等這些過程。
自己著手寫詞法分析的時候還不清楚詞法分析的任務(wù)內(nèi)容，還不知道詞法分析的結(jié)果是什么，詞法分析出錯的情況和類型有哪些，也總是將詞法分析和語法分析混在一起，不明白哪些錯誤在詞法分析中報(bào)，哪些錯誤在語法分析中判斷，后來經(jīng)過查書、網(wǎng)上資料、請教同學(xué)等途徑逐步清晰了詞法分析的工作內(nèi)容是從源代碼文件中獲取出Token，供語法分析使用。在充分了解了語法分析需要哪些信息時，我才真正了解了詞法分析的工作內(nèi)容和目標(biāo)，才知道詞法分析需要完成哪些任務(wù)獲取到哪些信息。充分了解了詞法分析的任務(wù)之后，就開始理論知識的學(xué)習(xí)。經(jīng)過揣摩書上的例子，自己理解和掌握了怎么設(shè)計(jì)過濾注釋和分析程序中Token的DFA，于是開始根據(jù)設(shè)計(jì)好的DFA進(jìn)行編碼，最后經(jīng)過調(diào)試已經(jīng)可以正確地完成詞法階段的任務(wù)了。這只是詞法分析的原始代碼，在之后還進(jìn)行了兩次徹底的改動。雖然之前寫的詞法分析的代碼已經(jīng)完成了詞法分析的需求，也是根據(jù)DFA的原理編寫的，但是在代碼結(jié)構(gòu)上卻難以體現(xiàn)，在對書上的根據(jù)已知DFA寫代碼的例子進(jìn)行了詳細(xì)的研究之后，發(fā)現(xiàn)自己的代碼并沒有像書上那樣完全按照所依據(jù)的DFA各狀態(tài)轉(zhuǎn)移的關(guān)系進(jìn)行編寫，所以對代碼進(jìn)行了重寫，像書上一樣嚴(yán)格按照狀態(tài)之間轉(zhuǎn)移的方式進(jìn)行編寫，將狀態(tài)劃分成11個狀態(tài)，狀態(tài)分別按1~11進(jìn)行標(biāo)注，程序也按照DFA來編寫，也實(shí)現(xiàn)了詞法分析的功能。再后來寫報(bào)告的時候，發(fā)現(xiàn)分析出Token的那個DFA并不是最簡的，有很多多余的狀態(tài)，完全可以用一個flag標(biāo)志來標(biāo)識，從而簡化代碼結(jié)構(gòu)，于是又重寫了一次詞法分析函數(shù)scan()的代碼，將狀態(tài)縮減為5個，且不再用1-5來表示，而是像書上那樣分別取了名字（START、INNUM、INID、INDBSYM、DONE），同時為了簡化代碼將輸出Token到文件的部分從scan()中剝離開來，而在Lexical類中加了一個printToken()的函數(shù)，使scan()函數(shù)邏輯更加清晰，使讀者能夠容易地將代碼與DFA進(jìn)行查看比照。
在寫語法分析的時候，已經(jīng)對編譯器的語法分析的內(nèi)容有了一定的了解，所以直接進(jìn)行了理論的學(xué)習(xí)。首先自己對遞歸向下分析法進(jìn)行了學(xué)習(xí)，將書上的幾個遞歸向下分析的偽代碼看過之后，自己對遞歸向下的分析方法的原理有了初步的認(rèn)識，大概知道了根據(jù)文法怎么分析，但是對于如何編寫代碼卻還在此處鍵入]
是難以下手，于是就對照TINY語言的文法看了幾遍書后面的TINY語言的遞歸向下分析的語法分析程序，這樣就基本知道了C-語言的語法分析程序怎么寫。由于C-語言給出的文法有左遞歸存在，于是自己將存在左遞歸的文法改寫成EBNF的形式，并據(jù)此進(jìn)行代碼編寫。由于在編寫代碼的過程中需要確定分析是否正確或選擇多個文法中的某一個文法進(jìn)行分析，有時必須探測需要的或下一個Token的類型，在這種情況下需要求First集合，在推導(dǎo)中若存在empty，又需要求Follow集合，所以這樣又需要我了解First集合和Follow集合，自己在程序中也根據(jù)求出的First集合和Follow集合進(jìn)行判斷，以確定程序的走向。在編寫過程中，還有一類問題，就是存在公共左因子，如文法expression→ var = expression | simple-expression，左因子為ID，在分析過程中，由于已經(jīng)取出了一個ID的Token，且生成了一個IdK的節(jié)點(diǎn)，但是在當(dāng)前狀態(tài)無法確定是哪一個推導(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并滿足語法階段的所有要求，能夠判別詞法分析階段是否出錯和出錯類型和位置。語法分析主要能根據(jù)遞歸向下的分析思想和C-文法對詞法分析獲取的Token進(jìn)行語法分析，能夠構(gòu)造出語法樹，能夠判別語法分析過程中是否出錯以及出錯位置和錯誤類型。
由于在編寫程序過程中，涉及到了正則表達(dá)式、DFA、提取公共左因子、消除左遞歸、EBNF、求First集合和Follow集合、遞歸向下分析方法以及編程語言方面的知識，所以，通過本次的課程設(shè)計(jì)的實(shí)踐，使得自己對編譯原理這門課的許多知識點(diǎn)有了更加深刻和具體的理解，而不再只限制于做題。此外，對以前那些已掌握的知識有了溫習(xí)和動手鍛煉的機(jī)會。如：以前在編譯原理課上雖然知道First集合和Follow集合怎么求的，卻不知道First集合和Follow集合到底是干什么的，通過編寫程序自己明白了他們的實(shí)際作用，使得自己不僅知其然還知其所以然，從而使得自己加深了對知識點(diǎn)的理解和掌握。由于以前編寫代碼都是使用JAVA語言，所以C/C++很多內(nèi)容都忘記了，通過本次的實(shí)踐，自己又重新拾起了以前的知識。此外，由于在做報(bào)告的時候，需要描繪DFA和程序流程圖，使得自己初步掌握了使用visio和word畫圖的能力。此外，對于文檔的編寫和美化自己也獲得了許多有用的經(jīng)驗(yàn)。[
第三篇：編譯原理課程設(shè)計(jì)簡介
編譯原理實(shí)踐課程
編譯原理課程是計(jì)算機(jī)專業(yè)必修的一門重要的專業(yè)基礎(chǔ)課程，也是計(jì)算機(jī)系統(tǒng)軟件中非常重要的一個分支，經(jīng)過多年建設(shè)取得了豐碩的教學(xué)成果：2003年被評為“吉林大學(xué)百門精品課程”之一，2004年被評為吉林省精品課程，2006年被評為教育部—微軟精品課程。編譯原理實(shí)踐課程建設(shè)作為新世紀(jì)教學(xué)改革重點(diǎn)項(xiàng)目和編譯原理精品課程建設(shè)的一個重要組成部分，在教材建設(shè)、教學(xué)內(nèi)容和教學(xué)方法的改革等方面也取得了較突出的成績，并發(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í)，理解編譯原理的同時，注重學(xué)生實(shí)踐能力的培養(yǎng)，進(jìn)一步鞏固對知識的理解，通過實(shí)際的鍛煉，掌握編譯技術(shù)，進(jìn)而能夠獨(dú)立的進(jìn)行編譯器的設(shè)計(jì)。
二、實(shí)驗(yàn)內(nèi)容及要求
編譯程序不同于一般的應(yīng)用程序，是一個十分龐大和復(fù)雜的系統(tǒng)軟件。一般的應(yīng)用程序是以數(shù)據(jù)作為操作對象，而編譯程序則是以程序作為操作對象，是一個元級處理程序，它所包含的算法和思想比較特殊，理論性較強(qiáng)，抽象度也較高，因而編譯原理課程一直以來都是計(jì)算機(jī)專業(yè)學(xué)生比較難于理解和掌握的一門課程。為此我們開設(shè)編譯原理實(shí)踐課程。編譯原理實(shí)踐課程的主要實(shí)踐題目有：
實(shí)驗(yàn)一： 詞法分析程序開發(fā)
實(shí)驗(yàn)要求： 1.掌握詞法分析程序自動生成工具LEX的使用。
2.掌握各類單詞的形式描述。
3.學(xué)會用數(shù)據(jù)中心法實(shí)現(xiàn)有限自動機(jī)。4.學(xué)會用直接轉(zhuǎn)向法實(shí)現(xiàn)有限自動機(jī)。5.獨(dú)立完成SNL語言的詞法分析器。
實(shí)驗(yàn)二： 遞歸下降語法分析
實(shí)驗(yàn)要求： 1.理解遞歸下降語法分析方法的主要原理。
2.理解遞歸下降分析法對文法的要求。
3.熟練掌握Predict集合的求法。
4.熟練掌握文法變換算法（消除左遞歸和消除公共前綴）。實(shí)驗(yàn)三： LL(1)語法分析
實(shí)驗(yàn)要求： 1.理解LL(1)分析法的主要原理。
2.理解LL(1)分析法對文法的要求。
3.熟練掌握Predict集合的求法。
4.通過編程熟練掌握LL(1)分析法的工作過程。實(shí)驗(yàn)四： 符號表管理
實(shí)驗(yàn)要求： 1.了解符號表在編譯過程中的重要作用。
2.掌握符號表應(yīng)包含的符號的屬性信息。3.了解符號表的組織原則。4.掌握符號表的操作。
5.掌握符號表的可見性問題。
實(shí)驗(yàn)五： 語義檢查
實(shí)驗(yàn)要求： 1.了解語義檢查是語義分析的一個重要內(nèi)容。
2.掌握語義檢查的一般內(nèi)容。
3.學(xué)會在語法分析的同時進(jìn)行語義檢查。4.學(xué)會將語義分析作為一遍獨(dú)立的掃描。
實(shí)驗(yàn)六： 中間代碼生成
實(shí)驗(yàn)要求： 1.了解中間代碼生成是為優(yōu)化和移植而進(jìn)行的。
2.了解幾種常見中間代碼表示形式掌握符號表應(yīng)包含的符號的屬性信息。
3.會用簡單的程序?qū)崿F(xiàn)中綴式到后綴式的轉(zhuǎn)換。4.會用棧實(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á)式局部優(yōu)化算法。
3.理解公共表達(dá)式局部優(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í)踐，我們在編譯原理實(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í)際動手編程，將抽象的編譯理論知識具體化和形象化，加深了對基本概念和方法的理解和運(yùn)用，從而全面系統(tǒng)地掌握了編譯器的構(gòu)造過程。
該課程采用教研室自編實(shí)踐教材《編譯程序設(shè)計(jì)與實(shí)現(xiàn)》（高等教育出版社）作為輔導(dǎo)教材，通過對教材中提供的編譯實(shí)例的透徹解析，加深了學(xué)生對編譯程序的直觀認(rèn)識，提高了學(xué)生對源程序的分析和設(shè)計(jì)能力。同時，對學(xué)生學(xué)習(xí)、理解和掌握編譯原理理論課程也有很大的促進(jìn)作用。在課程中，學(xué)生通過親自動手實(shí)踐，把原理性的抽象理論知識具體化和形象化，消化了課堂上、書本中難于理解的概念和方法，全面系統(tǒng)的掌握了編譯器的構(gòu)造過程，激發(fā)了學(xué)生的學(xué)習(xí)興趣，培養(yǎng)了學(xué)生進(jìn)行更深入學(xué)習(xí)的主動性。在教學(xué)方法上，結(jié)合多媒體課件，強(qiáng)調(diào)啟發(fā)式教學(xué)，培養(yǎng)學(xué)生的創(chuàng)新能力和動手實(shí)踐能力。實(shí)踐證明，這些教學(xué)方式的嘗試在實(shí)際教學(xué)中取得了良好的教學(xué)效果。
教學(xué)環(huán)境：
擁有良好的實(shí)踐教學(xué)環(huán)境，已建成3個大型網(wǎng)絡(luò)化、多媒體微機(jī)實(shí)驗(yàn)室，共有800臺奔IV微機(jī)，32臺服務(wù)器，實(shí)驗(yàn)室面積為2040平方米，完全能夠滿足教學(xué)實(shí)踐要求，通過開放式的實(shí)踐教學(xué)，收到了良好的教學(xué)效果。除實(shí)踐課程中規(guī)定的實(shí)驗(yàn)之外，還設(shè)計(jì)了一些難度較大的選作實(shí)驗(yàn)題目，激發(fā)學(xué)生的能動性，提高學(xué)生分析問題、解決問題的能力。教學(xué)手段：
1.多媒體輔助教學(xué)軟件－PCMCAI（Principle of Compile Multimedia CAI）在教學(xué)過程中，我們發(fā)現(xiàn)由于編譯原理理論性強(qiáng)，抽象度高，學(xué)生不易于理解。針對這一情況，我們研制了編譯原理多媒體輔助教學(xué)軟件－PCMCAI（Principle of Compile Multimedia CAI），該軟件以多媒體動畫的形式生動形象地描述了編譯器的各個階段的工作過程。借助現(xiàn)代化的教學(xué)手段和工具，將抽象的知識具體化，便于學(xué)生理解復(fù)雜的原理，極大地調(diào)動了學(xué)生的學(xué)習(xí)積極性，學(xué)習(xí)效果有了明顯的提高；
2.編譯實(shí)例庫
我們完成了編譯實(shí)例庫的構(gòu)建，建立實(shí)例庫的目的是使學(xué)生通過編譯實(shí)例庫，可以了解和掌握不同類型語言的編譯原理和構(gòu)造技術(shù)，培養(yǎng)學(xué)生的主動參與、自主思考和創(chuàng)新能力，擴(kuò)大學(xué)生的知識面。通過實(shí)踐課程，我們總結(jié)和綜合了學(xué)生中優(yōu)秀的設(shè)計(jì)實(shí)例，同時，廣泛的收集當(dāng)前國內(nèi)外最新的素材資料，對編譯實(shí)例庫不斷地進(jìn)行完善。目前，實(shí)例庫已經(jīng)初具規(guī)模并投入使用，為學(xué)生提供了廣泛的實(shí)踐素材和范例，在教學(xué)過程中作為一種輔助教學(xué)手段，效果良好。
3.網(wǎng)絡(luò)教學(xué)平臺：http://softlab.jlu.edu.cn 針對目前學(xué)生人數(shù)增多，教學(xué)資源不足，學(xué)生質(zhì)量參差不齊，教學(xué)質(zhì)量和效率得不到保證的情況，我們充分利用Internet，建立和實(shí)施網(wǎng)絡(luò)課程體系，利用Internet在信息制造、貯存和遞送方面的優(yōu)勢，克服資源不足的缺點(diǎn)，同時也為學(xué)生提供了完全個性化的學(xué)習(xí)環(huán)境，發(fā)揮網(wǎng)絡(luò)教學(xué)優(yōu)勢。目前我們已經(jīng)開始了這方面的建設(shè)，完成了編譯原理實(shí)例庫、課件、習(xí)題庫等方面的建設(shè)，構(gòu)建了網(wǎng)絡(luò)課程的框架體系，目前正著手網(wǎng)絡(luò)課程的進(jìn)一步完善工作。
四、教材及課件
教材建設(shè)：
1.校內(nèi)教材：《一個教學(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í)例庫（C語言版本）。4.編譯原理實(shí)例庫（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.《測試語言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é)方法研究》，張晶等，全國首屆計(jì)算機(jī)程序設(shè)計(jì)類課程教學(xué)研討會，2005(9)。7.《“編譯原理”課程建設(shè)研究》，劉磊等，計(jì)算機(jī)教育，2006(6)。獲得獎勵：
1.2004年，《編譯原理實(shí)踐課程建設(shè)》，吉林大學(xué)教學(xué)成果二等獎。2.2006年，《編譯程序的設(shè)計(jì)與實(shí)現(xiàn)》一書獲吉林大學(xué)本科優(yōu)秀教材。3.2002年，編譯原理CAI課件－PCMCAI獲被吉林省教育廳評為二等獎，并在第六屆全國多媒體教育軟件大獎賽上獲得優(yōu)秀獎。
4.《編譯原理》課程先后被評為吉林大學(xué)精品課程、吉林省精品課程及教育部-微軟精品課程。
總之，經(jīng)過多年的研究、探索與實(shí)踐，我們在編譯原理實(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í)際動手編程，將抽象的編譯理論知識具體化和形象化，加深了對基本概念和方法的理解和運(yùn)用，從而全面系統(tǒng)地掌握了編譯器的構(gòu)造過程。該課程采用我們自編實(shí)踐教材《編譯程序設(shè)計(jì)與實(shí)現(xiàn)》作為輔導(dǎo)教材，通過對教材中提供的編譯實(shí)例的透徹解析，加深了學(xué)生對編譯程序的直觀認(rèn)識，提高了學(xué)生對源程序的分析和設(shè)計(jì)能力。同時，對學(xué)生學(xué)習(xí)、理解和掌握編譯原理理論課程也有很大的促進(jìn)作用。在教學(xué)方法上，結(jié)合多媒體課件，強(qiáng)調(diào)啟發(fā)式教學(xué)，培養(yǎng)學(xué)生的創(chuàng)新能力和動手實(shí)踐能力。實(shí)踐證明，這些教學(xué)方式的嘗試在實(shí)際教學(xué)中取得了良好的教學(xué)效果。
附件（獲得獎勵證書）
第四篇：《編譯原理課程設(shè)計(jì)》教學(xué)大綱
《編譯原理課程設(shè)計(jì)》教學(xué)大綱
課程名稱： 課程編號： 適用專業(yè)： 總 學(xué) 分： 總 周 時： 主 撰 人： 撰寫日期：
一、目的與任務(wù)
通過程序設(shè)計(jì)上機(jī)調(diào)試程序?qū)崿F(xiàn)算法，學(xué)習(xí)編譯程序調(diào)試技巧和設(shè)計(jì)編譯程序的一般原則，加深對詞法分析、語法分析、語義分析和中間代碼生成等編譯階段及實(shí)用編譯系統(tǒng)的認(rèn)識，初步掌握編譯程序構(gòu)造的基本原理與技術(shù), 從形式語言理論的角度, 進(jìn)一步認(rèn)識與理解程序設(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è)計(jì)的時間為2周，目的是通過實(shí)際的題目如：詞法分析、語法分析、代碼優(yōu)化等，使學(xué)生了解和掌握編譯程序的工作原理，同時培養(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ù)存儲結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問題的算法，描述算法可以使用自然語言、偽代碼、或函數(shù)的方式。
給出實(shí)現(xiàn)功能的一組或多組測試數(shù)據(jù)（測試文法），程序調(diào)試后，將按照此測試數(shù)據(jù)進(jìn)行測試的結(jié)果列出來。
如果程序不能正常運(yùn)行或運(yùn)行過程中出現(xiàn)了不滿足算法思想的情況，寫出出現(xiàn)這一情況的原因或改進(jìn)行的方法。
源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。
程序能夠運(yùn)行，要有基本的容錯功能。盡量避免出現(xiàn)操作錯誤時出現(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é)果分析 ⑧收獲及體會 3．實(shí)施方式
本次課程設(shè)計(jì)分成9個題目，都有一定的工作量，涵蓋本課程內(nèi)容和實(shí)際應(yīng)用相關(guān)的主要技術(shù)，學(xué)生可以自由組隊(duì)選擇其中一個實(shí)現(xiàn)。課程設(shè)計(jì)題目見“主要內(nèi)容”。
根據(jù)老師給定的9個題目進(jìn)行分析設(shè)計(jì)，本次課程設(shè)計(jì)采取分組的辦法進(jìn)行，3-4人為一組，要求每組學(xué)生在規(guī)定時間內(nèi)獨(dú)立完成。4．答辯：課題的論述、測試及問題回答
三、課程設(shè)計(jì)內(nèi)容
1、詞法分析器的構(gòu)造：
人們理解一個程序，起碼是在單詞級別上來思考。同樣，在編繹一個程序時，也是在單詞級別上來分析和翻譯源程序。詞法分析是編繹的基礎(chǔ)，執(zhí)行詞法分析的程序即為詞法分析器，它的任務(wù)是對輸入或給定的源程序，從左至右逐個字符進(jìn)行掃描，產(chǎn)生一個個單詞符號，把作為字符串的源程序改造成單詞符號串的中間程序。設(shè)計(jì)目的與任務(wù)：
通過本課程設(shè)計(jì)教學(xué)所要求達(dá)到的目的是：對詞法分析工作流程進(jìn)行總體設(shè)計(jì)和詳細(xì)設(shè)計(jì)，最終用C語言來設(shè)計(jì)一個簡單詞法分析器，實(shí)現(xiàn)對源程序的詞法分析功能，對輸入程序去除注釋，并以二元式形式輸出程序中所有單詞。
2、正則表達(dá)式到NFA 在編譯系統(tǒng)中，詞法分析階段是整個編譯系統(tǒng)的基礎(chǔ)。對于單詞的識別，有限自動機(jī)FA是一種十分有效的工具。有限自動機(jī)由其映射f是否為單值而分為確定的有限自動機(jī)DFA和非確定的有限自動機(jī)NFA。在非確定的有限自動機(jī)NFA中，由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進(jìn)行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。這種不確定性給識別過程帶來的反復(fù)，無疑會影響到FA的工作效率。而DFA引擎在任意時刻必定處于某個確定的狀態(tài)，它搜索是無需象NFA一樣必須記錄所有的可能路徑（trace multiple possible routes through the NFA），這也是DFA運(yùn)行效率高于NFA的原因。而已經(jīng)證明DFA是NFA的一個特例，即對于每一個NFA M存在一個DFA M’’，使得L(M)=L(M’’)。
設(shè)計(jì)目的與任務(wù)
通過本課程設(shè)計(jì)教學(xué)所要求達(dá)到的目的是：充分理解和掌握NFA，DFA以及NFA確定化過程的相關(guān)概念和知識，編程實(shí)現(xiàn)對輸入的任意正規(guī)式轉(zhuǎn)換成NFA的形式輸出。
3、NFA的確定化
有限自動機(jī)理論是描述詞法規(guī)則的基本理論。一條詞法規(guī)則表示一個正規(guī)表達(dá)式(又叫正規(guī)式)，而一個正規(guī)式又可化為一個DFA(確定有窮自動機(jī))，這個有限自動機(jī)可用來識別詞法規(guī)則所定義的所有單詞符號。把程序設(shè)計(jì)語言的所有詞法規(guī)則都構(gòu)造出相應(yīng)的有限自動機(jī),就得到一個詞法分析器。然后,再轉(zhuǎn)換為計(jì)算機(jī)可識別的程序就能自動實(shí)現(xiàn)詞法的分析和檢查。在實(shí)際應(yīng)用中，用NFA(不確定有窮自動機(jī))識別詞法存在不確定和狀態(tài)的冗余,因而,就要將NFA(不確定有窮自動機(jī))轉(zhuǎn)換為DFA(確定有窮自動機(jī)),消除了不可到達(dá)和不確定。設(shè)計(jì)目的與任務(wù)
通過本課程設(shè)計(jì)教學(xué)所要求達(dá)到的目的是：掌握從NFA到DFA的轉(zhuǎn)換，以及用子集法把NFA轉(zhuǎn)換成DFA理論，編程實(shí)現(xiàn)將NFA(不確定有窮自動機(jī))轉(zhuǎn)換為DFA(確定有窮自動機(jī))。
4、DFA的最小化
確定性有限自動機(jī)(DFA ,Deterministic Finite Automata)的最小化仍是有限自動機(jī)應(yīng)用及實(shí)現(xiàn)方面的重要問題之一。DFA的最小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系，便于其存儲實(shí)現(xiàn)，便于建立用DFA描述的任務(wù)模型，一些理論問題也與最小化思想有關(guān)。DFA的最小化是指,構(gòu)造一個與之等價且狀態(tài)數(shù)最小的DFA,即等價最小DFA。許多文獻(xiàn)給出了一個最小化算法，算法的思想是，構(gòu)造狀態(tài)集的一個劃分，再將這個劃分中的每個子集作為新的狀態(tài)，從而得到等價最小DFA。
DFA的最小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系，便于其存儲實(shí)現(xiàn),便于建立用DFA描述的任務(wù)模型，一些理論問題也與最小化思想有關(guān)。
5、語法分析之LL(1)文法
通過該課程設(shè)計(jì)了解了程序語言的自上而下的語法分析過程,提高了編程能力,能使我們了解編程語言更多的細(xì)節(jié) 設(shè)計(jì)目的與任務(wù)（1）讀入文法（2）求出first(), follow()（3）判斷是否為LL(1)文法
（4）若是，構(gòu)造分析表；
（5）輸入一個字符串看是否是文法的一個句子。
6、算符優(yōu)先文法
一個文法，如果它的任一產(chǎn)生式的右邊都不含有兩個相繼（并列）的非終結(jié)符，即不 含有如下形式的產(chǎn)生式的右部：
?QR?
則我們稱該文法為算符文法。
假設(shè)文法中的任意兩個終結(jié)符之間最多只有一個優(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)造一個最右推導(dǎo)的逆過程。這種方法可以適用于很大一類上下無關(guān)文法的語法分析。LR方法的基本思想是：在規(guī)范歸約過程中，一方面記住已經(jīng)移進(jìn)和歸約出的整個符號串，即記住“歷史”；另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入符號，即對未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧的頂端時，我們希望能夠根據(jù)所記載的“歷史”和“展望”以及“現(xiàn)實(shí)”的輸入符號等三方面的材料，來確定棧頂?shù)姆杺魇欠駱?gòu)成相對某一產(chǎn)生式的句柄。
LR分析器的核心部分是一張分析表。這張分析表包括兩部分，一是“動作”(ACTION)表，另一是“狀態(tài)轉(zhuǎn)換”(GOTO)表。對于一個文法，如果能用一個每步頂多向前檢查K個輸入符號的LR分析器進(jìn)行分析，則這個文法就稱為LR(K)文法。本文研究的LR(0)文法即K=0時的文法。
設(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)分析表對輸入串進(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)在邏輯上更為簡單明確。以中間語言為界面，編譯前端和后端的接口更清晰。設(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)在邏輯上更為簡單明確；
而以中間語言為界面，編譯前端和后端的接口更清晰，表達(dá)式可以用四個域分別稱為OP、ORG1、ORG2及RESULT來表示。
四、時間安排
《編譯原理課程設(shè)計(jì)》安排在第三學(xué)期進(jìn)行，時間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)與管理工作。
六、成績考核與評定
學(xué)生課程設(shè)計(jì)結(jié)束后寫出總結(jié)報(bào)告，對設(shè)計(jì)的內(nèi)容和效果進(jìn)行總結(jié)，按照學(xué)生在設(shè)計(jì)期間的表現(xiàn)，指導(dǎo)老師對每位學(xué)生寫出評語和鑒定，系課程設(shè)計(jì)領(lǐng)導(dǎo)小組組織答辯，最后確定每位學(xué)生課程設(shè)計(jì)成績，課程設(shè)計(jì)成績分為優(yōu)、良、中、及格和不及格五個等級。課程設(shè)計(jì)成績?yōu)槠綍r表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%。評分標(biāo)準(zhǔn)：
① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學(xué)校的各項(xiàng)紀(jì)律。工作認(rèn)真，積極 主動，吃苦耐勞，能出色的完成設(shè)計(jì)任務(wù)。撰寫了高質(zhì)量的總結(jié)報(bào)告。答辯準(zhǔn)確流利。
② 良好：目的明確，態(tài)度端正，能遵守學(xué)校的各項(xiàng)紀(jì)律，工作比較積極主動。能較好地完成設(shè)計(jì)任務(wù)，成績較突出，表現(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)，自由散漫，工作消極被動，不能完成實(shí)習(xí)任務(wù)，實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過失?；驘o實(shí)習(xí)報(bào)告，沒有通過答辯。
2．成績評定
依據(jù)上述考核內(nèi)容，最后采用優(yōu)（>90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（<60分）五級記分制評定學(xué)生課程設(shè)計(jì)成績。
七、主要參考資料
教材：
《編譯原理及實(shí)踐》馮博琴等譯，機(jī)械工業(yè)出版社 教學(xué)參考書
1、《程序設(shè)計(jì)語言與編譯》龔天富、侯文永編，電子工業(yè)出版社。
2、《編譯原理》呂映芝、張素琴、蔣維杜主編，清華大學(xué)出版社，1998年
3、《編譯原理》胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社2002年
4、《編譯原理》（第二版）蔣立源、康慕寧主編，西北工業(yè)大學(xué)出版社，2002年
5、《編譯原理習(xí)題精選》陳意云、張昱著，中國科技大學(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ì)一個完整的編譯程序模型，能夠進(jìn)一步加深理解和掌握所學(xué)知識，對提高自己的軟件設(shè)計(jì)水平具有十分重要的意義。大家在進(jìn)行課程設(shè)計(jì)時，可從所學(xué)內(nèi)容中選擇某個主題，抽象成一個模型，可適當(dāng)進(jì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ì)的輸入和輸出形式，測試、模擬的結(jié)果（屏幕拷貝、生成結(jié)果的打印輸出），總結(jié)（體會），源程序清單，等等。
大家應(yīng)把該門課的課程設(shè)計(jì)當(dāng)成對自己學(xué)習(xí)效果的一次檢驗(yàn)，當(dāng)成是為在大四能夠順利完成畢業(yè)設(shè)計(jì)的一次基本功訓(xùn)練。希望每個同學(xué)盡可能不要都選擇完全一樣的題目。大家可以自主選題，或選擇我提供的題目，也可以把幾個題目合起來做（如開發(fā)一個小的編譯器）。鼓勵選擇有一定技術(shù)難度、有一定工作量、綜合性較強(qiáng)的題目，在評定成績時將會給予好的成績。
編譯原理課程設(shè)計(jì)部分參考選題： 1． 題目： FORTRAN語言實(shí)型常數(shù)識別程序設(shè)計(jì)
設(shè)計(jì)內(nèi)容及要求： 將教材P.41的圖3.2(d)識別FORTRAN實(shí)型常數(shù)的狀態(tài)轉(zhuǎn)換圖用程序?qū)崿F(xiàn)。程序能夠從用戶輸入的任意一個字符串中識別出FORTRAN實(shí)型常數(shù)，顯示輸出。
2． 題目： 簡化的FORTRAN語言詞法分析程序設(shè)計(jì)
設(shè)計(jì)內(nèi)容及要求：將教材P.42上的表3.1的詞法分析器構(gòu)造出來，限制條件如教材所述。保留字的識別按標(biāo)識符一樣識別，通過查找保留字表區(qū)分是保留字還是標(biāo)識符。程序能夠從用戶輸入的源程序中，識別出的單詞符號，并用二元式表示，顯示輸出或輸出到文件中。
3． 題目： ε-CLOSURE(I)構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(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)造與之等價的有限自動機(jī)的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：構(gòu)造一轉(zhuǎn)換程序，實(shí)現(xiàn)將用戶任意給定的右線性文法，轉(zhuǎn)換為與之等價的有限自動機(jī)FA M，輸出其狀態(tài)轉(zhuǎn)換矩陣（顯示輸出或輸出到文件中）。
5． 題目： 從有限自動機(jī)構(gòu)造與之等價的右線性文法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：構(gòu)造一轉(zhuǎn)換程序，實(shí)現(xiàn)將用戶任意給定的有限自動機(jī)FA M，轉(zhuǎn)換為與之等價的右線性文法，顯示輸出或輸出到文件中。6． 題目： 有限自動機(jī)的狀態(tài)轉(zhuǎn)換圖顯示程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：構(gòu)造一程序，實(shí)現(xiàn)：將任一給定的有限自動機(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)造與之等價的正規(guī)式r的程序?qū)崿F(xiàn)
設(shè)計(jì)內(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（或運(yùn)算）的NFA的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：對給定的正規(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)容及要求：對給定的正規(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)容及要求：對給定的正規(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)造一個語法分析程序，實(shí)現(xiàn)對任意正規(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劃分成若干互不相交的子集，使得：任何不同的兩個子集中的狀態(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 的算法實(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，要求從輸入串中匹配最長的子串。輸出所有識別出的符號串及其詞形。15． 題目： 根據(jù)句型的推導(dǎo)構(gòu)造其語法分析樹的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：構(gòu)造一程序，實(shí)現(xiàn)：接受用戶任意輸入的一個句型的推導(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)：接受用戶任意輸入的一個句型的語法分析樹（其表示存于指定文件中），生成該語法分析樹中包含的該句型的所有推導(dǎo)（顯示輸出）。17． 題目： 遞歸下降分析程序的實(shí)現(xiàn) 設(shè)計(jì)內(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頁 設(shè)計(jì)內(nèi)容及要求：構(gòu)造一程序，實(shí)現(xiàn)教材P.78的FIRST(X)集合的構(gòu)造算法。對任一給定的文法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)造算法。對任一給定的文法G，程序輸出所有非終結(jié)符P的FIRST(P)。在此基礎(chǔ)上，構(gòu)造一程序，實(shí)現(xiàn)教材P.79的FOLLOW(A)集合的構(gòu)造算法。對任一給定的文法G，程序輸出所有非終結(jié)符A的FOLLOW(A)。20． 題目： 預(yù)測分析表構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：對于給定的一個LL(1)文法，假定所有非終結(jié)符號P的集合FIRST(P)和集合FOLLOW(P)都已知，構(gòu)造其預(yù)測分析表（實(shí)現(xiàn)教材P.79給出的預(yù)測分析表構(gòu)造算法）。對教材P.79給出的例4.7構(gòu)造出預(yù)測分析表。程序顯示輸出預(yù)測分析表或輸出到指定文件中。21． 題目： 預(yù)測分析表自動構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：對于任意輸入的一個LL(1)文法，構(gòu)造其預(yù)測分析表。要求：首先實(shí)現(xiàn)集合FIRST(X)構(gòu)造算法和集合FOLLOW(A)構(gòu)造算法，再實(shí)現(xiàn)教材P.79給出的預(yù)測分析表構(gòu)造算法。程序顯示輸出預(yù)測分析表或輸出到指定文件中。22． 題目： 預(yù)測分析程序的實(shí)現(xiàn) 設(shè)計(jì)內(nèi)容及要求：
對文法 G: E→E+T|T 按教材P.76表4.1構(gòu)造出G的預(yù)測分析程序，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)造算法。對任一給定的算符文法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)造算法。對任一給定的算符文法G，程序輸出所有非終結(jié)符P的LASTVT(P)。25． 題目： 算符優(yōu)先分析算法的程序?qū)崿F(xiàn) 設(shè)計(jì)內(nèi)容及要求：
對文法 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． 題目： 帶出錯處理的算符優(yōu)先分析算法的程序?qū)崿F(xiàn) 設(shè)計(jì)內(nèi)容及要求：
對文法 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 要編制各出錯處理子程序。
27． 題目： 優(yōu)先表構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求： 實(shí)現(xiàn)教材P.92優(yōu)先表構(gòu)造算法。對任一給定的算符優(yōu)先文法G，假定所有非終結(jié)符P的FIRSTVT(P)、LASTVT(P)均已知。以教材P.90例5.4文法為例，程序生成表5.1優(yōu)先表。28． 題目： 優(yōu)先表自動構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：對任一給定的算符優(yōu)先文法G，構(gòu)造其優(yōu)先表。要求：首先實(shí)現(xiàn)對于非終結(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消除左遞歸算法。對于用戶任意輸入的文法G，輸出一個無左遞歸的等價文法，可顯示輸出，或輸出到指定文件中。31． 題目： 消除回溯算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：構(gòu)造一程序，實(shí)現(xiàn)：消除文法每一條產(chǎn)生式候選式的公共左因子。對于用戶任意輸入的文法G，輸出一個無回溯的等價文法，可顯示輸出，或輸出到指定文件中。32． 題目： LR分析器總控程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：對P.101中的文法，按圖5.5LR分析表構(gòu)造LR分析器。要求程序按P.102例5.7那樣，對于輸入串i*i+i，輸出LR分析器的工作過程。33． 題目： 識別文法活前綴的NFA構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：構(gòu)造一程序，對任意給定的文法G：①構(gòu)造并輸出G的所有LR(0)項(xiàng)目；②用這些LR(0)項(xiàng)目構(gòu)造并輸出識別文法活前綴的NFA(輸出其
第5頁 狀態(tài)轉(zhuǎn)換矩陣)。34． 題目： LR(0)項(xiàng)目集規(guī)范族構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：構(gòu)造一程序，對任意給定的文法G，構(gòu)造識別文法活前綴的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給出測試結(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的識別文法活前綴的DFA，輸出如P.109表5.4的LR(0)分析表，可輸出到指定文件中。36． 題目： LR(0)分析器自動構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：對任意給定的文法G，構(gòu)造識別文法活前綴的DFA，輸出DFA的狀態(tài)轉(zhuǎn)化矩陣及LR(0)項(xiàng)目集規(guī)范族；實(shí)現(xiàn)LR(0)分析表構(gòu)造算法；實(shí)現(xiàn)LR分析器總控程序。程序輸出一個完整的LR(0)分析器源程序，可輸出到指定文件中。37． 題目： SLR(1)分析表構(gòu)造算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：構(gòu)造一程序，實(shí)現(xiàn)SLR(1)分析表構(gòu)造算法(假定所給文法識別文法活前綴的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)造一程序，對任意給定的文法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)造算法(假定所給文法識別文法活前綴的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)分析表自動構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：對任意給定的文法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è)對于給定文法，識別文法活前綴的DFA、LR(1)項(xiàng)目集族已構(gòu)造出來了。構(gòu)造一程序，檢查兩個LR(1)項(xiàng)目集是否為同心集（可任意輸入），若是，則輸出合并后的同心集，并檢查合并后的集合是否含有沖突項(xiàng)目（指出存在何種沖突），輸出合并同心集后的識別文法活前綴的DFA，及LALR(1)項(xiàng)目集規(guī)范族。42． 題目： LALR(1)分析表自動構(gòu)造程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：對任意給定的文法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． 題目： 帶出錯處理的LR分析器總控程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：按教材P.127表5.9分析表構(gòu)造一LR分析器，輸出語法分析過程（如P.128所述），要構(gòu)造各出錯處理子程序。44． 題目： 算術(shù)表達(dá)式從中綴式翻譯成后綴式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將算術(shù)表達(dá)式從中綴式翻譯成后綴式。要求：先確定一個定義算術(shù)表達(dá)式的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達(dá)式，程序?qū)⑵滢D(zhuǎn)換成后綴式輸出。45． 題目：將算術(shù)表達(dá)式轉(zhuǎn)換成抽象語法樹的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將算術(shù)表達(dá)式轉(zhuǎn)換成抽象語法樹。要求：先確定一個定義算術(shù)表達(dá)式的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達(dá)式，程序?qū)⑵滢D(zhuǎn)換成抽象語法樹輸出(可按一定格式輸出到指定文件中)。46． 題目：將算術(shù)表達(dá)式轉(zhuǎn)換成DAG的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將算術(shù)表達(dá)式轉(zhuǎn)換成DAG。要求：先確定一個定義算術(shù)表達(dá)式的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達(dá)式，程序?qū)⑵滢D(zhuǎn)換成DAG輸出(可按一定格式輸出到指定文件中)。
第7頁 47． 題目：將算術(shù)表達(dá)式轉(zhuǎn)換成三元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將算術(shù)表達(dá)式翻譯成三元式。要求：先確定一個定義算術(shù)表達(dá)式的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達(dá)式，程序?qū)⑵滢D(zhuǎn)換成三元式輸出(可按一定格式輸出到指定文件中)。48． 題目：將算術(shù)表達(dá)式轉(zhuǎn)換成間接三元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將算術(shù)表達(dá)式翻譯成間接三元式。要求：先確定一個定義算術(shù)表達(dá)式的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達(dá)式，程序?qū)⑵滢D(zhuǎn)換成間接三元式輸出(可按一定格式輸出到指定文件中)。49． 題目：將算術(shù)表達(dá)式轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將算術(shù)表達(dá)式翻譯成四元式。要求：先確定一個定義算術(shù)表達(dá)式的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的算術(shù)表達(dá)式，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。50． 題目：將布爾表達(dá)式轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將布爾表達(dá)式翻譯成四元式。要求：先確定一個定義布爾表達(dá)式的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的布爾表達(dá)式，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。51． 題目：將條件語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將條件語句翻譯成四元式。要求：先確定一個定義條件語句的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的條件語句，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。52． 題目：將WHILE語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將WHILE語句翻譯成四元式。
第8頁 要求：先確定一個定義WHILE語句的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的WHILE語句，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。53． 題目：將FOR語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將FOR語句翻譯成四元式。要求：先確定一個定義FOR語句的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的FOR語句，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。54． 題目：將SWITCH語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將SWITCH語句翻譯成四元式。要求：先確定一個定義SWITCH語句的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的SWITCH語句，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。55． 題目：將包含數(shù)組引用的賦值語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，將包含數(shù)組引用的賦值語句翻譯成四元式。要求：先確定一個定義包含數(shù)組引用的賦值語句的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的包含數(shù)組引用的賦值語句，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。56． 題目：嵌套過程中的說明語句翻譯的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：設(shè)計(jì)一個語法制導(dǎo)翻譯器，完成對說明語句的翻譯，即構(gòu)造每個過程的符號表，填寫所有名字在符號表中的有關(guān)信息。要求：先確定一個定義允許嵌套過程的說明語句的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一組正確的說明語句，程序?qū)⑤敵鱿鄳?yīng)的符號表(可按一定格式輸出到指定文件中)。57． 題目：基本塊劃分算法的程序?qū)崿F(xiàn)
設(shè)計(jì)內(nèi)容及要求：根據(jù)基本塊劃分算法，構(gòu)造一個基本塊劃分程序，實(shí)現(xiàn)：對于任意輸入的一個四元式程序，將其劃分為基本塊，輸出各基本塊，并輸出程
第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)：對于任意輸入的一個基本塊（四元式程序），將其轉(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． 題目：局部優(yōu)化程序的實(shí)現(xiàn)
設(shè)計(jì)內(nèi)容及要求：根據(jù)將基本塊轉(zhuǎn)換成DAG的算法，實(shí)現(xiàn)：對于任意輸入的一個基本塊（四元式程序），將其轉(zhuǎn)換成DAG；然后按照DAG節(jié)點(diǎn)構(gòu)造順序，重構(gòu)基本塊四元式代碼。以P.283例10.4為輸入，完成并輸出局部優(yōu)化。
（待續(xù)）
。。。(大家也可以自行設(shè)計(jì)一個設(shè)計(jì)題目)
第10頁
點(diǎn)擊咨詢 