實驗1 詞法程式設計(11
實驗2 詞法程式設計(23
實驗3 語法程式設計(14
實驗4 語法程式設計(25
實驗5 語法程式設計(36
實驗6 中間**生成8
實驗1 詞法程式設計
——dfa（確定的有窮自動機）的化簡
一、 實驗目的與要求
通過設計、編寫和除錯將確定的有窮自動機的狀態數變為最少的c程式，使得學生掌握化簡為有窮自動機的過程中的相關概念和方法。dfa的表現形式可以為**或圖形。
二、 問題描述
每乙個正規集都可以由乙個狀態數最少的dfa所識別，這個dfa是唯一的（不考慮同構的情況）。任意給定的乙個dfa，根據以下演算法設計乙個c程式，將該dfa 化簡為與之等價的最簡dfa。
三、 演算法
（1）構造具有兩個組的狀態集合的初始劃分i：接受狀態組 f 和非接受狀態組 non-f。
（2）對i採用下面所述的過程來構造新的劃分i-new.
for i 中每個組g do
begin
當且僅當對任意輸入符號a,狀態s和讀入a後轉換到i的同一組中最壞情況下，乙個狀態就可能成為乙個組*/
用所有新形成的小組集代替i-new中的g;
end（3）如果i-new=i，令i-final=i,再執行第（4）步，否則令i=i=new,重複步驟（2）。
（4）在劃分i-final的每個狀態組中選乙個狀態作為該組的代表。這些代表構成了化簡後的dfa m＇狀態。令s是乙個代表狀態，而且假設：
在dfa m中，輸入為a時有從s到t轉換。令t所在組的代表是r,那麼在m』中有乙個從s到r的轉換，標記為a。令包含s0的狀態組的代表是m』的開始狀態，並令m』的接受狀態是那些屬於f的狀態所在組的代表。
注意,i-final的每個組或者僅含f中的狀態，或者不含f中的狀態。
（5）如果m』含有死狀態（即乙個對所有輸入符號都有刀自身的轉換的非接受狀態d）,則從m』中去掉它；刪除從開始狀態不可到達的狀態；取消從任何其他狀態到死狀態的轉換。
四、基本要求
1、輸入乙個dfa m,輸出乙個與之等價的最小化的dfa m』，上機程式設計實現。
2、實驗報告格式要求書寫要點：
概要設計（總體設計思想）；
詳細設計：程式主流程、dfa的儲存格式（即資料結構）、關鍵函式的流程圖；
結果分析（輸入與輸出結果、存在問題及有待改進善的地方、實驗心得）
五、測試資料
輸入下圖的dfa m,得到其最簡的dfa m』。
dfa m
六、 實現提示：
（1） 可將輸入的dfa存放在外部文字檔案中，也可以直接從nfa轉換得到。對dfa的最小化分兩部分進行化簡，即分別對狀態（結點）和路徑（弧）進行最小化，最後輸出最小化的dfa。
（2） 實現的資料結構：
用鍊錶實現dfa的構造：由結點鍊錶和轉換弧鍊錶組成：
struct node //結點的定義
node;
struct arc//弧的定義
int start; //開始的頂點位置
char input; //弧上所接受的輸入字元
int end; //結束的頂點位置
struct arc *next;
}arc;
struct groups //分組後各結點所在組
int n; //屬於哪個組
int i;//在組中的位置
}groups;
（3） 實現方法：
根據accept的值為0還是1進行初次劃分i，將accept為0的所有結點構建成乙個鍊錶，將accept為1的所有結點構建乙個鍊錶。然後執行最小化函式，對每乙個輸入字元遍歷以上個鍊錶，對每個結點.num=弧.
start的情況，檢視該弧.end的組號是否相等，相等則不劃分；若不相等，則需進一步劃分，構建新的鍊錶等。
劃分完成後選頭結點為代表，刪除結點鍊錶上其他結點，並將弧線鍊錶上需被刪的弧.start或弧.end該為頭結點。
實驗2 詞法程式設計——dfa模擬程式
一、實驗目的
通過實驗教學，加深學生對所學的關於編譯的理論知識的理解，增強學生對所學知識的綜合應用能力，並通過實踐達到對所學的知識進行驗證。通過對dfa模擬程式實驗，使學生掌握詞法分析的實現技術，及具體實現方法。通過本實驗加深對詞法分析程式的功能及實現方法的理解 。
二、實驗環境
供windows系統的pc機，可用c++/c#/j**a等程式設計工具編寫
三、實驗內容
1、定義乙個右線性正規文法，示例如(僅供參考)
g[s]：s→au|bv u→bv|aq
v→au|bq q→aq|bq|
實驗前要考慮清楚用哪種資料結構儲存上述文法。
2、構造其有窮確定自動機，如
3、利用有窮確定自動機m=(k,σ,f, s,z）行為模擬程式演算法，來對於任意給定的串，若屬於該語言時，該過程經有限次計算後就會停止並回答「是」，若不屬於，要麼能停止並回答「不是」。
k:=s；
c:=getchar;
while c<>eof do
{k:=f(k,c);
c:=getchar
if k is in z then return (『yes』)
else return (『no』)
四、 實驗方式與要求
1、每位同學定義的語言或文法不同，上機程式設計實現
2、實驗報告格式要求書寫要點：概要設計（總體設計思想）；詳細設計（程式主流程、自動機的儲存格式、關鍵函式的流程圖）；結果分析（輸入與輸出結果、存在問題及有待改進善的地方、實驗心得）
實驗3 語法程式設計
——判斷文法是否是ll(1)文法？
一、實驗目的
首先能讓使用者輸入乙個文法，然後讓計算機自動判斷是否是乙個ll(1)文法，通過實驗教學，加深學生對所學的關於編譯的理論知識的理解，增強學生對所學知識的綜合應用能力，並通過實踐達到對所學的知識進行驗證。。
二、實驗環境
供windows系統的pc機，可用c++/c#/j**a等程式設計工具編寫
三、實驗步驟
1、讓計算機接受乙個文法，示例如(僅供參考)：
g[s] 為:
s→abs→bc
aa→b
bb→ad
c→adc→b
d→asd→c
1. 2、程式設計實現對上述文法是否是ll(1)文法的判斷，是則給出肯定回答，否則給出否定回答。
2. 判別是否是ll(1)文法
實驗流程圖如下：
實驗4-5 語法程式設計
——基於ll(1)文法的**分析表法dfa模擬程式
一、實驗目的
通過對基於ll(1)文法的**分析表法dfa模擬程式實驗，使學生掌握確定的自上而下的語法分析的實現技術，及具體實現方法。通過本實驗加深對語詞法分析程式的功能及實現方法的理解。
二、實驗環境
供windows系統的pc機，可用c++/c#/j**a等程式設計工具編寫
三、實驗步驟
1、定義乙個ll(1)文法，示例如(僅供參考)
g[e]：e →te' e'→+te'|ε
t →ft' t' → *ft'|ε
f → i|(e)
2、構造其**分析表，如
3、ll(1)文法的**分析表的模型示意圖
4、**分析控制程式的演算法流程
5、執行結果，示例如下
四、實驗方式與要求
1、每位同學定義的文法不同，上機程式設計實現;
2、實驗報告格式要求書寫要點：
概要設計（總體設計思想）；
詳細設計（程式主流程、自動機的儲存格式、關鍵函式的流程圖）；
結果分析（輸入與輸出結果、存在問題及有待改進善的地方、實驗心得）.
實驗6 逆波蘭式的產生及計算
一、實驗目的：
將非字尾式用來表示的算術表示式轉換為用逆波蘭式來表示的算術表示式，並計算用逆波蘭式來表示的算術表示式的值。
二、實驗內容:
1.定義部分：定義常量、變數、資料結構。
2.初始化：設立算符優先分析表、初始化變數空間（包括堆疊、結構體、陣列、臨時變數等）；
3.控制部分：從鍵盤輸入乙個表示式符號串；
4.利用算符優先分析演算法進行表示式處理：根據算符優先分析表對表示式符號串進行堆疊（或其他）操作，輸出分析結果，如果遇到錯誤則顯示錯誤資訊。
5.對生成的逆波蘭式進行計算。
三、實驗預習提示:
1、逆波蘭式定義
將運算物件寫在前面，而把運算符號寫在後面。用這種表示法表示的表示式也稱做字尾式。逆波蘭式的特點在於運算物件順序不變，運算符號位置反映運算順序。
採用逆波蘭式可以很好的表示簡單算術表示式，其優點在於易於計算機處理表示式。
2、產生逆波蘭式的前提
中綴算術表示式
3、逆波蘭式生成的實驗設計思想及演算法
(1)首先構造乙個運算子棧，此運算子在棧內遵循越往棧頂優先順序越高的原則。
(2)讀入乙個用中綴表示的簡單算術表示式，為方便起見,設該簡單算術表示式的右端多加上了優先順序最低的特殊符號「#」。
(3)從左至右掃瞄該算術表示式，從第乙個字元開始判斷，如果該字元是數字，則分析到該數字串的結束並將該數字串直接輸出。
(4)如果不是數字，該字元則是運算子，此時需比較優先關係。
做法如下：將該字元與運算子棧頂的運算子的優先關係相比較。如果，該字元優先關係高於此運算子棧頂的運算子，則將該運算子入棧。
倘若不是的話，則將此運算子棧頂的運算子從棧中彈出，將該字元入棧。
(5)重複上述操作(1)-(2)直至掃瞄完整個簡單算術表示式，確定所有字元都得到正確處理，我們便可以將中綴式表示的簡單算術表示式轉化為逆波蘭表示的簡單算術表示式。
四、逆波蘭式計算的實驗設計思想及演算法
(1)構造乙個棧，存放運算物件。
(2)讀入乙個用逆波蘭式表示的簡單算術表示式。
(3)自左至右掃瞄該簡單算術表示式並判斷該字元，如果該字元是運算物件，則將該字元入棧。若是運算子，如果此運算子是二目運算子，則將對棧頂部的兩個運算物件進行該運算，將運算結果入棧，並且將執行該運算的兩個運算物件從棧頂彈出。如果該字元是一目運算子，則對棧頂部的元素實施該運算，將該棧頂部的元素彈出，將運算結果入棧。
(4)重複上述操作直至掃瞄完整個簡單算術表示式的逆波蘭式，確定所有字元都得到正確處理，我們便可以求出該簡單算術表示式的值。
五、實驗步驟：
（一）準備：
1.閱讀課本有關章節，
2.考慮好設計方案；
3.設計出模組結構、測試資料，初步編制好程式。
（二）上課上機：
將源**拷貝到機上除錯，發現錯誤，再修改完善。第二次上機除錯通過。
（三）程式要求：
程式輸入/輸出示例：
輸出的格式如下：
(1)逆波蘭式的生成及計算程式，編制人：姓名，學號，班級
(2)輸入一以#結束的中綴表示式(包括+—*/（）數字#)：在此位置輸入符號串如(28+68)*2#
(3)逆波蘭式為：28&68+2*
(4)逆波蘭式28&68+2*計算結果為192
備註：(1)在生成的逆波蘭式中如果兩個數相連則用&分隔，如28和68，中間用&分隔；
(2)在此位置輸入符號串為使用者自行輸入的符號串。
注意：1.表示式中允許使用運算子（+-*/）、分割符（括號）、數字，結束符#；
2.如果遇到錯誤的表示式，應輸出錯誤提示資訊（該資訊越詳細越好）；
3.對學有餘力的同學，測試用的表示式事先放在文字檔案中，一行存放乙個表示式，同時以分號分割。同時將預期的輸出結果寫在另乙個文字檔案中，以便和輸出進行對照。
《編譯原理》實驗指導書
黃營楊躍武編寫 2014.4 前言編譯原理實驗是為電腦科學與技術專業本科 編譯原理 課程配套設定的，是 編譯原理 課程講授中乙個重要的 不可或缺的實踐環節。通過實驗訓練，達到如下目的 使學生進一步了解和掌握編譯原理，提高對實際專案的分析和設計能力，通過實驗課程，熟悉和基本掌握編譯器的詞法分析,語法分...
編譯原理實驗指導書
編譯原理實踐教程 作為 編譯原理和技術 課程的延伸，其目的是讓大家動手設計和實現某一規模適中的語言的編譯器，該編譯器不僅涉及編譯程式的各個階段，而且也強調了編譯的總體設計 各個階段的介面安排等等。通過上機實踐，來設計這個相對完整的編譯器，一方面可以使學生增加對編譯程式的整體認識和了解 鞏固 編譯原理...
編譯原理實驗
實驗三中間的 優化 一 實驗目的 掌握區域性優化方法 提高機器的執行速度 二 相關知識 某些編譯程式在中間 或目標 生產之後要對其進行優化，所謂優化就是對 進行等價的變換。而變換後的 執行結果與變換前的 執行結果相同。而執行速度加快或占用記憶體空間減少。中間的 優化就是對中間 進行等價的變換。基本塊...