第一篇：《編譯原理》課程設計教學大綱
《編譯原理》課程設計教學大綱
揭金良 2006．10．20 1 目的
通過課程設計，將《編譯原理》的相關理論和技術運用到軟件開發中，提高學生的應用程序設計能力，提高分析問題、解決問題的能力。內容
利用編譯原理的某種思想或方法，設計一個應用程序，實現的具體內容自擬（見下面的選題指導）。要求
進行簡單的需求分析、設計說明，寫出程序結構框架，闡明設計思路、用到的原理和方法。程序規模適中，著重于內核功能。估計時間
總共時間2.5周(150學時)，其中：1.講課2學時；2.上機48學時調試；3.其余非上機時間由同學自行安排分析、檢查問題、繪制流程圖、寫相關文檔，最后集成設計（實驗）報告并自行打印。過程指導
5．1 選題
通過平時積累，找到適合于自己的應用或某種軟件功能，該應用能利用編譯原理中的某些理論。題目大小適中。參考題目如下： 表達式計算器
表達式計算器：這是一款算術表達式計算程序，通過輸入表達式達到計算的目的，可代替目前普遍使用的計算器。使用了編譯原理中的詞法分析、算符優先分析等。根據功能的不同可分為：
⑴無符號整數表達式計算器：輸入無符號整數表達式，輸出結果。難度：較難。工作量：中等。
? 整數表達式計算器：考慮負數。難度：較難。工作量：中等。? 定點實數表達式計算器：難度：較難。工作量：中等。
? 通用表達式計算器：考慮1.23e-2的形式輸入。難度：難。工作量：中等。⑵函數表達式計算程序：這是一款能計算函數值的實用程序，輸入含有自變量x的函數表達式被接受后，可接著輸入自變量x的值，輸出函數值y的值。使用了詞法分析、算符優先分析。根據功能的不同可以分為：
? 多項式函數計算程序：只處理多項式函數，如f(x)=x^3+x^2+5等。難度：較難。也可設計成其他專用函數計算程序，如冪函數計算、三角函數計算等。但要避免出現不同用，如不要設計成僅能處理f(x)=2^x的冪函數，因為這樣的函數利用普通編程就能實現，無法體現編譯原理。工作量：中等。
? 通用初等函數計算程序：能處理所有的初等函數的計算。如f(x)=3*sin(x/2+3.1415)+x^2等。難度：難（因為涉及到函數名稱和參數的識別問題）。工作量：較大。
? 二元或多元函數的計算：如f(x,y)=x^2+y^2等。難度和工作量同一元函數的計算。⑶邏輯運算分析：輸入邏輯表達式串，對表達式進行分析，并得出結果。難度：較難。2 字符串搜索程序
輸入要查找的字符串的正規表達式，軟件可在大量文本(要求不低于3000字符的文檔資料文件)中找到符合描述的字符串。這個設計可參考微軟.NET的正規表達式的功能。
⑴字符串搜索程序：使用到正規式、詞法分析等，還需要有較大的設計技巧。根據功能的不同可以分為：
? 名稱查找程序（類似于文件名）：存有大量的名稱，如abc,123,a1,ab1245等，輸入要查找的規則，找出符合規則的名稱。
? 方案1：通配符，把“*、?”當作通配符：如輸入“a*”，顯示“abc,a1,ab1245”；輸入“a?”，輸出“a1”。
? 方案2：正規式，把“*”當作“閉包”，把“|”當作“或”：如輸入“(a|b)1”，輸出“a1”；輸入“(a|b)*c”，輸出“abc”。
? 方案3：只要包含正規式即可，當名稱中包含該正規式，就輸出來：如輸入“(a|b)1”，輸出“a1,ab1245（含有b1）”；輸入“(a|b)*”，輸出“abc,a1,ab1245”。
? 方案4：含有通配符的正規式，設“@”表示任意字母，“$”表示任意數字（其他可再設多一點，如表示符號等，但會減少名稱中的符號種數）：如輸入“a@*” 輸出“abc”；輸入“a(@|$)*”，輸出“abc,a1,ab1245”。
（以上涉及到正規式的方案難度較大，其他難度一般。注：以上的@$等符號是隨便設定的，與.NET中通用的符號不同且有沖突的，請在實際編程時修改它。）
? 文本搜索程序：在一連串文本中搜索所需的字符串。同“名稱查找程序”中的有關正規式的方案，難度較大，具體正規式包含哪些符號和通配符可另定。
（關于正則表達式的介紹參見另一文檔，詳細信息見.NET框架聯機文檔）3 邏輯運算分析
可對關系表達式進行分析，并得出結果。這個設計結果可改變后用于電路分析、謂詞演算等。源程序掃描程序
對某種高級語言的源程序進行分析，建立符號表，找出盡可能多的問題并輸出相關的出錯信息。轉義符的識別
C語言的字符串常量書寫時使用了大量的轉義符，如“”表示單斜杠，而“n”表示換行（同“u000A”），“x20”表示十六進制表示形式（恰好兩位）與 ASCII 字符匹配（這里代表值為32的ASCII字符，即空格）。請參照C語言教材，編制一個軟件，輸入包含轉義符的字符串，輸出沒有轉義符的真實字符串。難度：一般。工作量：一般。有限自動機的運行
設計一個確定的有限自動機，寫出狀態轉換函數，或畫出狀態圖，編制程序，輸入一個字符串，程序能判別該字符串是否能被該有限自動機接受，可以考慮輸出能否接受的同時，輸出狀態路徑。難度：一般。
⑴整數的判斷：寫出整數的正規式，畫出狀態圖，寫出狀態轉換函數。編出程序。難度：簡單。
⑵同上的過程還可以進行：正偶數的判斷、自然數的判斷、定點數的判斷等。⑶實數的判斷：過程同上。難度：一般。7 編寫一個語法分析程序
編寫一個語法分析程序，對輸入到緩沖區的符號進行分析，建立相應的語法樹，并輸出相應的語法樹。編寫一個代碼生成程序
編寫一個代碼生成程序，形成三地址程序并輸出到文件中，打印三地址程序。9 學習使用LEX和YACC工具
LEX和YACC分別是生成詞法分析程序和語法分析程序的工具，即編譯程序的編譯程序。其功能非常強大，可用于任何語言的分析。
學習使用LEX和YACC工具并編寫相應程序。請參考有關文檔資料。
5．2 分析
選好題目后，分析該題目的應用性，可用到編譯原理的哪些理論？對它們進行簡單闡述。同時對軟件進行需求分析，通過回答下面問題得到：
1．軟件提供哪些功能？軟件有什么用？界面怎樣？怎樣使用該軟件？對輸入數據的格式有什么要求？用什么語言開發？怎樣測試該軟件？該軟件開發的進度如何安排？
2．寫出以上問題的答案，然后自問：你的分析材料別人能非常清楚地看懂嗎？如果回答是肯定的，就可以搞設計了。
5．3 設計
對軟件劃分功能模塊，將模塊細化，設計出數據存放格式，寫出各模塊（函數）的功能、傳遞參數的格式和返回值的類型，畫出模塊結構圖。最后畫出較詳細的程序流程圖。
5．4上機
按課表的安排上機（修改設計/編碼/調試/測試）。
1．根據流程圖編制并輸入代碼，教師查看學生的設計，對設計提出修改意見。2．修改設計，繼續完成輸入代碼，并作初步調試。3．調試，教師幫助解決學生設計和調試中出現的難題。4．修改設計中的缺陷，完善程序。??
演示軟件，教師根據實際情況提出測試用例，學生作最后的修改和完善，教師評分。繼續完善程序，并完成設計說明書，上交成果。
5．5 注意事項
測試數據的設計：每組測試數據包括輸入數據、預期的輸出結果、實際的輸出結果和預期的是否相吻合（如果不吻合，實際輸出什么？可能錯誤的原因？檢查源代碼或設計進行查錯，紀錄結果）。上交文檔
1.程序源代碼（打印，文件名中包含姓名）；
2.一組較完備的測試數據（存在一個文本文件中）；
3.設計報告：有關的文檔資料，包括：選題報告，簡單的軟件需求分析說明書，軟件設計說明，設計經驗總結。其中設計經驗總結可以包括下列方面：你在編程過程中花時多少？多少時間在紙上設計？多少時間上機輸入和調試？多少時間在思考問題？遇到了哪些難題？你是怎么克服的？你對你的軟件如何評價？你的收獲有哪些？ 評分
教師對每個實驗結果進行評分(優、良、中、及格、不及格)，記入成績。以下幾方面可以提高分數： 7．1 軟件實用性強；
7．2 軟件使用了編譯原理中的某些理論； 7．3 軟件具有擴展性； 7．4 各類文檔寫的很規范；
7．5 設計時非常投入，設計后很有心得； 7．6 其他優點。
第二篇：《編譯原理課程設計》教學大綱
《編譯原理課程設計》教學大綱
課程名稱： 課程編號： 適用專業： 總 學 分： 總 周 時： 主 撰 人： 撰寫日期：
一、目的與任務
通過程序設計上機調試程序實現算法，學習編譯程序調試技巧和設計編譯程序的一般原則，加深對詞法分析、語法分析、語義分析和中間代碼生成等編譯階段及實用編譯系統的認識，初步掌握編譯程序構造的基本原理與技術, 從形式語言理論的角度, 進一步認識與理解程序設計語言。通過編譯程序的編寫和調試能力的訓練，激發學生進一步思考問題，培養學生的學習興趣和創新能力。并進一步培養學生的抽象思維能力，進一步鞏固《編譯原理》課程所學知識。
本次課程設計的時間為2周，目的是通過實際的題目如：詞法分析、語法分析、代碼優化等，使學生了解和掌握編譯程序的工作原理，同時培養學生用相關的程序設計語言進行程序設計，實現編譯的功能，從而提高學生的綜合能力。
二、教學基本要求
1．設計和調試過程要規范化
需求分析：將題目中要求的功能進行敘述分析，并且設計解決此問題的數據存儲結構，（有些題目已經指定了數據存儲的，按照指定的設計），設計或敘述解決此問題的算法，描述算法可以使用自然語言、偽代碼、或函數的方式。
給出實現功能的一組或多組測試數據（測試文法），程序調試后，將按照此測試數據進行測試的結果列出來。
如果程序不能正常運行或運行過程中出現了不滿足算法思想的情況，寫出出現這一情況的原因或改進行的方法。
源程序要按照寫程序的規則來編寫。要結構清晰，重點函數的重點變量，重點功能部分要加上清晰的程序注釋。
程序能夠運行，要有基本的容錯功能。盡量避免出現操作錯誤時出現死循環。2．課程設計實習報告的書寫格式
編譯原理 436105 軟件工程 2W 2012．6
審 核 人：
① 設計題目
②運行環境（軟、硬件環境）③算法設計的思想 ④算法設計分析 ⑤主要函數 ⑥源代碼 ⑦運行結果分析 ⑧收獲及體會 3．實施方式
本次課程設計分成9個題目，都有一定的工作量，涵蓋本課程內容和實際應用相關的主要技術，學生可以自由組隊選擇其中一個實現。課程設計題目見“主要內容”。
根據老師給定的9個題目進行分析設計，本次課程設計采取分組的辦法進行，3-4人為一組，要求每組學生在規定時間內獨立完成。4．答辯：課題的論述、測試及問題回答
三、課程設計內容
1、詞法分析器的構造：
人們理解一個程序，起碼是在單詞級別上來思考。同樣，在編繹一個程序時，也是在單詞級別上來分析和翻譯源程序。詞法分析是編繹的基礎，執行詞法分析的程序即為詞法分析器，它的任務是對輸入或給定的源程序，從左至右逐個字符進行掃描，產生一個個單詞符號，把作為字符串的源程序改造成單詞符號串的中間程序。設計目的與任務：
通過本課程設計教學所要求達到的目的是：對詞法分析工作流程進行總體設計和詳細設計，最終用C語言來設計一個簡單詞法分析器，實現對源程序的詞法分析功能，對輸入程序去除注釋，并以二元式形式輸出程序中所有單詞。
2、正則表達式到NFA 在編譯系統中，詞法分析階段是整個編譯系統的基礎。對于單詞的識別，有限自動機FA是一種十分有效的工具。有限自動機由其映射f是否為單值而分為確定的有限自動機DFA和非確定的有限自動機NFA。在非確定的有限自動機NFA中，由于某些狀態的轉移需從若干個可能的后續狀態中進行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。這種不確定性給識別過程帶來的反復，無疑會影響到FA的工作效率。而DFA引擎在任意時刻必定處于某個確定的狀態，它搜索是無需象NFA一樣必須記錄所有的可能路徑（trace multiple possible routes through the NFA），這也是DFA運行效率高于NFA的原因。而已經證明DFA是NFA的一個特例，即對于每一個NFA M存在一個DFA M’’，使得L(M)=L(M’’)。
設計目的與任務
通過本課程設計教學所要求達到的目的是：充分理解和掌握NFA，DFA以及NFA確定化過程的相關概念和知識，編程實現對輸入的任意正規式轉換成NFA的形式輸出。
3、NFA的確定化
有限自動機理論是描述詞法規則的基本理論。一條詞法規則表示一個正規表達式(又叫正規式)，而一個正規式又可化為一個DFA(確定有窮自動機)，這個有限自動機可用來識別詞法規則所定義的所有單詞符號。把程序設計語言的所有詞法規則都構造出相應的有限自動機,就得到一個詞法分析器。然后,再轉換為計算機可識別的程序就能自動實現詞法的分析和檢查。在實際應用中，用NFA(不確定有窮自動機)識別詞法存在不確定和狀態的冗余,因而,就要將NFA(不確定有窮自動機)轉換為DFA(確定有窮自動機),消除了不可到達和不確定。設計目的與任務
通過本課程設計教學所要求達到的目的是：掌握從NFA到DFA的轉換，以及用子集法把NFA轉換成DFA理論，編程實現將NFA(不確定有窮自動機)轉換為DFA(確定有窮自動機)。
4、DFA的最小化
確定性有限自動機(DFA ,Deterministic Finite Automata)的最小化仍是有限自動機應用及實現方面的重要問題之一。DFA的最小化可以揭示狀態之間的內在聯系，便于其存儲實現，便于建立用DFA描述的任務模型，一些理論問題也與最小化思想有關。DFA的最小化是指,構造一個與之等價且狀態數最小的DFA,即等價最小DFA。許多文獻給出了一個最小化算法，算法的思想是，構造狀態集的一個劃分，再將這個劃分中的每個子集作為新的狀態，從而得到等價最小DFA。
DFA的最小化可以揭示狀態之間的內在聯系，便于其存儲實現,便于建立用DFA描述的任務模型，一些理論問題也與最小化思想有關。
5、語法分析之LL(1)文法
通過該課程設計了解了程序語言的自上而下的語法分析過程,提高了編程能力,能使我們了解編程語言更多的細節 設計目的與任務（1）讀入文法（2）求出first(), follow()（3）判斷是否為LL(1)文法
（4）若是，構造分析表；
（5）輸入一個字符串看是否是文法的一個句子。
6、算符優先文法
一個文法，如果它的任一產生式的右邊都不含有兩個相繼（并列）的非終結符，即不 含有如下形式的產生式的右部：
?QR?
則我們稱該文法為算符文法。
假設文法中的任意兩個終結符之間最多只有一個優先關系，則該文法稱為算符優先文法。
該課程設計按照求,(P),(P)各兩條規則，求出各非終結符的集。然后按照算符優先算法求出各終結符的算符優先關系，填寫算符優先表，并將其輸出。
7、LR(0)分析表的構造
LR分析技術是一種有效的自下而上分析技術，是一種規范歸約，其中L表示從左到右掃描輸入串，R表示構造一個最右推導的逆過程。這種方法可以適用于很大一類上下無關文法的語法分析。LR方法的基本思想是：在規范歸約過程中，一方面記住已經移進和歸約出的整個符號串，即記住“歷史”；另一方面根據所用的產生式推測未來可能碰到的輸入符號，即對未來進行“展望”。當一串貌似句柄的符號串呈現于分析棧的頂端時，我們希望能夠根據所記載的“歷史”和“展望”以及“現實”的輸入符號等三方面的材料，來確定棧頂的符號傳是否構成相對某一產生式的句柄。
LR分析器的核心部分是一張分析表。這張分析表包括兩部分，一是“動作”(ACTION)表，另一是“狀態轉換”(GOTO)表。對于一個文法，如果能用一個每步頂多向前檢查K個輸入符號的LR分析器進行分析，則這個文法就稱為LR(K)文法。本文研究的LR(0)文法即K=0時的文法。
設計目的與任務
本課程設計所設計目的與任務是：通過C語言程序實現LR(0)分析表的構造，熟練掌握LR(0)分析表的構造方法，即利用拓廣文法和構造項目集規范族的方法。了解LR(0)分析器的工作原理，并能利用LR(0)分析表對輸入串進行分析。
8、逆波蘭表達式生成算法
雖然源程序可以直接翻譯為目標語言代碼，但許多編譯程序采用了獨立于機器的、復雜性介于源語言和機器翻譯語言之間的中間語言：后綴式（逆波蘭表達式）等。這樣做的好處是：
（1）便于進行與機器無關的代碼優化工作；（2）使編譯程序改變目標機更容易；
（3）使編譯程序的結構在邏輯上更為簡單明確。以中間語言為界面，編譯前端和后端的接口更清晰。設計目的與任務
將非后綴式用來表示的算術表達式轉換為用逆波蘭式來表示的算術表達式，并能運行查看結果。
9、表達式的中間代碼生成
源程序可以直接翻譯為目標語言代碼，但是許多編譯程序卻采用了獨立于機器的、復雜性介于源語言和機器語言之間的中間語言。這樣我們可以做下面工作：
（1）：便于進行與機器無關的代碼優化工作；（2）：使編譯程序以改變目標機更容易；（3）：使編譯程序的結構在邏輯上更為簡單明確；
而以中間語言為界面，編譯前端和后端的接口更清晰，表達式可以用四個域分別稱為OP、ORG1、ORG2及RESULT來表示。
四、時間安排
《編譯原理課程設計》安排在第三學期進行，時間2周（17-18周）。
五、組織管理
1．由院、系指派經驗豐富的專業教師擔任指導教師。
2．課程設計實行指導教師負責制，由指導教師全面負責課程設計的指導與管理工作。
六、成績考核與評定
學生課程設計結束后寫出總結報告，對設計的內容和效果進行總結，按照學生在設計期間的表現，指導老師對每位學生寫出評語和鑒定，系課程設計領導小組組織答辯，最后確定每位學生課程設計成績，課程設計成績分為優、良、中、及格和不及格五個等級。課程設計成績為平時表現30%、設計報告50%、答辯20%。評分標準：
① 優秀：目的明確，態度端正，模范遵守學校的各項紀律。工作認真，積極 主動，吃苦耐勞，能出色的完成設計任務。撰寫了高質量的總結報告。答辯準確流利。
② 良好：目的明確，態度端正，能遵守學校的各項紀律，工作比較積極主動。能較好地完成設計任務，成績較突出，表現良好；撰寫了質量比較高的實習報告。答辯較準確流利。
③ 及格：目的明確，態度基本端正，能遵守學校紀律，在督促下能開展工作 并完成一定的設計任務，無大的違紀違規現象；撰寫了實習報告。通過了答辯。
④ 不及格：實習態度端正，不能遵守實習單位的紀律，不服從領導，自由散漫，工作消極被動，不能完成實習任務，實習期間有失職、曠工、打架、酗酒等大的過失。或無實習報告，沒有通過答辯。
2．成績評定
依據上述考核內容，最后采用優（>90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（<60分）五級記分制評定學生課程設計成績。
七、主要參考資料
教材：
《編譯原理及實踐》馮博琴等譯，機械工業出版社 教學參考書
1、《程序設計語言與編譯》龔天富、侯文永編，電子工業出版社。
2、《編譯原理》呂映芝、張素琴、蔣維杜主編，清華大學出版社，1998年
3、《編譯原理》胡倫駿、徐蘭芳、劉建農編，電子工業出版社2002年
4、《編譯原理》（第二版）蔣立源、康慕寧主編，西北工業大學出版社，2002年
5、《編譯原理習題精選》陳意云、張昱著，中國科技大學出版社，2002年
6、《編譯原理習題與解析》 伍春香著，清華大學出版社，2001年
7、《編譯原理實驗指導書》自編
第三篇：編譯原理課程設計
課 程 設 計 報 告
設計題目：一個簡單文法的編譯器前端的設計與實現
班
級： 計算機1206 組長學號：201239 組長姓名：閆智宣 指導教師：李曉華 設計時間：2014年12月
[在此處鍵入]
設計分工
組長學號及姓名： 20123974
閆智宣
分工：
語法分析，四元式生成，目標代碼優化及生成 組員1學號及姓名：20123977
廖峭 分工：
詞法分析，錯誤處理 組員2學號及姓名：20123959
郭天龍
分工：
符號表生成，語義動作插入，操作界面[在此處鍵入]
摘要
編譯原理課程設計是通過C語言編譯器相關子系統的設計，進一步加深對編譯器構造的理解；第一部分詞法分析，設計各單詞的狀態轉換圖，并為不同的單詞設計種別碼，制作掃描器識別一個個單詞，返回值為識別碼的序號，返回Token序列。將詞法分析器設計成供語法分析器調用的子程序。詞法分析器具備預處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設計一個供詞法分析調用的預處理子程序；第二部分，語法分析，用遞歸下降法，實現對表達式、各種說明語句、控制語句進行語法分析。若語法正確，則用語法制導翻譯法進行語義翻譯；生成并打印出語法樹；若語法錯誤，要求指出出錯性質和出錯位置（行號）。
我們還做了附加功能，即編譯后端，有中間代碼優化，生成目標代碼匯編語言。通過此次課程設計，提高了我們的獨立分析問題、解決問題的能力，以及系統軟件設計的能力； 提高程序設計能力、程序調試能力，團結協作能力
關鍵詞：詞法分析，語法分析，四元式生成，錯誤處理，符號表生成，語義動作插入，中間代碼優化，生成目標代碼 [在此處鍵入]
目錄
摘要
1.概述
2.課程設計任務及要求
2.1 設計任務
2.2 設計要求
3.算法及數據結構
3.1算法的總體思想（流程）
3.2 詞法分析模塊
3.2.1 功能
3.2.2 數據結構
3.2.3 算法
3.3 語法分析模塊
3.3.1功能
3.3.2 數據結構
3.3.3算法
3.4 符號表模塊
3.4.1功能
3.4.2 數據結構
3.4.3算法
3.5 四元式模塊
3.5.1功能
[在此處鍵入]
3.5.2 數據結構
3.5.3算法
3.6 語義動作分析模塊
3.6.1功能 3.6.2 數據結構
3.6.3算法
3.7 錯誤處理模塊
3.7.1功能
3.7.2 數據結構
3.7.3算法
3.8 目標代碼模塊
3.8.1功能
3.8.2 數據結構
3.8.3算法
4.程序設計與實現
4.1 程序流程圖
4.2 程序說明
4.3 實驗結果
5.結論 6.參考文獻。7.收獲、體會和建議。
[在此處鍵入]
1.概述
編譯器是將C語言翻譯為匯編語言代碼的計算機程序。編譯器將源程序（source language）編寫的程序作為輸入，翻譯產生目標語言（target language）機器代碼的等價程序。通常地，源程序為高級語言（high-level language），C語言程序，而目標則是 機器語言的目標代碼（object code），也就是可以在計算機硬件中運行的機器代碼軟件程序。這一過程可以表示為：
源程序→編譯器 →目標機器代碼程序
2.課程設計任務及要求
2.1設計任務
學生在學習《編譯原理》課程過程中，結合各章節的構造編譯程序的基本理論，要求用C#語言描述及上機調試，實現一個 C編譯程序（包括詞法分析，語法分析等重要子程序），使學生將理論與實際應用結合起來，受到軟件設計等開發過程的全面訓練，從而提高學生軟件開發的能力。
2.2設計要求 要求：
（1）設計詞法分析器
設計各單詞的狀態轉換圖，并為不同的單詞設計種別碼。將詞法分析器設計成供語法分析器調用的子程序。功能包括：
a.具備預處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設計一個供詞法分析調用的預處理子程序；
b.能夠拼出語言中的各個單詞； [在此處鍵入]
c.返回（種別碼，屬性值，行號）。
（2）語法分析
要求用學習過的自底向上或自頂向下的分析方法等，實現對表達式、各種說明語句、控制語句進行語法分析。若語法正確，則用語法制導翻譯法進行語義翻譯；生成并打印出語法樹；若語法錯誤，要求指出出錯性質和出錯位置（行號）。
3.算法及數據結構
3.1算法的總體思想（流程）
本節主要分析程序的代碼結構和代碼工程文件的劃分。（程序由幾個類組成: 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分別對應Token類和Variable類SymbolTable類ObjectCode類Lexical類Grammar類Four_Yuan類Action類ErrorItem類的聲明和實現文件）。本程序采用C#語言以面向對象的思想編寫，程序分為幾部分：詞法分析（Lexical），語法分析（Grammer），目標代碼生成（ObjectCode）。Lexical類主要的工作是詞法分析獲取Token。Grammer類的主要工作是根據Lexical類詞法分析之后的Token進行語法分析，生成語法樹，最后并輸出語法樹。在處理過程中，Token類的對象作為Lexical類的一個成員變量，配合Grammer類進行語法分析。
工程文件總體上是按照九個類的格局分為十個文件，分別是九個類的聲明文件和實現文件。十個文件為Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs，他們分別是Lexical類聲明文件、Lexical類實現文件、Grammer類聲明文件、Grammer類實現文件。[在此處鍵入]
程序流程
在程序中，Lexical類的對象(Token)作為Grammer類中的一個成員變量，配合Grammer類進行語法分析。它們的關系是這樣的：Grammer類的一個成員變量temp首先對源程序刪除注釋，然后進行詞法分析獲取所有Token，并將獲取的Token存儲在Token對象的tokenList（List類型）中。然后Grammer類的語法分析程序就根據tokenList中的Token進行語法分析，生成語法樹，最后打印語法樹。同時，這也是程序的流程。[在此處鍵入]
3.2 詞法分析模塊 3.2.1功能
Lexical類主要的工作是詞法分析獲取Token序列。
3.2.2數據結構
詞法分析階段的代碼被封裝成一個類——Lexical，Token中主要是Lexical類的聲明代碼，Lexical.cs中主要是Lexical類的實現代碼。Lexical類對外提供的函數主要有：
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)，以上幾個函數構成了詞法分析的骨架，在Lexical類中還有其他成員變量和函數，主要作為這三個函數處理過程的中間步驟，為這三個函數服務。Lexical類的代碼結構和主要的成員變量和函數及其含義如下圖所示：
3.2.3算法
算法的基本任務是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是[在此處鍵入]
根據掃描到單詞符號的第一個字符的種類，拼出相應的單詞符號。
主程序示意圖：
主程序示意圖如圖3-1所示。
⑴ 關鍵字表的初值。
關鍵字作為特殊標識符處理，把它們預先安排在一張表格中（稱為關鍵字表），當掃描程序識別出標識符時，查關鍵字表。如能查到匹配的單詞，則該單詞為關鍵字，否則為一般標識符。
（2）程序中需要用到的主要變量為type和number 掃描子程序的算法思想：
首先設置3個變量： [在此處鍵入]
①token用來存放構成單詞符號的字符串； ②number用來整型單詞；
③type用來存放單詞符號的種別碼。
Token定義
Token定義:
Token類型（TokenType）:
3.3 語法分析模塊
3.3.1功能
語法分析是編譯過程的一個邏輯階段。語法分析的功能是在詞法分析的基礎上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達式”等等.語法分析程序判斷源程序在結構上是否正確.源程序的結構由上下文無關文法描述.3.3.2 數據結構
下圖為實現語法分析的類Grammar，屬性與方法的作用都已說明 在此處鍵入]
3.3.3算法
1.文法
下面終結符與非終結符意義
B程序開始
Z 數據類型，如int,char,float等
V 標識符
S 語句
P 語句塊
E 加減算術表達式
D 逗號表達式
T 乘除算術表達式
C 關系表達式
L 邏輯表達式
Q 標識符或圓括號
e 表示空
i 表示標識符 a)函數文法
B----ZV()S
[
[在此處鍵入]
b)語句塊文法
P----SP|e
S----{P} c)語句文法
表達式語句文法
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)表達式文法
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.遞歸下降程序流程圖
對應于每個文法編寫如下遞歸下降子程序
主程序（B）[在此處鍵入] [在此處鍵入]
3.4 符號表模塊
3.4.1功能
進行符號表的儲存，添加，更新，查找，保存標識符活躍信息以及輸出。3.4.2 數據結構
在此處鍵入]
3.4.3算法
3.5 四元式模塊
3.5.1功能
四元式為中間代碼，編譯程序進行完語義分析后，先生成中間代碼作為過渡，此時中間代碼與目標代碼已經比較相似
3.5.2 數據結構
[ 在此處鍵入]
3.5.3算法
3.6語義動作分析模塊
3.6.1功能
在語法分析中嵌入相應的語義動作，生成四元式 3.6.2 數據結構
[
[在此處鍵入]
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功能 保存運行時發現的錯誤，儲存行號已經詳細信息并輸出。
3.7.2 數據結構
3.7.3算法 [在此處鍵入]
public static void AddErrorMessage(int lineno,string content)函數用作在發現錯誤時保存錯誤信息以及行號。
public static string PrintErrorList()把所有發現的錯誤格式化后統一輸出。
錯誤信息在語法分析，語義分析，符號表檢錯中添加。3.8 目標代碼模塊
3.8.1功能
目標代碼生成把優化后的中間代碼變換成目標代碼，此處的目標代碼為匯編代碼，采用單寄存器生成目標代碼 3.8.2 數據結構[在此處鍵入]
3.8.3算法
對于一個基本塊有如下流程圖
W：操作符，B：第一操作數，C：第二操作數，R：寄存器
5.結論
網上找一段話抄上 [在此處鍵入]
6.測試
測試打開文件
測試保存文件
如果沒打開文件，直接敲代碼，點保存時會彈出另存為窗口[在此處鍵入]
測試錯誤檢測，程序缺少main函數的類型，錯誤列表中顯示第一行函數缺少錯誤類型。
測試錯誤檢測，程序缺少分號，錯誤列表中顯示該行缺少語句結束標志';' 單擊錯誤列表，會自動選定錯誤行
編譯成功，生成并顯示token串、符號表、四元式與目標代碼 [在此處鍵入]
測試if與while語句，而且while嵌套在if當中
測試goto語句，結果正確。[在此處鍵入]
測試優化，輸入課件中的代碼，結果與課件一樣
6.參考文獻。
1、陳火旺.《程序設計語言編譯原理》（第3版）.北京：國防工業出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著.李建中，姜守旭譯.《編譯原理》.24 [在此處鍵入]
北京：機械工業出版社.2003.3、美 Kenneth C.Louden著.馮博琴等譯.《編譯原理及實踐》.北京：機械工業出版社.2002.4、金成植著.《編譯程序構造原理和實現技術》.北京：高等教育出版社.2002.7.收獲、體會和建議。
直接拷貝好歹也檢查一下錯誤
對于編譯原理的這次課程設計，自己經歷了從剛開始的不懂?明白任務的要求和內容?理論知識的了解?開始著手寫代碼?完成基本功能?根據DFA及自頂向下等理論修改完善代碼等這些過程。
自己著手寫詞法分析的時候還不清楚詞法分析的任務內容，還不知道詞法分析的結果是什么，詞法分析出錯的情況和類型有哪些，也總是將詞法分析和語法分析混在一起，不明白哪些錯誤在詞法分析中報，哪些錯誤在語法分析中判斷，后來經過查書、網上資料、請教同學等途徑逐步清晰了詞法分析的工作內容是從源代碼文件中獲取出Token，供語法分析使用。在充分了解了語法分析需要哪些信息時，我才真正了解了詞法分析的工作內容和目標，才知道詞法分析需要完成哪些任務獲取到哪些信息。充分了解了詞法分析的任務之后，就開始理論知識的學習。經過揣摩書上的例子，自己理解和掌握了怎么設計過濾注釋和分析程序中Token的DFA，于是開始根據設計好的DFA進行編碼，最后經過調試已經可以正確地完成詞法階段的任務了。這只是詞法分析的原始代碼，在之后還進行了兩次徹底的改動。雖然之前寫的詞法分析的代碼已經完成了詞法分析的需求，也是根據DFA的原理編寫的，但是在代碼結構上卻難以體現，在對書上的根據已知DFA寫代碼的例子進行了詳細的研究之后，發現自己的代碼并沒有像書上那樣完全按照所依據的DFA各狀態轉移的關系進行編寫，所以對代碼進行了重寫，像書上一樣嚴格按照狀態之間轉移的方式進行編寫，將狀態劃分成11個狀態，狀態分別按1~11進行標注，程序也按照DFA來編寫，也實現了詞法分析的功能。再后來寫報告的時候，發現分析出Token的那個DFA并不是最簡的，有很多多余的狀態，完全可以用一個flag標志來標識，從而簡化代碼結構，于是又重寫了一次詞法分析函數scan()的代碼，將狀態縮減為5個，且不再用1-5來表示，而是像書上那樣分別取了名字（START、INNUM、INID、INDBSYM、DONE），同時為了簡化代碼將輸出Token到文件的部分從scan()中剝離開來，而在Lexical類中加了一個printToken()的函數，使scan()函數邏輯更加清晰，使讀者能夠容易地將代碼與DFA進行查看比照。
在寫語法分析的時候，已經對編譯器的語法分析的內容有了一定的了解，所以直接進行了理論的學習。首先自己對遞歸向下分析法進行了學習，將書上的幾個遞歸向下分析的偽代碼看過之后，自己對遞歸向下的分析方法的原理有了初步的認識，大概知道了根據文法怎么分析，但是對于如何編寫代碼卻還在此處鍵入]
是難以下手，于是就對照TINY語言的文法看了幾遍書后面的TINY語言的遞歸向下分析的語法分析程序，這樣就基本知道了C-語言的語法分析程序怎么寫。由于C-語言給出的文法有左遞歸存在，于是自己將存在左遞歸的文法改寫成EBNF的形式，并據此進行代碼編寫。由于在編寫代碼的過程中需要確定分析是否正確或選擇多個文法中的某一個文法進行分析，有時必須探測需要的或下一個Token的類型，在這種情況下需要求First集合，在推導中若存在empty，又需要求Follow集合，所以這樣又需要我了解First集合和Follow集合，自己在程序中也根據求出的First集合和Follow集合進行判斷，以確定程序的走向。在編寫過程中，還有一類問題，就是存在公共左因子，如文法expression→ var = expression | simple-expression，左因子為ID，在分析過程中，由于已經取出了一個ID的Token，且生成了一個IdK的節點，但是在當前狀態無法確定是哪一個推導，然而IdK節點已經生成，又無法回退，并且是使用自頂向下的分析方法，已經生成的IdK在程序上方無法使用，自己通過查閱資料等途徑的學習確定了在這種情形下的處理方式：將已經生成的IdK節點傳到下方的處理程序，所以TreeNode * simple_expression(TreeNode * k)、TreeNode * additive_expression(TreeNode * k)等函數都被設計成有節點類型參數的函數，目的就是將已經生成的節點傳到下面的分析函數中去。
通過這次的編譯原理課程的學習和實踐，自己獲益良多。首先最基本的成果是完成了課程設計的任務，實現了編譯器的詞法分析和語法分析階段的功能，詞法分析主要能過濾注釋、分析出語法分析階段需要的Token并滿足語法階段的所有要求，能夠判別詞法分析階段是否出錯和出錯類型和位置。語法分析主要能根據遞歸向下的分析思想和C-文法對詞法分析獲取的Token進行語法分析，能夠構造出語法樹，能夠判別語法分析過程中是否出錯以及出錯位置和錯誤類型。
由于在編寫程序過程中，涉及到了正則表達式、DFA、提取公共左因子、消除左遞歸、EBNF、求First集合和Follow集合、遞歸向下分析方法以及編程語言方面的知識，所以，通過本次的課程設計的實踐，使得自己對編譯原理這門課的許多知識點有了更加深刻和具體的理解，而不再只限制于做題。此外，對以前那些已掌握的知識有了溫習和動手鍛煉的機會。如：以前在編譯原理課上雖然知道First集合和Follow集合怎么求的，卻不知道First集合和Follow集合到底是干什么的，通過編寫程序自己明白了他們的實際作用，使得自己不僅知其然還知其所以然，從而使得自己加深了對知識點的理解和掌握。由于以前編寫代碼都是使用JAVA語言，所以C/C++很多內容都忘記了，通過本次的實踐，自己又重新拾起了以前的知識。此外，由于在做報告的時候，需要描繪DFA和程序流程圖，使得自己初步掌握了使用visio和word畫圖的能力。此外，對于文檔的編寫和美化自己也獲得了許多有用的經驗。[
第四篇：編譯原理教學大綱（范文模版）
編譯原理教學大綱
一、課程的性質、地位
本課程是計算機專業的重要專業課之一，是一門理論性和實踐性較強的課程。主要介紹程序設計語言編譯程序構造的基本原理和基本實現方法。本課程主要講授形式語言、有限自動機、自上而下和自下而上的語法分析、LR分析方法、屬性文法和語法制導翻譯、語義分析的代碼產生、存儲器的動態分配與管理、符號表的組織與管理、優化問題、代碼生成等內容。通過本課程學習，使學生對編譯的基本概念、原理和方法有完整的和清楚的理解，并能正確地、熟練地運用。
二、課程的目的、任務和要求
該課程的目的是讓學生掌握程序設計語言編譯程序構造的一般原理、基本設計方法、主要實現技術和一些自動構造工具。通過本課程的學習，使學生較好地掌握編譯原理的基本原理和基本技術、編譯原理中涉及的基本算法、基本結構和主要實現技術，從而讓學生了解將高級程序設計語言源程序翻譯成計算機能處理的目標代碼語言的整個過程，基本掌握計算機系統軟件之一 編譯程序的構造原理及相關技術，同時，還可提高學生計算機專業素質，培養學生的抽象思維能力。通過學習，學生可基本掌握計算機系統軟件之一 編譯程序的構造原理及相關技術，同時，還可提高學生計算機專業素質，培養學生的抽象思維能力。
三、與其它課程的關系
要求學生具有較好的計算機基礎知識，對計算機的工作原理有一定了解，前導課程包括：高等數學、線性代數、計算機原理、離散數學、高級程序設計語言、數據結構等課程。
四、課程內容(建議理論課時：62 上機課時：18)第一章 編譯程序概論
1、教學目的及要求：
本章介紹編譯程序在計算機科學中的地位和作用，介紹編譯技術的發展歷史，講解編譯程序、解釋程序的基本概念，概述編譯過程，介紹編譯程序的邏輯結構和編譯程序的組織形式。要求理解編譯程序、解釋程序和遍的基本概念；掌握編譯過程各階段的任務和編譯程序邏輯結構及其各部分的基本功能。
2、教學內容：
編譯程序，編譯過程概述，編譯程序的結構，編譯程序與程序設計環境，編譯程序生成，學習構造編譯程序。
3、教學重點：
重點：編譯程序工作的基本過程及其各階段的基本任務，編譯程序總框。
4、教學難點：
編譯的遍。
5、教學時間分配及進度安排：
建議本章教學時數2學時。
6、章節內容
1、什么是編譯程序
2、編譯過程概述
3、編譯程序的結構
4、編譯技術和軟件工具 第二章 文法和語言
1、教學目的及要求：
本章是編譯原理課程的理論基礎，要求理解文法、語言、規范推導、規范歸約和短語、簡單短語、句炳的基本概念；掌握語言的求解方法、文法的二義性與遞歸性的判斷方法及句型的分析方法。
2、教學內容：
形式語言的基本概念，包括符號串的基本概念和術語、文法和語言的形式定義、句型分析、文法和語言的Chomsky分類，二義性。
3、教學重點：
上下文無關文法，語言定義。
4、教學難點：
推導，文法與語言的相互轉換。
5、教學時間分配及進度安排：
建議本章教學時數5學時。
6、章節內容
1、文法的直觀概念
2、符號和符號串
3、文法和語言的形式定義
4、文法的類型
5、語法樹和二義性
6、句型的分析
7、文法中的實用限制 第三章 詞法分析
1、教學目的及要求：
本章介紹編譯程序的第一個階段詞法分析的設計原理和設計方法，要求掌握正則文法、狀態轉換圖、DFA、NFA、正規式和正規集的基本概念和詞法分析設計與編寫。
2、教學內容：
詞法分析的設計原理和設計方法，源程序輸入與詞法分析程序輸出、正則文法及其狀態轉換圖、確定的有限自動機（DFA）不確定的有限自動機（NFA）正則表達式與正規集。
3、教學重點：
重點：詞法分析器的任務與設計，狀態轉換圖。
4、教學難點：
正則文法、正規集、DFA、NFA的相互轉化。
5、教學時間分配及進度安排：
建議本章教學時數8學時。
6、章節內容
1、詞法分析程序的設計
2、單詞的描述工具
3、有窮自動機
4、正規式和有窮自動機的等價性
5、正規文法和有窮自動機間的轉換 第四章 語法分析—自上而下分析
1、教學目的及要求：
本章介紹編譯程序的第二個階段語法分析的設計方法和實現原理，包括自上而下分析的無回朔的遞歸下降分析、LL(1)分析法。要求理解遞歸下降分析、LL(1)文法的基本概念；掌握無回朔的遞歸下降分析的設計和實現、LL(1)分析表的構造與分析方法。
2、教學內容：
語法分析器的功能，自上而下語法分析（遞歸下降分析法，預測分析程序），LL（1）分析法，遞歸下降分析程序構造，預測分析程序。
3、教學重點：
遞歸下降子程序，預測分析表構造，LL(1)文法。
4、教學難點：
LL(1)文法預測分析表構造。
5、教學時間分配及進度安排：
建議本章教學時數5學時。
6、章節內容
1、確定的自頂向下分析思想
2、LL（1）文法的判別
3、某些非LL（1）文法到LL（1）文法的等價變換
4、不確定的自頂向下分析思想
5、確定的自頂向下分析方法 第五章 語法分析—自下而上分析
1、教學目的及要求：
要求理解算符優先文法、最左素短語、有效項目的基本概念；掌握算符優先分析方法、LR(0)文法的判斷及LR(0)分析表的構造與分析方法、SLR(1)文法的判斷與SLR(1)分析方法和LR(1)文法的判斷與LR(1)分析方法。
2、教學內容：
自下而上語法分析（算符優先分析法），算符優先分析，LR分析器，LR(0)項目集族和LR(0)分析表的構造，SLR分析表的構造，規范LR分析表的構造。
3、教學重點：
歸約，算符優先表構造，LR分析法。
4、教學難點：
歸約，LR分析法。
5、教學時間分配及進度安排：
建議本章教學時數12學時。
6、章節內容
1、自底向上分析思想
2、算符優先分析法
3、LR分析法 第六章 屬性文法和語法制導翻譯
1、教學目的及要求：
本章介紹編譯程序的第三個階段語義分析及中間代碼生成的設計原理和實現方法，要求理解語法制導翻譯、語義動作的基本概念；掌握算數表達式和賦值語句到中間代碼的翻譯、布爾表達式和幾種控制語句的目標代碼結構分析和到四元式的語法制導翻譯；說明語句的語法制導翻譯。
2、教學內容：
語法制導翻譯的基本概念、中間代碼的形式，可執行語句和說明語句的語法制導翻譯方法。
3、教學重點：
語法制導翻譯基本思想，語法制導翻譯概述，基于屬性文法的處理方法，自下而上分析制導翻譯概述。
4、教學難點：
屬性文法的處理方法
5、教學時間分配及進度安排：
建議本章教學時數9學時。
6、章節內容
1、屬性文法
2、語法制導翻譯概論
3、中間代碼的形式
4、簡單賦值語句的翻譯
5、布爾表達式的翻譯
6、控制語句的翻譯 第七章 符號表
1、教學目的及要求：
本章介紹編譯程序的組成部分之一符號表的管理，要求掌握符號表管理的基本方法。
2、教學內容：
符號表的作用、建立、符號表欄目的組織、符號表上的操作。
3、教學重點：
符號表的作用與內容。
4、教學難點：
符號表的內容。
5、教學時間分配及進度安排：
建議本章教學時數3學時。
6、章節內容
1、符號表的作用和地位
2、符號表的主要屬性及作用
3、符號表的組織
4、符號表的管理 第八章 運行時存儲空間組織
1、教學目的及要求：
本章介紹目標程序運行時的存儲組織方式，包括靜態存儲分配和動態存儲分配。要求掌握各種存儲組織形式的基本方法。
2、教學內容：
目標程序運行時的活動，運行時存儲器的劃分，靜態存儲管理，簡單的棧式存儲分配的實現，嵌套過程語言的棧式實現，堆式動態存儲分配。
3、教學重點：
靜態分配策略和動態分配策略基本思想，嵌套過程語言棧式分配，活動記錄、運行時棧的組織。
4、教學難點：
嵌套過程語言棧式分配，活動記錄、運行時棧的組織。
5、教學時間分配及進度安排：
建議本章教學時數9學時。
6、章節內容
1、數據空間的三種不同使用方法
2、棧式存儲分配的實現
3、參數傳遞
第九章 代碼優化
1、教學目的及要求：
本章介紹優化的相關知識，要求掌握局部優化，基本塊的DAG表示及其應用，控制流分析和循環查找算法，到達定值與引用定值鏈，循環優化。
2、教學內容：
主要內容：優化概述，局部優化，基本塊的DAG表示及其應用，控制流分析和循環查找算法，到達定值與引用定值鏈，循環優化。
3、教學重點：
局部優化；DAG的構造與應用。
4、教學難點：
循環查找。
5、教學時間分配及進度安排：
建議本章教學時數6學時。
6、章節內容
1、優化技術簡介
2、局部優化
3、控制流分析和循環優化 第十章 代碼生成
1、教學目的及要求： 本章介紹編譯程序的第五階段目標代碼的生成的設計原理和實現方法，要求掌握四元式到匯編語言的目標代碼生成方法。
2、教學內容：
目標機器模型，一個簡單代碼生成器，寄存器分配，DAG目標代碼，窺孔優化。
3、教學重點：
簡單代碼生成器，寄存器分配策略。
4、教學難點：
寄存器分配策略。
5、教學時間分配及進度安排：
建議本章教學時數3學時。
6、章節內容
1、代碼生成概述
2、一個計算機模型
3、一個簡單的代碼生成器
4、代碼生成研究現狀
注：使用教材－編譯原理（第二版）.張素琴，呂映芝，蔣維杜，戴桂蘭編著，清華大學出版社，2005.2。參考書：
1）編譯原理, 何炎祥, 華中理工大學出版社, 2000.10 2）編譯原理, 陳火旺等, 國防工業出版社, 2000.1 3）編譯原理, 蔣立源, 西北工業大學出版社, 1999.9
第五篇：編譯原理課程設計報告
武 漢 紡 織 大 學
編譯原理課程設計實驗報告
學院：數學與計算機 專業：計算機 姓名： 班級： 學號： 編譯原理
編譯原理課設報告
一、實驗目的
加強對編譯程序的整體認識和了解，鞏固《編譯原理》課程所學知識。通過本次課程設計掌握編譯程序調試技巧和設計編譯程序一般的原則，加深對詞法分析、語法分析、語義分析等編譯階段及實用編譯系統的認識。使學生能將編譯理論與實際應用結合起來，提高學生軟件開發的能力。
二、實驗內容
1）仔細閱讀PL/0編譯程序文本（編譯原理(第二版)張素琴 呂映芝 蔣維杜 戴桂蘭 主編
清華大學出版社），并上機調試通過。
2）對PL/0語言進行下列擴充（1）擴充一維整型數組。
擴充var數組：VAR <數組標識名>（<下界>：<上界>）〈下界〉和〈上界〉可用常量標識名。
（2）擴充條件語句的功能使其為：IF<條件>THEN<語句>[ELSE<語句>]（3）增加repeat重復語句: REPEAT<語句>{;<語句>}UNTIL<條件> 可根據自己具體情況從中選擇2個以上題目進行擴充。
三、實驗原理
PL/0語言可以看成PASCAL語言的子集，它的編譯程序是一個編譯解釋執行系統。PL/0的目標程序為假想棧式計算機的匯編語言，與具體計算機無關。
PL/0的編譯程序和目標程序的解釋執行程序都是用PASCAL語言書寫的，因此PL/0語言可在配備PASCAL語言的任何機器上實現。其編譯過程采用一趟掃描方式，以語法分析程序為核心，詞法分析和代碼生成程序都作為一個獨立的過程，當語法分析需要讀單詞時就調用詞法分析程序，而當語法分析正確需要生成相應的目標代碼時，則調用代碼生成程序。
用表格管理程序建立變量、常量和過程表示符的說明與引用之間的信息聯系。
當源程序編譯正確時，PL/0編譯程序自動調用解釋執行程序，對目標代碼進行解釋執行，并按用戶程序的要求輸入數據和輸出運行結果。
四、實驗分析
PL/0語言編譯程序采用以語法分析為核心、一遍掃描的編譯方法。詞法分析和代碼生成作為獨立的子程序供語法分析程序調用。語法分析的同時，提供了出錯報告和出錯恢復的功能。在源程序沒有錯誤編譯通過的情況下，調用類PCODE解釋程序解釋執行生成的類PCODE代碼。
詞法分析子程序分析：
詞法分析子程序名為GETSYM，功能是從源程序中讀出一個單詞符號（TOTAKEN），把它的信息放入全局變量 SYM、ID和NUM中，字符變量放入CH中，語法分析器需要單詞時，直接從這三個變量中獲得。Getch過程通過反復調用Getch子過程從源程序過獲取字符，并把它們拼成單詞。GETCH過程中使用了行緩沖區技術以提高程序運行效率。
詞法分析器的分析過程：調用GETSYM時，它通過GETCH過程從源程序中獲得一個字符。如果這個字符是字母，則繼續獲取字符或數字，最終可以拼成一個單詞，查保留字表，如果查到為保留字，則把SYM變量賦成相應的保留字類型值；如果沒有查到，則這個單詞應是一個用戶自定義的標識符（可能是變量名、常量名或是過程的名字），把SYM置為IDENT，把這個單詞存入ID變量。查保留字表時使用了二分法查找以提高效率。如果Getch獲得的字符是數字，則繼續用Getch獲取數字，并把它們拼成一個整數或實數，然后把SYM置為 INTEGER或REAL，并把拼成的數值放入NUM變量。如果識別出其它合法的符號（比如：賦值號、大于號、小于等于號等），則把SYM則成相應的類型。如果遇到不合法的字符，把SYM置成NUL。
語法分析子程序分析：
語法分析子程序采用了自頂向下的遞歸子程序法，語法分析同時也根據程序的語義生成相應三元代碼，并提供了出錯處理的機制。語法分析主要由分程序分析過程（BLOCK）、參數變量分析過程（ParaDeclaration）、參數變量處理過程（ParaGetSub）、數組處理過程（ParaGetSub）、常量定義分析過程（ConstDeclaration）、變量定義分析過程（Vardeclaration）、語句分析過程（Statement）、表達式處理過程（Expression）、項處理過程（Term）、因子處理過程（Factor）和條件處理過程（Condition）構成。這些過程在結構上構成一個嵌套的層次結構。除此之外，還有出錯報告過程（Error）、代碼生成過程（Gen）、測試單詞合法性及出錯恢復過程（Test）、登錄名字表過程（Enter）、查詢名字表函數（Position）以及列出類 PCODE代碼過程（Listcode）作過語法分析的輔助過程。
由PL/0的語法圖可知：一個完整的PL/0程序是由分程序和句號構成的。因此，本編譯程序在運行的時候，通過主程序中調用分程序處理過程block來分析分程序部分（分程序分析過程中還可能會遞歸調用block過程），然后，判斷最后讀入的符號是否為句號。如果是句號且分程序分析中未出錯，則是一個合法的PL/0程序，可以運行生成的代碼，否則就說明源PL/0程序是不合法的，輸出出錯提示即可。
if-then-else語句的處理：
按if語句的語法，首先調用邏輯表達式處理過程處理if語句的條件，把相應的真假值放到數據棧頂。接下去記錄下代碼段分配位置（即下面生成的jpc指令的位置），然后生成 條件轉移jpc指令（遇0或遇假轉移），轉移地址未知暫時填0。然后調用語句處理過程處理 then語句后面的語句或語句塊。then后的語句處理完后，如果遇到else，就調用語句處理過程處理else語句后面的語句或語句塊，這時當前代碼段分配指針的位置就應該是上面的jpc指令的轉移位置。通過前面記錄下的jpc指令的位置，把它的跳轉位置改成當前的代碼段指針位置，否則沒遇到else，那么此時的當前代碼段分配指針的位置也是上面jpc指令的轉移位置，也是通過前面記錄下的jpc位置指令的位置，把它的跳轉到當前的代碼段指針位置。
Repeat語句的處理：
首先用CX1變量記下當前代碼段分配位置，作為循環的開始位置。然后通過遞歸調用語句分析過程分析，直到遇到until保留字，如果未對應until則出錯。調用條件表達式處理過程生成相應代碼把結果放在數據棧頂，再生成條件轉移指令，轉移位置為上面記錄的CX1。
五、相關代碼及運行結果
實驗代碼； PL0.h代碼： #include
#ifndef WIRTH_ZYC_ #define WIRTH_ZYC_ using namespace std;
const int norw = 16;
// no.of reserved words 保留字的個數
const int txmax = 100;
// length of identifier table 標示符表的長度（容量）const int al = 10;
// length of identifiers 標示符的最大長度
const int nmax = 14;
// max.no.of digits in numbers 數字的最大長度 const int amax = 2047;
// maximum address 尋址空間
const int levmax = 3;
// maximum depth of block nesting 最大允許的塊嵌套層數 const int cxmax = 200;
// size of code array 類PCODE目標代碼數組長度（可容納代碼行數）
const int lineLength = 82;// 行緩沖區長度
typedef enum {NUL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH,ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN，RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES,BEGINSYM,ENDSYM,IFSYM,THENSYM,WHILESYM，WRITESYM,READSYM,DOSYM,CALLSYM,CONSTSYM,VARSYM,PROCSYM,ELSESYM,REPEATSYM,UNTILSYM} symbol;// symobl類型標識了不同類型的詞匯
typedef char alfa[al+1];
// alfa類型用于標識符 typedef enum {CONSTANT,VARIABLE,PROCEDURE,ARRAY} obj0;
// 三種標識符的類型 typedef enum {LIT,OPR,LOD,STO,CAL,INT,JMP,JPC} fct;
// functions typedef set
struct instruction{ fct f;// function code int l;// level,cann't big than levmax
int a;// displacement address,cann't big than amax };
// 類PCODE指令類型，包含三個字段：指令f、層差l和另一個操作數a
/******************************************* * lit 0,a: load constant a
* * opr 0,a: execute operation a
* * lod l,a: load variable l,a
* * sto l,a: store variable l,a
* * cal l,a: call procedure a at level l
* * int 0,a: increment t-register by a
* * jmp 0,a: jump to a
* * jpc 0,a: jump conditional to a
* *******************************************/
typedef struct{ alfa name;obj0 kind;union {
struct{int level,adr,size;}inOther;
int val;}other;} Table;
class PL0 {
protected:
bool listswitch,sourceEnd;char ch;
// last character read symbol sym;
// last symbol read alfa id;
// last identifier read int num;
// last number read
int cc;
// character count int ll;
// line length int kk,err;int cx;
// code allocation index int codeNo;
// code line no.static string errStr[];
// error string
char line[lineLength];
// code line vector
// error array alfa a;
// 詞法分析器中用于臨時存放正在分析的詞
instruction code[cxmax+1];
// destination code array
alfa word[norw+1];
// 保留字表
symbol wsym[norw+1];
// 保留字表中每一個保留字對應的symbol類型
symbol ssym[100];
// 一些符號對應的symbol類型表
合 char mnemonic[8][6];
// 類PCODE指令助記符表
symset declbegsys,statbegsys,facbegsys;// 聲明開始、表達式開始和項開始符號集 Table table[txmax+1];
// 符號表
FILE* fin,*fout;
public:
PL0(char* source,char*destination);
~PL0(){fclose(fin),fclose(fout);}
void error(int n);
位置和出錯代碼
void getsym();
個單詞
void getch();
個字符
void gen(fct x,int y,int z);
程序區
void test(symset s1,symset s2,int n);
合法
void block(int lev,int tx,symset fsys);
void enter(obj0 k,int &tx,int &dx,int lev);
int position(alfa id,int tx);的位置
void constdeclaration(int&tx,int&dx,int lev);
void vardeclaration(int&tx,int&dx,int lev);
void listcode(int cx0);
void statement(symset fsys,int tx,int lev);
void expression(symset fsys,int tx,int lev);
void term(symset fsys,int tx,int lev);
void factor(symset fsys,int tx,int lev);
void condition(symset fsys,int tx,int lev);
void arraydeclaration(int& tx,int& dx,int lev);
void interpret();
執行程序
int base(int l,int b,int s[]);
基地址
void SaveCode();
// 構造函數
// 析構函數
// 出錯處理，打印出錯
// 詞法分析，讀取一
// 漏掉空格，讀取一// 生成目標代碼，并送入目標
// 測試當前單詞符號是否
// 分程序分析處理過程
// 登入名字表
// 查找標示符在名字表中
// 常量定義處理
// 變量說明處理
// 列出目標代碼清單
// 語句部分處理
// 表達式處理
// 項處理
// 因子處理
// 條件處理
// 數組說明處理
// 對目標代碼的解釋
// 通過靜態鏈求出數據區的 // 保存代碼
};#endif PL0.cpp代碼： #include “pl0.h”
// 錯誤字符串數組
string PL0::errStr[]={“",”error 0001: 常數說明中“=”寫成“：=”“, ”error 0002: 常數說明中的“=”后應為數字“, ”error 0003: 常數說明中的標識符后應是“=”“, ”error 0004: const,var,procedure后應為標識符“, ”error 0005: 漏掉了‘,’或‘;’“, ”error 0006: 過程說明后的符號不正確（應是語句開始符或過程開始符）“, ”error 0007: 應是語句開始符“, ”error 0008: 過程體內語句部分的后跟符不正確“, ”error 0009: 程序皆為丟了句號‘.’“, ”error 0010: 語句之間漏了‘;’“, ”error 0011: 標識符沒說明“, ”error 0012: 賦值語句中，賦值號左部標識符屬性應是變量“, ”error 0013: 賦值語句左部標識符應是賦值號:=“, ”error 0014: call后應為標識符“, ”error 0015: call后標識符屬性應為過程“, ”error 0016: 條件語句中丟了then“, ”error 0017: 丟了end或;“, ”error 0018: while型循環語句中丟了do“, ”error 0019: 語句后的標識符不正確“, ”error 0020: 應為關系運算符“, ”error 0021: 表達式內標識符屬性不能是過程“, ”error 0022: 表達式中漏掉了右括號‘)’“, ”error 0023: 因子后的非法符號“, ”error 0024: 表達式開始符不能是此符號“, ”error 0025: 文件在不該結束的地方結束了“, ”error 0026: 結束符出現在不該結束的地方“, ”error 0027: “,”error 0028: “,”error 0029: “,”error 0030: “, ”error 0031: 數越界“, ”error 0032: read語句括號中標識符不是變量“, ”error 0033: else附近錯誤“ , ”error 0034: repeat附近錯誤“};
// PL0構造函數
PL0::PL0(char* source,char*destination){ listswitch=true,sourceEnd=false;
strcpy(word[1],”begin“);
// 初始化存儲保留字
strcpy(word[2],”call“);strcpy(word[3],”const“);
strcpy(word[4],”do“);strcpy(word[5],”else“);strcpy(word[6],”end“);strcpy(word[7],”if“);strcpy(word[8],”odd“);strcpy(word[9],”procedure“);strcpy(word[10],”read“);
strcpy(word[11],”repeat“);strcpy(word[12],”then“);strcpy(word[13],”until“);strcpy(word[14],”var“);
strcpy(word[15],”while“);strcpy(word[16],”write“);
wsym[1]= BEGINSYM;
wsym[2]= CALLSYM;留字對應的symbol類型
wsym[3]= CONSTSYM;
wsym[4]= DOSYM;wsym[5]= ELSESYM;
wsym[6]= ENDSYM;wsym[7]= IFSYM;
wsym[8]= ODDSYM;wsym[9]= PROCSYM;
wsym[10]= READSYM;
wsym[11]= REPEATSYM;wsym[12]= THENSYM;wsym[13]= UNTILSYM;wsym[14]= VARSYM;
wsym[15]= WHILESYM;wsym[16]= WRITESYM;
memset(code,0,sizeof(code));memset(ssym,0,100*sizeof(symbol));memset(table,0,sizeof(table));memset(line,0,sizeof(line));
ssym['+']= PLUS;
類型表
ssym['-']= MINUS;ssym['*']= TIMES;ssym['/']= SLASH;ssym['(']= LPAREN;ssym[')']= RPAREN;ssym['=']= EQL;ssym[',']= COMMA;ssym['.']= PERIOD;
// 初始化保留字表中每一個保
// 初始化一些符號對應的symbol
ssym['#']= NEQ;ssym['<']= LSS;ssym['>']= GTR;ssym[';']= SEMICOLON;
strcpy(mnemonic[LIT],” lit “);
// 初始化類PCODE指令助記符表
strcpy(mnemonic[OPR],” opr “);strcpy(mnemonic[LOD],” lod “);strcpy(mnemonic[STO],” sto “);strcpy(mnemonic[CAL],” cal “);strcpy(mnemonic[INT],” int “);strcpy(mnemonic[JMP],” jmp “);strcpy(mnemonic[JPC],” jpc “);
declbegsys.insert(CONSTSYM),declbegsys.insert(VARSYM),declbegsys.insert(PROCSYM);// 初始化聲明開始符號集合 statbegsys.insert(BEGINSYM),statbegsys.insert(CALLSYM),statbegsys.insert(IFSYM),statbegsys.insert(WHILESYM);// 初始化表達式開始符號集合facbegsys.insert(IDENT),facbegsys.insert(NUMBER),facbegsys.insert(LPAREN);// 初始化項開始符號集合
err= 0;cc= 0;
// 行緩沖區指針
cx= 0;
// 代碼分配指針，代碼生成模塊總在cx所指位置生成新的代碼
ll= 0;
// 行緩沖區長度
ch= ' ';
// last character read
}
kk= al;
// 引入此變量是出于程序性能考慮 codeNo=0;
// code line no.fin=fopen(source,”r“);fout=fopen(destination,”w“);// 出錯處理，打印出錯位置和出錯代碼 void PL0::error(int n){ char s[10];sprintf(s,”第 %d 行:“,codeNo);errorString.push_back(s+errStr[n]);err= err+1;//error count }//error end // 詞法分析，讀取一個單詞
void PL0::getsym(){ if(sourceEnd)
return;int i,j,k;while(ch ==' '||ch==9)
getch();
// cls space and tab if(isalpha(ch))// id or reserved word {
k=0;
memset(a,0,al+1);
// 檢測一個單詞長度 do{ if(k < al){
a[k]= ch;
k= k+1;} getch();if(sourceEnd)
return;}while(isalpha(ch)||isdigit(ch));if(k >= kk)kk = k;else { do{
a[kk]= ' ';
kk= kk-1;}while(kk > k);} strcpy(id,a);i= 1;j= norw;// 判斷是否是關鍵字（二分搜索）do{ k=(i+j)/ 2;if(strcmp(id, word[k])<=0)
j= k-1;if(strcmp(id,word[k])>=0)
i= k+1;}while(i<=j);if(i-1 > j)
sym= wsym[k];else
sym= IDENT;} else if(isdigit(ch))// number { k= 0;num= 0;sym= NUMBER;do{
num= 10 * num + ch-'0';
k= k+1;
getch();}while(isdigit(ch));if(k > nmax)
error(30);} else if(ch == ':'){ getch();if(ch == '='){
sym= BECOMES;
getch();} else
sym= NUL;} else if(ch == '<')
// extra stuff added to support <= { getch();if(ch== '='){
sym= LEQ;
getch();} else
sym= LSS;} else if(ch == '>'){ getch();if(ch == '='){
sym= GEQ;
getch();} else
sym= GTR;} else
// end of extra stuff { sym= ssym[ch];// 其它符號的賦值
getch();} }
// 漏掉空格，讀取一個字符
void PL0::getch(){ if(cc == ll){
if(feof(fin))
{
if(sym!=PERIOD)
error(25);
sourceEnd=true;
return;
}
cc= 0;
fgets(line,lineLength,fin);
codeNo++;
ll=strlen(line);
if(line[ll-1]==10)ll--;} ch= line[cc];cc= cc+1;}
// 生成目標代碼，并送入目標程序區void PL0::gen(fct x,int y,int z){ if(cx > cxmax){
cout<<”Program too longn“;
return;}
code[cx].f= x;code[cx].l= y;code[cx].a= z;
cx= cx+1;}//gen end
// 測試當前單詞符號是否合法
void PL0::test(symset s1,symset s2,int n){ if(sourceEnd)
return;if(s1.find(sym)==s1.end()){
error(n);
symset::iterator it;
for(it=s2.begin();it!=s2.end();it++)
s1.insert(*it);//s1=s1+s2
while(s1.find(sym)==s1.end())
getsym();} }//test end
// 分程序分析處理過程
void PL0::block(int lev,int tx,symset fsys){ if(sourceEnd)
return;int dx;// data allocation index int tx0;// initial table index int cx0;// initial code index
dx= 3;
// 變量的個數 tx0= tx;// 表指針
table[tx].other.inOther.adr= cx;gen(JMP,0,0);if(lev>levmax)error(32);do{
if(sym == CONSTSYM)
// 處理常量聲明
{
getsym();
do{
constdeclaration(tx,dx,lev);
while(sym == COMMA)
{
}
getsym();
constdeclaration(tx,dx,lev);} if(sym ==SEMICOLON)
getsym();else
error(5);}while(sym==IDENT);if(sym == VARSYM)
// 處理變量聲明 { getsym();do{
vardeclaration(tx,dx,lev);
while(sym == COMMA){
getsym();
vardeclaration(tx,dx,lev);
}
if(sym ==SEMICOLON)
getsym();
else
error(5);}while(sym==IDENT);} while(sym ==PROCSYM)
// 處理過程的聲明 { getsym();if(sym ==IDENT){
enter(PROCEDURE,tx,dx,lev);
getsym();} else
error(4);if(sym ==SEMICOLON)
getsym();else
error(5);symset tmp = fsys;tmp.insert(SEMICOLON);block(lev+1,tx,tmp);if(sym == SEMICOLON){
getsym();
symset tmp = statbegsys;
for(int i= IDENT;i<=PROCSYM;i++)
tmp.insert((symbol)i);
test(tmp,fsys,6);
}
else
error(5);
}
symset tmp=statbegsys;
tmp.insert(IDENT);
test(tmp,declbegsys,7);}while(declbegsys.find(sym)!=declbegsys.end());
code[table[tx0].other.inOther.adr].a= cx;table[tx0].other.inOther.adr= cx;// start adr of code table[tx0].other.inOther.size=dx;
cx0= cx;gen(INT,0,dx);symset tmp=statbegsys;for(int i=SEMICOLON;i <= ENDSYM;i++)
tmp.insert((symbol)i);statement(tmp,tx,lev);gen(OPR,0,0);// return symset s2;test(fsys,s2,8);listcode(cx0);}// block end
// 登入名字表
void PL0::enter(obj0 k,int &tx,int &dx,int lev){ tx= tx+1;strcpy(table[tx].name,id);table[tx].kind=k;switch(k){ case CONSTANT:
if(num>amax)
{
error(31);
num=0;
}
table[tx].other.val=num;
break;case VARIABLE:
table[tx].other.inOther.level=lev;
table[tx].other.inOther.adr=dx;
dx++;
break;case PROCEDURE:
table[tx].other.inOther.level=lev;
break;case ARRAY:
table[tx].other.inOther.size = lev;
break;} }//enter end
// 查找標示符在名字表中的位置
int PL0::position(alfa id,int tx)//find identifier id in table { int i;strcpy(table[0].name, id);i= tx;while(strcmp(table[i].name,id)!=0)i--;return i;}//position end
// 常量定義處理
void PL0::constdeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){
getsym();
if(sym>=EQL&&sym<=BECOMES)
{
if(sym ==BECOMES)
error(1);
getsym();
if(sym == NUMBER)
{
enter(CONSTANT,tx,dx,lev);
getsym();
}
else
error(2);
}
else
error(3);} else
error(4);}// constdeclaration end
// 變量說明處理
void PL0::vardeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){
enter(VARIABLE,tx,dx,lev);
getsym();} else
error(4);}//vardeclaration end
// 數組說明處理
void PL0::arraydeclaration(int&tx,int&dx,int lev){
int upscript=0,downscript=0;getsym();if(sym == NUMBER || sym == CONSTSYM){
if(num == 0)
{
upscript = num;
getsym();
}
else
error(32);} if(sym == COMMA)
getsym();else
error(32);if(sym == NUMBER || sym == CONSTSYM){
downscript = num;
getsym();} if(sym!= RPAREN)
} error(32);else { enter(ARRAY,tx,dx,downscript+1);getsym();} // 列出目標代碼清單
void PL0::listcode(int cx0)//list code generated for this block { int i;if(listswitch)
for(i= cx0;i cout<<”“< <<”“< // 語句部分處理 void PL0::statement(symset fsys,int tx,int lev){ if(sourceEnd) return;int i,cx1,cx2;if(sym ==IDENT){ i= position(id,tx); if(i == 0) error(11); else if(table[i].kind!=VARIABLE) { error(12); i= 0; } getsym(); if(sym ==BECOMES) getsym(); else error(13); expression(fsys,tx,lev); if(sym!= SEMICOLON) error(10); if(i!= 0) gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr); } else if(sym == READSYM){ getsym();if(sym!=LPAREN) error(34);else do{ getsym(); if(sym==IDENT) i=position(id,tx); else i=0; if(i==0) error(35); else { gen(OPR,0,16); gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr); } getsym(); }while(sym == COMMA); if(sym!= RPAREN) { error(33); while(fsys.find(sym)!=fsys.end())getsym(); } else getsym();} else if(sym == WRITESYM){ getsym();if(sym==LPAREN){ do{ getsym(); symset tmp=fsys; for(int t=RPAREN;t<=COMMA;t++) tmp.insert((symbol)t); expression(tmp,tx,lev); gen(OPR,0,14); }while(sym==COMMA); if(sym!=RPAREN) error(33); else getsym();} gen(OPR,0,15);} else if(sym ==CALLSYM){ getsym();if(sym!=IDENT) error(14);else { i= position(id,tx); if(i == 0) error(11); else if(table[i].kind = PROCEDURE) gen(CAL,lev-table[i].other.inOther.level,table[i].other.inOther.adr); else error(15); getsym();} } else if(sym ==IFSYM){ getsym();symset tmp=fsys;for(int i = THENSYM;i<= DOSYM;i++) tmp.insert((symbol)i);condition(tmp,tx,lev);if(sym == THENSYM) getsym();else error(16);cx1= cx;gen(JPC,0,0);tmp.insert(ELSESYM);statement(tmp,tx,lev);getsym(); code[cx1].a= cx; if(sym == ELSESYM){ getsym(); cx2=cx; gen(JMP,0,0); code[cx1].a=cx; statement(fsys,tx,lev); code[cx2].a=cx;} } else if(sym ==BEGINSYM){ getsym();symset tmp=fsys;for(int i=SEMICOLON;i<=ENDSYM;i++) tmp.insert((symbol)i);statement(tmp,tx,lev);tmp=statbegsys;tmp.insert(SEMICOLON);while(tmp.find(sym)!=tmp.end()){ if(sourceEnd)return; if(sym ==SEMICOLON||sym ==ENDSYM) getsym(); else if(sym=PERIOD) { error(26); getsym(); } else error(10); tmp=fsys; for(i=SEMICOLON;i<=ENDSYM;i++) tmp.insert((symbol)i); if(sourceEnd)return; if(sym==ENDSYM) break; statement(tmp,tx,lev);} if(sym ==ENDSYM) getsym();else if(!sourceEnd) error(17);} else if(sym ==WHILESYM){ cx1= cx; // 記下當前代碼分配位置，這是while循環的開始位置 getsym();symset tmp=fsys;tmp.insert(DOSYM);condition(tmp,tx,lev); cx2= cx; // 記下當前代碼分配位置，這是while的do中的語句的開始位置 gen(JPC,0,0); if(sym ==DOSYM) getsym(); else error(18); statement(fsys,tx,lev); gen(JMP,0,cx1); code[cx2].a= cx;} else if(sym == REPEATSYM){ symset temp1, temp2; temp1= fsys,temp1.insert(SEMICOLON),temp1.insert(UNTILSYM); cx1= cx; getsym(); statement(temp1,tx,lev); temp2 = statbegsys; temp2.insert(SEMICOLON); while(temp2.find(sym)!= temp2.end()) { if(sym == SEMICOLON) getsym(); else error(34); statement(temp1,tx,lev); } if(sym == UNTILSYM) { getsym(); condition(fsys,tx,lev); gen(JPC,0,cx1); } else error(34); } symset setT;test(fsys,setT,19);}//statement end // 表達式處理 void PL0::expression(symset fsys,int tx,int lev){ symbol addop;symset tmp=fsys;for(int t=PLUS;t<=MINUS;t++) tmp.insert((symbol)t);if(sym>=PLUS&&sym<=MINUS){ addop= sym; getsym(); term(tmp,tx,lev); if(addop ==MINUS) gen(OPR,0,1);} else term(tmp,tx,lev);while(sym >=PLUS&&sym<=MINUS){ addop= sym; getsym(); term(tmp,tx,lev); if(addop ==PLUS) gen(OPR,0,2); else gen(OPR,0,3);} }// expression end // 項處理 void PL0::term(symset fsys,int tx,int lev){ if(sourceEnd) return;symbol mulop;symset tmp=fsys;for(int t=TIMES;t<=SLASH;t++) tmp.insert((symbol)t);factor(tmp,tx,lev);while(sym>=TIMES && sym<=SLASH){ mulop= sym; getsym(); factor(tmp,tx,lev); if(mulop ==TIMES) gen(OPR,0,4); else gen(OPR,0,5);} }// term end // 因子處理 void PL0:: factor(symset fsys,int tx,int lev){ int i;test(facbegsys,fsys,24);while(facbegsys.find(sym)!=facbegsys.end()){ if(sym ==IDENT) { i= position(id,tx); if(i == 0) error(11); else switch(table[i].kind) { case CONSTANT: gen(LIT,0,table[i].other.val); break; case VARIABLE: gen(LOD,lev-table[i].other.inOther.level,table[i].other.inOther.adr); break; case PROCEDURE: error(21); break; } getsym(); } else if(sym ==NUMBER) { if(num>amax) { error(31); num= 0; } gen(LIT,0,num); getsym(); } else if(sym ==LPAREN) { getsym(); symset tmp=fsys; tmp.insert(RPAREN); expression(tmp,tx,lev); if(sym == RPAREN) getsym(); else error(22); } test(fsys,facbegsys,23);} }//factor end // 條件處理 void PL0::condition(symset fsys,int tx,int lev){ symbol relop;symset tmp=fsys;tmp.insert(EQL),tmp.insert(NEQ),tmp.insert(LSS),tmp.insert(LEQ),tmp.insert(GTR),tmp.insert(GEQ); if(sym == ODDSYM){ getsym(); expression(fsys,tx,lev); gen(OPR,0,6);} else { expression(tmp,tx,lev); if(tmp.find(sym)==tmp.end()) error(20); else { relop= sym; getsym(); expression(fsys,tx,lev); switch(relop) { case EQL: gen(OPR,0,8); break; case NEQ: gen(OPR,0,9); break; case LSS: gen(OPR,0,10); break; case GEQ: gen(OPR,0,11); break; case GTR: gen(OPR,0,12); break; case LEQ: gen(OPR,0,13); break; } } } }//condition end // 對目標代碼的解釋執行程序 void PL0::interpret(){ int err1=errorString.size();if(err1>0){ cout<<”存在%d個錯誤:“< cout< t= t+1; s[t]= i.a; break;case OPR: switch(i.a)//operator { case 0:// return t= b-1; p= s[t+3]; b= s[t+2];break;case 1: s[t]=-s[t];break;case 2: t= t-1;s[t]= s[t]+s[t+1];break;case 3: t= t-1;s[t]= s[t]-s[t+1];break;case 4: t= t-1;s[t]= s[t]*s[t+1];break;case 5: t= t-1;s[t]= s[t] / s[t+1];break;case 6: if(s[t]%2) s[t]=1;else s[t]=0;break;case 8: t= t-1;if(s[t]==s[t+1]) s[t]=1;else s[t]=0;break;case 9: t= t-1;if(s[t]==s[t+1]) s[t]=0;else s[t]=1;break; case 10: t= t-1;if(s[t] s[t]=1;else s[t]=0;break;case 11: t= t-1;if(s[t]>=s[t+1]) s[t]= 1;else s[t]=0;break;case 12: t= t-1;if(s[t]>s[t+1]) s[t]= 1;else s[t]=0;break;case 13: t= t-1;if(s[t]<=s[t+1]) s[t]= 1;else s[t]=0;break;case 14: cout<<”“< t= t+1; s[t]= s[base(i.l,b,s)+i.a]; break; case STO: s[base(i.l,b,s)+i.a]= s[t]; t= t-1; break; case CAL:// generate new block mark s[t+1]= base(i.l,b,s); s[t+2]= b; s[t+3]= p; b= t+1; p=i.a; break; case INT: t= t+i.a; break; case JMP: p= i.a; break; case JPC: if(s[t] == 0) p= i.a; t= t-1; break; }//switch end }while(p!=0); cout<<” End PL/0n“;} // interpret end // 通過靜態鏈求出數據區的基地址 int PL0::base(int l,int b,int s[]){ int b1;b1= b;//find base l levels down while(l>0){ b1= s[b1]; l= l-1;} return b1;} // 保存代碼 void PL0::SaveCode(){ if(fout) for(int i=0;i fprintf(fout,”%d %s %d %dn “,i,mnemonic[code[i].f],code[i].l,code[i].a);} TestPL0.cpp代碼： #include ”pl0.h“ void main(){ PL0 cp(”testPas2.txt“,”nasm.txt"); symset fsys; fsys.insert(PERIOD);fsys.insert(CONSTSYM),fsys.insert(VARSYM),fsys.insert(PROCSYM);fsys.insert(BEGINSYM),fsys.insert(CALLSYM),fsys.insert(IFSYM),fsys.insert(WHILESYM);cp.getsym(); // 詞法分析，分析一個詞 cp.block(0,0,fsys); // 分程序分析處理功能 cp.SaveCode(); // 保存代碼 cp.interpret(); // 對目標代碼的解釋執行程序 } 實驗運行結果： 運行的的文件見下圖右側：實驗中我是固定了文件名的，可以是改寫成動態輸入，由于在測試中我把所有的測試語句都放在同一個文件中了，沒有太多的必要。 六、心得體會 在編譯程序實現的過程中反復使用了遞歸調用的思想，且也使用了模塊化處理問題的思想，使用模塊化的思想關鍵是在抽象階段要抽象出對應的模塊，且模塊的層次必須是清晰的。 在實現此程序中，由于要實現關鍵字和符號表中字段的搜索，實現中就必須注意快速查找的方法，而在實現的過程中多次用到了二分搜索的方法，這是個比較快的搜索方法。 由于此程序的實現相對比較復雜，且不方便調試，改進時可以把此程序的詞法分析，語法分析和執行原代碼作為單獨的測試程序來測試，這樣也方便大家來調試。 通過本次的課設我知道了一個算法的設計是需要靜下心來仔細的研究的，且實現中必須先了解程序的整個流程，也就是說在編程中首先必須看懂那些對應的UML圖，只有在圖的指導下，編程中才不會盲目，也有一定的方向性。同樣在編程中必須注意代碼的規范，多寫一些對應的注釋是很必要的，要時刻想這代碼并不是給你自己看的，而是必須要給別人看，因此我覺得代碼的規范是相當重要的。
點擊咨詢 